Accelerated nonlinear primal-dual hybrid gradient methods with applications to supervised machine learning
This work addresses a bottleneck in optimization for machine learning practitioners, offering a more efficient method for large-scale problems, though it is incremental as it builds on existing PDHG frameworks.
The authors tackled the problem of expensive stepsize parameter computation in first-order optimization methods for large-scale machine learning by introducing accelerated nonlinear primal-dual hybrid gradient methods, achieving optimal convergence rates with simpler stepsize parameters and demonstrating considerable speed improvements in experiments on logistic regression and matrix games.
The linear primal-dual hybrid gradient (PDHG) method is a first-order method that splits convex optimization problems with saddle-point structure into smaller subproblems. Unlike those obtained in most splitting methods, these subproblems can generally be solved efficiently because they involve simple operations such as matrix-vector multiplications or proximal mappings that are fast to evaluate numerically. This advantage comes at the price that the linear PDHG method requires precise stepsize parameters for the problem at hand to achieve an optimal convergence rate. Unfortunately, these stepsize parameters are often prohibitively expensive to compute for large-scale optimization problems, such as those in machine learning. This issue makes the otherwise simple linear PDHG method unsuitable for such problems, and it is also shared by most first-order optimization methods as well. To address this issue, we introduce accelerated nonlinear PDHG methods that achieve an optimal convergence rate with stepsize parameters that are simple and efficient to compute. We prove rigorous convergence results, including results for strongly convex or smooth problems posed on infinite-dimensional reflexive Banach spaces. We illustrate the efficiency of our methods on $\ell_{1}$-constrained logistic regression and entropy-regularized matrix games. Our numerical experiments show that the nonlinear PDHG methods are considerably faster than competing methods.