Efficient first-order methods for convex minimization: a constructive approach

Yoel Drori, Adrien B. Taylor

TL;DR

This paper introduces a novel "constructive approach" to design efficient first-order optimization methods for convex minimization problems. By leveraging a greedy conjugate gradient-like method as a conceptual starting point, they develop a procedure to transform these methods into efficient fixed-step algorithms that achieve the same or better worst-case performance guarantees. This framework allows for the derivation of optimal methods for various classes of convex functions, including smooth, non-smooth, and strongly convex settings.

What Problem Does This Paper Address?

First-order optimization methods are crucial for large-scale convex minimization problems due to their low per-iteration cost. However, they often suffer from slow convergence, limiting their use to obtaining low-to-medium accuracy solutions. The challenge lies in designing methods that achieve optimal convergence rates while remaining computationally efficient and practical. Existing methods often rely on specific problem properties (like smoothness or strong convexity) or require complex line searches. This paper aims to bridge this gap by providing a systematic way to construct efficient first-order methods that are guaranteed to perform as well as theoretically optimal, yet potentially impractical, methods.

Methods

The core of the paper's contribution is a "constructive approach" that starts with a conceptual "Greedy First-Order Method" (GFOM). GFOM is a subspace-search method that, while theoretically optimal, is computationally intractable. The authors then develop a "Subspace-search Elimination Procedure" (SSEP) to transform GFOM into efficient fixed-step methods. This procedure leverages a performance estimation framework, which reformulates the problem of finding optimal method parameters into a convex optimization problem (specifically, a semidefinite program or its dual). By solving these problems, they derive the coefficients for new methods that inherit GFOM's worst-case guarantees. This approach is applied to derive optimal methods for smooth, non-smooth, and strongly convex functions, and even a universal method that works for both smooth and non-smooth cases without prior knowledge of their specific parameters.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Constructive Approach: The paper introduces a powerful paradigm: start with a theoretically optimal but impractical method (GFOM) and systematically "construct" efficient, practical methods that match its performance. This is a significant shift from simply analyzing existing methods.
  • Performance Estimation Problem (PEP): The authors effectively use PEPs as a central tool. By formulating the worst-case performance of GFOM as a PEP, they can then derive constraints for designing new methods. This framework allows for rigorous analysis and guarantees.
  • Subspace-Search Elimination Procedure (SSEP): This procedure is the key to transforming the conceptual GFOM into practical algorithms. It cleverly eliminates the need for explicit subspace searches by deriving fixed update rules.
  • Universality: The development of a universal method that doesn't require knowledge of whether a function is smooth or non-smooth, or its specific parameters, is a significant achievement. This method achieves optimal performance by performing a three-dimensional subspace minimization, which is still computationally feasible.
  • Tightness of Bounds: A recurring theme is demonstrating that the derived methods achieve tight worst-case bounds, meaning their performance matches the theoretical lower bounds for the problem classes they address.

Key Results

  • Optimal Methods for Specific Classes: The paper derives optimal first-order methods for:
  • Non-smooth convex minimization: Achieves a worst-case bound of $O(MR_x/\sqrt{N})$.
  • Smooth convex minimization: Achieves a worst-case bound of $O(LR_x^2/\sqrt{N})$ (for GFOM) and $O(LR_x^2/\sqrt{N})$ for the derived SSEP method.
  • Strongly convex minimization: Derives a method with an improved worst-case bound compared to Nesterov's fast gradient method.
  • Universal Method: A single method is presented that works for both smooth and non-smooth convex functions, achieving optimal worst-case bounds for each class by performing a three-dimensional subspace search.
  • Fixed-Step Methods: The SSEP procedure successfully generates fixed-step methods that match the performance of their subspace-searching counterparts, eliminating the need for line searches in many cases.

Limitations and Future Work

  • Computational Complexity of PEPs: While the framework is powerful, solving the performance estimation problems can become computationally expensive for very large numbers of iterations ($N$) or high-dimensional problems. The paper notes that for some cases, numerical solutions to SDPs are used.
  • Contraction-Preserving Property: The tightness of the derived bounds relies on the "contraction-preserving" property of function classes, which is satisfied by common classes but might not hold for all possible function families.
  • Future Work: The authors suggest several avenues for future research, including:
  • Extending the approach to other function classes (e.g., composite functions, inexact oracles, stochastic oracles, block-coordinate descent).
  • Investigating alternative optimality criteria for the greedy method.
  • Exploring methods for real-time embedded optimization where pre-computation is acceptable.

Summary updated

Abstract

We describe a novel constructive technique for devising efficient first-order methods for a wide range of large-scale convex minimization settings, including smooth, non-smooth, and strongly convex minimization. The technique builds upon a certain variant of the conjugate gradient method to construct a family of methods such that a) all methods in the family share the same worst-case guarantee as the base conjugate gradient method, and b) the family includes a fixed-step first-order method. We demonstrate the effectiveness of the approach by deriving optimal methods for the smooth and non-smooth cases, including new methods that forego knowledge of the problem parameters at the cost of a one-dimensional line search per iteration, and a universal method for the union of these classes that requires a three-dimensional search per iteration. In the strongly convex case, we show how numerical tools can be used to perform the construction, and show that the resulting method offers an improved worst-case bound compared to Nesterov's celebrated fast gradient method.
BibTeX
@inproceedings{drori2020efficient,
  author = {Yoel Drori and Adrien B. Taylor},
  title = {{Efficient first-order methods for convex minimization: a constructive approach}},
  booktitle = {Math. Program},
  year = {2020},
  url = {https://openreview.net/forum?id=zVezanVNzr},
}
Figure