2024

最新文章

• Joint Mixability and Notions of Negative Dependence AI翻译
  作者：Koike, Takaaki; Lin, Liyuan; Wang, Ruodu
  作者单位：Hitotsubashi University; University of Waterloo
  摘要：A joint mix (JM) is a random vector with a constant component-wise sum. The dependence structure of a joint mix minimizes some common objectives, such as the variance of the component-wise sum, and it is regarded as a concept of extremal negative dependence. In this paper, we explore the connection between the joint mix structure and popular notions of negative dependence in statistics, such as negative correlation dependence, negative orthant dependence, and negative association. A joint mix ...
• Inner Moreau Envelope of Nonsmooth Conic Chance-Constrained Optimization Problems AI翻译
  作者：van Ackooij, Wim; Perez-Aros, Pedro; Soto, Claudia; Vilches, Emilio
  作者单位：Electricite de France (EDF); Universidad de O'Higgins; Universidad de Chile
  摘要：Optimization problems with uncertainty in the constraints occur in many applications. Particularly, probability functions present a natural form to deal with this situation. Nevertheless, in some cases, the resulting probability functions are nonsmooth, which motivates us to propose a regularization employing the Moreau envelope of a scalar representation of the vector inequality. More precisely, we consider a probability function that covers most of the general classes of probabilistic constr...
• Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functions AI翻译
  作者：Bianchi, Pascal; Hachem, Walid; Schechtman, Sholom
  作者单位：IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom Paris; Universite Gustave-Eiffel; Centre National de la Recherche Scientifique (CNRS)
  摘要：In nonsmooth stochastic optimization, we establish the nonconvergence of the stochastic subgradient descent (SGD) to the critical points recently called active strict saddles by Davis and Drusvyatskiy. Such points lie on a manifold M, where the function f has a direction of second-order negative curvature. Off this manifold, the norm of the Clarke subdifferential of f is lower-bounded. We require two conditions on f. The first assumption is a Verdier stratification condition, which is a refine...
• Naive Feature Selection: A Nearly Tight Convex Relaxation for Sparse Naive Bayes AI翻译
  作者：Askari, Armin; d'Aspremont, Alexandre; El Ghaoui, Laurent
  作者单位：University of California System; University of California Berkeley; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS)
  摘要：Because of its linear complexity, naive Bayes classification remains an attractive supervised learning method, especially in very large-scale settings. We propose a sparse version of naive Bayes, which can be used for feature selection. This leads to a combinatorial maximum-likelihood problem, for which we provide an exact solution in the case of binary data, or a bound in the multinomial case. We prove that our convex relaxation bounds become tight as the marginal contribution of additional f...
• Stateful Posted Pricing with Vanishing Regret via Dynamic Deterministic Markov Decision Processes AI翻译
  作者：Emek, Yuval; Lavi, Ron; Niazadeh, Rad; Shi, Yangguang
  作者单位：Technion Israel Institute of Technology; University of Bath; University of Chicago; Shandong University
  摘要：An online problem called dynamic resource allocation with capacity constraints (DRACC) is introduced and studied in the realm of posted price mechanisms. This problem subsumes several applications of stateful pricing, including but not limited to posted prices for online job scheduling and matching over a dynamic bipartite graph. Because existing online learning techniques do not yield vanishing regret for this problem, we develop a novel online learning framework over deterministic Markov dec...
• V-Learning-A Simple, Efficient, Decentralized Algorithm for Multiagent Reinforcement Learning AI翻译
  作者：Jin, Chi; Liu, Qinghua; Wang, Yuanhao; Yu, Tiancheng
  作者单位：Princeton University; Princeton University; Massachusetts Institute of Technology (MIT)
  摘要：A major challenge of multiagent reinforcement learning (MARL) is the curse of multiagents, where the size of the joint action space scales exponentially with the number of agents. This remains to be a bottleneck for designing efficient MARL algorithms, even in a basic scenario with finitely many states and actions. This paper resolves this challenge for the model of episodic Markov games. We design a new class of fully decentralized algorithms-V-learning, which provably learns Nash equilibria ...
• Interim Rationalizable Implementation of Functions AI翻译
  作者：Kunimoto, Takashi; Saran, Rene; Serrano, Roberto
  作者单位：Singapore Management University; University System of Ohio; University of Cincinnati; Brown University
  摘要：This paper investigates rationalizable implementation of social choice functions (SCFs) in incomplete information environments. We identify weak interim rationalizable monotonicity (weak IRM) as a novel condition and show it to be a necessary and almost sufficient condition for rationalizable implementation. We show by means of robust examples that interim rationalizable monotonicity (IRM), found in the literature, is strictly stronger than weak IRM and that IRM is not necessary for rationaliz...
• Minimization Fractional Prophet Inequalities for Sequential Procurement AI翻译
  作者：Qin, Junjie; Vardi, Shai; Wierman, Adam
  作者单位：Purdue University System; Purdue University; California Institute of Technology
  摘要：We consider a minimization variant on the classical prophet inequality with monomial cost functions. A firm would like to procure some fixed amount of a divisible commodity from sellers that arrive sequentially. Whenever a seller arrives, the seller's cost function is revealed, and the firm chooses how much of the commodity to buy. We first show that if one restricts the set of distributions for the coefficients to a family of natural distributions that include, for example, the uniform and tr...
• A Semismooth Newton-Type Method for the Nearest Doubly Stochastic Matrix Problem AI翻译
  作者：Hu, Hao; Li, Xinxin; Im, Haesol; Wolkowicz, Henry
  作者单位：Clemson University; University of Waterloo; Jilin University
  摘要：We study a semismooth Newton-type method for the nearest doubly stochastic matrix problem where the nonsingularity of the Jacobian can fail. The optimality conditions for this problem are formulated as a system of strongly semismooth functions. We show that the nonsingularity of the Jacobian does not hold for this system. By exploiting the problem structure, we construct a modified two step semismooth Newton method that guarantees a nonsingular Jacobian matrix at each iteration, and that conve...
• On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-Rank Matrix Optimization br AI翻译
  作者：Luo, Yuetian; Li, Xudong; Zhang, Anru R.
  作者单位：University of Chicago; Fudan University; Duke University; Duke University; Duke University; Duke University
  摘要：In this paper, we propose a general procedure for establishing the geometric land-scape connections of a Riemannian optimization problem under the embedded and quotient geometries. By applying the general procedure to the fixed-rank positive semidefinite (PSD) and general matrix optimization, we establish an exact Riemannian gradient connection under two geometries at every point on the manifold and sandwich inequalities between the spectra of Riemannian Hessians at Riemannian first-order stat...