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, andKDD2010-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