Research map / Learning theory and algorithms / Prediction and decision losses
Accelerating Optimization via Differentiable Stopping Time
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.
Proposes a differentiable discrete stopping time for iterative optimizers, with a discrete adjoint method to compute its sensitivity, and applies it to learning to optimize and online learning-rate adaptation.
Problem
Minimizing the time to reach a target loss is considered non-differentiable with respect to algorithm hyperparameters, so it is usually handled conceptually or with zeroth-order methods.
Approach
Define a discrete stopping time N_J for forward-Euler discretized ODE optimizers and approximate its sensitivity by implicitly differentiating the stopping condition J(x_N)=ε, with the vector-Jacobian products computed by a discrete adjoint recursion; the approximation error is O(h) relative to the continuous stopping time gradient.
Key results
- The discrete stopping-time sensitivity approximates the continuous gradient with relative error decreasing as O(h), while requiring fewer forward function evaluations than adaptive ODE solvers (NFE ratio <1).
- On logistic regression, L2O-RNNprop with the stopping-time penalty reaches the stopping criterion in hundreds fewer iterations than GD, NAG, and Adam, and generalizes to 4x larger problems.
- Online learning-rate adaptation outperforms HB, NAG-SC, Adagrad and Adam-HD on smooth SVM problems, especially in late convergence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use differentiable stopping-time penalty during L2O-RNNprop training (λ=1) instead of no penalty (λ=0) | L2O-RNNprop · Synthetic logistic regression, d=512, n=256 and d=2048, n=1024 | iterations to stopping criterion | Helped |
| Use differentiable stopping-time-based online learning-rate adaptation | Algorithm (online adaptation) · Smooth SVM, a1a and a2a | function value | Helped |
| Approximate continuous stopping-time gradients with discrete stopping-time sensitivity and the discrete adjoint method | Differentiable discrete stopping time · High-dimensional quadratic optimization, d∈{10²,10³,10⁴} | relative error | Helped |
Limitations
- Forward Euler with a fixed time step may be too coarse; error is O(h).
- Theorem requires smoothness and non-vanishing derivative of criterion along trajectory.
- Sensitivity is an approximation to the continuous stopping time gradient, not exact for the discrete N.
Experimental setup
Datasets: synthetic logistic regression data LIBSVM
Benchmarks: synthetic quadratic optimization synthetic logistic regression LIBSVM smooth SVM (a1a, a2a)
Metrics: relative error of sensitivity NFE ratio function value vs iteration iterations to stopping criterion
Baselines: GD NAG Adam HB NAG-SC Adagrad Adam-HD L2O-DM
Builds on: Neural ODE / torchdiffeq adjoint L2O-DM L2O-RNNprop Adam hypergradient descent
Closest papers by meaning
- Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent Flows (AAAI 2022 · similarity 0.87)
- A simpler approach to accelerated optimization: iterative averaging meets optimism (ICML 2020 · similarity 0.87)
- Scalable Acceleration for Classification-Based Derivative-Free Optimization (AAAI 2025 · similarity 0.86)
- Accelerated last-iterate convergence of Extragradient via power-law stepsizes (NeurIPS 2026 · similarity 0.86)
- Automatic Differentiation of Optimization Algorithms with Time-Varying Updates (ICML 2025 · similarity 0.86)
- Optimal Acceleration for Minimax and Fixed-Point Problems is Not Unique (ICML 2024 · similarity 0.86)
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.