@techreport{wang2017exploiting,
author = {Wang, Jialei and Xiao, Lin},
title = {Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms},
year = {2017},
month = {March},
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.},
url = {http://approjects.co.za/?big=en-us/research/publication/exploiting-strong-convexity-data-primal-dual-first-order-algorithms/},
number = {MSR-TR-2017-13},
}