Research map / Bandits and online learning / Online convex optimization and games
Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel–Young Losses
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.
Constructs a convex smooth surrogate loss for arbitrary discrete target losses via convolutional Fenchel–Young losses (infimal convolution of a negentropy and negative Bayes risk), proving a linear surrogate regret bound with a tailored prediction link.
Problem
Existing convex smooth surrogate losses only yield square-root surrogate regret bounds, while linear-rate surrogates are non-smooth or non-convex; it is unclear whether convexity, smoothness and linear regret can coexist for discrete target losses.
Approach
Define a convolutional negentropy Omega_T = Omega + T, where T is the negative target Bayes risk (polyhedral); its Fenchel–Young loss is convex and smooth (base negentropy strongly convex) and, via infimal convolution, admits a linear surrogate regret bound with a pi-argmax prediction link.
Key results
- Convolutional Fenchel–Young loss is convex and smooth for strongly convex base negentropy, and the pi-argmax link gives surrogate regret bound Regret_l(phi(theta)) <= N * Regret_L(theta), with N the number of predictions.
- Improved bound with constant affdim(L)+1 via Carathéodory, and randomized link gives dimension-free constant 1.
- For multiclass classification with Shannon negentropy, the loss is a cross-entropy variant with bounded perturbation, computable in O(K log K) via a sparsemax-like algorithm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Construct a convolutional Fenchel–Young loss and pair it with the π-argmax link | Arbitrary discrete prediction problems · Arbitrary discrete prediction problems | surrogate regret bound constant: N | Helped |
| Use a sparse selector with support size at most affdim(ℒ^ρ)+1 | Convolutional Fenchel–Young loss · Arbitrary discrete prediction problems | surrogate regret bound constant: N -> [affdim(ℒ^{\bm{\rho}})+1] | Helped |
| Randomize predictions according to π(θ) | Convolutional Fenchel–Young loss · Arbitrary discrete prediction problems (expected target regret) | surrogate regret bound constant: N -> 1 | Helped |
| Use the exact π_log minimizer algorithm | Multiclass classification · Multiclass classification | optimization time: O(K\ln K) | Helped |
Surprising findings
- Convex smooth surrogates can achieve linear surrogate regret bounds, contrary to the belief that they inevitably yield square-root rates.
Limitations
- Regret bound constant N can be prohibitively large in general; improved only to affdim+1 or randomized link.
- Gradient computation requires solving an inner optimization problem for general discrete targets.
- Empirical evaluation is not reported in the provided text; no fast-rate results established.
Experimental setup
Baselines: hinge loss logistic loss polyhedral losses sigmoid loss
Builds on: Fenchel-Young losses polyhedral losses SELF decomposition sparsemax
Closest papers by meaning
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.90)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.89)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.88)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.87)
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.87)
- Exploiting Curvature in Online Convex Optimization with Delayed Feedback (ICML 2025 · similarity 0.86)
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.