A first-order primal-dual algorithm with linesearch
This work improves the practical efficiency of primal-dual algorithms for convex optimization, particularly for regularized least squares, by reducing computational cost per iteration.
The paper introduces a linesearch for a primal-dual method that requires updating only one variable per iteration, achieving an ergodic O(1/N) convergence rate under standard assumptions, with improved rates for strongly convex cases, and demonstrates efficiency through numerical experiments.
The paper proposes a linesearch for a primal-dual method. Each iteration of the linesearch requires to update only the dual (or primal) variable. For many problems, in particular for regularized least squares, the linesearch does not require any additional matrix-vector multiplications. We prove convergence of the proposed method under standard assumptions. We also show an ergodic $O(1/N)$ rate of convergence for our method. In case one or both of the prox-functions are strongly convex, we modify our basic method to get a better convergence rate. Finally, we propose a linesearch for a saddle point problem with an additional smooth term. Several numerical experiments confirm the efficiency of our proposed methods.