Convex and Nonsmooth Optimization

Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation

  • Aaron Mishkin
  • Mert Pilanci
  • Mark Schmidt
    • Categories Convex Optimization, Stochastic Programming Tags , , ,

    \(\) We prove new convergence rates for a generalized version of stochastic Nesterov acceleration under interpolation conditions. Unlike previous analyses, our approach accelerates any stochastic gradient method which makes sufficient progress in expectation. The proof, which proceeds using the estimating sequences framework, applies to both convex and strongly convex functions and is easily specialized to … Read more

    Horoballs and the subgradient method

  • Adrian Lewis
    • Categories Convex and Nonsmooth Optimization, Other Topics Tags , , , , ,

    To explore convex optimization on Hadamard spaces, we consider an iteration in the style of a subgradient algorithm. Traditionally, such methods assume that the underlying spaces are manifolds and that the objectives are geodesically convex: the methods are described using tangent spaces and exponential maps. By contrast, our iteration applies in a general Hadamard space, … Read more

    Second-Order Strong Optimality and Second-Order Duality for Nonsmooth Constrained Multiobjective Fractional Programming Problems

  • Chen Jiawei
  • Luyu Liu
  • Jen-Chih Yao
    • Categories Multi-Criteria Optimization, Nonsmooth Optimization Tags , , , ,

    \(\) This paper investigates constrained nonsmooth multiobjective fractional programming problem (NMFP) in real Banach spaces. It derives a quotient calculus rule for computing the first- and second-order Clarke derivatives of fractional functions involving locally Lipschitz functions. A novel second-order Abadie-type regularity condition is presented, defined with the help of the Clarke directional derivative and the … Read more

    Slow convergence of the moment-SOS hierarchy for an elementary polynomial optimization problem

  • Didier Henrion
  • Adrien Le Franc
  • Victor Magron
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    We describe a parametric univariate quadratic optimization problem for which the moment-SOS hierarchy has finite but increasingly slow convergence when the parameter tends to its limit value. We estimate the order of finite convergence as a function of the parameter. Article Download View Slow convergence of the moment-SOS hierarchy for an elementary polynomial optimization problem

    Fast convergence of the primal-dual dynamical system and algorithms for a nonsmooth bilinearly coupled saddle point problem

  • Kewei Ding
  • Jörg Fliege
  • Phan Vuong
    • Categories Game Theory, Nonsmooth Optimization Tags , , , ,

    \(\) This paper is devoted to study the convergence rates of a second-order dynamical system and its corresponding discretizations associated with a nonsmooth bilinearly coupled convex-concave saddle point problem. We derive the convergence rate of the primal-dual gap for the second-order dynamical system with asymptotically vanishing damping term. Based on the implicit discretization, we propose … Read more

    Scalable Projection-Free Optimization Methods via MultiRadial Duality Theory

  • Thabo Samakhoana
  • Benjamin Grimmer
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

    Recent works have developed new projection-free first-order methods based on utilizing linesearches and normal vector computations to maintain feasibility. These oracles can be cheaper than orthogonal projection or linear optimization subroutines but have the drawback of requiring a known strictly feasible point to do these linesearches with respect to. In this work, we develop new … Read more

    ε-Optimality in Reverse Optimization

  • Mounir El Maghri
    • Categories Convex and Nonsmooth Optimization, Global Optimization Tags , , , ,

    The purpose of this paper is to completely characterize the global approximate optimality (ε-optimality) in reverse convex optimization under the general nonconvex constraint “h(x) ≥ 0”. The main condition presented is obtained in terms of Fenchel’s ε-subdifferentials thanks to El Maghri’s ε-efficiency in difference vector optimization [J. Glob. Optim. 61 (2015) 803–812], after converting the … Read more

    The stochastic Ravine accelerated gradient method with general extrapolation coefficients

  • Hédy Attouch
  • Jalal Fadili
  • Vyacheslav Kungurtsev
    • Categories Convex Optimization, Nonlinear Optimization Tags ,

    Abstract: In a real Hilbert space domain setting, we study the convergence properties of the stochastic Ravine accelerated gradient method for convex differentiable optimization. We consider the general form of this algorithm where the extrapolation coefficients can vary with each iteration, and where the evaluation of the gradient is subject to random errors. This general … Read more

    On Averaging and Extrapolation for Gradient Descent

  • Alan Luner
  • Benjamin Grimmer
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    \(\) This work considers the effect of averaging, and more generally extrapolation, of the iterates of gradient descent in smooth convex optimization. After running the method, rather than reporting the final iterate, one can report either a convex combination of the iterates (averaging) or a generic combination of the iterates (extrapolation). For several common stepsize … Read more