acceleration

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

    Accelerated Gradient Descent via Long Steps

  • Benjamin Grimmer
  • Kevin Shu
  • Alex L. Wang
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Unconstrained Optimization Tags , , , , ,

    Recently Grimmer [1] showed for smooth convex optimization by utilizing longer steps periodically, gradient descent’s state-of-the-art O(1/T) convergence guarantees can be improved by constant factors, conjecturing an accelerated rate strictly faster than O(1/T) could be possible. Here we prove such a big-O gain, establishing gradient descent’s first accelerated convergence rate in this setting. Namely, we … Read more

    Provably Faster Gradient Descent via Long Steps

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

    This work establishes provably faster convergence rates for gradient descent in smooth convex optimization via a computer-assisted analysis technique. Our theory allows nonconstant stepsize policies with frequent long steps potentially violating descent by analyzing the overall effect of many iterations at once rather than the typical one-iteration inductions used in most first-order method analyses. We … Read more

    On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport

  • Minhui Huang
  • Shiqian Ma
  • Lifeng Lai
    • Categories Convex Optimization Tags , , , , , ,

    This paper studies the equitable and optimal transport (EOT) problem, which has many applications such as fair division problems and optimal transport with multiple agents etc. In the discrete distributions case, the EOT problem can be formulated as a linear program (LP). Since this LP is prohibitively large for general LP solvers, Scetbon \etal \cite{scetbon2021equitable} … Read more

    Accelerated derivative-free spectral residual method for nonlinear systems of equations

  • Ernesto G. Birgin
  • José Mario Martínez
  • John L. Gardenghi
  • Diaulas S. Marcondes
    • Categories Nonlinear Systems and Least-Squares Tags , , , , ,

    Spectral residual methods are powerful tools for solving nonlinear systems of equations without derivatives. In a recent paper, it was shown that an acceleration technique based on the Sequential Secant Method can greatly improve its efficiency and robustness. In the present work, an R implementation of the method is presented. Numerical experiments with a widely … Read more

    Accelerated derivative-free nonlinear least-squares applied to the estimation of Manning coefficients

  • Ernesto G. Birgin
  • José Mario Martínez
    • Categories Nonlinear Systems and Least-Squares Tags , , ,

    A general framework for solving nonlinear least squares problems without the employment of derivatives is proposed in the present paper together with a new general global convergence theory. With the aim to cope with the case in which the number of variables is big (for the standards of derivative-free optimization), two dimension-reduction procedures are introduced. … Read more

    Secant acceleration of sequential residual methods for solving large-scale nonlinear systems of equations

  • Ernesto G. Birgin
  • José Mario Martínez
    • Categories Nonlinear Systems and Least-Squares Tags , , ,

    Sequential Residual Methods try to solve nonlinear systems of equations $F(x)=0$ by iteratively updating the current approximate solution along a residual-related direction. Therefore, memory requirements are minimal and, consequently, these methods are attractive for solving large-scale nonlinear systems. However, the convergence of these algorithms may be slow in critical cases; therefore, acceleration procedures are welcome. … Read more

    Robust stochastic optimization with the proximal point method

  • Damek Davis
  • Dmitriy Drusvyatskiy
    • Categories Convex Optimization, Stochastic Programming Tags , , , ,

    Standard results in stochastic convex optimization bound the number of samples that an algorithm needs to generate a point with small function value in expectation. In this work, we show that a wide class of such algorithms on strongly convex problems can be augmented with sub-exponential confidence bounds at an overhead cost that is only … Read more

    A unified framework for Bregman proximal methods: subgradient, gradient, and accelerated gradient schemes

  • David H. Gutman
  • Javier F. Peña
    • Categories Convex Optimization Tags , , , ,

    We provide a unified framework for analyzing the convergence of Bregman proximal first-order algorithms for convex minimization. Our framework hinges on properties of the convex conjugate and gives novel proofs of the convergence rates of the Bregman proximal subgradient, Bregman proximal gradient, and a new accelerated Bregman proximal gradient algorithm under fairly general and mild … Read more

    Convergence rates of proximal gradient methods via the convex conjugate

  • David H. Gutman
  • Javier F. Peña
    • Categories Convex Optimization Tags , ,

    We give a novel proof of the $O(1/k)$ and $O(1/k^2)$ convergence rates of the proximal gradient and accelerated proximal gradient methods for composite convex minimization. The crux of the new proof is an upper bound constructed via the convex conjugate of the objective function. Citation Technical Report, Carnegie Mellon University, January 2018. Article Download View … Read more