Stochastic quasi-gradient methods: variance reduction via Jacobian sketching.

Area of Science:

• Optimization
• Machine Learning
• Numerical Linear Algebra

Background:

• Minimizing the average of a large number of smooth functions is a common problem in machine learning.
• Existing methods like stochastic gradient descent can suffer from slow convergence or high variance.

Purpose of the Study:

• To develop a new family of variance-reduced stochastic gradient descent (SGD) methods for large-scale optimization.
• To improve the efficiency and convergence rates of optimization algorithms.

Main Methods:

• JacSketch method: maintains a stochastic estimate of the Jacobian matrix using randomized linear algebra and sketching.
• Efficiently updates the Jacobian estimate via sketching and projection.
• Computes a variance-reduced unbiased gradient estimator.
• Analogous to quasi-Newton methods, termed a stochastic quasi-gradient method.

Main Results:

• Proved linear convergence for smooth and strongly convex functions with a general convergence theorem for sketches.
• Developed a refined convergence theorem using a stochastic Lyapunov function for specific sketches.
• Achieved sharper complexity results for importance sampling variants.
• Specializing JacSketch recovers stochastic average gradient (SAGA) and its variants.
• Established the current best-known rate for SAGA with importance sampling, resolving a conjecture.
• Obtained superior rates for minibatch SAGA, showing decreased complexity with increased batch size.
• Introduced the first minibatch SAGA method with importance sampling.

Conclusions:

• JacSketch offers a powerful and versatile framework for large-scale optimization.
• The method provides theoretical guarantees and practical improvements over existing techniques.
• It unifies and extends several existing optimization algorithms, including SAGA.