Mathematics of Operations Research

最新文章

• Global Algorithms for Mean-Variance Optimization in Markov Decision Processes AI翻译
  作者：Xia, Li; Ma, Shuai
  作者单位：Sun Yat Sen University
  摘要：Dynamic optimization of mean and variance in Markov decision processes (MDPs) is a long-standing challenge caused by the failure of dynamic programming. In this paper, we propose a new approach to finding the globally optimal policy for combined metrics of steady-state mean and variance in an infinite-horizon undiscounted MDP. By introducing the concepts of pseudo mean and pseudo variance, we convert the original problem to a bilevel MDP problem, where the inner one is a standard MDP optimizin...
• Generalized Metric Subregularity with Applications to High-Order Regularized Newton Methods AI翻译
  作者：Li, Guoyin; Mordukhovich, Boris; Zhu, Jiangxing
  作者单位：University of New South Wales Sydney; Wayne State University; Yunnan University
  摘要：This paper pursues a twofold goal. First, we introduce and study in detail a new notion of variational analysis called generalized metric subregularity, which is a far-going extension of the conventional metric subregularity conditions. Our primary focus is on examining this concept concerning first-order and second-order stationary points. We develop an extended convergence framework that enables us to derive superlinear and quadratic convergence under the generalized metric subregularity con...
• A Single-Loop Algorithm for Decentralized Bilevel Optimization AI翻译
  作者：Dong, Youran; Ma, Shiqian; Yang, Tunfeng; Yin, Chao
  作者单位：Nanjing University; Rice University; Hohai University
  摘要：Bilevel optimization has gained significant attention in recent years because of its broad applications in machine learning. This paper focuses on bilevel optimization in decentralized networks and proposes a novel single-loop algorithm for solving decentralized bilevel optimization with a strongly convex lower-level problem. Our approach is built on the basis of the SOBA framework, and it is a fully single-loop method that approximates the hypergradient by using merely two matrix-vector multi...
• Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning AI翻译
  作者：Srikant, R.
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign
  摘要：We prove a nonasymptotic central limit theorem (CLT) for vector-valued martingale differences using Stein's method, and we use Poisson's equation to extend the result to functions of Markov chains. We then show that these results can be applied to establish a nonasymptotic CLT for temporal difference learning with averaging.
• On the Sequential Convergence of Lloyd's Algorithms AI翻译
  作者：Portales, Leo; Cazelles, Elsa; Pauwelsc, Edouard
  作者单位：Communaute d'universites et etablissements de Toulouse (Comue); Universite de Toulouse (EPE); Universite Toulouse 1 Capitole; Institut National Polytechnique de Toulouse; Toulouse School of Economics; Centre National de la Recherche Scientifique (CNRS); Communaute d'universites et etablissements de Toulouse (Comue); Communaute d'universites et etablissements de Toulouse (Comue); Universite Toulouse 1 Capitole; Toulouse School of Economics
  摘要：Lloyd's algorithm is an iterative method that solves the quantization problem, that is, the approximation of a target probability measure by a discrete one, and is particularly used in digital applications. This algorithm can be interpreted as a gradient method on a certain quantization functional which is given by optimal transport. We study the sequential convergence (to a single accumulation point) for two variants of Lloyd's method: (i) optimal quantization with an arbitrary discrete measu...
• Single-Server Queues with State-Dependent Hawkes Arrivals AI翻译
  作者：Li, Bo; Pang, Guodong
  作者单位：Nankai University; Nankai University; Rice University
  摘要：We study single-server queues with Hawkes arrivals whose intensity process depends on the queue length through the self-exciting function, and with independent and identically distributed general service times, under the first-come first-served discipline. We prove the functional law of large numbers and functional central limit theorems (FCLT) for the joint processes of the arrivals, queue-length, and workload processes, in the heavy traffic regime. The fluid limit is given by a set of nonlin...
• 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...