We propose a novel 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 provided at each iteration by 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.

In this paper, the authors propose a randomized first order optimization method (SEGA) which progressively builds a variance reduced estimate of the gradient from random linear measurements of the gradient. The proposed method (or class of methods - depending on the sketch matrix and metric used) updates the current estimate of the gradient through a sketch-and-project operation using new gradient information and the past estimate of the gradient. However, the quality of the paper deteriorates after page 6. The paper has minor typos and grammatical mistakes that can be corrected easily. The experiments are well though out to highlight certain algorithmic features of the method, however, several details are missing (e.g., what is the dimension n of the problems solved?), comparison with more methods would strengthen the claims made and experiments on real ML problems would highlight the merits (and limitations) of SEGA.

We propose a novel 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 provided at each iteration by 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.