Timezone: »

 
Poster
Constant Nullspace Strong Convexity and Fast Convergence of Proximal Methods under High-Dimensional Settings
Ian En-Hsu Yen · Cho-Jui Hsieh · Pradeep Ravikumar · Inderjit Dhillon

Mon Dec 08 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D
in Poster Session and Reception »

State of the art statistical estimators for high-dimensional problems take the form of regularized, and hence non-smooth, convex programs. A key facet of thesestatistical estimation problems is that these are typically not strongly convex under a high-dimensional sampling regime when the Hessian matrix becomes rank-deficient. Under vanilla convexity however, proximal optimization methods attain only a sublinear rate. In this paper, we investigate a novel variant of strong convexity, which we call Constant Nullspace Strong Convexity (CNSC), where we require that the objective function be strongly convex only over a constant subspace. As we show, the CNSC condition is naturally satisfied by high-dimensional statistical estimators. We then analyze the behavior of proximal methods under this CNSC condition: we show global linear convergence of Proximal Gradient and local quadratic convergence of Proximal Newton Method, when the regularization function comprising the statistical estimator is decomposable. We corroborate our theory via numerical experiments, and show a qualitative difference in the convergence rates of the proximal algorithms when the loss function does satisfy the CNSC condition.

[ PDF] 

Author Information

Ian En-Hsu Yen (University of Texas at Austin)
Cho-Jui Hsieh (UCLA)
Pradeep Ravikumar (Carnegie Mellon University)
Inderjit Dhillon (Google & UT Austin)

More from the Same Authors