A Distributed Quasi-Newton Algorithm for Empirical Risk Minimization with Nonsmooth Regularization

Ching-pei Lee, Cong Han Lim, Stephen J. Wright

TL;DR

This paper introduces a novel distributed optimization algorithm that leverages second-order (quasi-Newton) information to efficiently solve large-scale empirical risk minimization (ERM) problems with nonsmooth regularization. The key innovation is a communication-efficient method for approximating and utilizing the Hessian of the smooth part of the objective, leading to significantly faster convergence and reduced communication overhead compared to existing methods, even for non-convex problems.

What Problem Does This Paper Address?

Training machine learning models often involves minimizing a complex objective function, typically an empirical risk minimization (ERM) problem. This usually takes the form of minimizing a sum of losses over a dataset, plus a regularization term to prevent overfitting. When datasets become massive, distributed optimization is essential. However, many advanced optimization techniques, like quasi-Newton methods that use second-order (Hessian) information, are computationally expensive and require significant communication between machines, making them impractical for distributed settings. Existing distributed methods either struggle with nonsmooth regularizers (like L1 regularization, common in feature selection) or don't fully exploit the curvature information of the smooth part of the objective, leading to slower convergence and higher communication costs. This paper aims to bridge this gap by developing a distributed quasi-Newton algorithm that is both communication- and computation-efficient, even for problems with nonsmooth regularization.

Methods

The core of the proposed algorithm is a distributed successive quadratic approximation (SQA) method. At each step, it constructs a subproblem that approximates the original objective with a quadratic function (using a quasi-Newton approximation of the Hessian) plus the original nonsmooth regularizer. The key challenges addressed are:

  • Distributed Hessian Approximation: The paper adapts the Limited-memory Broyden–Fletcher–Goldfarb–Shanno (LBFGS) algorithm for approximating the Hessian. It describes how to maintain and update this approximation efficiently across multiple machines with minimal communication. This involves clever use of compact representations and parallel computation of inner products.
  • Efficient Subproblem Solving: The subproblem, which involves minimizing a quadratic plus a nonsmooth term, is solved using a distributed version of the SpaRSA (Sparse Reconstruction by Separable Approximation) algorithm. This iterative solver is designed to handle the nonsmoothness and is parallelized to reduce computation per machine.
  • Communication Efficiency: The algorithm is designed to minimize communication rounds. It leverages an "allreduce" model (common in MPI) and carefully orchestrates computations so that local work is maximized, and communication is limited to essential steps like gradient aggregation and updates to the Hessian approximation.
  • Line Search: A modified Armijo-type backtracking line search is employed to ensure sufficient decrease in the objective function, which is crucial for convergence guarantees.

Datasets

The paper evaluates its method on several publicly available binary classification datasets:

  • news20
  • epsilon
  • webspam
  • avazu-site

These datasets are standard benchmarks for large-scale machine learning tasks, particularly in the context of logistic regression with L1 regularization.

Key Insights and Ideas

  • Harnessing Curvature in Distributed Settings: The most significant insight is that it's possible to effectively leverage second-order (Hessian) information in a distributed setting for nonsmooth problems, overcoming the communication bottlenecks that typically plague such methods.
  • LBFGS for Distributed Nonsmooth Optimization: Adapting LBFGS for distributed, nonsmooth ERM problems is a novel contribution. The paper shows how to manage the LBFGS approximation efficiently across machines.
  • SpaRSA as an Efficient Subproblem Solver: Using SpaRSA as the distributed solver for the quadratic subproblem is a practical choice that balances accuracy and computational cost.
  • Global Convergence for Non-Strongly Convex Problems: The algorithm achieves global linear convergence for a broad class of problems, including non-strongly convex ones, which is a strong theoretical guarantee. This is a significant improvement over methods that might only offer asymptotic convergence.
  • Potential for Deep Learning: The algorithm's convergence on non-convex problems suggests its applicability to areas like deep learning, where non-convexity is common.

Key Results

  • Significant Speedup: Initial computational results show that the proposed distributed quasi-Newton method (DPLBFGS) significantly improves on communication cost and running time compared to state-of-the-art methods.
  • Orders of Magnitude Faster: For the "epsilon" dataset, the method was orders of magnitude faster, demonstrating the benefit of effectively using curvature information.
  • Communication Efficiency: The algorithm achieves lower communication complexity, particularly for larger datasets, by reducing the number of communication rounds and the amount of data transmitted per round.
  • Robustness to Inexactness: The experiments show that even with inexact solutions to the subproblem (controlled by SpaRSA's stopping criteria), the overall algorithm converges well, with the unit step size often being accepted in practice.

Limitations and Future Work

  • Non-convex Exploration: While the paper mentions convergence on non-convex problems, the empirical evaluation primarily focuses on convex ERM problems (l1-regularized logistic regression). Further exploration of its performance on non-convex applications like deep learning is suggested.
  • Dual Problem Extension: The authors suggest extending their framework to solve the distributed dual ERM problem with a strongly convex primal regularizer, expecting it to outperform existing methods that use only block-diagonal Hessian approximations.
  • Heuristics for L1: Incorporating specific heuristics for L1-regularized problems, similar to those used in other works, could further accelerate the method.

Summary updated

Abstract

We propose a communication- and computation-efficient distributed optimization algorithm using second-order information for solving ERM problems with a nonsmooth regularization term. Current second-order and quasi-Newton methods for this problem either do not work well in the distributed setting or work only for specific regularizers. Our algorithm uses successive quadratic approximations, and we describe how to maintain an approximation of the Hessian and solve subproblems efficiently in a distributed manner. The proposed method enjoys global linear convergence for a broad range of non-strongly convex problems that includes the most commonly used ERMs, thus requiring lower communication complexity. It also converges on non-convex problems, so has the potential to be used on applications such as deep learning. Initial computational results on convex problems demonstrate that our method significantly improves on communication cost and running time over the current state-of-the-art methods.
BibTeX
@inproceedings{lee2018distributed,
  author = {Ching-pei Lee and Cong Han Lim and Stephen J. Wright},
  title = {{A Distributed Quasi-Newton Algorithm for Empirical Risk Minimization with Nonsmooth Regularization}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2018},
  url = {https://openreview.net/forum?id=AysOYTmQMKS},
}
Figure