Research map / Bandits and online learning / Online convex optimization and games

Small-loss Adaptive Regret for Online Convex Optimization

ICML 2024 · Bandits and online learning › Online convex optimization and games · approach: Dynamic and adaptive regret

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 FLHS, a small-loss adaptive regret algorithm for smooth exp-concave and strongly convex losses, and USIA, a universal meta-expert algorithm that attains small-loss adaptive regret for general convex, exp-concave and strongly convex smooth functions simultaneously.

Problem

Adaptive regret in online convex optimization has small-loss bounds only for general convex smooth functions; it was unknown whether similar bounds hold for exp-concave and strongly convex functions, and no universal method provided them.

Approach

Builds problem-dependent (compact PGC) geometric covering intervals driven by the cumulative loss of experts, combined with a meta-learner (FLH-style for FLHS; Adapt-ML-Prod extended to sleeping experts for USIA) whose weights are initialized and updated by the number of intervals, so meta-regret and expert-regret both scale with cumulative loss.

Key results

• FLHS achieves O(sqrt(d/alpha) log L*_{1,s} log L*_{r,s}) small-loss adaptive regret for alpha-exp-concave smooth functions, improving the log s log(s-r) factor of prior work.
• USIA simultaneously attains small-loss adaptive regret bounds O(sqrt(L*_{r,s} log L*_{1,s} log L*_{r,s})), O(d/alpha log L*_{1,s} log L*_{r,s}) and O(1/lambda log L*_{1,s} log L*_{r,s}) for general convex, exp-concave and strongly convex smooth functions.
• Both algorithms retain minimax adaptive regret bounds when functions are non-smooth (e.g., O(sqrt((s-r) log s log(s-r))) for general convex).

Limitations

• Small-loss guarantees require smooth functions; non-smooth case gives only minimax bounds.
• USIA maintains O(log^2 T) expert-algorithms, which is computationally costly.
• Requires a bounded modulus of exp-concavity/strong convexity in [1/T, 1].

Experimental setup

Metrics: adaptive regret regret bound order

Baselines: FLH SACS Zhang et al. 2021 universal adaptive regret Zhang et al. 2018 strongly convex adaptive regret UFO

Builds on: Follow-the-Leading-History Zhang et al. 2019 problem-dependent intervals (SACS) Adapt-ML-Prod S2OGD UFO/Maler universal algorithms

Closest papers by meaning

• Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.92)
• Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets (NeurIPS 2024 · similarity 0.91)
• Universal Online Convex Optimization with $1$ Projection per Round (NeurIPS 2024 · similarity 0.91)
• An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.91)
• From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization (NeurIPS 2026 · similarity 0.91)
• Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points (NeurIPS 2026 · similarity 0.90)