Part of Advances in Neural Information Processing Systems 34 (NeurIPS 2021)
Maria-Luiza Vladarean, Yura Malitsky, Volkan Cevher
We consider the problem of finding a saddle point for the convex-concave objective min, where f is a convex function with locally Lipschitz gradient and g is convex and possibly non-smooth. We propose an adaptive version of the Condat-Vũ algorithm, which alternates between primal gradient steps and dual proximal steps. The method achieves stepsize adaptivity through a simple rule involving \|A\| and the norm of recently computed gradients of f. Under standard assumptions, we prove an \mathcal{O}(k^{-1}) ergodic convergence rate. Furthermore, when f is also locally strongly convex and A has full row rank we show that our method converges with a linear rate. Numerical experiments are provided for illustrating the practical performance of the algorithm.