Primal-Dual Block Generalized Frank-Wolfe.

Qi Lei, Jiacheng Zhuo, Constantine Caramanis, Inderjit S. Dhillon, Alexandros G. DimakisNeurIPS 2019 · OpenReview

Abstract

We propose a generalized variant of Frank-Wolfe algorithm for solving a class of sparse/low-rank optimization problems. Our formulation includes Elastic Net, regularized SVMs and phase retrieval as special cases. The proposed Primal-Dual Block Generalized Frank-Wolfe algorithm reduces the per-iteration cost while maintaining linear convergence rate. The per iteration cost of our method depends on the structural complexity of the solution (i.e. sparsity/low-rank) instead of the ambient dimension. We empirically show that our algorithm outperforms the state-of-the-art methods on (multi-class) classification tasks.

Introduction

In modern machine learning, we frequently encounter high-dimensional problems where the underlying solution possesses a "simple" structure—such as a model with millions of features where only a few hundred are significant (sparsity), or a massive matrix describable by a few underlying factors (low-rank).

Standard optimization tools for these problems often face a difficult trade-off. Projected Gradient Descent (PGD) converges quickly (linearly) but requires an expensive "projection" step in every iteration to maintain constraints. Conversely, the Frank-Wolfe (FW) algorithm avoids expensive projections but typically converges slowly (sub-linearly). Furthermore, calculating the gradient in high dimensions remains a massive bottleneck for standard FW. This paper, presented at NeurIPS 2019, introduces the Primal-Dual Block Generalized Frank-Wolfe (PDBFW) algorithm to achieve the "best of both worlds": a projection-free method that maintains linear convergence with a per-iteration cost scaling with the solution's structural complexity rather than the massive ambient dimension.

Methodology

The PDBFW algorithm is built upon three primary pillars designed to optimize high-dimensional, structured problems:

  • Primal-Dual Reformulation: The problem is transformed into a "saddle-point" formulation involving both primal variables ($x$) and dual variables ($y$).
  • Partial/Block Updates: Instead of updating every dimension in every step, the algorithm performs sparse updates. It uses a "Block Frank-Wolfe" step in the primal space and a greedy coordinate ascent (the Gauss-Southwell rule) in the dual space to select only the most impactful coordinates.
  • Efficient Bookkeeping: By maintaining intermediate values like $Ax$ and $A^\top y$, the algorithm ensures that the computational cost scales with the number of non-zero elements ($s$) rather than the total dimension ($d$). This reduces per-iteration complexity from $O(nd)$ to $O(ns)$.

Crucially, the authors provide theoretical proof that this "lazy" update approach maintains a linear convergence rate, reaching high-accuracy solutions in significantly fewer iterations than standard FW variants.

Experimental Evaluation

The researchers evaluated PDBFW on several standard high-dimensional classification datasets from the LIBSVM repository, including duke breast-cancer, rcv1, news20.binary, and augmented versions of MNIST, ijcnn, and cod-rna using random binning features.

Performance comparison of PDBFW against state-of-the-art methods on IJCNN.RB, cod-rna.RB, and duke breast-cancer datasets.

In empirical tests across these datasets, PDBFW achieved roughly a 10-fold speedup in CPU time compared to state-of-the-art methods like SVRG, Accelerated PGD, and standard Frank-Wolfe. The "winning margin" of the algorithm was found to be proportional to the sparsity of the solution: the sparser the optimal solution, the more dominant PDBFW becomes.

Convergence performance on the MNIST.RB dataset, illustrating the rapid decline of the relative primal objective for PDBFW compared to other methods.

Key Insights and Discussion

The most significant takeaway is that if a final solution is sparse, the algorithm should not have to "touch" every dimension of the data in every step. The complexity becomes dimension-free, depending on the solution's structure rather than the problem's size. The primal-dual framework provides a natural way to "mask" the data and only compute what is strictly necessary.

However, some limitations exist. The current theoretical guarantees are tailored for $\ell_1$ (vector sparsity) and trace norm (matrix low-rank) constraints; extending this to more general polytope constraints remains challenging. Additionally, the algorithm requires tuning hyperparameters like learning rates and relies on objective smoothness and strong convexity for its linear convergence guarantees.

Conclusion

PDBFW successfully bridges the gap between the low iteration cost of Frank-Wolfe and the fast convergence speed of Gradient Descent. With an overall time complexity of $O(s(n + \kappa) \log(1/\epsilon))$, it matches or beats the best-known bounds while offering a significantly lower cost per step in practice.

Summary updated

Abstract

We propose a generalized variant of Frank-Wolfe algorithm for solving a class of sparse/low-rank optimization problems. Our formulation includes Elastic Net, regularized SVMs and phase retrieval as special cases. The proposed Primal-Dual Block Generalized Frank-Wolfe algorithm reduces the per-iteration cost while maintaining linear convergence rate. The per iteration cost of our method depends on the structural complexity of the solution (i.e. sparsity/low-rank) instead of the ambient dimension. We empirically show that our algorithm outperforms the state-of-the-art methods on (multi-class) classification tasks.
BibTeX
@inproceedings{lei2019primal,
  author = {Qi Lei and Jiacheng Zhuo and Constantine Caramanis and Inderjit S. Dhillon and Alexandros G. Dimakis},
  title = {{Primal-Dual Block Generalized Frank-Wolfe.}},
  booktitle = {NeurIPS},
  year = {2019},
  url = {https://openreview.net/forum?id=nKLeawLQnxd},
}
Figure