Research map / Optimization / Optimizers

Discounted Adaptive Online Learning: Towards Better Regularization

ICML 2024 · Optimization › Optimizers · approach: Second-order and structured preconditioning · 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.

Proposes an adaptive, FTRL-based discounted online convex optimization algorithm (via a rescaling trick and erfi-potential magnitude learner) that is instance-optimal and applies it to online conformal prediction with coverage guarantees.

Problem

Online learning in adversarial nonstationary environments requires forgetting old data; existing discounted regret methods use non-adaptive constant-learning-rate OGD, which is only minimax optimal and needs hyperparameter tuning. Online conformal prediction under distribution shift also needs cover

Approach

Reduce discounted regret to undiscounted regret of an adaptive FTRL-based algorithm via a rescaling trick on surrogate gradients (upweighting recent losses), combined with a polar-decomposition erfi-potential magnitude learner with discounted variance and Lipschitz statistics, yielding instance-dependent bounds O(||u|| sqrt(V_T)) up to logs; in OCP, FTRL iterate stability gives coverage guarantees

Key results

• MagL-D achieves the lowest local coverage error (0.08) among all methods in the OCP experiment, versus 0.09 for Sf-Ogd and 0.11 for Simple OGD.
• MagDis reaches LCE_100 of 0.07 with average width 122.1 and average coverage 0.888, competitive with baselines despite no guarantee.
• MagL-D has average width 118.5, lower than Simple OGD (125.0) but with average coverage 0.884 slightly below the 0.9 target; runtime ~1.06x Simple OGD versus 11.07x for Saocp.

Measured effects reported in the paper

Surprising findings

• The simplified variant MagDis, which drops the performance guarantee, performs competitively, suggesting the full algorithm's complexity is not strictly needed in practice.
• Gradient-adaptive OGD with time-varying learning rates (AdaGrad-style oracle tuning) does not achieve the O(||u||sqrt(V_T)) bound, so naive oracle tuning of OGD fails.

Limitations

• Results are for convex losses; the connection to non-convex lifelong learning is not established in this paper.
• The discount factors are treated as given side information; online selection of discount factors is left open.
• Experiments are limited to a single image classification OCP setup, and the proposed methods give lower average coverage than some baselines.

Experimental setup

Datasets: image classification benchmark with time-varying corruption (setup following prior OCP work)

Benchmarks: sequential corrupted image classification for online conformal prediction

Metrics: average coverage average width local coverage error (LCE_100) normalized runtime

Baselines: Simple OGD Sf-Ogd Saocp SplitConformal NExConformal Faci Faci-S

Builds on: AdaGrad constant-LR online gradient descent erfi potential learner (Zhang et al. 2023) Adaptive Conformal Inference (ACI) polar decomposition for parameter-free OCO

Closest papers by meaning

• A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.90)
• The Relationship Between No-Regret Learning and Online Conformal Prediction (ICML 2025 · similarity 0.89)
• 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.89)
• Gradient-Variation Online Learning under Generalized Smoothness (NeurIPS 2024 · similarity 0.89)
• Minimax Adaptive Online Nonparametric Regression over Besov spaces (NeurIPS 2025 · similarity 0.88)
• On the necessity of adaptive regularisation: Optimal anytime online learning on $\boldsymbol{\ell_p}$-balls (NeurIPS 2025 · similarity 0.88)