Research map / Bandits and online learning / Online convex optimization and games
No Internal Regret with Non-convex Loss Functions
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 internal (swap) regret minimization from finite experts to continuous action spaces with non-convex (Lipschitz and dispersed piecewise-constant) losses, via discretization and a potential-based algorithm, in full and bandit feedback.
Problem
Internal regret has been studied only for finite expert sets; the standard reduction to external regret depends on finite action spaces, so minimizing internal regret over continuous action spaces with non-convex losses is open.
Approach
Defines internal regret on a continuum as a limit of mass-redistribution between balls, then obtains sublinear bounds by discretizing the action space into an epsilon-cover and applying the exponential-potential internal regret algorithm (Cesa-Bianchi and Lugosi), with a piecewise-constant variant using dispersion and a bandit variant with exploration.
Key results
- Full-information internal regret O(sqrt(dT log(RLT))) for L-Lipschitz losses in d-dimensional Euclidean action spaces via DEPoM.
- One-dimensional piecewise-constant losses with K pieces achieve O(sqrt(T log(KT))) internal regret under dispersion/bounded-density discontinuities, with a matching Omega(sqrt(T)) lower bound.
- Bandit feedback gives expected internal regret O~(T^((d+1)/(d+2))) for Lipschitz losses and O(T^(2/3) poly(K, ln T)) for piecewise-constant losses.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DEPOM with a discretized action-space cover | Online learning with Lipschitz losses and full information · Lipschitz losses, full information | internal regret: O(√(dT log RLT)) | Helped |
| Use CEPoM with an experts schedule based on piecewise-constant loss pieces | Online learning with dispersed piecewise-constant losses and full information · One-dimensional piecewise-constant losses, full information | internal regret: O(√(T ln(KT))) | Helped |
| Use INTERNAL EXP3 with discretization and exploration | Online learning with Lipschitz losses and bandit feedback · Lipschitz losses, bandit feedback | internal regret: O(T^{(d+1)/(d+2)}(√d R^d + L)polylog(T)) | Helped |
| Use INTERNAL EXP3 with a tuned parameter setting and fixed schedule | Online learning with piecewise-constant losses and bandit feedback · One-dimensional piecewise-constant losses, bandit feedback | internal regret: O(T^{2/3}poly(K, ln T)) | Helped |
| Allow arbitrary unrestricted loss functions | Online learning over a continuous action space · Unrestricted losses | swap regret: Ω(T) | Hurt |
Surprising findings
- Without further assumptions, linear swap regret is unavoidable for non-Lipschitz piecewise-constant losses, so dispersion is needed.
Limitations
- Full-information computational cost scales with cover size (3R/eps)^d, inefficient for large action dimension d.
- Bandit lower bounds and tight regret rates remain open; the d-dimensional piecewise-constant extension is not fully handled.
- Non-Lipschitz results rely on dispersion/bounded-density assumptions; without them linear regret is unavoidable.
Experimental setup
Metrics: internal regret
Baselines: Blum and Mansour 2007 reduction Cesa-Bianchi and Lugosi 2003 finite-expert algorithm
Builds on: Cesa-Bianchi and Lugosi potential-based internal regret Blum and Mansour reduction dispersion (Balcan, Dick, and Vitercik 2018) Exp3
Closest papers by meaning
- Optimal No-Regret Learning for One-Sided Lipschitz Functions (ICML 2023 · similarity 0.88)
- Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability (ICML 2025 · similarity 0.88)
- Cumulative Regret Analysis of the Piyavskii–Shubert Algorithm and Its Variants for Global Optimization (AAAI 2024 · similarity 0.87)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.87)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.87)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · 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.