Proximal Gradient Algorithms under Local Lipschitz Gradient Continuity: A Convergence and Robustness Analysis of PANOC

Alberto De Marchi, Andreas Themelis

TL;DR

This paper introduces PANOC+, an improved version of the PANOC algorithm for solving complex, non-convex optimization problems. PANOC+ offers more robust convergence guarantees, especially when the smooth part of the problem is only locally Lipschitz continuous, and handles inexact computations more effectively, making it a more practical tool for real-world applications.

What Problem Does This Paper Address?

Many real-world problems, from control systems to machine learning, can be modeled as minimizing a sum of a smooth and a non-smooth function. While proximal gradient (PG) methods are well-suited for these problems, they often struggle with non-convexity and require strong assumptions like global Lipschitz continuity of the smooth function's gradient. Existing accelerated methods like PANOC have limitations, particularly when this global Lipschitz assumption is violated, leading to poor performance or divergence. This paper addresses the challenge of developing robust optimization algorithms that can handle non-convex problems with only local Lipschitz continuity and can tolerate inexact computations, which are common in practical scenarios.

Methods

The paper introduces PANOC+, an enhanced version of the PANOC algorithm. The core innovation lies in a "good" adaptive stepsize selection rule. Unlike the original PANOC's "bad" adaptive rule, PANOC+ tightly intertwines two linesearch steps: one for the update direction and another for the proximal gradient stepsize. This entanglement allows the algorithm to better capture the problem's geometry and adapt to local Lipschitz continuity. The authors also extend the analysis to handle inexact proximal mapping computations, meaning the subproblem doesn't need to be solved perfectly. This is achieved by introducing a "suboptimal prox step" criterion. The theoretical framework is built upon the Forward-Backward Envelope (FBE) as a merit function for globalizing convergence.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses illustrative example problems for demonstration rather than large-scale datasets.

Key Insights and Ideas

  • Local Lipschitz is Enough: The most significant insight is demonstrating that robust convergence guarantees for accelerated methods like PANOC can be achieved even when the smooth function's gradient is only locally Lipschitz continuous, a much weaker and more realistic assumption than global Lipschitz continuity.
  • Intertwined Linesearch is Crucial: The "good" adaptive stepsize rule in PANOC+ is key. By tightly coupling the linesearch for the update direction and the proximal stepsize, the algorithm avoids the asynchrony that plagued the original PANOC, leading to better performance and robustness.
  • Inexactness is Manageable: The paper shows that PANOC+ can effectively handle inexact proximal mapping computations, a common scenario in practice where solving subproblems perfectly is computationally prohibitive. This significantly broadens its applicability.
  • FBE as a Universal Tool: The Forward-Backward Envelope (FBE) continues to be a powerful tool for analyzing and globalizing the convergence of these complex optimization algorithms.

Key Results

  • Theoretical Guarantees: The paper provides theoretical convergence guarantees for PANOC+ under local Lipschitz continuity and with inexact proximal computations.
  • Robustness Demonstrated: Through illustrative examples, the authors show that the original PANOC can diverge or perform poorly when its assumptions are violated, while PANOC+ maintains convergence and better performance.
  • Improved Practicality: The findings suggest that PANOC+ is a more reliable and efficient solver for a wider range of non-convex composite optimization problems, including those encountered in embedded systems and control applications.
  • Finite Termination: The adaptive linesearch procedure in PANOC+ is shown to terminate in finite time, preventing infinite loops.

Limitations and Future Work

  • Computational Cost of Inexactness: While the paper shows theoretical convergence with inexact computations, the practical trade-off between the degree of inexactness and the overall computational cost is not deeply explored.
  • Specific Problem Structures: The analysis is general, but specific problem structures might benefit from tailored algorithms or further theoretical investigation.
  • Future Work: The authors suggest that their findings significantly enlarge the scope of PANOC, both as a standalone tool and as an internal solver for other algorithms like ALM and sequential programming approaches. Further exploration of nonmonotone variants and arbitrary acceleration directions is also implied.

Summary updated

Abstract

Composite optimization offers a powerful modeling tool for a variety of applications and is often numerically solved by means of proximal gradient methods. In this paper, we consider fully nonconvex composite problems under only local Lipschitz gradient continuity for the smooth part of the objective function. We investigate an adaptive scheme for PANOC-type methods (Stella et al. in Proceedings of the IEEE 56th CDC, 1939--1944, 2017), namely accelerated linesearch algorithms requiring only the simple oracle of proximal gradient. While including the classical proximal gradient method, our theoretical results cover a broader class of algorithms and provide convergence guarantees for accelerated methods with possibly inexact computation of the proximal mapping. These findings have also significant practical impact, as they widen scope and performance of existing, and possibly future, general purpose optimization software that invoke PANOC as inner solver.
BibTeX
@article{marchi2022proximal,
  author = {Alberto De Marchi and Andreas Themelis},
  title = {{Proximal Gradient Algorithms under Local Lipschitz Gradient Continuity: A Convergence and Robustness Analysis of PANOC}},
  journal = {Journal of Optimization Theory and Applications},
  year = {2022},
  doi = {10.1007/s10957-022-02048-5},
}
Figure