TY - GEN
T1 - Exploiting strong convexity from data with primal-dual first-order algorithms
AU - Wang, Jialei
AU - Xiao, Lin
N1 - Publisher Copyright:
© Copyright 2017 by the authors(s).
PY - 2017
Y1 - 2017
N2 - We consider empirical risk minimization of linear predictors with convex loss functions. Such problems can be reformulated as convex-concave saddle point problems and solved by 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 adaptive primal-dual algorithms that do not need the dual proximal mapping, which are especially suitable for logistic regression.
AB - We consider empirical risk minimization of linear predictors with convex loss functions. Such problems can be reformulated as convex-concave saddle point problems and solved by 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 adaptive primal-dual algorithms that do not need the dual proximal mapping, which are especially suitable for logistic regression.
UR - http://www.scopus.com/inward/record.url?scp=85048527067&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85048527067
T3 - 34th International Conference on Machine Learning, ICML 2017
SP - 5648
EP - 5671
BT - 34th International Conference on Machine Learning, ICML 2017
PB - International Machine Learning Society (IMLS)
Y2 - 6 August 2017 through 11 August 2017
ER -