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

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Online learning with feedback graphs · 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.

Extends the batch-to-online transformation of Dong and Yoshida to time-varying approximation accuracy, yielding small-loss regret bounds under the random-order model via average sensitivity and concave conjugates, with applications to online submodular minimization and l1 regression.

Problem

Obtaining standard (non-approximate) small-loss regret bounds in the random-order model, where the regret depends on the offline optimum and the average sensitivity of offline approximation algorithms, rather than only (1+eps)-approximate regret.

Approach

Choose the approximation parameter eps_t per round by minimizing the accuracy-stability trade-off (OPT_t+lambda)eps + phi(eps), which yields a regret bound of order H_T phi*(OPT_T/H_T + lambda) via the concave conjugate phi*, plus a parameter-change stability term that is controlled by telescoping with the supergradient property of eps_min.

Key results

• General small-loss regret bound R_T <= H_T phi*(OPT_T/H_T + lambda) + C_pc(phi*(OPT_T+lambda) - phi*(lambda)) + O(1) under the random-order model.
• Online submodular function minimization achieves regret O~(n^3 + n^{3/4} OPT_T^{3/4}) in polynomial time.
• Online l1 regression achieves regret O~(d + d^{1/4} OPT_T^{3/4}).

Surprising findings

• The paper notes that a naive doubling trick does not apply in the random-order analysis, motivating per-round adaptive epsilon_t instead.

Limitations

• Results are limited to the random-order model; the stochastically extended adversarial model is left to future work.
• Re-running the offline algorithm on all observed data each round is computationally expensive.
• Tightness is open; lower bound Omega(sqrt(n OPT_T)) only matches when OPT_T ~ T, and the parameter-change stability condition must be verified per application.

Experimental setup

Metrics: regret bound (theoretical) average sensitivity inconsistency

Baselines: Dong and Yoshida (2023) fixed-epsilon batch-to-online Hazan and Kale style online submodular minimization (O(sqrt(nT))) Ito et al. 2022 best-of-both-worlds submodular minimization multiplicative weights over 2^n experts

Builds on: batch-to-online transformation (Dong and Yoshida 2023) submodular hypergraph cut sparsifiers (Kenneth 2024) Lewis-weight sampling Follow-the-Regularized-Leader

Closest papers by meaning

• Online Convex Optimization in the Random Order Model (ICML 2020 · similarity 0.92)
• A Batch-to-Online Transformation under Random-Order Model (NeurIPS 2023 · similarity 0.92)
• Efficient online algorithms for fast-rate regret bounds under sparsity (NeurIPS 2018 · similarity 0.91)
• Online Learning in the Random-Order Model (ICML 2025 · similarity 0.90)
• Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.89)
• Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.89)