Safeguarded Learned Convex Optimization

Howard Heaton, Xiaohan Chen, Zhangyang Wang, Wotao Yin

Introduction

In the field of optimization, practitioners often face a trade-off between speed and safety. Classical analytic algorithms, such as the Iterative Soft-Thresholding Algorithm (ISTA), are "safe" because they come with mathematical proofs of convergence. However, they are often slow, requiring thousands of iterations. Conversely, "Learning to Optimize" (L2O) methods use neural networks to learn high-speed "shortcuts" for specific problems. While fast, these models are "black boxes" that can diverge wildly when encountering data different from their training set (distribution shift).

This paper introduces Safe-L2O, a framework that combines the lightning-fast performance of L2O with the rigorous guarantees of classical optimization. By wrapping L2O updates in a mathematical "safeguard," the algorithm ensures convergence even on data far outside the training distribution.

The Safe-L2O Framework

Safe-L2O acts as a supervisor for any L2O neural network through three core mechanisms:

  • The Safeguard Condition: At each iteration, the framework checks a tentative L2O update by measuring its fixed-point residual. This determines if the update is making reasonable progress toward a solution.
  • The Fallback Mechanism: If an update is deemed "bad" or diverging, the framework rejects it and performs a "Fallback Update" using a classical, proven analytic operator.
  • Non-Monotonic Flexibility: Crucially, the safeguard allows for "trailing" behavior. It doesn't require the error to drop at every single step, allowing the neural network the flexibility to take non-monotonic shortcuts that lead to a faster overall solution.

Experimental Evaluation

The researchers evaluated Safe-L2O across several distinct problem types, including Synthetic LASSO (testing the ALISTA variant), Natural Image Denoising on the BSD500 dataset, and problems with varying dictionaries. They specifically focused on performance under "distribution shift"—where the test data differs significantly from the training data.

Key Results and Robustness

The primary strength of Safe-L2O is its ability to maintain performance on familiar data while preventing catastrophic failure on new data.

Performance of ALISTA vs. Safe-L2O on seen and unseen data distributions.

As illustrated in Figure 3(a), on "seen" data, the safeguard rarely triggers, allowing the algorithm to maintain the full ~20x speedup of the underlying L2O model compared to ISTA. However, as shown in Figure 3(b), when faced with "unseen" data, standard L2O models like ALISTA can see their relative error explode to $10^6$. Safe-L2O (the blue line) successfully detects these instabilities, activating the safeguard to steer the error back down and ensure convergence.

Conclusion

Safe-L2O demonstrates that learned optimizers do not have to be unreliable. By treating L2O as a shortcut generator rather than a replacement for optimization theory, the framework provides a path toward deploying high-performance neural optimizers in critical applications. Future work will look into extending this deterministic framework to the stochastic settings common in training massive machine learning models.

Summary updated

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