Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions

2018/03/18 by Kim, Donghwan, Fessler, Jeffrey A. · 3 citations
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1803.06600

Abstract

This paper optimizes the step coefficients of first-order methods for smooth convex minimization in terms of the worst-case convergence bound (i.e., efficiency) of the decrease in the gradient norm. This work is based on the performance estimation problem approach. The worst-case gradient bound of the resulting method is optimal up to a constant for large-dimensional smooth convex minimization problems, under the initial bounded condition on the cost function value. This paper then illustrates that the proposed method has a computationally efficient form that is similar to the optimized gradient method.

Cited by

• Data-Driven Analysis of First-Order Methods via Distributionally Robust Optimization
• A Theory of Composition and Duality of Extremal Optimal Fixed-Point Algorithms
• Numerical Design of Optimized First-Order Algorithms

Related

• Performance of first-order methods for smooth convex minimization: a\n novel approach
• Smooth Strongly Convex Interpolation and Exact Worst-case Performance of\n First-order Methods
• Numerical Design of Optimized First-Order Algorithms
• An optimal lower bound for smooth convex functions
• An optimal gradient method for smooth strongly convex minimization