PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Optimize: A Primer and A Benchmark

Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, Wotao Yin

arXiv:2103.12828v2math.OCcs.LGstat.ML

TL;DR

L2O addresses the labor of hand-designing optimization methods by learning update rules from training problems. This paper surveys continuous-optimization L2O, benchmarks representative approaches, and releases Open-L2O, finding task-dependent benefits alongside stability, scalability, and generalization limitations.

  • Problem

    L2O lacks a common benchmark and faces limited convergence, scalability, stability, and out-of-distribution guarantees, hindering consistent assessment of learned optimizers.

  • Method

    The paper surveys and categorizes model-free and model-based L2O methods, reviews their training and architectures, and benchmarks representative approaches using Open-L2O.

  • Results

    Across representative tests, L2O benefits are task-dependent: problem-specific structure helps analytic and learned optimizers, while L2O-Swarm achieves significantly better final loss on Rastrigin with n = 10 but converges more slowly.

  • Takeaways & Limitations

    L2O is promising for repeatedly solving related optimization tasks, but practical performance depends on optimizer architecture, problem structure, and training procedure.

  • Takeaways & Limitations

    Current L2O methods have limited stability and generalization: loss variances can grow during neural-network training, and out-of-distribution convergence guarantees remain under-studied.

Abstract

from arXiv · show

Learning to optimize (L2O) is an emerging approach that leverages machine learning to develop optimization methods, aiming at reducing the laborious iterations of hand engineering. It automates the design of an optimization method based on its performance on a set of training problems. This data-driven procedure generates methods that can efficiently solve problems similar to those in the training. In sharp contrast, the typical and traditional designs of optimization methods are theory-driven, so they obtain performance guarantees over the classes of problems specified by the theory. The difference makes L2O suitable for repeatedly solving a certain type of optimization problems over a specific distribution of data, while it typically fails on out-of-distribution problems. The practicality of L2O depends on the type of target optimization, the chosen architecture of the method to learn, and the training procedure. This new paradigm has motivated a community of researchers to explore L2O and report their findings. This article is poised to be the first comprehensive survey and benchmark of L2O for continuous optimization. We set up taxonomies, categorize existing works and research directions, present insights, and identify open challenges. We also benchmarked many existing L2O approaches on a few but representative optimization problems. For reproducible research and fair benchmarking purposes, we released our software implementation and data in the package Open-L2O at https://github.com/VITA-Group/Open-L2O.

1. Introduction

L2O uses machine learning to train optimization methods on sample problems, targeting faster or higher-quality solutions for repeatedly solving related tasks. The paper surveys L2O approaches, develops a benchmark for fair comparison, and releases Open-L2O for reproducible research.

  • 1. Introduction: L2O trains an optimization method from performance on sample problems rather than designing it solely from optimization theory.Its offline training process learns parameters and update rules from optimizees representing a target task distribution.
  • 1. Introduction: L2O is suited to repeatedly solving similar optimization problems drawn from a narrow task distribution.Learned optimizers are trained on sample optimizees and applied online to new optimizees assumed to come from the same distribution.
  • 1. Introduction: L2O can improve speed or solution quality on suitable tasks, including sparse-signal recovery and compressive sensing.Reported examples include faster convergence than ISTA/FISTA and potentially more faithful recovery than LASSO under similar computing budgets.
  • 1. Introduction: Model-free L2O lacks convergence guarantees and may require many training samples, especially when critical analytic operations must be learned from scratch.Model-based L2O incorporates existing optimization methods to reduce the parameter and algorithm search space.
  • 1. Introduction: The paper distinguishes model-free and model-based L2O, reviews recurrent, unrolling, and plug-and-play methods, and discusses training and structural design choices.It emphasizes how optimizer design can exploit optimizee structure and classic optimization methods.
  • 1. Introduction: The Open-L2O benchmark addresses inconsistent and sometimes unfair comparisons by evaluating existing approaches on representative optimization problems.The authors released software implementation and test cases to support reproducible research and fair benchmarking.

2. Model-Free L2O Approaches

