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

2017/03/07 by Wang, Jialei, Xiao, Lin
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1703.02624

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.

Related

• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk\n Minimization
• A convex combination based primal-dual algorithm with linesearch for general convex-concave saddle point problems
• Randomized Primal-Dual Methods with Adaptive Step Sizes
• Dual optimization for convex constrained objectives without the gradient-Lipschitz assumption
• A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm