Research map / Optimization / Nonconvex and smooth optimization
Can Gaussian Sketching Converge Faster on a Preconditioned Landscape?
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 GSGD, a Gaussian-sketched gradient method with a variance-reduction variate that converges linearly without importance sampling, including for inseparable regularizers, evaluated on synthetic quadratic problems.
Problem
Gradient sketching methods (random coordinate descent, SEGA) need importance sampling to reach the best linear rate for smooth strongly convex objectives, which requires diagonal access to the curvature matrix, and classical sketches fail to converge linearly with non-separable regularizers.
Approach
Replace coordinate sketches with Gaussian sketches u~N(0,I) and track the gradient with a variance-reduction variate h_k updated by a Gaussian sketch; this matches SEGA's iteration complexity tr(M)/mu without importance sampling and gives linear rates with composite regularizers, including a rank(W)-dependent rate for affine-subspace indicators.
Key results
- Without regularization, GSGD achieves iteration complexity O(tr(M)/mu log(1/eps)) matching SEGA with importance sampling, without needing diagonal entries of M.
- With an inseparable regularizer, GSGD converges linearly with complexity O(dL/mu log(1/eps)).
- With affine-subspace indicator regularizers, complexity O(L tr(W)/mu log(1/eps)) depends on the rank of the projection W; experiments show faster convergence for lower rank in most settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Gaussian sketching without importance sampling instead of coordinate sketching with uniform sampling | GSGD vs. Coordinate sketching SEGA · Synthetic quadratic optimization with φ = 0, diagonal matrix types 1–3 | convergence speed | Helped |
| Use Gaussian sketching without importance sampling instead of coordinate sketching with uniform sampling | GSGD vs. Coordinate sketching SEGA · Synthetic quadratic optimization with φ = 0, diagonal matrix type 4 | convergence speed | No clear effect |
| Use GSGD with an affine-subspace regularizer whose projection matrix has lower rank (ablation) | GSGD · Synthetic quadratic with an affine-subspace regularizer, diagonal matrix types 1–4 | convergence speed | Mixed |
Surprising findings
- In the uniform-diagonal setting, GSGD performs similarly to SEGA rather than clearly faster, since tr(M)/mu is then close to dL/mu.
Limitations
- Experiments only on small synthetic quadratic problems (d=500), no real ML tasks
- Non-separable regularizer rate O(dL/mu) is weaker than tr(M)/mu-based rate in some regimes
- Zeroth-order variant is discussed but not evaluated
Experimental setup
Datasets: synthetic quadratic minimization problems (dimension 500)
Benchmarks: synthetic quadratic minimization (d=500)
Metrics: objective suboptimality vs iterations
Baselines: SEGA (coordinate sketching with importance sampling) Yue et al. 2023 gradient sketching SVRCD Song et al. 2023 Gaussian sketching federated
Builds on: SEGA SVRCD ASVRCD sketch-and-project Nesterov random coordinate descent
Closest papers by meaning
- Iterative Double Sketching for Faster Least-Squares Optimization (ICML 2022 · similarity 0.89)
- Gradient Projection Iterative Sketch for Large-Scale Constrained Least-Squares (ICML 2017 · similarity 0.88)
- Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees (ICLR 2025 · similarity 0.87)
- Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update (NeurIPS 2021 · similarity 0.86)
- Learning the Positions in CountSketch (ICLR 2023 · similarity 0.86)
- Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuning (NeurIPS 2024 · similarity 0.84)
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.