Abstract
Dual averaging-type methods are widely used in industrial machine learning applications due to their ability to promote solution structure (e.g., sparsity) efficiently. In this paper, we propose a novel accelerated dual-averaging primal-dual algorithm for minimizing a composite convex function. We also derive a stochastic version of the proposed method which solves empirical risk minimization, and its advantages on handling sparse data are demonstrated both theoretically and empirically.
Introduction
In modern machine learning, optimization problems often take the form of composite convex minimization: $\min_x f(Ax) + g(x)$. Here, $f$ typically represents a smooth loss function (such as least squares), while $g$ is a regularizer (such as the $L_1$ penalty) designed to promote specific structures like sparsity.
Practitioners currently face a significant trade-off between two classes of algorithms. Dual Averaging (DA) methods are highly effective at promoting sparsity and handling sparse data structures, yet they often suffer from slow convergence rates. Conversely, Proximal Gradient Methods (PGM) and their accelerated variants offer superior convergence speeds but are computationally expensive on high-dimensional sparse data. This expense arises because their acceleration steps typically require updating every feature in every iteration, regardless of whether the data point itself is sparse. This paper introduces a framework that bridges this gap, providing an "optimal" accelerated algorithm that remains practically efficient for sparse, high-dimensional datasets.
The DAPD and SDAPD Framework
The authors propose two primary algorithms to address these challenges:
- DAPD (Dual-Averaging Primal-Dual): A deterministic method utilizing a primal-dual hybrid approach. Unlike standard gradient methods that rely solely on the current gradient, DAPD employs a weighted average of all past dual variables to update the primal variable.
- SDAPD (Stochastic DAPD): A stochastic variant optimized for finite-sum problems involving $n$ data samples. By updating only a single random coordinate of the dual variable per iteration, SDAPD significantly reduces the per-step computational overhead.
The "Lazy Update" Innovation
The core breakthrough of this work is a novel mathematical decomposition of the dual-averaging step. The authors demonstrate that the sum of gradients can be partitioned into two sequences that allow for "lazy updates." In practice, if a specific feature in a dataset is zero, the algorithm can skip updating that feature's internal state for multiple iterations. The state is only "caught up" when the feature eventually appears in a non-zero data point. This mechanism reduces per-iteration complexity from $O(d)$ to $O(\rho d)$, where $\rho$ is the sparsity ratio—often less than 1% in industrial applications.
Theoretical Complexity
SDAPD is not just a practical heuristic; it matches the theoretical lower bound for stochastic first-order methods. It achieves a complexity of $O(n + \sqrt{n\kappa} \log(1/\epsilon))$, where $\kappa$ is the condition number. This ensures that the algorithm provides the best possible theoretical convergence rates without sacrificing the efficiency required for large-scale sparse data.
Empirical Results
The researchers evaluated the proposed methods against synthetic ridge regression problems and real-world benchmarks, including the colon-cancer, w8a, and rcv1 datasets.
- Wall-Clock Efficiency: On the highly sparse
rcv1dataset ($n=20,242, d=47,236, \rho=0.16\%$), SDAPD outperformed competitors like SPDC and ProxSGD by orders of magnitude. While SPDC required approximately 21 seconds per epoch, SDAPD completed the same task in roughly 0.2 seconds. - Convergence and Sparsity: In strongly convex settings, both DAPD and SDAPD exhibited linear convergence, outperforming non-accelerated methods like RDA and ProxSVRG as problem difficulty increased. Furthermore, SDAPD consistently produced solutions with higher sparsity (fewer non-zero entries) than the popular Regularized Dual Averaging (RDA) method, likely due to increasing primal step sizes that enhance the regularization effect over time.
Limitations and Future Work
While the framework offers significant advantages, certain constraints remain. The "lazy update" mechanism currently requires the regularizer $g(x)$ to be separable (e.g., $L_1$ or $L_2$ penalties). Complex penalties like group-sparsity or graph-based regularizers may not yet benefit from this specific speedup. Additionally, the algorithm's performance is sensitive to step-size parameters, and the current theoretical framework is limited to convex problems. Extending these sparse acceleration techniques to non-convex domains, such as deep learning, remains a promising area for future research.
Summary updated