Accelerated dual-averaging primal-dual method for composite convex minimization

Conghui Tan, Yuqiu Qian, Shiqian Ma, Tong Zhang

TL;DR

This paper introduces a new optimization framework that combines the structural benefits of Dual Averaging with the speed of Primal-Dual methods. The resulting algorithms (DAPD and its stochastic version, SDAPD) achieve optimal "accelerated" convergence rates while offering a unique "lazy update" mechanism that makes them significantly faster than existing methods when working with high-dimensional sparse data.

What Problem Does This Paper Address?

In machine learning, we often need to minimize a "composite" function: $f(Ax) + g(x)$. Here, $f$ usually represents the data fit (like least squares), and $g$ is a regularizer (like the Lasso's $L_1$ penalty) that promotes specific structures like sparsity.

Currently, researchers face a trade-off:

  1. Dual Averaging (DA) is great at promoting sparsity in the solution and handling sparse data, but it often converges slowly.
  2. Proximal Gradient Methods (PGM) and their accelerated versions are fast but can be computationally expensive on sparse data because their "acceleration" steps often require updating every single feature in every iteration—even if the data itself is mostly zeros.

The authors aim to bridge this gap: Can we create an algorithm that is theoretically "optimal" (accelerated) but practically efficient for the sparse, high-dimensional datasets common in industrial ML?

Methods

The authors propose two main algorithms:

  • DAPD (Dual-Averaging Primal-Dual): A deterministic method that uses a primal-dual hybrid approach. Unlike standard methods that only look at the current gradient, DAPD uses a weighted average of all past dual variables (gradients) to update the primal variable.
  • SDAPD (Stochastic DAPD): A version designed for "finite-sum" problems (where you have $n$ data samples). It updates only one random coordinate of the dual variable per iteration, drastically reducing the cost per step.

The "Aha!" Innovation: The real breakthrough is a novel mathematical decomposition. The authors show that the "sum of gradients" in their dual-averaging step can be split into two sequences that can be updated "lazily." This means if a feature in your data is zero, the algorithm can skip updating that feature's internal state for many iterations and "catch up" only when that feature finally appears in a non-zero data point. This reduces the per-iteration complexity from $O(d)$ to $O(\rho d)$, where $\rho$ is the sparsity ratio (often $< 1\%$).

Datasets

The researchers evaluated their methods using:

  • Synthetic Data: Ridge regression problems to test convergence under varying condition numbers ($\lambda$).
  • Real-World Benchmarks:
    • colon-cancer: A small, dense dataset ($n=62, d=2,000$).
  • w8a: A medium sparse dataset ($n=49,749, d=300, \rho=3.88\%$).
  • rcv1: A large, highly sparse text dataset ($n=20,242, d=47,236, \rho=0.16\%$).

Key Insights and Ideas

  • Acceleration without Density: Most accelerated stochastic methods (like SPDC or Katyusha) lose their edge on sparse data because their extrapolation steps are "dense" (they touch every feature). DAPD proves you can have acceleration and "lazy" sparse updates simultaneously.
  • Dual Averaging as a Computational Tool: Usually, Dual Averaging is praised for solution sparsity (getting more zeros in the final $x$). This paper highlights its value for algorithmic efficiency—it provides a cleaner way to manage historical gradient information than standard gradient descent.
  • Optimal Complexity: SDAPD matches the theoretical lower bound for stochastic first-order methods ($O(n + \sqrt{n\kappa} \log(1/\epsilon))$), meaning you aren't sacrificing theoretical guarantees for these practical speedups.

Key Results

  • Wall-Clock Speedup: On the highly sparse rcv1 dataset, SDAPD was orders of magnitude faster than competitors like SPDC and ProxSGD. While SPDC took ~21 seconds per epoch, SDAPD took only ~0.2 seconds.
  • Linear Convergence: In strongly convex settings (like Ridge Regression), DAPD and SDAPD converge linearly, outperforming non-accelerated methods like RDA and ProxSVRG as the problem becomes more difficult (smaller $\lambda$).
  • Better Sparsity: Compared to the popular RDA (Regularized Dual Averaging), SDAPD consistently produced solutions with a lower proportion of non-zero entries, likely due to its increasing primal step sizes which strengthen the regularization effect over time.

Limitations and Future Work

  • Separability Requirement: The "lazy update" trick for sparse data currently requires the regularizer $g(x)$ to be separable (meaning $g(x) = \sum g_j(x_j)$). While this covers $L_1, L_2,$ and Huber penalties, it might not directly apply to complex group-sparsity or graph-based penalties.
  • Parameter Tuning: Like many accelerated methods, the algorithm's performance is sensitive to the choice of step sizes ($\eta, \tau, \beta$), though the authors provide theoretical formulas for these based on the problem's smoothness and strong convexity.
  • Extension to Non-Convexity: The current proof and logic are strictly for convex minimization; extending this "sparse acceleration" to deep learning (non-convex) remains an open challenge.

Summary updated

Abstract

Dual averaging-type methods are widely used in industrial machine learning applications due to their ability to promoting 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.
BibTeX
@inproceedings{tan2020accelerated,
  author = {Conghui Tan and Yuqiu Qian and Shiqian Ma and Tong Zhang},
  title = {{Accelerated dual-averaging primal-dual method for composite convex minimization}},
  booktitle = {Optim. Methods Softw},
  year = {2020},
  url = {https://openreview.net/forum?id=L7sqoxWQjT},
}

Loading related content...

Figure