# SEGA: Variance Reduction via Gradient Sketching

arXiv: https://arxiv.org/abs/1809.03054 · HTML: https://mlsanity.com/paper/1809.03054/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2018.

## Built on by (most cited first, 29 of 29)

- [Gradients without Backpropagation](https://mlsanity.com/paper/2202.08587/) (2022)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles](https://mlsanity.com/paper/2303.03751/) (2023)
- [CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression](https://mlsanity.com/paper/2107.09461/) (2021)
- [Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization](https://mlsanity.com/paper/2102.07245/) (2021)
- [Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox](https://mlsanity.com/paper/2207.03957/) (2022)
- [GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity](https://mlsanity.com/paper/2210.16402/) (2022)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation](https://mlsanity.com/paper/2206.03588/) (2022)
- [Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification](https://mlsanity.com/paper/2307.06565/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Differentially Private Coordinate Descent for Composite Empirical Risk Minimization](https://mlsanity.com/paper/2110.11688/) (2021)
- [Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?](https://mlsanity.com/paper/2309.07452/) (2023)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [A Semismooth Newton Stochastic Proximal Point Algorithm with Variance Reduction](https://mlsanity.com/paper/2204.00406/) (2022)
- [High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent](https://mlsanity.com/paper/2207.01560/) (2022)
- [Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems](https://mlsanity.com/paper/2406.02413/) (2024)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [Escaping Saddle Points with Compressed SGD](https://mlsanity.com/paper/2105.10090/) (2021)
- [CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity](https://mlsanity.com/paper/2309.13307/) (2023)
- [ALS: Augmented Lagrangian Sketching Methods for Linear Systems](https://mlsanity.com/paper/2208.06152/) (2022)
- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)
- [Subspace Langevin Monte Carlo](https://mlsanity.com/paper/2412.13928/) (2024)
- [Differentially Private Random Block Coordinate Descent](https://mlsanity.com/paper/2412.17054/) (2024)
- [An Enhanced Zeroth-Order Stochastic Frank-Wolfe Framework for Constrained Finite-Sum Optimization](https://mlsanity.com/paper/2501.07201/) (2025)
- [A stochastic gradient descent algorithm with random search directions](https://mlsanity.com/paper/2503.19942/) (2025)
- [Zero-Order Optimization for LLM Fine-Tuning via Learnable Direction Sampling](https://mlsanity.com/paper/2602.13659/) (2026)
- [Adaptive directional gradients for parameterised quantum circuits](https://mlsanity.com/paper/2606.09734/) (2026)

## Abstract (arXiv)

We propose a randomized first order optimization method--SEGA (SkEtched GrAdient method)-- which progressively throughout its iterations builds a variance-reduced estimate of the gradient from random linear measurements (sketches) of the gradient obtained from an oracle. In each iteration, SEGA updates the current estimate of the gradient through a sketch-and-project operation using the information provided by the latest sketch, and this is subsequently used to compute an unbiased estimate of the true gradient through a random relaxation procedure. This unbiased estimate is then used to perform a gradient step. Unlike standard subspace descent methods, such as coordinate descent, SEGA can be used for optimization problems with a non-separable proximal term. We provide a general convergence analysis and prove linear convergence for strongly convex objectives. In the special case of coordinate sketches, SEGA can be enhanced with various techniques such as importance sampling, minibatching and acceleration, and its rate is up to a small constant factor identical to the best-known rate of coordinate descent.