Research map / Bandits and online learning / Online convex optimization and games
Dimension-Free Adaptive Subgradient Methods with Frequent Directions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes FTSL and FTFSL, adaptive subgradient methods that sketch the gradient outer-product matrix with frequent directions under a primal-dual framework, achieving dimension-free regret and O(τd) per-round time, plus FTSL-Shampoo for matrix-valued parameters.
Problem
Adaptive subgradient methods (ADA-FULL) are expensive in space and time for high dimensions, and existing FD-based variants (ADA-FD, S-ADA, S-Shampoo) have regret bounds that depend linearly on dimensionality d (or m, n) and O(τ²d) time per round.
Approach
Integrate frequent directions with ADA-FULL under the primal-dual (lazy) framework and add back cumulative escaped eigenvalues to keep the preconditioner monotone, yielding a dimension-free regret bound; a fast FD variant reduces per-round time to O(τd), and the same idea is applied to Shampoo.
Key results
- FTFSL outperforms all compared methods in both loss and testing accuracy on Gisette and Epsilon online classification, aligning with its regret bound.
- FTFSL and Fast S-ADA have significantly lower runtime than S-ADA owing to O(τd) per-round time versus O(τ²d).
- FTSL achieves dimension-free regret O(tr(G^{1/2}_T) + sqrt(ρ_{1:T})), improving over S-ADA's O(tr(G^{1/2}_T) + sqrt(d(d−τ)ρ_{1:T})).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Integrate FD with ADA-FULL under the primal-dual framework and add cumulative discarded eigenvalues back | FTSL · OCO | regret bound: O(tr(G^{1/2}_T) + √ρ_{1:T}) vs. O(tr(G^{1/2}_T) + √(d(d − τ)ρ_{1:T})) | Helped |
| Use fast FD by doubling the sketching size | FTFSL · OCO | time complexity: O(τ²d) -> O(τd) | Helped |
| Apply fast FD to S-ADA | S-ADA · OCO | time complexity: O(τ²d) -> O(τd) | Helped |
| Adapt FD to Shampoo under the primal-dual framework and add back cumulative discarded eigenvalues | FTSL-Shampoo · Matrix decision variables | regret bound: O(√r(tr(L^{1/4}_T) + m(ρ^L_{1:T})^{1/4})(tr(R^{1/4}_T) + n(ρ^R_{1:T})^{1/4})) -> O(√r(tr(L^{1/4}_T) + (ρ^L_{1:T})^{1/4}) | Helped |
| Use FTFSL instead of the other compared methods | Online classification methods · Gisette and Epsilon | testing accuracy | Helped |
| Use FTFSL or Fast S-ADA instead of S-ADA | Online classification methods · Gisette and Epsilon | runtime | Helped |
Limitations
- Neural network experiments are described only briefly in the main text; full results deferred to appendix.
- FTFSL O(τd) time holds only when τ ≤ O(√d).
Experimental setup
Datasets: Gisette Epsilon
Benchmarks: Gisette Epsilon
Metrics: testing accuracy training loss runtime
Baselines: ADA-DIAG RADAGRAD FD-SON ADA-FFD S-ADA Fast S-ADA S-Shampoo Shampoo
Builds on: AdaGrad frequent directions Sketchy-ADAGRAD Shampoo fast frequent directions
Closest papers by meaning
- Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching (ICLR 2026 · similarity 0.87)
- Non-stationary Projection-Free Online Learning with Dynamic and Adaptive Regret Guarantees (AAAI 2024 · similarity 0.85)
- Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound (NeurIPS 2025 · similarity 0.85)
- The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithms (NeurIPS 2024 · similarity 0.85)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.85)
- Adaptive Partitioning Schemes for Optimistic Optimization (ICML 2025 · similarity 0.85)
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.