Research map / Optimization / Optimizers
MAST: model-agnostic sparsified training
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 MAST, a sketched optimization formulation that minimizes the expected loss over random sparsifying sketches applied around a pre-trained shift model, with SGD variants and convergence theory for single-node and distributed settings.
Problem
Standard loss minimization ignores that models are later sparsified or trained with dropout/sparse training, and existing analyses of such methods give vacuous bounds or restrictive assumptions.
Approach
Reformulate training as minimizing the expectation over random sketch matrices S of f(shift + S(x - shift)), so the objective itself is sparsity-aware; gradient estimator S^T grad f(y) gives sketched SGD with convergence guarantees requiring only smoothness/convexity.
Key results
- On a5a logistic regression, MAST-trained models retain higher median test accuracy and lower variance than ERM models under random partition-sketch pruning across sparsity levels.
- Theory: MAST loss is sandwiched between f(x*) and f(x*)+((L_D-1)L_f/2)||x*-shift||^2, and sketched SGD converges linearly to a neighborhood whose size depends on the gap tf_inf - f_inf rather than gradient variance.
- ResNet-50 distributed experiments show a step size of 0.5 is a sweet spot; high sparsity (p=0.5) causes loss stagnation and large step sizes can diverge.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MAST instead of ERM before applying random pruning at the same sparsity | MAST vs ERM · a5a test set | test accuracy | Helped |
| Use MAST instead of ERM before applying random pruning | MAST vs ERM · a5a test set | test accuracy variability | Helped |
| Increase sparsity | ERM and MAST · a5a test set | test accuracy | Hurt |
| Increase the step size beyond γ=0.5 | Distributed Algorithm with Bernoulli sketches · ResNet-50 | convergence speed | Hurt |
| Use γ=1 with p=0.9 | Distributed Algorithm with Bernoulli sketches · ResNet-50 | convergence speed | Hurt |
| Use γ=1 with p=0.7 instead of a smaller step size | Distributed Algorithm with Bernoulli sketches · ResNet-50 | performance | Hurt |
| Use high sparsity p=0.5 | Distributed Algorithm with Bernoulli sketches · ResNet-50 | loss progression | Hurt |
| Use an excessively large step size | Distributed Algorithm with Bernoulli sketches · ResNet-50 | training stability | Hurt |
| Increase the step size and use more aggressive sparsification (lower p) | Distributed Algorithm with Bernoulli sketches · ResNet-50 | loss variance | Hurt |
| Decrease the step size for sparse optimization and Dropout training | Sparse optimization and Dropout training · ResNet-50 and convex models | optimization performance | Helped |
Surprising findings
- Neighborhood size depends on the gap between minima of the sketched and original losses rather than gradient variance at the optimum, so linear convergence to the exact solution is possible under interpolation.
- Dropout without 1/p scaling is not unbiased, unlike the proposed sketch formulation; the framework indicates higher sparsity can make optimization harder.
Limitations
- Experiments are small: convex logistic regression on a5a plus a limited ResNet-50 study.
- Analysis restricted to linear sketches; contractive/quantization compressors left to future work.
- Condition number can grow with sparsity, making the sketched problem harder to optimize.
Experimental setup
Datasets: a5a (LibSVM)
Benchmarks: a5a
Metrics: test accuracy convergence rate loss stagnation
Baselines: empirical risk minimization (ERM) formulation
Builds on: stochastic gradient descent Dropout DropConnect Independent Subnetwork Training Model-Agnostic Meta-Learning
Closest papers by meaning
- The Convergence of Sparsified Gradient Methods (NeurIPS 2018 · similarity 0.88)
- Gradient Sparsification for Communication-Efficient Distributed Optimization (NeurIPS 2018 · similarity 0.87)
- A Single-Step, Sharpness-Aware Minimization is All You Need to Achieve Efficient and Accurate Sparse Training (NeurIPS 2024 · similarity 0.86)
- Smoothing Proximal Gradient Methods for Nonsmooth Sparsity Constrained Optimization: Optimality Conditions and Global Convergence (ICML 2024 · similarity 0.86)
- LPGD: A General Framework for Backpropagation through Embedded Optimization Layers (ICML 2024 · similarity 0.85)
- On the Convergence of Loss and Uncertainty-based Active Learning Algorithms (NeurIPS 2024 · 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.