Speaker: Adams Wei Yu
We proposed a doubly stochastic primal-dual coordinate optimization
algorithm for regularized empirical risk minimization that can be formulated
as a bilinear saddle-point problem using convex conjugate functions.
Our method randomly samples a block of primal and dual coordinates to update
in each iteration. The convergence of our method is established in both
the solution's distance to optimality and the primal-dual objective gap. We
show that the proposed method has a lower overall complexity than existing
coordinate methods when the data matrix has a factorized structure or the
proximal mapping on each block of coordinates is computationally expensive,
e.g., involves an eigenvalue decomposition. Furthermore, we prove a theoretical
lower bound on the iteration complexity of a family of primal-dual (block)
coordinate methods, including our method, for bilinear saddle-point problems.
A draft of the work can be found in http://arxiv.org/abs/1508.03390.