First-order algorithms converge faster than O(1/k) on convex problems

2018/12/20 by Lee, Ching-pei, Wright, Stephen J. · 1 citation
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1812.08485

Abstract

It is well known that both gradient descent and stochastic coordinate descent achieve a global convergence rate of O(1/k) in the objective value, when applied to a scheme for minimizing a Lipschitz-continuously differentiable, unconstrained convex function. In this work, we improve this rate to o(1/k). We extend the result to proximal gradient and proximal coordinate descent on regularized problems to show similar o(1/k) convergence rates. The result is tight in the sense that a rate of O(1/k^1+ε) is not generally attainable for any ε>0, for any of these methods.

Cited by

• Optimization in Theory and Practice

Related

• Lower Bounds for Finding Stationary Points II: First-Order Methods
• Block Coordinate Descent Only Converge to Minimizers
• Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity
• First-Order Algorithms Without Lipschitz Gradient: A Sequential Local Optimization Approach
• The Randomized Block Coordinate Descent Method in the Hölder Smooth Setting