Dynamic Visualization and Fast Computation for Convex Clustering via Algorithmic Regularization

• Activity Number: 329 - SLDS Student Paper Awards
• Type: Topic Contributed
• Date/Time: Tuesday, July 30, 2019 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Learning and Data Science
• Author(s): Michael Weylandt* and John Nagorski and Genevera Allen
• Companies: Rice University and Rice University, Department of Statistics and Rice University
• Keywords: Clustering; Optimization; Algorithmic Regularization; Visualization; Dendrograms; Convex Clustering

Abstract

We introduce algorithmic regularization, a novel approach to efficient computation of the entire solution path of penalized estimators using an iterative one-step approximation scheme. The effectiveness of algorithmic regularization is illustrated with an extended application to convex clustering, where it achieves over a 100-fold speed-up over existing methods while constructing a finer approximation grid than standard methods. These improvements allow creation of a convex-clustering dendrogram and dynamic path-wise visualizations based on modern web technologies. We justify our approach with a novel theoretical result, guaranteeing global convergence of the approximate path to the exact path under easily-checked non-data-dependent assumptions. Finally, we will discuss the application of algorithmic regularization to other problems in machine learning, and discuss some future directions. Our methods are implemented in the open-source R package clustRviz, available at https://dataslingers.github.io/clustRviz. This talk is based on joint work with Genevera Allen, John Nagorski, and Yue Hu.