Hao Yu

joint work with Michael Neely

A primal-dual parallel method with O(1/ε) convergence for constrained composite convex programs

This work considers large scale constrained (composite) convex programs, which are difficult to solve by interior point methods or other Newton-type methods due to the non-smoothness or the prohibitive computation and storage complexity for Hessians and matrix inversions. The conventional Arrow-Hurwicz-Uzawa subgradient method is a parallel algorithm with O(1/ε^2) convergence for constrained convex programs that are possibly non-smooth or non-separable. This work proposes a new primal-dual parallel algorithm with faster O(1/ε) convergence for such challenging constrained convex programs.

Runchao Ma

joint work with Qihang Lin

Iteration Complexity for Constrained Optimization Problem under Local Error Bound and Weak Convexity

This paper considers the constrained optimization problem with functional constraints. We first consider the case when problem is convex and has local error bound condition. Algorithms are proposed when condition number in local error bound is either known or unknown. Iteration complexity is derived to show the benefit coming from local error property. We then consider the case that constrained optimization problem is a weakly convex problem where both objective function and constraint are weakly convex. Algorithm is proposed and corresponding complexity is analyzed.

Yuyuan Ouyang

Lower complexity bounds of first-order methods for some machine learning models

We consider a class of large-scale optimization problems that arise from machine learning applications. In particular, the objective function has rotational invariance with respective decision variables. We show that, given the machine learning model, there exists worst-case datasets that yield lower complexity bounds of first-order methods for the specified model.