Introduction: The Communication Bottleneck
In large-scale machine learning, data is frequently distributed across multiple machines. However, the primary bottleneck in these systems is rarely CPU or RAM—it is the network. Synchronizing models between machines is slow and expensive.
Communication cost is driven by two factors:
- The number of communication rounds (how many times machines exchange updates).
- The bytes per round (the size of the payload sent each time).
Most existing methods tackle only one of these factors. Second-order methods reduce the number of rounds but still transmit massive $d$-dimensional vectors (where $d$ is the number of features). Compression techniques send fewer bytes but introduce noise, often requiring more rounds to converge. This paper introduces MADPQN (Manifold-Aware Distributed Proximal Quasi-Newton), an algorithm that slashes communication costs by reducing both rounds and bytes simultaneously.
The MADPQN Algorithm
MADPQN is a two-stage distributed optimization algorithm designed for problems with "partly smooth" regularizers, such as $L_1$ or Group-LASSO. It works by identifying the low-dimensional "manifold" (akin to a sparsity pattern) where the optimal solution resides.
Stage 1: Progressive Manifold Identification
Instead of broadcasting the full $d$-dimensional gradient in every round, MADPQN predicts which features are actually important. Crucially, it does not wait to find the final, perfect manifold. Instead, it progressively identifies smaller and smaller subspaces during the optimization process.
As the algorithm iterates, the number of bytes sent per round drops dramatically from $O(d)$ to $O(|\mathcal{M}^*|)$, where $|\mathcal{M}^*|$ is the dimension of the final manifold (e.g., the number of non-zero features in a sparse model).
Stage 2: Local Acceleration
Once the algorithm is confident it has found the correct manifold, it switches gears. It transitions from a standard quasi-Newton method to a Truncated Semismooth Newton (SSN) method. Operating within this restricted, low-dimensional subspace allows the algorithm to achieve superlinear convergence, reaching high-precision solutions in very few communication rounds.
Datasets and the Power of Sparsity
The authors evaluated MADPQN on several large-scale public datasets across two problem types: $L_1$-regularized Logistic Regression and Group-LASSO-regularized Multinomial Logistic Regression.
The true power of the manifold identification approach becomes obvious when looking at the dataset statistics.
For instance, in the news20 dataset, the original feature space $d$ is over 1.3 million, but the optimal manifold size $|\mathcal{M}^*|$ is merely 506. By identifying this manifold, MADPQN reduces the per-round communication payload by orders of magnitude.
Key Insights and Results
- Exploiting "Partly Smoothness": Many ML regularizers are non-smooth at the origin but smooth along certain manifolds. By identifying this manifold early, the problem can be treated as smooth optimization in a vastly reduced dimensional space.
- Don't Wait, Iterate: Unlike traditional "active set" methods that only switch to a smaller problem after the final set is perfectly identified, MADPQN leverages intermediate manifolds to save communication costs during the search process.
- Unmatched Efficiency: In empirical tests, MADPQN required orders of magnitude fewer bytes to reach the same accuracy as baselines like DPLBFGS, OWLQN, and L-COMM.
- Speed and Precision: Total training time was often an order of magnitude faster than state-of-the-art methods. Because of the superlinear convergence in Stage 2, MADPQN is particularly dominant when high-precision solutions are required.
Limitations and Future Work
While highly effective, the theoretical guarantee for finding the manifold depends on a "non-degeneracy" condition. If this condition fails, the algorithm might not enter Stage 2 (though it still performs efficiently in Stage 1). Additionally, while the loss function can be non-convex, the theory currently requires the regularization term to be convex.
Future directions include extending this approach to non-linear manifolds using Riemannian optimization and applying these techniques to deep learning models that utilize sparsity-inducing norms, such as those used in neural network pruning.
Summary updated