Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms
Jialei Wang · Lin Xiao

Mon Aug 7th 06:30 -- 10:00 PM @ Gallery #96

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.

Author Information

Jialei Wang (University of Chicago)
Lin Xiao (Microsoft Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors