SGD with Variance Reduction beyond Empirical Risk Minimization

Massil Achab, Agathe Guilloux, Stéphane Gaïffas, Emmanuel BacryarXiv 2015 · arXiv

Abstract

Traditional Stochastic Gradient Descent (SGD) methods often struggle with models where the gradient of a single observation depends on the entire dataset. A prominent example is the Cox partial-likelihood model used in survival analysis. This paper introduces a "doubly stochastic" proximal gradient algorithm (2SVRG) that combines the variance reduction of SVRG with Markov Chain Monte Carlo (MCMC) sampling. By approximating expensive expectations within the gradient calculation and employing a precision-scheduling technique, the algorithm achieves linear convergence rates. Empirical results across high-dimensional genomic datasets demonstrate that 2SVRG significantly outperforms traditional batch methods and standard mini-batch SGD in computational efficiency.

Introduction

In modern machine learning, Stochastic Gradient Descent (SGD) is the standard for large-scale optimization. Its efficiency stems from the assumption that the gradient of a loss function can be decomposed into a sum of independent components, where calculating the gradient for a single data point ($\nabla f_i$) is significantly cheaper than calculating the full gradient ($\nabla f$).

However, this assumption fails for several important statistical models. In survival analysis, the Cox partial-likelihood model is the gold standard for predicting time-to-event data. Unlike standard empirical risk minimization (ERM), the gradient for a single individual in the Cox model depends on a cumulative sum of all individuals still "at risk" at that specific time. Consequently, a single stochastic step carries an $O(n)$ complexity, making it nearly as computationally expensive as a full gradient step. As datasets in biostatistics and economics scale to millions of observations and thousands of features, traditional solvers like Newton-Raphson or coordinate descent become computationally prohibitive.

The 2SVRG Framework

To address this bottleneck, the researchers developed 2SVRG (Doubly Stochastic Proximal Gradient Descent). The algorithm is characterized by two distinct layers of randomness designed to mitigate both the variance of the stochastic gradient and the computational cost of the Cox model's structure.

1. Variance Reduction via SVRG

Like the standard Stochastic Variance Reduced Gradient (SVRG) algorithm, 2SVRG utilizes a "control variate" to reduce the noise inherent in stochastic gradients. This allows the algorithm to use a constant step size while maintaining a fast, linear convergence rate, avoiding the slow $O(1/k)$ convergence typically associated with vanilla SGD.

2. MCMC Approximation of Expectations

The primary innovation lies in the "second layer" of stochasticity. The authors reframe the expensive cumulative sum in the Cox gradient as an expectation under a Gibbs distribution. Instead of calculating this sum exactly—which requires $O(n)$ operations—they use Monte-Carlo Markov-Chain (MCMC) algorithms, such as Independent Metropolis-Hastings (IMH) or Importance Sampling (IS), to approximate the expectation using a small number of samples.

Precision Scheduling and Hybridization

A critical component of 2SVRG is the scheduling of the MCMC chain length ($N_k$). During the early stages of optimization, when the parameter estimates are far from the optimum, high-precision gradients are unnecessary. The algorithm starts with very short (cheap) MCMC chains and increases the number of iterations as it nears the solution.

To ensure practical utility, the authors also proposed Hybrid SVRG (HSVRG). Because the required MCMC chain length grows exponentially to maintain linear convergence, it eventually reaches a point where it is more expensive than a standard mini-batch calculation. HSVRG monitors this threshold and automatically switches from MCMC sampling to mini-batch SVRG to maintain optimal efficiency.

Empirical Evaluation

The algorithm was evaluated on several high-dimensional and large-scale datasets:

  • NKI70 and Lymphoma: Standard gene expression datasets for breast cancer and lymphoma patients.
  • Luminal: A high-dimensional dataset featuring over 44,000 expression measurements for 277 patients.
  • Simulated Large-Scale Data: A synthetic dataset ($n=10,000, d=500$) designed to test scalability.

Key Findings

  • Computational Efficiency: When measured by the number of inner products (a proxy for CPU time), 2SVRG and HSVRG variants converged significantly faster than batch methods like L-BFGS-B and FISTA.
  • Robustness: Unlike many traditional Cox solvers (e.g., cocktail or coxnet) that require a "warm start" or a sequence of regularization strengths to converge, 2SVRG is robust enough to minimize a single objective directly from a zero-vector initialization.
  • Theoretical Convergence: The authors proved that 2SVRG maintains a linear convergence rate under strong convexity, matching the theoretical performance of standard SVRG despite the approximation noise introduced by the MCMC layer.

Conclusion and Future Directions

By treating the computational bottlenecks of survival analysis as intractable expectations, 2SVRG provides a scalable path forward for high-dimensional time-to-event modeling. The success of this "doubly stochastic" approach suggests broader applications. The authors suggest that this framework could be extended to Conditional Random Fields (CRFs) and other structured prediction models where gradients involve complex, expensive expectations. This work bridges the gap between MCMC sampling and variance-reduced optimization, offering a powerful toolkit for non-ERM optimization problems.

Summary updated

Abstract

We introduce a doubly stochastic proximal gradient algorithm for optimizing a finite average of smooth convex functions, whose gradients depend on numerically expensive expectations. Our main motivation is the acceleration of the optimization of the regularized Cox partial-likelihood (the core model used in survival analysis), but our algorithm can be used in different settings as well. The proposed algorithm is doubly stochastic in the sense that gradient steps are done using stochastic gradient descent (SGD) with variance reduction, where the inner expectations are approximated by a Monte-Carlo Markov-Chain (MCMC) algorithm. We derive conditions on the MCMC number of iterations guaranteeing convergence, and obtain a linear rate of convergence under strong convexity and a sublinear rate without this assumption. We illustrate the fact that our algorithm improves the state-of-the-art solver for regularized Cox partial-likelihood on several datasets from survival analysis.
BibTeX
@misc{achab2015sgd,
  author = {Massil Achab and Agathe Guilloux and Stéphane Gaïffas and Emmanuel Bacry},
  title = {{SGD with Variance Reduction beyond Empirical Risk Minimization}},
  year = {2015},
  eprint = {1510.04822},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1510.04822},
}
Figure