Research map / Optimization / Optimizers
Towards Robust Learning to Optimize with Theoretical Guarantees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives theoretical analysis of learning-to-optimize (L2O) convergence under out-of-distribution shift via a virtual-feature framework, and proposes GO-Math-L2O, a gradient-only Math-L2O model with gradient-based history modeling that reports up to 10x faster OOD convergence.
Problem
Learning-to-optimize models lack theoretical guarantees of convergence and robustness when test problems are out-of-distribution relative to training problems.
Approach
Relates OOD L2O trajectories to InD trajectories through a virtual feature (difference of input features), derives convergence bounds that worsen with feature magnitude, and therefore builds an L2O model whose only input features are gradients and subgradients, shrinking the virtual feature.
Key results
- GO-Math-L2O outperforms all baselines in the InD LASSO regression comparison (Figure 1), with better optimality and faster convergence.
- On real-world OOD LASSO, GO-Math-L2O converges at about 400 iterations while other baselines need 1,000 iterations.
- Under synthetic OOD translation (trigger 2), GO-Math-L2O converges in about 20 steps for t=±10 where L2O-PA fails to converge; the paper claims up to 10x faster convergence in OOD scenarios.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GO-Math-L2O instead of L2O-PA | LASSO Regression · real-world OOD | iterations to converge: 1,000 iterations -> 400 iterations | Helped |
| Use GO-Math-L2O instead of L2O-PA | LASSO Regression · OOD trigger 1 (initial point shifted) | objective convergence | Helped |
| Use GO-Math-L2O instead of L2O-PA | LASSO Regression · OOD trigger 2 (function shifted, t = ±10) | iterations to converge | Helped |
| Use gradient-only input features and gradient-based history modeling | GO-Math-L2O · LASSO Regression, OOD scenarios | convergence: up to 10× convergence speedup | Helped |
Surprising findings
- Theory shows that even with InD-robust L2O, OOD convergence is not guaranteed, and the objective can deteriorate even for convex problems.
Limitations
- No guarantee of global convergence in OOD scenarios according to the theory; the model does not guarantee the convergence conditions and relies on training.
- Experiments limited to synthetic LASSO and logistic regression problems with specific OOD constructions.
- Theoretical results rely on Assumption 1 holding after training, and virtual Jacobian bounds are not explicit.
Experimental setup
Datasets: synthetic LASSO regression problems synthetic logistic regression problems
Benchmarks: LASSO regression (InD) LASSO regression (OOD trigger 1 and trigger 2) logistic regression (appendix)
Metrics: normalized objective gap (F(xk)-F(x*))/F(x*) vs iteration
Baselines: ISTA FISTA Adam AdamHD L2O-DM L2O-RNNprop Ada-LISTA L2O-PA
Builds on: Math-L2O proximal gradient method FISTA Adam
Closest papers by meaning
- Towards Constituting Mathematical Structures for Learning to Optimize (ICML 2023 · similarity 0.90)
- Distributionally Robust Optimization with Bias and Variance Reduction (ICLR 2024 · similarity 0.86)
- Outlier-Robust Distributionally Robust Optimization via Unbalanced Optimal Transport (NeurIPS 2024 · similarity 0.86)
- Learning Provably Improves the Convergence of Gradient Descent (NeurIPS 2025 · similarity 0.85)
- Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimization (AAAI 2024 · similarity 0.85)
- Statistical Properties of Robust Satisficing (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.