Research map / Bandits and online learning / Online convex optimization and games
Fully Unconstrained Online Learning
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 a parameter-free online linear optimization algorithm on the real line (and via reductions, general domains) whose regret matches the optimal G||w*||sqrt(T) up to logs plus lower-order G^2 and ||w*||^2 terms, without knowing G or ||w*||.
Problem
Online convex optimization where neither the comparator norm ||w_star|| nor the gradient magnitude bound G is known in advance; the goal is near-optimal regret G||w_star||sqrt(T) without any such prior knowledge.
Approach
Replace explicit domain constraints on the iterates with a tiny, carefully scheduled quadratic regularizer a_t w^2 whose coefficients are tied to the increase of magnitude hints (h_{t+1}-h_t), so the regularizer softly bounds |w_t| and the clipping error becomes small; combined with an epigraph reformulation and a coordinate-wise base learner, this yields a fully unconstrained bound with only a qu
Key results
- Achieves regret G||w_star||sqrt(T log(||w_star|| G sqrt(T))) + ||w_star||^2 + G^2 on G-Lipschitz losses without knowing G or ||w_star||, matching the known-parameter optimum up to logs.
- Matching lower bound shows the extra penalty of order G^2/gamma + gamma||w_star||^2 is unavoidable within the class of algorithms considered, up to log factors.
- Price of adaptivity for stochastic convex optimization of order tilde O(1+max(L,R)/sqrt(T)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a fully unconstrained algorithm that does not require prior bounds on gradient magnitude or comparator norm | Online learning with G-Lipschitz convex losses · Fully unconstrained OLO | regret bound: G\|w_\star\|\sqrt{T\log(\|w_\star\|G\sqrt{T})} + \|w_\star\|^2 + G^2 | Helped |
| Use the new quadratic-gradient-dependence bound instead of the prior compromise bound | Fully unconstrained online learning · Fully unconstrained OLO | regret-bound behavior | Mixed |
| Use ψ(w)=\|w\|^{1+q} instead of ψ(w)=\|w\|^2 (ablation) | Fully Unconstrained Online Learning · Fully unconstrained OLO | regret bound: \frac{G^{1+1/q}}{\gamma^{1/q}}\log\left(1+\log\left(\frac{G}{h_1}\right)\right)^{1/q} | Mixed |
Surprising findings
- A very small quadratic regularizer, with coefficients chosen from magnitude-hint increments, suffices to avoid explicit norm constraints and their known-parameter requirement.
- Lower bound in the paper applies only to algorithms that depend linearly on max gradient magnitude, so a quadratic dependence sidesteps it.
Limitations
- Bound depends on G/h_1 (range-ratio problem) through logarithmic terms.
- Stochastic price of adaptivity has a gap versus the best known lower bound.
- Lower bound leaves G and ||w_star|| dependent on the algorithm, not for arbitrary G and ||w_star||.
Experimental setup
Metrics: regret bound
Baselines: prior fully unconstrained compromise bound (Cutkosky 2019-style) SGD with known G and ||w_star||
Builds on: parameter-free online learning with magnitude hints coin-betting / potential-based unconstrained online learning reduction from general domain to one dimension (Cutkosky and Orabona style) online-to-batch conversion
Closest papers by meaning
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.88)
- Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound (NeurIPS 2025 · similarity 0.88)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · similarity 0.87)
- Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability (ICML 2025 · similarity 0.87)
- Cumulative Regret Analysis of the Piyavskii–Shubert Algorithm and Its Variants for Global Optimization (AAAI 2024 · similarity 0.87)
- Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences (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.