Continuous-time Lower Bounds for Gradient-based Algorithms

2020/02/10 by Michael Muehlebach, Michael I. Jordan, Muehlebach, Michael +1 · 2 citations
Engineering · Computer Science · Mathematics · #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Advanced Optimization Algorithms Research

paper · pdf · doi:10.48550/arxiv.2002.03546

Abstract

This article derives lower bounds on the convergence rate of continuous-time gradient-based optimization algorithms. The algorithms are subjected to a time-normalization constraint that avoids a reparametrization of time in order to make the discussion of continuous-time convergence rates meaningful. We reduce the multi-dimensional problem to a single dimension, recover well-known lower bounds from the discrete-time setting, and provide insight into why these lower bounds occur. We present algorithms that achieve the proposed lower bounds, even when the function class under consideration includes certain nonconvex functions.

Cited by

• Essential Convergence Rates of Continuous-Time Models for Optimization Methods
• A Systems-Theoretic View on the Convergence of Algorithms under Disturbances

Related

• Temporal Variabilities Limit Convergence Rates in Gradient-Based Online Optimization
• Continuous-time Models for Stochastic Optimization Algorithms
• Essential Convergence Rates of Continuous-Time Models for Optimization Methods
• Finite-time and Fixed-time Convergence in Continuous-time Optimization
• Optimization in Theory and Practice