1-2期

最新文章

• Faster first-order primal-dual methods for linear programming using restarts and sharpness AI翻译
  作者：Applegate, David; Hinder, Oliver; Lu, Haihao; Lubin, Miles
  作者单位：Alphabet Inc.; Google Incorporated; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; University of Chicago
  摘要：First-order primal-dual methods are appealing for their low memory overhead, fast iterations, and effective parallelization. However, they are often slow at finding high accuracy solutions, which creates a barrier to their use in traditional linear programming (LP) applications. This paper exploits the sharpness of primal-dual formulations of LP instances to achieve linear convergence using restarts in a general setting that applies to alternating direction method of multipliers (ADMM), primal...
• Zeroth-order optimization with orthogonal random directions AI翻译
  作者：Kozak, David; Molinari, Cesare; Rosasco, Lorenzo; Tenorio, Luis; Villa, Silvia
  作者单位：Istituto Italiano di Tecnologia - IIT; University of Genoa; Colorado School of Mines; University of Genoa
  摘要：We propose and analyze a randomized zeroth-order optimization method based on approximating the exact gradient by finite differences computed in a set of orthogonal random directions that changes with each iteration. A number of previously proposed methods are recovered as special cases including spherical smoothing, coordinate descent, as well as discretized gradient descent. Our main contribution is proving convergence guarantees as well as convergence rates under different parameter choices...
• Lower bounds for non-convex stochastic optimization AI翻译
  作者：Arjevani, Yossi; Carmon, Yair; Duchi, John C.; Foster, Dylan J.; Srebro, Nathan; Woodworth, Blake
  作者单位：Hebrew University of Jerusalem; Tel Aviv University; Stanford University; Microsoft; Inria
  摘要：We lower bound the complexity of finding epsilon-stationary points (with gradient norm at most epsilon) using stochastic first-order methods. In a well-studied model where algorithms access smooth, potentially non-convex functions through queries to an unbiased stochastic gradient oracle with bounded variance, we prove that (in the worst case) any algorithm requires at least epsilon(-4) queries to find an epsilon-stationary point. The lower bound is tight, and establishes that stochastic gradi...
• Vertex downgrading to minimize connectivity AI翻译
  作者：Aissi, Hassene; Chen, Da Qi; Ravi, R.
  作者单位：Universite PSL; Universite Paris-Dauphine; Carnegie Mellon University; Carnegie Mellon University
  摘要：We consider the problem of interdicting a directed graph by deleting nodes with the goal of minimizing the local edge connectivity of the remaining graph from a given source to a sink. We introduce and study a general downgrading variant of the interdiction problem where the capacity of an arc is a function of the subset of its endpoints that are downgraded, and the goal is to minimize the downgraded capacity of a minimum source-sink cut subject to a node downgrading budget. This models the ca...
• A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems AI翻译
  作者：Xu, Zi; Zhang, Huiling; Xu, Yang; Lan, Guanghui
  作者单位：Shanghai University; University System of Georgia; Georgia Institute of Technology
  摘要：Much recent research effort has been directed to the development of efficient algo-rithms for solving minimax problems with theoretical convergence guarantees due to the relevance of these problems to a few emergent applications. In this paper, we propose a unified single-loop alternating gradient projection (AGP) algorithm for solving smooth nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. AGP employs simple gradient projection steps for updating the primal and ...
• Principled analyses and design of first-order methods with inexact proximal operators AI翻译
  作者：Barre, Mathieu; Taylor, Adrien B.; Bach, Francis
  作者单位：Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Inria
  摘要：Proximal operations are among the most common primitives appearing in both practical and theoretical (or high-level) optimization methods. This basic operation typically consists in solving an intermediary (hopefully simpler) optimization problem. In this work, we survey notions of inaccuracies that can be used when solving those intermediary optimization problems. Then, we show that worst-case guarantees for algorithms relying on such inexact proximal operations can be systematically obtained...
• Towards explicit superlinear convergence rate for SR1 AI翻译
  作者：Ye, Haishan; Lin, Dachao; Chang, Xiangyu; Zhang, Zhihua
  作者单位：Xi'an Jiaotong University; Peking University; Peking University
  摘要：We study the convergence rate of the famous Symmetric Rank-1 (SR1) algorithm, which has wide applications in different scenarios. Although it has been extensively investigated, SR1 still lacks a non-asymptotic superlinear rate compared with other quasi-Newton methods such as DFP and BFGS. In this paper, we address the aforementioned issue to obtain the first explicit non-asymptotic rates of superlinear convergence for the vanilla SR1 methods with a correction strategy that is used to achieve n...
• Supermodularity and valid inequalities for quadratic optimization with indicators AI翻译
  作者：Atamturk, Alper; Gomez, Andres
  作者单位：University of California System; University of California Berkeley; University of Southern California
  摘要：We study the minimization of a rank-one quadratic with indicators and show that the underlying set function obtained by projecting out the continuous variables is supermodular. Although supermodular minimization is, in general, difficult, the specific set function for the rank-one quadratic can be minimized in linear time. We show that the convex hull of the epigraph of the quadratic can be obtained from inequalities for the underlying supermodular set function by lifting them into nonlinear i...
• Tangencies and polynomial optimization AI翻译
  作者：Tien-Son Pham
  作者单位：Dalat University
  摘要：Given a polynomial function f : R-n -> R and an unbounded closed semi-algebraic set S subset of R-n, we show that the conditions listed below are characterized exactly in terms of the so-called tangency variety of the restriction of f on S: f is bounded from below on S; f attains its infimum on S; The sublevel sets (x is an element of S vertical bar f (x) <= lambda} for lambda is an element of R are compact; f is coercive on S. Besides, we also provide some stability criteria for boundedness a...
• Primal-dual path following method for nonlinear semi-infinite programs with semi-definite constraints AI翻译
  作者：Okuno, Takayuki; Fukushima, Masao
  作者单位：Seikei University; RIKEN
  摘要：In this paper, we propose a primal-dual path following method for nonlinear semi-infinite semi-definite programs with infinitely many convex inequality constraints, called SISDP for short. A straightforward approach to the SISDP is to use classical methods for semi-infinite programs such as discretization and exchange methods and solve a sequence of (nonlinear) semi-definite programs (SDPs). However, it is often too demanding to find exact solutions of SDPs. In contrast, our approach does not ...