2024

最新文章

• Complementary composite minimization, small gradients in general norms, and applications AI翻译
  作者：Diakonikolas, Jelena; Guzman, Cristobal
  作者单位：University of Wisconsin System; University of Wisconsin Madison; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
  摘要：Composite minimization is a powerful framework in large-scale convex optimization, based on decoupling of the objective function into terms with structurally different properties and allowing for more flexible algorithmic design. We introduce a new algorithmic framework for complementary composite minimization, where the objective function decouples into a (weakly) smooth and a uniformly convex term. This particular form of decoupling is pervasive in statistics and machine learning, due to its...
• Shapes and recession cones in mixed-integer convex representability AI翻译
  作者：Zadik, Ilias; Lubin, Miles; Vielma, Juan Pablo
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：Mixed-integer convex representable (MICP-R) sets are those sets that can be represented exactly through a mixed-integer convex programming formulation. Following up on recent work by Lubin et al. (in: Eisenbrand (ed) Integer Programming and Combinatorial Optimization - 19th International Conference, Springer, Waterloo), (Math. Oper. Res. 47:720-749, 2022) we investigate structural geometric properties of MICP-R sets, which strongly differentiate them from the class of mixed-integer linear repr...
• Gradient regularization of Newton method with Bregman distances AI翻译
  作者：Doikov, Nikita; Nesterov, Yurii
  摘要：In this paper, we propose a first second-order scheme based on arbitrary non-Euclidean norms, incorporated by Bregman distances. They are introduced directly in the Newton iterate with regularization parameter proportional to the square root of the norm of the current gradient. For the basic scheme, as applied to the composite convex optimization problem, we establish the global convergence rate of the order O(k(-2)) both in terms of the functional residual and in the norm of subgradients. Our...
• A competitive algorithm for throughput maximization on identical machines AI翻译
  作者：Moseley, Benjamin; Pruhs, Kirk; Stein, Clifford; Zhou, Rudy
  作者单位：Carnegie Mellon University; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Columbia University
  摘要：This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline on m identical machines. The main result is an O(1) competitive deterministic algorithm for any number of machines m>1.
• Homotopic policy mirror descent: policy convergence, algorithmic regularization, and improved sample complexity AI翻译
  作者：Li, Yan; Lan, Guanghui; Zhao, Tuo
  作者单位：University System of Georgia; Georgia Institute of Technology
  摘要：We study a new variant of policy gradient method, named homotopic policy mirror descent (HPMD), for solving discounted, infinite horizon MDPs with finite state and action spaces. HPMD performs a mirror descent type policy update with an additional diminishing regularization term, and possesses several computational properties that seem to be new in the literature. When instantiated with Kullback-Leibler divergence, we establish the global linear convergence of HPMD applied to any MDP instance,...
• Optimal gradient tracking for decentralized optimization AI翻译
  作者：Song, Zhuoqing; Shi, Lei; Pu, Shi; Yan, Ming
  作者单位：Fudan University; Fudan University; The Chinese University of Hong Kong, Shenzhen
  摘要：In this paper, we focus on solving the decentralized optimization problem of minimizing the sum of n objective functions over a multi-agent network. The agents are embedded in an undirected graph where they can only send/receive information directly to/from their immediate neighbors. Assuming smooth and strongly convex objective functions, we propose an Optimal Gradient Tracking (OGT) method that achieves the optimal gradient computation complexity O (root kappa log 1/epsilon) and the optimal ...
• Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems AI翻译
  作者：Boob, Digvijay; Guzman, Cristobal
  作者单位：Southern Methodist University; Pontificia Universidad Catolica de Chile
  摘要：In this work, we conduct the first systematic study of stochastic variational inequality (SVI) and stochastic saddle point (SSP) problems under the constraint of differential privacy (DP). We propose two algorithms: Noisy Stochastic Extragradient (NSEG) and Noisy Inexact Stochastic Proximal Point (NISPP). We show that a stochastic approximation variant of these algorithms attains risk bounds vanishing as a function of the dataset size, with respect to the strong gap function; and a sampling wi...
• Splitting games over finite sets AI翻译
  作者：Koessler, Frederic; Laclau, Marie; Renault, Jerome; Tomala, Tristan
  作者单位：Paris School of Economics; Centre National de la Recherche Scientifique (CNRS); Hautes Etudes Commerciales (HEC) Paris; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
  摘要：This paper studies zero-sum splitting games with finite sets of states. Players dynamically choose a pair of martingales {p(t) , q(t)}(t), in order to control a terminal payoff u(p(infinity),q(infinity)). A first part introduces the notion of Mertens-Zamir transform of a real-valued matrix and use it to approximate the solution of the Mertens-Zamir system for continuous functions on the square [0, 1](2). A second part considers the general case of finite splitting games with arbitrary correspo...
• Optimality and fairness of partisan gerrymandering AI翻译
  作者：Lagarde, Antoine; Tomala, Tristan
  作者单位：Hautes Etudes Commerciales (HEC) Paris
  摘要：We consider the problem of optimal partisan gerrymandering: a legislator in charge of redrawing the boundaries of equal-sized congressional districts wants to ensure the best electoral outcome for his own party. The so-called gerrymanderer faces two issues: the number of districts is finite and there is uncertainty at the level of each district. Solutions to this problem consists in cracking favorable voters in as many districts as possible to get tight majorities, and in packing unfavorable v...
• The polyhedral geometry of truthful auctions AI翻译
  作者：Joswig, Michael; Klimm, Max; Spitz, Sylvain
  作者单位：Technical University of Berlin; Max Planck Society; Technical University of Berlin
  摘要：The difference set of an outcome in an auction is the set of types that the auction mechanism maps to the outcome. We give a complete characterization of the geometry of the difference sets that can appear for a dominant strategy incentive compatible multi-unit auction showing that they correspond to regular subdivisions of the unit cube. Similarly, we describe the geometry for affine maximizers for n players and m items, showing that they correspond to regular subdivisions of the m-fold produ...