Research map / Bandits and online learning / Online convex optimization and games
Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions
Adam Block, Max Simchowitz
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 the John ellipsoid center as the predictor instead of an arbitrary classifier from the version space | Realizable smoothed online linear classification · Unit-ball contexts with σ-smooth adversary | mistakes (regret): 136 d \log(d) + 34 \log\left(\frac{T}{\sigma \delta}\right) + 56 | Improved |
| Use pairwise binary classifiers and combine their predictions | K-class affine classification · Realizable smoothed online K-class affine classification | mistakes (regret): 136 K^2 d \log(d) + 91K^2 \log\left(TK^2/(\sigma \delta)\right) | Improved |
| Average feature vectors across multiple mistakes to construct meta-points | Polynomial-feature online classification · Realizable smoothed online classification with polynomial features | mistakes (regret): \lesssim m \log(m) + \log\left(\frac 1\alpha\right) + \ell^2 m^2 d \log^2\left(\frac{d \ell T L}{\sigma \delta}\right) | Improved |
| Use the Perceptron under directional smoothness rather than requiring full-context smoothness and realizability | Online classification · Directional-smooth adversary, including possibly non-realizable labels | mistakes (regret): \lesssim ( T/\sigdir)^{\frac{2}{3}} \cdot (\Nerr(w^\star,b^\star) )^{\frac{1}{3}} + \log(\ceil{\log T }/\delta) | Mixed |
Closest papers by meaning
- Smoothed Online Classification can be Harder than Batch Classification (NeurIPS 2024 · similarity 0.87)
- Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood (NeurIPS 2024 · similarity 0.87)
- Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound (NeurIPS 2025 · similarity 0.86)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.86)
- Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences (NeurIPS 2026 · similarity 0.86)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 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.
