On the Complexity Analysis of the Primal Solutions for the Accelerated Randomized Dual Coordinate Ascent

Huan Li, Zhouchen Lin

Abstract

Dual first-order methods are essential techniques for large-scale constrained convex optimization. However, when recovering the primal solutions, we need $T(\epsilon^{-2})$ iterations to achieve an $\epsilon$-optimal primal solution when we apply an algorithm to the non-strongly convex dual problem with $T(\epsilon^{-1})$ iterations to achieve an $\epsilon$-optimal dual solution, where $T(x)$ can be $x$ or $\sqrt{x}$. In this paper, we prove that the iteration complexity of the primal solutions and dual solutions have the same $O(1/\sqrt{\epsilon})$ order of magnitude for the accelerated randomized dual coordinate ascent. When the dual function further satisfies the quadratic functional growth condition, by restarting the algorithm at any period, we establish the linear iteration complexity for both the primal solutions and dual solutions even if the condition number is unknown. When applied to the regularized empirical risk minimization problem, we prove the iteration complexity of $O(n \log n + \sqrt{n/\epsilon})$ in both primal space and dual space, where $n$ is the number of samples. Our result removes the $\log(1/\epsilon)$ factor compared with methods based on smoothing/regularization or Catalyst reduction. To our knowledge, this is the first time that the optimal $O(\sqrt{n/\epsilon})$ iteration complexity in the primal space is established for dual coordinate ascent-based stochastic algorithms.

Introduction

In large-scale machine learning and engineering, optimization problems are frequently solved via their "dual" formulations. Dual first-order methods are often more computationally tractable than their primal counterparts, especially in constrained convex optimization. However, a persistent theoretical and practical bottleneck has been the "primal recovery" gap: while an algorithm might solve the dual problem to an accuracy of $\epsilon$ in $T$ iterations, recovering a primal solution of the same accuracy often required $T^2$ iterations.

Previous attempts to bridge this gap relied on smoothing techniques or complex regularization schemes (like Catalyst reduction), which introduced an additional $\log(1/\epsilon)$ overhead to the iteration complexity. This paper demonstrates that this "log tax" is not inherent. By analyzing the Accelerated Randomized Dual Coordinate Ascent (ARDCA) framework, the authors prove that primal solutions can achieve the same $O(1/\sqrt{\epsilon})$ convergence rate as dual solutions through a specific weighted averaging technique.

Methodology

Accelerated Randomized Dual Coordinate Ascent (ARDCA)

The core of the proposed approach is the ARDCA algorithm, which the authors adapt to ensure efficient primal recovery. The methodology relies on three primary innovations:

  1. Primal Averaging: Rather than relying on the final iterate of the dual algorithm to reconstruct the primal solution, the authors employ a weighted average of the primal iterates. They prove that this specific averaging scheme allows the primal gap to diminish at the same optimal rate as the dual objective.
  2. Restart Scheme: For problems exhibiting "quadratic functional growth"—a property common in Support Vector Machines (SVM) and least absolute deviation problems—the authors introduce a restarting variant of ARDCA. This allows the algorithm to achieve accelerated linear convergence without requiring prior knowledge of the problem's condition number.
  3. Two-Step Initialization for ERM: When applied to Empirical Risk Minimization (ERM), the authors utilize a non-accelerated initialization step to find a stable starting point, followed by the accelerated ARDCA phase. This ensures the $O(n \log n)$ initial cost is balanced by the subsequent $O(\sqrt{n/\epsilon})$ acceleration.

Key Theoretical Insights

Closing the Complexity Gap

The primary contribution is the proof that the iteration complexity for primal and dual solutions is of the same order: $O(1/\sqrt{\epsilon})$. This eliminates the historical $T^2$ penalty for primal recovery. By avoiding the "smoothing" of nonsmooth loss functions, the authors remove the $\log(1/\epsilon)$ factor that has characterized previous state-of-the-art methods.

Parameter-Free Acceleration

Many accelerated methods require precise estimates of the data's condition number ($\kappa$) to tune hyperparameters. The proposed restart scheme is robust and parameter-free, achieving linear convergence automatically for a broad class of problems, including those with nonsmooth losses like $L_1$ regression.

Optimality in ERM

For regularized ERM problems with $n$ samples, the paper establishes a complexity of $O(n \log n + \sqrt{n/\epsilon})$. This matches the theoretical lower bounds for this class of stochastic algorithms, marking the first time such optimality has been proven for dual coordinate ascent-based methods in the primal space.

Empirical Validation

The authors validated their theoretical findings using numerical experiments on sparse recovery problems, such as Lasso and compressed sensing.

  • Experimental Setup: Synthetic datasets were generated with $t=1000$ features and $n=200$ samples. The algorithm was tested against various noise profiles, including Gaussian noise (for $L_2$ loss) and sparse outliers (for $L_1$ loss).
  • Performance: The "ARDCA-restart" and "ARDCA-average" variants consistently outperformed standard Stochastic Dual Coordinate Ascent (SDCA) and other accelerated methods like ASDCA and APCG. The experiments confirmed that the primal gap reduces significantly faster using the proposed averaging and restarting techniques.

Conclusion and Future Work

This research provides a definitive complexity analysis for primal recovery in accelerated dual methods. By proving that the primal solution can catch up to the dual solution without extra logarithmic costs, the authors provide a cleaner and more efficient framework for large-scale optimization.

While the current analysis assumes $\mu$-strong convexity for the function $f(x)$, future work may explore extending these optimal primal rates to non-strongly convex functions. Additionally, the authors suggest that applying this complexity analysis to distributed optimization environments—where communication costs are a primary bottleneck—could yield significant practical benefits.

Summary updated

Abstract

Dual first-order methods are essential techniques for large-scale constrained convex optimization. However, when recovering the primal solutions, we need $T(ε^{-2})$ iterations to achieve an $ε$-optimal primal solution when we apply an algorithm to the non-strongly convex dual problem with $T(ε^{-1})$ iterations to achieve an $ε$-optimal dual solution, where $T(x)$ can be $x$ or $\sqrt{x}$. In this paper, we prove that the iteration complexity of the primal solutions and dual solutions have the same $O\left(\frac{1}{\sqrtε}\right)$ order of magnitude for the accelerated randomized dual coordinate ascent. When the dual function further satisfies the quadratic functional growth condition, by restarting the algorithm at any period, we establish the linear iteration complexity for both the primal solutions and dual solutions even if the condition number is unknown. When applied to the regularized empirical risk minimization problem, we prove the iteration complexity of $O\left(n\log n+\sqrt{\frac{n}ε}\right)$ in both primal space and dual space, where $n$ is the number of samples. Our result takes out the $\left(\log \frac{1}ε\right)$ factor compared with the methods based on smoothing/regularization or Catalyst reduction. As far as we know, this is the first time that the optimal $O\left(\sqrt{\frac{n}ε}\right)$ iteration complexity in the primal space is established for the dual coordinate ascent based stochastic algorithms. We also establish the accelerated linear complexity for some problems with nonsmooth loss, i.e., the least absolute deviation and SVM.
BibTeX
@article{li2020complexity,
  author = {Huan Li and Zhouchen Lin},
  title = {{On the Complexity Analysis of the Primal Solutions for the Accelerated Randomized Dual Coordinate Ascent}},
  journal = {J. Mach. Learn. Res.},
  year = {2020},
  url = {https://openreview.net/forum?id=i1UlQpKUknt},
}
Figure