Research map / Learning theory and algorithms / Prediction and decision losses
Margin-Independent Online Multiclass Learning via Convex Geometry
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 contextual search to predict inner products, updating its state only when the predicted classification sign is wrong | Online linear classification · Linear classifiers | total loss: O(d \log d) | Helped |
| Combine pairwise learners using a potential-based distribution over labels rather than simple majority voting | Nearest-neighbor partitions · Inner-product similarity | expected total loss: O(\alpha^{-2}k^2d\log d) | Helped |
| Use an exact polynomial-kernel map to linearize L^p distance | Nearest-neighbor partitions · L^p similarity, even integer p | expected total loss: O(p^4d^{(p+1)/p}k^2 \log d) | Helped |
| Use approximate kernel maps at multiple scales and assume centers are Δ-separated | Nearest-neighbor partitions · L^p similarity, p > 2 | total loss: \frac{k^2 \poly(d,p) }{\Delta} \cdot \left(\frac{1}{p-2}\right)^2 | Helped |
| Allow arbitrary convex regions instead of regions induced by nearest-neighbor centers | Online multiclass learning · General convex regions, k = 2 | total loss: \Omega\left(T^{(d-4) / (d-2)}\right) | Hurt |
| Use a distance-weighted loss rather than counting all classification errors equally | Online multiclass learning · Linear classifiers | total loss: O(d \log d) | Helped |
Closest papers by meaning
- Trading off Consistency and Dimensionality of Convex Surrogates for Multiclass Classification (NeurIPS 2024 · similarity 0.85)
- Multiclass Transductive Online Learning (NeurIPS 2024 · similarity 0.84)
- Online Linear Classification with Massart Noise (ICML 2025 · similarity 0.84)
- A Trichotomy for List Transductive Online Learning (ICML 2025 · similarity 0.84)
- Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification (NeurIPS 2025 · similarity 0.84)
- Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs (NeurIPS 2024 · similarity 0.83)
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.