Utilizing Second Order Information in Minibatch Stochastic Variance Reduced Proximal Iterations

Jialei Wang, Tong ZhangJMLR 2019

TL;DR

This paper introduces MB-SVRP, a novel optimization algorithm that efficiently combines first-order variance reduction techniques with second-order (Hessian) information. MB-SVRP achieves improved iteration complexity for empirical risk minimization problems, particularly for large-scale machine learning tasks, by leveraging sub-sampled second-order information without the computational cost of full Hessian inversion.

What Problem Does This Paper Address?

The paper addresses the challenge of efficiently solving large-scale finite-sum optimization problems, common in machine learning, of the form:

$$ \min_w f(w) := \frac{1}{n} \sum_{i=1}^n f_i(w) $$

Specifically, the focus is on regularized loss minimization of linear predictors, where $f_i(w) = l(w^T x_i; b_i) + \frac{\lambda}{2} ||w||^2$. While first-order methods like SVRG are efficient for such problems, they can be slow when the condition number (ratio of smoothness to strong convexity) is large. Second-order methods (like Newton's method) can achieve faster convergence by using Hessian information, but computing and inverting the full Hessian is computationally prohibitive for large datasets. Existing approaches that try to incorporate second-order information often still suffer from high per-iteration costs or lack theoretical guarantees. This paper aims to bridge this gap by developing an algorithm that effectively uses sub-sampled second-order information to accelerate convergence while maintaining low per-iteration complexity.

Methods

The core contribution is the MB-SVRP (Minibatch Stochastic Variance Reduced Proximal Iterations) algorithm. Its key innovations are:

  • Simultaneous Incorporation of First and Second-Order Information: MB-SVRP combines variance-reduced first-order gradients (similar to SVRG) with sub-sampled second-order (Hessian) information. This is achieved by approximating the Hessian using a minibatch of data.
  • Acceleration with Inexact Minimization: The algorithm employs an acceleration technique (inspired by Nesterov's momentum) and allows for inexact solutions to the subproblems. This enables the use of larger minibatch sizes without slowing down convergence, a common issue in standard minibatch methods.
  • Preconditioned SVRG: The paper shows that MB-SVRP can be viewed as a preconditioned minibatch SVRG update. The preconditioning matrix is derived from the sub-sampled Hessian, effectively transforming the problem into a better-conditioned one.
  • Extension to Composite Optimization: The proposed framework can be naturally extended to handle non-smooth composite optimization problems by incorporating proximal operators.

Datasets

The paper evaluates the proposed MB-SVRP algorithm on several real-world datasets for both regression and classification tasks. These include:

  • For Logistic Regression: codrna, covtype, svmguide3, synthetic-c.
  • For Ridge Regression: cadata, spacega, synthetic-r, year.

A synthetic dataset for each task was also generated to control problem properties like ill-conditioning.

Key Insights and Ideas

  • Leveraging Sub-sampled Hessians is Key: The paper demonstrates that by intelligently using sub-sampled Hessian information, one can achieve faster convergence than pure first-order methods, especially for ill-conditioned problems, without incurring the full cost of second-order methods.
  • Preconditioning as a Transformation: Viewing the MB-SVRP update as a preconditioned SVRG update provides a powerful theoretical lens. This transformation effectively improves the condition number of the problem, leading to faster convergence.
  • Acceleration Enables Larger Minibatches: The use of acceleration techniques is crucial for allowing larger minibatch sizes. This is a significant advantage over standard minibatch methods where increasing batch size often leads to slower convergence.
  • Theoretical Guarantees for Practical Performance: The paper provides theoretical guarantees for improved iteration complexity, which are then supported by empirical results showing MB-SVRP outperforming existing methods.

Key Results

  • Improved Iteration Complexity: MB-SVRP achieves provably better iteration complexity than state-of-the-art methods under suitable conditions, particularly for quadratic convex objectives (global fast convergence) and general convex objectives (local fast convergence).
  • Empirical Advantage: Experiments show that MB-SVRP significantly outperforms existing methods (SVRG, SDCA, SAGA, L-BFGS) on various datasets, especially when the regularization parameter (and thus condition number) is small. For instance, in Figure 2, MB-SVRP shows substantial gains when $\lambda = 10^{-2}/n$.
  • Effective for Composite Optimization: The method also demonstrates strong performance on non-smooth composite optimization problems, outperforming its prox-SVRG counterparts.
  • Sensitivity to Minibatch Size: The algorithm performs well across a range of minibatch sizes, often converging faster than SVRG even with larger batches.

Limitations and Future Work

  • Local Convergence Analysis: For non-quadratic convex objectives, the theoretical analysis is local, assuming solutions are within a bounded region near the optimum. The authors suggest future work to improve the size of this local region.
  • Hessian Lipschitz Condition: The theoretical analysis relies on a Hessian Lipschitz condition, which is common for second-order methods but not required for first-order methods. However, this condition is often satisfied by popular loss functions.
  • Parameter Tuning: While the algorithm is shown to work for a range of parameters, optimal parameter choices might depend on properties of the Hessian at the optimum. The authors discuss strategies for choosing conservative parameters.
  • Further Investigation of Nested Approaches: The paper mentions the possibility of using MB-SVRP to solve its own subproblems (nested approach), which could further reduce dependency on the condition number but might increase dependency on data properties and complexity. This is left for future research.

Summary updated

BibTeX
@article{wang2019utilizing,
  author = {Jialei Wang and Tong Zhang},
  title = {{Utilizing Second Order Information in Minibatch Stochastic Variance Reduced Proximal Iterations}},
  journal = {J. Mach. Learn. Res.},
  year = {2019},
}
Figure