Online Program Home
  My Program

All Times EDT

Abstract Details

Activity Number: 586 - Theoretical Investigations on Discrete Structure Recovery
Type: Topic Contributed
Date/Time: Thursday, August 6, 2020 : 3:00 PM to 4:50 PM
Sponsor: IMS
Abstract #309668
Title: Iterative Algorithm for Discrete Structure Recovery
Author(s): Anderson Ye Zhang* and Chao Gao
Companies: University of Pennsylvania and University of Chicago
Keywords: k-means clustering; approximate ranking; high-dimensional statistics; Hamming distance; variable selection
Abstract:

We propose a general modeling and algorithmic framework for discrete structure recovery that can be applied to a wide range of problems. Under this framework, we are able to study the recovery of clustering labels, ranks of players, and signs of regression coefficients from a unified perspective. A simple iterative algorithm is proposed for discrete structure recovery, which generalizes methods including Lloyd's algorithm and the iterative feature matching algorithm. A linear convergence result for the proposed algorithm is established in this paper under appropriate abstract conditions on stochastic errors and initialization. We illustrate our general theory by applying it on three representative problems: clustering in Gaussian mixture model, approximate ranking, and sign recovery in compressed sensing, and show that minimax rate is achieved in each case.


Authors who are presenting talks have a * after their name.

Back to the full JSM 2020 program