  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.
