Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms

Abstract

We consider empirical risk minimization of linear predictors with convex loss functions. Such problems can be reformulated as convex-concave saddle point problems, and thus are well suitable for primal-dual first-order algorithms. However, primal-dual algorithms often require explicit strongly convex regularization in order to obtain fast linear convergence, and the required dual proximal mapping may not admit closed-form or efficient solution. In this paper, we develop both batch and randomized primal-dual algorithms that can exploit strong convexity from data adaptively and are capable of achieving linear convergence even without regularization. We also present dual-free variants of the adaptive primal-dual algorithms that do not require computing the dual proximal mapping, which are especially suitable for logistic regression.

References in corpus (4)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A first-order primal-dual algorithm with linesearch
• Adaptive Primal-Dual Hybrid Gradient Methods for Saddle-Point Problems
• An optimal randomized incremental gradient method

Cited by in corpus (8)

• Stochastic, Distributed and Federated Optimization for Machine Learning
• A unified variance-reduced accelerated gradient method for convex optimization
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
• A Stochastic Proximal Point Algorithm for Saddle-Point Problems
• An $O(s^r)$-Resolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems
• Breaking the $O(1/\epsilon )$ Optimal Rate for a Class of Minimax Problems
• Strong Convexity for Risk-Averse Two-Stage Models with Fixed Complete Linear Recourse