Model-free L2O learns parameterized iterative update rules from sampled optimizees, commonly using recurrent networks such as LSTMs. Its central challenges include limited generalization and the tension between short unrolling, which creates truncation bias, and long unrolling, which destabilizes training.

  • LSTM-based methods: LSTM-based methods implicitly model optimization updates by unrolling recurrent networks and sharing learned parameters across iterative steps.RNNs provide an inductive bias for learning optimization trajectories, while coordinate-wise shared weights reduce memory overhead.
  • Basic workflow: Model-free L2O learns a parameterized iterative update rule from optimizees sampled from a task distribution, then applies it to new optimizees from that distribution.The workflow separates offline meta-training from online meta-testing.
  • Empirical scope: Early L2O studies showed faster convergence than SGD, RMSprop, and Adam on small-scale tasks, but reported underwhelming scalability and generalizability.The cited proof-of-concept studies included MNIST classification.
  • Generalization challenges: Longer training iterations remain difficult because longer LSTM unrolling causes gradient explosion or vanishing and increases the memory bottleneck.Consequently, many LSTM-based methods truncate optimization trajectories, often to limits such as 20 steps.
  • Truncation dilemma: Short unrolling can cause premature termination and truncation bias, while longer unrolling creates optimization difficulty during L2O training.At meta-testing, naively extending an optimizer trained with a small unrolling length can produce instability and poor-quality solutions.
  • Research directions: Follow-up work explores debiasing truncation, stronger hierarchical RNN architectures, enhanced training techniques, and reinforcement-learning-based optimizer discovery.Reported extensions include heavy-tailed unroll lengths, MLP optimizers, three-scale RNNs, analytic-optimizer imitation, and transfer across tasks and architectures.

3. Model-Based L2O Approaches

Model-based L2O combines optimization-inspired update structures with learnable components, spanning Plug-and-Play and algorithm-unrolling approaches. These methods trade general-purpose flexibility for compact, interpretable, and data-efficient architectures when an optimization model is available or inferable.

  • Overview: Model-based L2O fuses traditional optimization algorithms with deep learning architectures by learning update rules inspired by analytic methods.These approaches replace general-purpose recurrent architectures with learnable structures tied to optimization algorithms.
  • Design trade-offs: Model-based L2O is a semi-parameterized design that balances model-based priors with data-driven learning capacity.The approach is described as compact, data-efficient, interpretable, and high-performance when the underlying optimization model is available or partially inferred.
  • Plug and Play: Plug-and-Play inserts a pretrained neural network into part of an optimization update and applies the modified algorithm without additional training.The neural network can replace an analytic expression such as a proximal operator.
  • Algorithm Unrolling: Algorithm unrolling truncates an iterative optimization algorithm into a neural network whose updates use learnable parameters at each iteration.The update is written as xk+1 = T(xk; θk), with layers corresponding to algorithm iterations.
  • Training: Unrolled schemes train parameters end-to-end through the final iterate xK, unlike Plug-and-Play methods whose parameters are trained separately.The training loss is applied to xK as a function of all layer parameters θk.

3.1 Plug and Play

Plug-and-Play methods replace analytic optimization components with pretrained or learned operators, enabling immediate application and later extensions that learn operators, regularizers, or parameters. Their empirical success has also motivated convergence analyses under conditions such as Lipschitz continuity.

  • Core approach: Plug-and-Play methods replace an analytic proximal operator with a pretrained denoiser or neural network inside an optimization algorithm.The original PnP formulation replaces the proximal for g with an operator Hθ.
  • Learned operators: Learned PnP methods model the proximal operator as a deep neural network and learn it from data instead of manually designing a denoiser.The surveyed works report empirical performance exceeding prior PnP methods.
  • Learned regularizers: PnP can learn a regularizing functional, such as an image-distribution model represented by a differentiable denoising autoencoder.The differentiability enables solving the inverse problem with gradient-based optimization.
  • Parameter learning: Reinforcement learning can tune PnP parameters, producing results comparable to oracle parameters tuned with inaccessible ground truth.A learned policy network guides the optimization without access to the ground-truth-tuned parameters.
  • Theory: PnP convergence can be guaranteed under conditions such as a Lipschitz constraint on the denoiser.A normalization method was proposed for training deep-learning-based denoisers to meet convergence-related conditions.

