Research map / Optimization / Optimizers

A Generalization Result for Convergence in Learning-to-Optimize

ICML 2025 · Optimization › Optimizers · approach: Differentiating through embedded optimization · 0 citations (OpenAlex)

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.

Proves a PAC-Bayesian generalization bound for convergence to critical points of learned optimization algorithms on possibly non-smooth non-convex losses, using sufficient-descent and relative-error conditions plus Kurdyka-Łojasiewicz theory.

Problem

Convergence guarantees for learning-to-optimize algorithms are hard to obtain because convergence is a tail event that cannot be observed on finite training trajectories, and existing approaches restrict the learned update via safeguards.

Approach

Encode the abstract convergence conditions (sufficient descent, relative error, boundedness) as measurable sets in parameter-trajectory space, then transfer the probability of satisfying them to unseen problems via a PAC-Bayesian bound, yielding a high-probability lower bound on the convergence probability without restricting the learned update.

Key results

• On quadratic problems, the PAC-bound guarantees convergence of the learned algorithm on about 75% of test problems, with the learned algorithm clearly outperforming HBF.
• On neural network training, the PAC-bound guarantees the learned algorithm converges to a critical point in about 92% of problems and minimizes the loss faster than Adam.
• The PAC-bound is tight for the event of sufficient descent plus relative error plus boundedness, with a gap to the full convergence event.

Measured effects reported in the paper

Surprising findings

• Sufficient descent alone is not sufficient for convergence to a critical point, as shown by counterexamples (a common misconception).

Limitations

• Only finite trajectory prefixes can be checked during training, so conditions are verified only up to a fixed number of iterations.
• The continuity condition cannot be checked in practice and must be assumed via continuity of the loss.
• Training learned algorithms to satisfy the conditions on most problems is difficult and time-consuming; not well suited to stochastic optimization as stated.

Experimental setup

Datasets: synthetic quadratic problems (d=200) synthetic polynomial regression datasets

Benchmarks: synthetic quadratic minimization neural network training on synthetic regression

Metrics: distance to minimizer loss estimated probability of event A PAC-bound on convergence probability

Baselines: Heavy-ball with friction (HBF) Adam

Builds on: PAC-Bayesian generalization theorem (Rivasplata et al.) Attouch-Bolte-Svaiter abstract convergence theorem Heavy-ball with friction Adam

Closest papers by meaning

• A Solver-Free Training Method for Predict-then-Optimize (ICML 2026 · similarity 0.88)
• Sharper Generalization Bounds for Learning with Gradient-dominated Objective Functions (ICLR 2021 · similarity 0.88)
• Safeguarded Learned Convex Optimization (AAAI 2023 · similarity 0.88)
• Solver-Free Decision-Focused Learning for Linear Optimization Problems (NeurIPS 2025 · similarity 0.86)
• Random Function Descent (NeurIPS 2024 · similarity 0.86)
• The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.86)