Research map / Bandits and online learning / Online convex optimization and games
Efficient online algorithms for fast-rate regret bounds under sparsity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BOA with multiple learning rates per expert | Finite-reference-set online aggregation · Finite reference set, arbitrary data | average risk bound: \left(\frac{\cK(\pi,\widehat \pi_0)+ \ln\ln(GT) + x }{\alpha T} \right)^{\frac{1}{2-\beta}} | Helped |
| Use a quantile bound that depends on the proportion of well-performing experts | Squint · Finite reference set, arbitrary data | average risk: \ln(K/\Card(\Theta')) | Helped |
| Discretize the unit ℓ1-ball with an ε-cover | BOA on a finite grid · Unit ℓ1-ball, arbitrary data | average risk bound: \left(\frac{d \ln T + \ln\ln(GT) + x }{\alpha T}\right)^{\frac1{2-\beta}} + \frac{G }{T^2} | Helped |
| Use a sparsity-pattern prior instead of a uniform prior over the discretization | BOA on the unit ℓ1-ball · Unit ℓ1-ball, arbitrary data | average risk bound: \left(\frac{\|\theta\|_0 \ln(d T/\|\theta\|_0) + x }{\alpha T}\right)^{\frac1{2-\beta}} + \frac{\|\theta\|_0 G }{T^2} | Helped |
| Use a fixed grid with small averaging-accelerability distance to the comparator | BOA · Unit ℓ1-ball, arbitrary data | average risk bound: G D(\theta,\Theta_0) \sqrt{\frac{a}{T}} | Helped |
| Add sparse versions of the empirical leader to the grid and restart BOA | BOA+ · Adversarial strongly convex losses | average regret: \tilde \cO \left( \min\left\{ G \sqrt{\frac{\ln d}{T}}, \sqrt{\frac{\|\theta\|_0}{\mu}} \left(G \sqrt{\frac{\ln d}{T}}\r | Helped |
| Ensure leaders and the comparator are d₀-sparse | BOA+ · Adversarial strongly convex losses | average regret: \tilde \cO(d_0/ T) | Helped |
| Add averaged estimates to the grid and restart BOA | SABOA · i.i.d. losses under the Łojasiewicz assumption | average risk: \left(\frac{\ln d+\ln \ln (GT) + x}{T} \left(\frac{1}{\alpha}+ \frac{G^2}{\mu}\Big(d_0^2 \wedge \frac{d_0}{\gamma^2}\Big | Helped |
| Allow multiple risk minimizers under the Łojasiewicz condition | SABOA · i.i.d. losses with degenerate collinear design | applicability to sparse risk bounds | Helped |
Closest papers by meaning
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.91)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.91)
- Unconstrained Robust Online Convex Optimization (ICML 2025 · similarity 0.91)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.90)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.90)
- Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets (NeurIPS 2024 · similarity 0.90)
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.