Pathwise Calibrated Active Shooting Algorithm with Application to Semiparametric Graph Estimation

• Activity Number: 579
• Type: Invited
• Date/Time: Thursday, August 7, 2014 : 8:30 AM to 10:20 AM
• Sponsor: JCGS-Journal of Computational and Graphical Statistics
• Author(s): Tuo Zhao and Han Liu*+
• Companies: Johns Hopkins University and Princeton University
• Keywords: High dimensional inference ; semiparametric sparsity ; graphical model ; nonconvexity ; Rates of convergence

Abstract

The pathwise coordinate optimization -- combined with the active set strategy -- is arguably one of the most popular computational frameworks for high dimensional problems. It is conceptually simple, easy to implement, and applicable to a wide range of convex and nonconvex problems. However, there is still a gap between its theoretical justification and practical success: For high dimensional convex problems, existing theories only show sublinear rates of convergence; For nonconvex problems, almost no theory on the rates of convergence exists. To bridge this gap, we propose a novel unified computational framework named PICASA for pathwise coordinate optimization. The main difference between PICASA and existing pathwise coordinate descent methods is that we exploit a proximal gradient pilot to identify an active set. Such a modification, though simple, has profound impact: with high probability, PICASA attains a global geometric rate of convergence to a unique sparse local solution with good statistical properties (e.g. minimax optimality, oracle property) for solving a large family of convex and nonconvex problems. We provide thorough numerical results to back up the theory.