1期

最新文章

• Inexact Bregman Proximal Gradient Method and Its Inertial Variant with Absolute and Partial Relative Stopping Criteria AI翻译
  作者：Yang, Lei; Toh, Kim-Chuan
  作者单位：Sun Yat Sen University; National University of Singapore
  摘要：The Bregman proximal gradient method (BPGM), which uses the Bregman distance as a proximity measure in the iterative scheme, has recently been redeveloped for minimizing convex composite problems without the global Lipschitz gradient continuity assumption. This makes the BPGM appealing for a wide range of applications, and hence, it has received growing attention in recent years. However, most existing convergence results are obtained only under the assumption that the involved subproblems are...
• Convergence of Augmented Lagrangian Methods for Composite Optimization Problems AI翻译
  作者：Hang, Nguyen Thi Van; Sarabi, Ebrahim
  作者单位：Nanyang Technological University; Vietnam Academy of Science & Technology (VAST); University System of Ohio; Miami University
  摘要：Local convergence analysis of the augmented Lagrangian method (ALM) is established for a large class of composite optimization problems with nonunique Lagrange multipliers under a second-order sufficient condition. We present a new second-order variational property called the semistability of second subderivatives and demonstrate that it is widely satisfied for numerous classes of functions, which is important for applications in constrained and composite optimization problems. Using the latte...
• Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems AI翻译
  作者：Tran-Dinh, Quoc; Luo, Yang
  作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
  摘要：In this paper, we develop two new randomized block-coordinate optimistic gradient algorithms to approximate a solution of nonlinear equations in large-scale settings, which are known as root-finding problems. Our first algorithm is nonaccelerated with constant step sizes and achieves a O(1/k) best-iterate convergence rate on E[& Vert;Gxk & Vert;2] when the underlying operator G is Lipschitz continuous and possesses a weak Minty solution, in which E[] is the expectation and k is the iteration c...
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation AI翻译
  作者：Zhang, Brian Hu; Farina, Gabriele; Celli, Andrea; Sandholm, Tuomas
  作者单位：Carnegie Mellon University; Massachusetts Institute of Technology (MIT); Bocconi University
  摘要：We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games: normal-form coarse correlated equilibrium (NFCCE), extensive-form coarse correlated equilibrium (EFCCE), and extensive-form correlated equilibrium (EFCE). We make two primary contributions. First, we introduce a new algorithm for computing optimal equilibria in all three notions. Its runtime depends exponentially only on a parameter related to the information structure of the game. We also p...
• Robustness and Approximation of Discrete-Time Mean-Field Games Under Discounted Cost Criterion AI翻译
  作者：Aydin, Ugur; Saldi, Naci
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Ihsan Dogramaci Bilkent University
  摘要：In this paper, we investigate the robustness of stationary mean-field equilibria in the presence of model uncertainties, specifically focusing on infinite-horizon discounted cost functions. To achieve this, we initially establish convergence conditions for value iterationbased algorithms in mean-field games. Subsequently, utilizing these results, we demonstrate that the mean-field equilibrium obtained through this value iteration algorithm remains robust even in the face of system dynamics mis...
• A Momentum-Based Linearized Augmented Lagrangian Method for Nonconvex Constrained Stochastic Optimization AI翻译
  作者：Shi, Qiankun; Wang, Xiao; Wang, Hao
  作者单位：Sun Yat Sen University; ShanghaiTech University
  摘要：Nonconvex constrained stochastic optimization has emerged in many important application areas. Subject to general functional constraints, it minimizes the sum of an expectation function and a nonsmooth regularizer. Main challenges arise because of the stochasticity in the random integrand and the possibly nonconvex functional constraints. To address these issues, we propose a momentum-based linearized augmented Lagrangian method (MLALM). MLALM adopts a single-loop framework and incorporates a ...
• Probabilistic Analysis of Edge Elimination for Euclidean TSP AI翻译
  作者：Zhong, Xianghui
  作者单位：University of Bonn
  摘要：One way to speed up the calculation of optimal traveling salesman problem tours in practice is eliminating edges that are certainly not in the optimal tour as a preprocessing step. In order to do so, several edge elimination approaches have been proposed in the past. In this work, we investigate two of them in the scenario where the input consists of n independently distributed random points in the two-dimensional unit square with density function bounded from above and below by arbitrary posi...
• Square-Root Regret Bounds for Continuous-Time Episodic Markov Decision Processes AI翻译
  作者：Gao, Xuefeng; Zhou, Xunyu
  作者单位：Chinese University of Hong Kong; Columbia University
  摘要：We study reinforcement learning for continuous-time Markov decision processes (MDPs) in the finite-horizon episodic setting. In contrast to discrete-time MDPs, the intertransition times of a continuous-time MDP are exponentially distributed with rate parameters depending on the state-action pair at each transition. We present a learning algorithm based on the methods of value iteration and upper confidence bound. We derive an upper bound on the worst case expected regret for the proposed algor...
• SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization AI翻译
  作者：Kurpisz, Adam; Potechin, Aaron; Wirth, Elias
  作者单位：ETH Zurich; Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Chicago; Technical University of Berlin
  摘要：We introduce several methods to study the rank of the sum of squares (SoS) hierarchy for problems over the Boolean hypercube. We apply our techniques to improve upon existing results, thus answering several open questions. We answer the question by Laurent regarding the SoS rank of the empty integral hull (EIH) problem. We prove that the SoS rank is between inverted right perpendicularn/2inverted left perpendicular and inverted right perpendicularn/2+ root n log 2ninverted left perpendicular. ...
• Uniform Moment Bounds for Generalized Jackson Networks in Multiscale Heavy Traffic AI翻译
  作者：Guang, Jin; Chen, Xinyun; Dai, J. G.
  作者单位：The Chinese University of Hong Kong, Shenzhen; Cornell University
  摘要：We establish uniform moment bounds for steady-state queue lengths of generalized Jackson networks (GJNs) in multiscale heavy traffic as recently proposed by Dai et al. in 2023. Uniform moment bounds lay the foundation for further analysis of the limit stationary distribution. Our result can be used to verify the crucial moment state space collapse (SSC) assumption in Dai et al. in 2023 to establish a product-form limit of GJN in the multiscale heavy traffic regime. Our proof critically utilize...