3.2 Algorithm Unrolling

Algorithm unrolling converts truncated iterative algorithms into trainable networks for objective minimization, signal recovery, and downstream tasks. The literature concentrates on first-order methods and sparse or low-rank problems while extending to graphical models, PDEs, quadratic optimization, and constraints.

  • Goals: Unrolled L2O methods pursue either objective minimization or signal recovery, with inverse problems emphasizing reconstruction accuracy rather than objective minimization.For objective minimization, the practical goal is to accelerate convergence.
  • Scope: The surveyed works are organized by problem type, unrolled algorithm, optimization goal, and degree of parameterization in the learned update rule.The review covers probabilistic graphical models, sparse and low-rank regression, differential equations, and quadratic optimization.
  • Sparse and low-rank regression: Sparse regression is the most investigated unrolling area, including ISTA-based LASSO methods, group LASSO, convolutional LASSO, and related variants.The unrolling philosophy also extends to low-rank regression because of shared structural properties.
  • Sparse and low-rank regression: Unrolling also covers analysis sparsity, ℓ0 and ℓ∞ minimization, anti-sparse representations, and low-rank matrix factorization.Specialized pursuit architectures can address robust PCA and non-negative matrix factorization while avoiding expensive SVD operations per iteration.
  • Other problem settings: Unrolling extends beyond regression to probabilistic graphical models, PDE evolution, quadratic optimization, constrained optimization, and downstream clustering or classification.Downstream tasks may evaluate end-task output rather than the fidelity of the original unrolled algorithm output.
  • Inverse problems: Inverse-problem objectives are used because manually designed regularizers such as sparsity and total variation only approximate the complexity of natural signals.Consequently, many methods target direct recovery of the original signals of interest.
  • Algorithms: Most unrolled algorithms are forward-backward splitting, primal-dual, or other methods, with the first two categories consisting entirely of first-order algorithms.Their low computational complexity and relatively reliable training help explain the emphasis on these categories.

3.3 Applications

Model-based L2O has been applied across image, medical, wireless, seismic, and other domains. Applications typically adapt optimization-inspired updates or learned operators to domain-specific reconstruction, estimation, detection, and prediction tasks.

  • Image restoration and reconstruction: Unrolled and Plug-and-Play methods are widely used for image denoising, deblurring, super-resolution, inpainting, and compressive sensing.These applications cover image restoration, enhancement, and reconstruction.
  • Medical and biological imaging: Medical and biological imaging uses model-based L2O for accurate MRI and CT reconstruction from as few measurements as possible.These settings also pose challenges for extending natural-image methods to complex-valued imaging data.
  • Wireless communication: Wireless applications include resource management, channel estimation, signal detection, and LDPC coding.MIMO detection can be formulated as sparse recovery and addressed by deep unfolding with trainable parameters.
  • Seismic imaging: Seismic imaging often uses Plug-and-Play methods that integrate data-trained CNN projectors into classic iterative updates.This design preserves emphasis on physical modeling while learning the projector from data.
  • Miscellaneous applications: Other applications include clustering, classification, phase retrieval, RNA structure prediction, speech recognition, source separation, remote sensing, smart grids, graph recovery, and photometric stereo.The surveyed application areas extend beyond image reconstruction and communications.

3.4 Theoretical Efforts

Theoretical work on L2O remains limited because black-box training complicates analysis, although model-based methods connect more readily to classic optimization tools. Existing efforts address capacity, convergence, out-of-distribution safeguards, generalization, stability, and interpretability, while trainability remains especially underdeveloped.

  • Black-box training limits L2O theory and makes its broader usability questionable, whereas model-based structures offer more opportunities for theoretical analysis.
  • Capacity and interpretability are partially addressed, generalization is receiving increasing attention, and trainability has very limited theory because L2O training is highly nonconvex.
  • Capacity: Capacity studies characterize L2O through approximation or convergence, including LISTA rates reported as better than classic ISTA/FISTA.Other work improves LISTA theory by designing model operators, while differentiable linearized ADMM has also been analyzed for convergence rates.
  • Capacity: Safeguard mechanisms can support convergence on out-of-distribution inputs by rejecting tentative L2O updates that fail an energy-reduction test and applying a classic fallback update.The overall algorithm converges because the energy is monotonically decreasing.
  • Interpretability: Interpretability efforts connect L2O behavior to analytic optimization algorithms, including analyses of unrolled IHT and LISTA mechanisms.
  • Generalization: Generalization research studies interpolation, extrapolation, generalization gaps, Rademacher complexity, and stability with respect to inputs or model parameters.One result bounds generalization as a function of model depth, reflecting a capacity–generalization trade-off in unrolled models.

