Research map / Bandits and online learning / Online convex optimization and games
On the necessity of adaptive regularisation: Optimal anytime online learning on $\boldsymbol{\ell_p}$-balls
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.
Studies online convex optimisation on ℓp-balls (p>2) across high- and low-dimensional regimes, shows adaptive dimension-dependent regularisation makes FTRL anytime optimal, proves fixed separable regularisers cannot be, and shows linear bandit regret is unavoidable in high dimension.
Problem
Optimal regret for online convex optimisation on ℓp-balls (p>2) shifts between high-dimensional (d > T) and low-dimensional (d ≤ T) regimes, and the horizon T is unknown in advance; the question is whether FTRL or OMD with a single fixed regulariser can be anytime optimal.
Approach
FTRL with a time-varying regulariser switching from the uniformly-convex (1/p)||x||_p^p in early high-dimensional rounds to the strongly-convex (1/2)||x||_2^2 after t0 ≈ d achieves anytime optimal regret. The authors prove that for separable regularisers no fixed choice can be optimal in both regimes, so adaptivity is necessary.
Key results
- Adaptive FTRL switching from (1/p)||x||_p^p to (1/2)||x||_2^2 at t0 = 3^{-2p/(p-2)} d achieves R_T ≤ L(2p*T)^{1/p*} for T ≤ t0 and R_T ≤ L sqrt(2T d^{1-2/p}) for T > t0, i.e. anytime optimal up to constants.
- For any separable regulariser psi in the class Psi and any decreasing step-sizes, there are no constants c_h, c_l such that R_T ≤ c_h L T^{1-1/p} for all d > T and R_T ≤ c_l L sqrt(T d^{1-2/p}) for all d ≤ T.
- For linear bandits on the ℓp-ball with p ≥ 1, for sufficiently large d, any algorithm suffers expected pseudo-regret at least LT/80.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Switch regularisation from φₚ to φ₂ at t₀ | FTRL on ℓ_p-balls with unknown horizon · ℓ_p-ball OCO across dimension regimes | regret: L \brb{2 p_\star T}^{1/p_\star} ; L \sqrt{2Td^{1 - 2/p}} | Helped |
| Use fixed φ₂ instead of adaptive regularisation (ablation) | FTRL on ℓ_p-balls · High-dimensional OCO | regret: R_T \geq L \cdot \min\Brb{\frac{T}{16}, \frac{1}{8}\sqrt{T d^{1-2/p}}} | Hurt |
| Use fixed φₚ instead of adaptive regularisation (ablation) | FTRL on ℓ_p-balls · Low-dimensional OCO | regret: L \cdot \min\Brb{\frac{T}{8p}, \frac{T^{1/p_\star}}{8}} | Hurt |
| Replace adaptive regularisation with any fixed separable regulariser (ablation) | FTRL on ℓ_p-balls · OCO across high- and low-dimensional regimes | regret | Hurt |
| Use a fixed ℓ_r^r regulariser with r between 2 and p (ablation) | FTRL on ℓ_p-balls · OCO across dimension regimes | regret | Hurt |
| Use a larger switching threshold t₀ = 2d instead of t₀ = 3^{-2p/(p-2)} d (ablation) | Adaptive FTRL · Transient dimensions in the loss-construction experiment | regret | Helped |
| Use φₚ rather than φ₂ (ablation) | FTRL · Low-dimensional OCO experiment | regret | Hurt |
| Use φₚ rather than φ₂ (ablation) | FTRL · High-dimensional OCO experiment | regret | Helped |
| Use adaptive regularisation rather than either fixed φ₂ or fixed φₚ (ablation) | FTRL · Low- and high-dimensional OCO experiment | regret | Mixed |
| Use a strongly-convex regulariser in sufficiently high dimension (ablation) | FTRL on ℓ_p-balls · High-dimensional OCO | regret: R_T \geq \frac{1}{8} LT | Hurt |
| Use bandit feedback rather than full-information feedback | Online learning on ℓ_p-balls · Linear bandit, sufficiently large dimension | expected pseudo-regret: \mathbb{E} \bsb{\Bar{R}_T} \geq \frac{LT}{80} | Hurt |
Surprising findings
- Any strongly-convex regulariser is sub-optimal in high dimensions, with regret linear in T once d is large enough relative to T.
- Sub-linear regret is impossible for linear bandits on ℓp-balls (p ≥ 1) in sufficiently high dimension.
Limitations
- Negative result on fixed regularisers is proven only for separable regularisers (and those within constant factors); general non-separable regularisers remain open.
- Experiments are small numerical simulations on a specific loss construction, run on Google Colab CPU.
- Anytime procedure requires switching regulariser at a dimension-dependent threshold and uses knowledge of L and related constants for the step-sizes.
Experimental setup
Metrics: regret
Baselines: FTRL with strongly-convex regulariser (1/2)||x||_2^2 FTRL with uniformly-convex regulariser (1/p)||x||_p^p OMD with strongly-convex regulariser Adagrad-style diagonal step-sizes
Builds on: FTRL analysis with uniformly-convex regularisers Clarkson's inequality online mirror descent Adagrad
Closest papers by meaning
- A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $\Theta(T^{2/3})$ and its Application to Best-of-Both-Worlds (NeurIPS 2024 · similarity 0.90)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.89)
- Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences (NeurIPS 2026 · similarity 0.89)
- Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting (AAAI 2025 · similarity 0.88)
- Discounted Adaptive Online Learning: Towards Better Regularization (ICML 2024 · similarity 0.88)
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.88)
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.