Research map / Bandits and online learning / Online convex optimization and games
Online Learning with Imperfect Hints
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 adaptive hint scaling and surrogate-loss FTRL that tolerates hints below the correlation threshold | Constrained online linear optimization · Constrained online linear optimization, strongly convex norm | regret: O \left( \sqrt{ \sum_{t \in B_{T, \alpha}} \norm{c_t}_*^2} + \frac{r_T}{\mu \alpha} \log \big( 1 + \sum_{t \in G_{T, \al | Helped |
| Add a scalar learner that uses the accumulated hint-cost correlation | Unconstrained online linear optimization · Unconstrained online linear optimization with hints | regret: \tilde{O}\left(\epsilon + \dfrac{\|u\|\log\left(1 + \frac{T \|u\|}{\epsilon^2}\right)\left(1 + \sqrt{|B^*_{T,\alpha}|}\r | Helped |
| Allow hints to be good on average rather than requiring each useful hint to meet the threshold individually | Unconstrained hint algorithm · Unconstrained online learning with hints | regret: O(\log T) | Helped |
| Use the constrained imperfect-hints algorithm in a (q, μ)-uniformly convex space | Constrained imperfect-hints algorithm · Constrained online learning, (q, μ)-uniformly convex space | regret: O\left(\frac{S}{(\alpha \mu)^{p/q}} + |B_{T,\alpha}|^{1/p} + \frac{S^{1/p}}{(\mu\alpha)^{1/q}}|B_T|^{1/q}\right) | Helped |
| Have B initial steps with uninformative hints before perfect-hint steps | Any constrained online algorithm · Euclidean unit ball, first B rounds uninformative | expected regret: \Omega(\sqrt{B}) | Hurt |
| Spread bad hints randomly across rounds | Any one-dimensional online algorithm · One-dimensional unit interval, randomly distributed bad hints | expected regret: \sqrt{B}/2 | Hurt |
| Use an ℓq geometry with q>2, even when hints have constant positive correlation | Any dimension-free online algorithm · ℓq norm, dimension T+1, hints Ω(1)-correlated | expected regret: \Omega \left( T^{\frac{(q-2)}{(q-1)}} \right) | Hurt |
Closest papers by meaning
- Online Learning with Unknown Constraints (ICML 2025 · similarity 0.89)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.88)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · similarity 0.87)
- Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound (NeurIPS 2025 · similarity 0.87)
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.87)
- Avoiding Catastrophe in Online Learning by Asking for Help (ICML 2025 · 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.