4. The Open-L2O Benchmark

The Open-L2O benchmark compares model-based and model-free learned optimizers with analytic methods across sparse recovery, Lasso, Rastrigin minimization, and neural-network training. Results favor problem-specific model-based L2O on structured tasks, while model-free gains are inconsistent and stability or generalization can degrade.

  • Benchmark design: The benchmark addresses inconsistent and sometimes unfair comparisons by evaluating diverse L2O methods on representative optimization tasks.The testbed includes convex sparse optimization, nonconvex Rastrigin minimization, and neural-network training.
  • Sparse recovery: Model-based L2O performs strongly on sparse recovery, with different methods leading under noiseless, noisy, coherent-dictionary, and larger-scale settings.ALISTA leads in noiseless and larger-scale settings, GLISTA leads under noise and dictionary coherence, while LAMP degrades severely under noise.
  • Lasso: On Lasso, 16-layer ISTA and ALISTA reach FISTA-level precision far sooner than analytic baselines, while model-free methods generally converge more slowly or fail.At larger problem size, LISTA and ALISTA retain high-precision convergence in 16 iterations, whereas most model-free methods remain poor.
  • Overall findings: Across tests, model-based L2O is more reliable when problem structure is available, whereas model-free advantages are inconsistent and testing stability worsens with scale or iterations.All L2O optimizers show larger loss variances as training iterations grow, and no model-free method consistently wins across tests.
  • Rastrigin minimization: On Rastrigin functions, most model-free L2O methods match analytic optimizers, but L2O-Swarm finds lower-loss solutions at higher search cost.For n = 10, L2O-Swarm achieves significantly better final loss while converging more slowly than most alternatives.
  • Neural-network training: On neural-network training, L2O transferability varies: L2O-enhanced performs best after extended training, while other learned optimizers struggle on ConvNets.L2O-Scale and L2O-RNNprop generalize to ReLU-MLP but cannot effectively optimize ConvNet; L2O-DM diverges on ConvNet.

5. Concluding Remarks

The paper surveys L2O and benchmarks its emerging methods, finding substantial promise alongside unresolved theoretical, scalability, generalization, and deployment challenges.

  • The article presents a panoramic review of L2O state of the art alongside a first-of-its-kind benchmark.
  • Open challenges: Theoretical foundations remain limited, especially for model-free training convergence and generalization beyond the task distribution.
  • Open challenges: Model-free L2O faces scalability hurdles for larger models, more complicated models, and more meta-testing iterations.
  • Open challenges: Model-specific L2O has shown empirical success mainly in special inverse-problem and sparse-optimization instances requiring case-by-case modeling.
  • Research opportunities: Unrolled networks occupy an intermediate position between generic networks and analytic algorithms and might be more data-efficient to learn.
  • Deployment status: The approaches discussed remain exploratory and are not yet ready as general-purpose or commercial solvers.

Appendix A. List of Abbreviations

The appendix defines abbreviations used throughout the paper, covering optimization methods, machine-learning architectures, and broader automation frameworks.

  • ADMM means Alternating Direction Method of Multipliers, an algorithm that decomposes convex problems into smaller subproblems.
  • HPO means Hyperparameter Optimization, the problem of choosing optimal hyperparameters for a machine-learning algorithm.
  • L2O means Learning to Optimize: learnable optimizers predict update rules for optimizees fit from data.
  • LSTM means Long-short Term Memory, a recurrent neural-network architecture typically used to process sequence data.
  • MLP means Multi-layer Perceptron, a feedforward neural network composed of multiple perceptron layers.
  • PGD means Projected Gradient Descent, which minimizes a constrained function by taking gradient steps and projecting onto the feasible set.
Loading 2103.12828v2…