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.,
cocktailorcoxnet) 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