2024

最新文章

• Convergence Analysis of Accelerated Stochastic Gradient Descent Under the Growth Condition AI翻译
  作者：Chen, You-Lin; Na, Sen; Kolar, Mladen
  作者单位：University of Chicago; University of California System; University of California Berkeley; University of Chicago
  摘要：We study the convergence of accelerated stochastic gradient descent (SGD) for strongly convex objectives under the growth condition, which states that the variance of stochastic gradient is bounded by a multiplicative part that grows with the full gradient and a constant additive part. Through the lens of the growth condition, we investigate four widely used accelerated methods: Nesterov's accelerated method (NAM), robust momentum method (RMM), accelerated dual averaging method (DAM+), and imp...
• Quantitative Convergence for Displacement Monotone Mean Field Games with Controlled Volatility AI翻译
  作者：Jackson, Joe; Tangpib, Ludovic
  作者单位：University of Chicago; Princeton University
  摘要：We study the convergence problem for mean field games with common noise and controlled volatility. We adopt the strategy recently put forth by Laurie re and the second author, using the maximum principle to recast the convergence problem as a question of forward-backward propagation of chaos (i.e., (conditional) propagation of chaos for systems of particles evolving forward and backward in time). Our main results show that displacement monotonicity can be used to obtain this propagation of c...
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness AI翻译
  作者：Amanatidis, Georgios; Birmpas, Georgios; Fusco, Federico; Lazos, Philip; Leonardi, Stefano; Reiffenhauser, Rebecca
  作者单位：University of Essex; University of Liverpool; Sapienza University Rome; University of Amsterdam
  摘要：We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers, and therefore, a mechanism in our setting is an algorithm that takes as input the reported- rather than the true-values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspon...
• Worst-Case Iteration Bounds for Log Barrier Methods on Problems with Nonconvex Constraints AI翻译
  作者：Hinder, Oliver; Ye, Yinyu
  作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Stanford University
  摘要：Interior point methods (IPMs) that handle nonconvex constraints such as IPOPT, KNITRO and LOQO have had enormous practical success. We consider IPMs in the setting where the objective and constraints are thrice differentiable, and have Lipschitz first and second derivatives on the feasible region. We provide an IPM that, starting from a strictly feasible point, finds a mu-approximate Fritz John point by solving O(mu-7=4) trustregion subproblems. For IPMs that handle nonlinear constraints, this...
• Extreme-Case Distortion Risk Measures: A Unification and Generalization of Closed-Form Solutions AI翻译
  作者：Shao, Hui; Zhang, Zhe George
  作者单位：Zhejiang University; Western Washington University; Simon Fraser University
  摘要：Extreme-case risk measures provide an approach for quantifying the upper and lower bounds of risk in situations where limited information is available regarding the underlying distributions. Previous research has demonstrated that for popular risk measures, such as value-at-risk and conditional value-at-risk, the worst-case counterparts can be evaluated in closed form when only the first two moments of the underlying distributions are known. In this study, we extend these findings by presentin...
• Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number AI翻译
  作者：Chaudhury, Bhaskar Ray; Garg, Jugal; Mehlhorn, Kurt; Mehta, Ruta; Misra, Pranabendu
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Max Planck Society; University of Illinois System; University of Illinois Urbana-Champaign; Chennai Mathematical Institute
  摘要：We study the problem of fairly allocating a set of indivisible goods among n agents with additive valuations. Envy freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of an EFX allocation has not been settled and is one of the most important problems in fair division. Toward resolving this question, many impressive results show the existence of its relaxations. In particular, it is known that 0.618-EFX allocations exist and that...
• The Competition Complexity of Dynamic Pricing AI翻译
  作者：Brustle, Johannes; Correa, Jose; Duetting, Paul; Verdugo, Victor
  作者单位：University of London; London School Economics & Political Science; Universidad de Chile; Alphabet Inc.; Google Incorporated; Universidad de O'Higgins
  摘要：We study the competition complexity of dynamic pricing relative to the optimal auction in the fundamental single-item setting. In prophet inequality terminology, we compare the expected reward Am(F) achievable by the optimal online policy on m independent and identically distributed (i.i.d.) random variables distributed according to F to the expected maximum Mn(F)of n i.i.d. draws from F. We ask how big m has to be to ensure that (1 + epsilon)Am(F) >_ Mn(F) for all F. We resolve this question ...
• Uniform Mixed Equilibria in Network Congestion Games with Link Failures AI翻译
  作者：Bilo, Vittorio; Moscardelli, Luca; Vinci, Cosimo
  作者单位：University of Salento; G d'Annunzio University of Chieti-Pescara; Gran Sasso Science Institute (GSSI)
  摘要：Motivated by possible applications in fault-tolerant selfish routing, we introduce the notion of uniform mixed equilibrium in network congestion games with adversarial link failures, where agents need to route traffic from a source to a destination node. Given an integer p >_ 1, a p-uniform mixed strategy is a mixed strategy in which an agent plays exactly p edge-disjoint paths with uniform probability; therefore, a p-uniform mixed equilibrium is a tuple of p-uniform mixed strategies, one for ...
• Asymptotic Optimality of Constant-Order Policies in Joint Pricing and Inventory Models AI翻译
  作者：Chen, Xin; Stolyar, Alexander L.; Xin, Linwei
  作者单位：University System of Georgia; Georgia Institute of Technology; University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; University of Chicago
  摘要：We consider a classic joint pricing and inventory control problem with lead times, which is extensively studied in the literature but is notoriously difficult to solve because of the complex structure of the optimal policy. In this work, rather than analyzing the optimal policy, we propose a class of constant-order dynamic pricing policies, which are fundamentally different from base-stock list price policies, the primary emphasis in the existing literature. Under such a policy, a constant-ord...
• A First-Order Primal-Dual Method for Nonconvex Constrained Optimization Based on the Augmented Lagrangian AI翻译
  作者：Zhu, Daoli; Zhao, Lei; Zhang, Shuzhong
  作者单位：Shanghai Jiao Tong University; Shanghai Jiao Tong University; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; Shanghai Jiao Tong University; Shanghai Jiao Tong University; University of Minnesota System; University of Minnesota Twin Cities
  摘要：Nonlinearly constrained nonconvex and nonsmooth optimization models play an increasingly important role in machine learning, statistics, and data analytics. In this paper, based on the augmented Lagrangian function, we introduce a flexible first-order primal-dual method, to be called nonconvex auxiliary problem principle of augmented Lagrangian (NAPP-AL), for solving a class of nonlinearly constrained nonconvex and nonsmooth optimization problems. We demonstrate that NAPP-AL converges to a sta...