Optimal Complexity and Certification of Bregman First-Order Methods.

Radu-Alexandru Dragomir, Adrien Taylor, Alexandre d'Aspremont, Jérôme BolteMath. Program 2019 · DOI · OpenReview

TL;DR

This paper proves that the standard Bregman gradient method (NoLips) achieves an optimal convergence rate of $O(1/k)$ for a broad class of "relatively-smooth" optimization problems. This optimality implies that generic acceleration of these methods is impossible without stronger assumptions, settling a long-standing open question. The authors achieve this by extending the powerful "performance estimation problem" (PEP) framework to Bregman methods, enabling them to construct worst-case scenarios.

What Problem Does This Paper Address?

First-order optimization methods are crucial for large-scale problems due to their simplicity. While standard gradient descent has well-understood convergence rates, its generalization to non-Euclidean geometries via Bregman methods has been an active research area. A key question was whether these Bregman methods could be accelerated, similar to how Nesterov's accelerated gradient method speeds up Euclidean gradient descent. The "relative smoothness" assumption, which generalizes L-smoothness, has emerged as a natural framework for analyzing Bregman methods. However, it was unclear if acceleration was possible in this general setting, or if the $O(1/k)$ rate of the basic Bregman gradient (NoLips) was already optimal. This paper tackles this question by providing a theoretical lower bound on the convergence rate for any Bregman first-order method under the relative smoothness assumption.

Methods

The core of the paper's contribution lies in two main areas:

  1. Performance Estimation Problems (PEPs): The authors extend the PEP framework, originally developed for Euclidean settings, to analyze Bregman first-order methods. PEPs are a powerful tool that reformulates the problem of finding the worst-case convergence rate of an algorithm into a convex optimization problem (specifically, a semidefinite program or SDP). By solving these SDPs, one can derive both worst-case functions and theoretical convergence bounds.
  2. Worst-Case Function Construction: Using the PEP framework, the authors construct specific, "pathological" functions that are difficult for any Bregman first-order method to optimize. These functions are designed to expose the limitations of the algorithms, forcing them to explore only one dimension at a time. The analysis of these worst-case functions leads to the proof of the lower bound.

The paper also formalizes a class of "Bregman first-order algorithms" (Definition 4) that encompasses NoLips and other related methods, defining the oracle model and the allowed operations.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and worst-case scenario construction rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Optimality of NoLips: The most significant insight is the proof that the $O(1/k)$ convergence rate of the NoLips algorithm is optimal for the general relatively-smooth setting. This means that no Bregman first-order method can achieve a better guaranteed convergence rate for this class of problems without additional assumptions.
  • Impossibility of Generic Acceleration: This optimality result directly implies that generic acceleration of Bregman methods, in the same way as for Euclidean gradient descent, is not possible in the relatively-smooth setting. Acceleration would require stronger assumptions on the objective function or the kernel.
  • Power of PEPs for Bregman Methods: The paper demonstrates the effectiveness of the PEP framework for analyzing Bregman methods, extending its applicability beyond standard smooth convex optimization. This opens doors for analyzing other Bregman-based algorithms.
  • Worst-Case Functions as Limits of Smooth Functions: The construction of worst-case functions involves creating smooth approximations of nonsmooth, "pathological" functions. This technique highlights how the worst-case behavior for algorithms operating on open sets (like differentiable functions) can be found at the boundary of those sets, i.e., in nonsmooth functions.

Key Results

  • Lower Bound: The paper establishes a lower bound of $\Omega(1/N)$ for the convergence rate of any Bregman first-order method on relatively-smooth problems, where $N$ is the number of oracle calls. This matches the upper bound achieved by NoLips, proving its optimality.
  • Worst-Case Functions: The authors construct specific worst-case functions that are relatively-smooth and demonstrate the $O(1/k)$ lower bound. These functions are derived from numerical solutions to performance estimation problems.
  • Extension of PEPs: The paper provides a detailed framework for applying PEPs to Bregman methods, including interpolation conditions for differentiable and strictly convex functions.

Limitations and Future Work

  • Limitations:
    • The lower bound is established for a specific class of algorithms (Bregman first-order algorithms) that rely on primal and mirror oracles. Algorithms using more advanced oracles (e.g., second-order information for the kernel) might achieve better rates.
  • The paper focuses on the $O(1/k)$ convergence rate for function values. While other criteria are briefly explored (e.g., stationarity measure), the primary focus is on this rate.
  • The analysis of inertial Bregman algorithms suggests that they might fail to converge in the general relatively-smooth setting, which is a strong negative result but based on numerical evidence and conjecture rather than a formal proof for all inertial variants.
  • Future Work:
    • Weaker Assumptions: The paper suggests exploring weaker assumptions than relative smoothness that could still allow for improved convergence rates or acceleration.
  • Different Algorithm Classes: Investigating algorithms that do not fit the current oracle model, such as those using second-order information for the kernel, is a promising direction.
  • Understanding Inertial Methods: Further theoretical work is needed to formally prove or disprove the conjecture about the failure of inertial Bregman methods in the general setting.
  • Connections to Other Methods: Exploring connections between Bregman methods and other optimization paradigms, like conditional gradient methods, could yield new insights.

Summary updated

Abstract

We provide a lower bound showing that the $O(1/k)$ convergence rate of the NoLips method (a.k.a. Bregman Gradient) is optimal for the class of functions satisfying the $h$-smoothness assumption. This assumption, also known as relative smoothness, appeared in the recent developments around the Bregman Gradient method, where acceleration remained an open issue. On the way, we show how to constructively obtain the corresponding worst-case functions by extending the computer-assisted performance estimation framework of Drori and Teboulle (Mathematical Programming, 2014) to Bregman first-order methods, and to handle the classes of differentiable and strictly convex functions.
BibTeX
@inproceedings{dragomir2019optimal,
  author = {Radu-Alexandru Dragomir and Adrien Taylor and Alexandre d'Aspremont and Jérôme Bolte},
  title = {{Optimal Complexity and Certification of Bregman First-Order Methods.}},
  booktitle = {Math. Program},
  year = {2019},
  doi = {10.1007/s10107-021-01618-1},
}
Figure