Safeguarded Learned Convex Optimization

Howard Heaton, Xiaohan Chen, Zhangyang Wang, Wotao Yin

Learned optimization (L2O) algorithms offer significant speedups over classical iterative methods but often lack rigorous convergence guarantees, especially when faced with out-of-distribution (OOD) data. This paper introduces Safe-L2O, a framework that wraps L2O algorithms in a mathematical safeguard to ensure reliability without sacrificing performance.

The Problem: The Safety Gap in Optimization

Optimization algorithms are fundamental to modern scientific computing, powering applications from medical imaging to logistics. Traditionally, practitioners have faced a trade-off between two paradigms:

  1. Analytic Algorithms (e.g., ISTA, ADMM): These hand-designed methods are mathematically guaranteed to converge but are often computationally slow.
  2. Learned Optimization (L2O): These methods use neural networks (like LISTA or ALISTA) to learn efficient update rules. While they can be up to 20x faster than analytic methods, they are "black boxes" that may diverge when encountering data different from their training set.

The "safety gap" refers to this lack of theoretical reliability. Safe-L2O addresses this by providing a framework where speed does not come at the cost of convergence guarantees.

The Safe-L2O Framework

The Safe-L2O framework acts as a supervisor for the L2O process using a conditional update logic. At each step, the L2O model proposes a "shortcut" update. A Safeguard then checks if this update is "good" based on a fixed-point residual. If the update is accepted, the algorithm proceeds; if it is rejected (e.g., due to divergence), the algorithm performs a Fallback Update using a classical, guaranteed analytic method.

Technical Innovation: Non-Monotonic Safeguarding

L2O algorithms often take non-monotonic paths, meaning the error might temporarily increase to reach a better solution later. Safe-L2O's safeguard is specifically designed to allow this behavior by using a "trailing behavior" approach. It maintains a reference value that decreases over time, ensuring overall progress without being overly restrictive. The authors explored several schemes for this threshold, finding an Exponential Moving Average (EMA) approach to be the most practical.

Experimental Validation

The researchers evaluated Safe-L2O on benchmarks including synthetic LASSO problems and natural image denoising using the BSD500 dataset. A key focus was robustness in out-of-distribution (OOD) scenarios.

Figure 1: Performance of ALISTA vs. Safe-L2O on seen and unseen distributions. On seen data (a), ALISTA is highly efficient. On unseen data (b), ALISTA diverges, but Safe-L2O's safeguard (indicated by spikes in activation) ensures convergence.

As shown in Figure 1, standard L2O models like ALISTA can diverge significantly when encountering OOD data. Safe-L2O successfully detects these failures. The "spike in safeguard activations" in Figure 1b corresponds to points where the L2O update performed poorly, triggering the fallback mechanism to bring the error back down immediately.

Figure 2: Performance of LISTA vs. Safe-L2O. Similar to ALISTA, the standard LISTA model fails on unseen distributions, while Safe-L2O maintains convergence through its fallback mechanism.

Key Results and Insights

  • Guaranteed Convergence: By utilizing "averaged operators" from fixed-point theory as fallbacks, Safe-L2O is mathematically proven to always converge to the true solution.
  • Zero Overhead on "Seen" Data: On data similar to the training set, the safeguard rarely triggers, allowing the system to maintain the ~10-20x speedup of L2O with negligible penalty.
  • Infinite Iterations: Unlike standard L2O models limited by their fixed number of layers, Safe-L2O can run for an arbitrary number of iterations by transitioning to the fallback operator once learned layers are exhausted.

Conclusion and Future Work

Safe-L2O bridges the gap between the speed of deep learning and the reliability of classical optimization. While currently focused on convex problems, it provides a robust template for future work, including extensions to non-convex problems, the development of faster "learned fallbacks," and adaptations for stochastic settings like mini-batch gradient descent.

Summary updated

Abstract

Applications abound in which optimization problems must be repeatedly solved, each time with new (but similar) data. Analytic optimization algorithms can be hand-designed to provably solve these problems in an iterative fashion. On one hand, data-driven algorithms can "learn to optimize" (L2O) with much fewer iterations and similar cost per iteration as general-purpose optimization algorithms. On the other hand, unfortunately, many L2O algorithms lack converge guarantees. To fuse the advantages of these approaches, we present a Safe-L2O framework. Safe-L2O updates incorporate a safeguard to guarantee convergence for convex problems with proximal and/or gradient oracles. The safeguard is simple and computationally cheap to implement, and it is activated only when the data-driven L2O updates would perform poorly or appear to diverge. This yields the numerical benefits of employing machine learning to create rapid L2O algorithms while still guaranteeing convergence. Our numerical examples show convergence of Safe-L2O algorithms, even when the provided data is not from the distribution of training data.
BibTeX
@inproceedings{heaton2023safeguarded,
  author = {Howard Heaton and Xiaohan Chen and Zhangyang Wang and Wotao Yin},
  title = {{Safeguarded Learned Convex Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i6.25950},
}
Figure