Research map / Bandits and online learning / Online convex optimization and games
Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation
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 Algorithm 1 (extra observations, k' >= k+2) instead of greedy selection | online sparse linear regression with known k · Synthetic (d,k,k')=(20,5,7), T=5000 | regret R_T /10^2: 1.53 vs 33.28 for greedy | Helped |
| Use Algorithm 2/3 (no extra observations) instead of Algorithm 1 when ground-truth k is unknown (ablation) | online sparse regression, k unknown · Synthetic (d,k1,k), T=5000 | regret R_T /10^2: Algorithm 3 17.19 and Algorithm 2 20.59 vs Algorithm 1 26.88 | Helped |
| Algorithm 2/3 (sublinear-regret, polynomial time) vs exponential-time FKK | online sparse regression · Synthetic (d,k1,k), T=5000 | regret R_T /10^2: 17.19 (Alg 3) vs 58.71 (FKK) | Helped |
| Use Algorithm 1 (k'=k+2 observations) rather than baselines on synthetic (d,k,k') instances | online sparse regression · Synthetic (d,k,k')=(20,5,7), T=5000 | regret R_T /10^2: 1.53 vs 24.05 for FKK and 25.73 for uniform random | Helped |
| Algorithm 2 and 3 (no extra observation) vs Algorithm 1 in the k'=k setting with known k (ablation) | online sparse regression · Synthetic (d,k,k')=(20,5,7), T=5000 | regret R_T /10^2: Algorithm 2 2.38 and Algorithm 3 3.60 vs Algorithm 1 1.53 | Hurt |
| Algorithm 2/3 vs others on real CT-slice dataset (k' = 70, k1 = 60), square loss over rounds | online sparse regression · CT-slice dataset | cumulative square loss: qualitative: Algorithms 2 and 3 superior to others | Helped |
Closest papers by meaning
- Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge (NeurIPS 2021 · similarity 0.91)
- Adaptive Feature Selection: Computationally Efficient Online Sparse Linear Regression under RIP (ICML 2017 · similarity 0.90)
- Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression (ICML 2023 · similarity 0.90)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.88)
- Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound (NeurIPS 2025 · similarity 0.88)
- Online Linear Regression in Dynamic Environments via Discounting (ICML 2024 · similarity 0.88)
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.