Limited-memory common-directions method for large-scale optimization: convergence, parallelization, and distributed optimization

Ching-Pei Lee, Po-Wei Wang, Chih-Jen LinMath. Program. Comput 2022 · DOI · OpenReview

Abstract

Large-scale optimization often requires balancing the low per-iteration cost of first-order methods with the rapid convergence of second-order methods. This paper introduces a "limited-memory common-directions" (L-CommDir) framework that bridges this gap. By restricting optimization to a low-dimensional, intelligently chosen subspace, the algorithm achieves optimal theoretical convergence rates while maintaining high scalability for massive machine learning problems. The method is particularly effective in parallel and distributed settings due to its reliance on dense matrix operations and reduced communication overhead.

Introduction

In the domain of large-scale optimization, practitioners typically choose between two extremes. First-order methods, such as Gradient Descent, are computationally inexpensive per iteration but often require many steps to reach convergence. Conversely, second-order methods like Newton's method converge in fewer iterations but incur high costs due to the calculation and inversion of the Hessian matrix.

Modern large-scale datasets introduce additional challenges: sparsity and communication bottlenecks. Sparse data can create memory access inefficiencies, while distributed environments are often limited by the speed of transmitting large gradient vectors across networks. This research proposes a method that combines the efficiency of first-order updates with the convergence properties of second-order methods, optimized for modern hardware and distributed architectures.

Methodology

The L-CommDir framework performs optimization within a low-dimensional subspace (a "manifold") at each iteration.

Subspace Construction

Instead of navigating the full $n$-dimensional parameter space, the algorithm identifies a small set of "common directions" ($m \ll n$, typically $2 \le m \le 20$). These directions generally include the current gradient and historical information, such as previous update steps or gradient differences.

Subspace Newton Steps

Within this $m$-dimensional subspace, the algorithm applies a full Newton method. Due to the minimal dimensionality, solving the resulting Newton system is computationally negligible.

Structural Efficiency

For common loss functions like Logistic Regression or Support Vector Machines (SVMs), the authors developed specialized implementation techniques. These allow for updating the necessary matrices without explicitly forming the full Hessian, keeping the per-iteration cost comparable to first-order methods.

Parallel and Distributed Design

The core operations are formulated as dense matrix-matrix products. Unlike sparse operations, these are compute-bound and scale efficiently on multicore CPUs. In distributed settings, nodes only need to communicate $O(m^2)$ values—a significant reduction compared to the $O(n)$ vectors required by traditional methods.

Experimental Evaluation

The method was evaluated across a diverse range of datasets, from standard benchmarks to massive industrial datasets:

  • Small/Medium: a9a, real-sim, news20, rcv1t.
  • Large-scale: yahoo-japan, yahoo-korea.
  • Massive/Distributed: url, epsilon, webspam, and KDD2010-a (8.4 million instances, 20 million features).

Key Insights

  • Optimal Subspace Dimension: Theoretical analysis reveals that a subspace of dimension two (containing the gradient and a momentum term) is sufficient to achieve optimal convergence rates associated with accelerated gradient methods.
  • Hardware-Aware Computation: By transforming sparse data operations into dense matrix kernels, the algorithm leverages the strengths of modern hardware, which favors contiguous memory access.
  • Communication Efficiency: The method trades minimal local computation for a drastic reduction in network traffic, making it ideal for cloud-based distributed optimization.
  • Monotonic Convergence: Unlike some accelerated methods that exhibit oscillatory behavior, L-CommDir is a strict descent algorithm, ensuring improvement in the objective value at every step.

Results

Empirical results demonstrate that the L-CommDir-BFGS variant consistently outperforms standard Accelerated Gradient (AG) methods on single-core tests, often reaching high precision orders of magnitude faster. In multicore environments, the method exhibits superior speedup compared to state-of-the-art packages like Multicore-LIBLINEAR. On the massive KDD2010-a dataset, the approach required significantly fewer communication rounds than traditional Newton-CG methods, highlighting its suitability for large-scale distributed tasks.

Conclusion and Future Work

The L-CommDir framework provides a robust solution for large-scale smooth optimization. Future research directions include extending the framework to non-smooth problems (e.g., $L_1$ regularization), exploring non-linear manifolds for subspace selection, and integrating regularization terms directly into the subproblem solvers.

Summary updated

Abstract

In this paper, we present a limited-memory common-directions method for smooth optimization that interpolates between first- and second-order methods. At each iteration, a subspace of a limited dimension size is constructed using first-order information from previous iterations, and an efficient Newton method is deployed to find an approximate minimizer within this subspace. With properly selected subspace of dimension as small as two, the proposed algorithm achieves the optimal convergence rates for first-order methods while remaining a descent method, and it also possesses fast convergence speed on nonconvex problems. Since the major operations of our method are dense matrix-matrix operations, the proposed method can be efficiently parallelized in multicore environments even for sparse problems. By wisely utilizing historical information, our method is also communication-efficient in distributed optimization that uses multiple machines as the Newton steps can be calculated with little communication. Numerical study shows that our method has superior empirical performance on real-world large-scale machine learning problems.
BibTeX
@article{lee2022limited,
  author = {Ching-Pei Lee and Po-Wei Wang and Chih-Jen Lin},
  title = {{Limited-memory common-directions method for large-scale optimization: convergence, parallelization, and distributed optimization}},
  journal = {Math. Program. Comput.},
  year = {2022},
  doi = {10.1007/s12532-022-00219-z},
}
Figure