Research map / Optimization / Nonconvex and smooth optimization
Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality
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 optimistic online-to-batch conversions that build optimism into the analysis, yielding optimal accelerated rates for convex and strongly convex smooth optimization and a universal variant needing one gradient query per iteration.
Problem
Understanding and achieving accelerated convergence (O(T^-2) for convex smooth, optimal linear rate for strongly convex smooth) via online-to-batch conversion, plus universality to smoothness with one gradient query per iteration.
Approach
Replace the stabilized O2B conversion with an optimistic conversion that inserts optimism directly into the convergence analysis, so plain online gradient descent with look-ahead regret (querying the gradient at a lookahead average) recovers NAG-type acceleration; the universal variant uses self-confident step sizes and a Bregman-based identity to need only one gradient per iteration.
Key results
- Optimistic conversion with online gradient descent (weights alpha_t=t, eta=1/(4L)) achieves f(x_T)-f* <= O(L||x_0-x*||^2/T^2) for unconstrained convex smooth objectives.
- For strongly convex smooth objectives, the method achieves f(x_T)-f* <= O(lambda||x_1-x*||^2 exp(-(T-1)/(1+2 sqrt(kappa)))), the first optimal accelerated rate via O2B conversion.
- The universal variant with one gradient query per iteration attains O(LD^2/T^2) for smooth and O(GD/sqrt(T)) for non-smooth convex objectives.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use optimistic O2B with simple online gradient descent and weights α_t = t | Convex smooth optimization · Convex smooth optimization (unconstrained) | suboptimality gap: O(L ||x_0 - x_s||^2 / T^2) | Helped |
| Combine optimistic O2B with one-step optimistic online gradient descent | Strongly convex and smooth optimization · Strongly convex and smooth optimization (unconstrained) | suboptimality gap: O[λ ||x_1 - x_s||^2 · exp[-(T-1)/(1+2√κ)]] | Helped |
| Use an AdaGrad-type step size based on successive gradients at xt, with α_T = 0, instead of the two-gradient universal conversion | Optimistic O2B + online gradient descent · Convex smooth optimization (bounded domain) | suboptimality gap: O(LD^2/T^2) | No clear effect |
| Use an AdaGrad-type step size based on successive gradients at xt, with α_T = 0, instead of the two-gradient universal conversion | Optimistic O2B + online gradient descent · Convex non-smooth optimization (bounded domain) | suboptimality gap: O(GD/√T) | No clear effect |
Surprising findings
- Optimal accelerated rates are achieved with plain online gradient descent once optimism is placed in the conversion analysis, without an optimistic online algorithm.
Limitations
- Universal result requires a bounded feasible domain; unconstrained universal accelerated case is open.
- Requires knowing total iteration count T to set alpha_T=0.
- Universal optimal rate for strongly convex objectives remains open.
Experimental setup
Datasets: LIBSVM
Benchmarks: LIBSVM squared loss minimization LIBSVM logistic regression
Metrics: suboptimality gap / convergence performance
Baselines: Nesterov's accelerated gradient gradient descent UniXGrad stabilized online-to-batch conversion method
Builds on: online-to-batch conversion stabilized online-to-batch conversion optimistic online learning Nesterov's accelerated gradient AdaGrad
Closest papers by meaning
- A simpler approach to accelerated optimization: iterative averaging meets optimism (ICML 2020 · similarity 0.92)
- Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness (NeurIPS 2025 · similarity 0.91)
- Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization (NeurIPS 2025 · similarity 0.88)
- General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization (ICML 2025 · similarity 0.88)
- Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent (ICML 2025 · similarity 0.87)
- From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization (NeurIPS 2026 · similarity 0.87)
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.