2025

最新文章

• A Characterization of Simultaneous Optimization, Majorization, and (Bi-)Submodular Polyhedra AI翻译
  作者：Uiterkamp, Martijn H. H. Schoot
  作者单位：Tilburg University
  摘要：Motivated by resource allocation problems (RAPs) in power management applications, we investigate the existence of solutions to optimization problems that simultaneously minimize the class of Schur-convex functions, also called least-majorized elements. For this, we introduce a generalization of majorization and least-majorized elements, called (a, b)-majorization and least (a, b)-majorized elements, and characterize the feasible sets of problems that have such elements in terms of base and (b...
• Oracle Complexities of Augmented Lagrangian Methods for Nonsmooth Composite Optimization on a Compact Submanifold AI翻译
  作者：Deng, Kangkang; Hu, Jiang; Wu, Jiayuan; Wen, Zaiwen
  作者单位：National University of Defense Technology - China; Tsinghua University; Peking University; Peking University
  摘要：In this paper, we present two novel manifold inexact augmented Lagrangian methods, ManIAL for deterministic settings and StoManIAL for stochastic settings, solving non-smooth composite optimization problems on a compact submanifold embedded in the Euclidean space. By using the Riemannian gradient method as a subroutine, we establish an O(epsilon-3) oracle complexity result of ManIAL, matching the best-known complexity result. Our algorithm relies on the careful selection of penalty parameters ...
• On the Uniform Convergence of Subdifferentials in Stochastic Optimization and Learning AI翻译
  作者：Ruan, Feng
  作者单位：Northwestern University
  摘要：We investigate the uniform convergence of subdifferential mappings from empirical risk to population risk in nonsmooth, nonconvex stochastic optimization. This question is key to understanding how empirical stationary points approximate population ones, yet characterizing this convergence remains a fundamental challenge because of the set-valued and nonsmooth nature of subdifferentials. This work establishes a general reduction principle: for weakly convex stochastic objectives, over any open ...
• Invariant States of Hydrodynamic Limits of Randomized Load-Balancing Networks AI翻译
  作者：Agarwal, Pooja; Ramanan, Kavita
  作者单位：Brown University
  摘要：Randomized load-balancing algorithms play an important role in improving performance in large-scale networks at relatively low computational cost. A common model of such a system is a network of N parallel queues in which incoming jobs with independent and identically distributed service times are routed on arrival using the join-the-shortest-ofd-queues routing algorithm. Under fairly general conditions, it was shown by Aghajani and Ramanan that as N-infinity, the state dynamics converge to th...
• Effort Decisions in Contests with Shared Attributes AI翻译
  作者：He, Jiahao; Zhang, Jiheng; Zhang, Rachel Q.
  作者单位：Hong Kong University of Science & Technology
  摘要：Individuals and organizations often face contests that require various skills, which can be developed through time and resource investments. Consider homogeneous contestants participating in multiple contests, each with multiple attributes and a reward for the winner or shared equally in case of a tie. Contestants can invest effort, at a cost, to enhance their skills in these attributes to maximize their expected net gain. Because contests may share some attributes while having unique ones, im...
• O'Neill's Theorem for Games AI翻译
  作者：Govindan, Srihari; Laraki, Rida; Pahl, Lucas
  作者单位：University of Rochester; Mohammed VI Polytechnic University; University of Sheffield
  摘要：We present the following analog of O'Neill's theorem (O'Neill B (1953) Essential sets and fixed points. Amer. J. Math. 75(3):497-509 (theorem 5.2)) for finite games. Let C-1, . . . , C-k be the components of Nash equilibria of a finite normal-form game G. For each i, let c(i) be the index of C-i. For each epsilon > 0, there exist pairwise disjoint neighborhoods V-1, . . . , V-k of the components such that for any choice of finitely many distinct completely mixed strategy profiles {sigma(ij)}(i...
• A Derivative-Free Algorithm for Minimization in One Dimension: Relaxation, Monte Carlo, and Sampling AI翻译
  作者：Gomes, Alexandra A.; Gomes, Diogo A.
  作者单位：King Abdullah University of Science & Technology
  摘要：We introduce a derivative-free optimization algorithm that efficiently computes minima for various classes of one-dimensional functions, including nonconvex and nonsmooth functions. This algorithm numerically approximates the gradient flow of a relaxed functional, integrating strategies such as Monte Carlo methods, rejection sampling, and adaptive techniques. These strategies enhance performance in solving a diverse range of optimization problems while significantly reducing the number of requ...
• Thompson Sampling for the Multinomial Logit Bandit AI翻译
  作者：Agrawal, Shipra; Avadhanula, Vashist; Goyal, Vineet; Zeevi, Assaf
  作者单位：Columbia University; Columbia University
  摘要：We consider a dynamic combinatorial optimization problem where at each time step, the decision maker selects a subset of cardinality K from N possible items and observes a feedback in the form of the index of one of the items in the said subset or none. Each of the N items is ascribed a certain value (reward), which is collected if the item is chosen. This problem is motivated by that of assortment selection in online retail, where items are products. Akin to that literature, it is assumed tha...
• Comparison Between Mean-Variance and Monotone Mean-Variance Preferences Under Jump Diffusion and Stochastic Factor Model AI翻译
  作者：Li, Yuchen; Liang, Zongxia; Pang, Shunzhi
  作者单位：Tsinghua University; Tsinghua University
  摘要：This paper compares the optimal investment problems based on monotone mean-variance (MMV) and mean-variance (MV) preferences in a Levy market with an untradable stochastic factor. It is an open question proposed by Trybu & lstrok;a and Zawisza. Using the dynamic programming and Lagrange multiplier methods, we get the HamiltonJacobi-Bellman-Isaacs (HJBI) and Hamilton-Jacobi-Bellman (HJB) equations corresponding to the two investment problems. The equations are transformed into a new-type parabo...
• A Retrospective Approximation Approach for Smooth Stochastic Optimization AI翻译
  作者：Newton, David; Bollapragada, Raghu; Pasupathy, Raghu; Yip, Nung Kwan
  作者单位：Purdue University System; Purdue University; University of Texas System; University of Texas Austin; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Madras; Purdue University System; Purdue University
  摘要：Stochastic Gradient (SG) is the de facto iterative technique to solve stochastic optimization (SO) problems with a smooth (nonconvex) objective f and a stochastic first-order oracle. SG's attractiveness is due in part to its simplicity of executing a single step along the negative subsampled gradient direction to update the incumbent iterate. In this paper, we question SG's choice of executing a single step as opposed to multiple steps between subsample updates. Our investigation leads natural...