Online Program Home
  My Program

Abstract Details

Activity Number: 380 - Recent Advances in High-Dimensional Statistics and Computational Methods
Type: Invited
Date/Time: Tuesday, August 1, 2017 : 2:00 PM to 3:50 PM
Sponsor: IMS
Abstract #321971 View Presentation
Title: RESTRICTED STRONG CONVEXITY IMPLIES WEAK SUBMODULARITY
Author(s): Sahand Negahban* and Ethan Elenberg and Rajiv Khanna and Alex Dimakis
Companies: Yale University and UT Austin and UT Austin and UT Austin
Keywords: submodular ; greedy
Abstract:

We connect high-dimensional subset selection and submodular maximization. Our results extend the work of Das and Kempe (2011) from the setting of linear regression to arbitrary objective functions. This connection allows us to obtain strong multiplicative performance bounds on several greedy feature selection methods without statistical modeling assumptions. This is in contrast to prior work that requires data generating models to obtain theoretical guarantees. Our work shows that greedy algorithms perform within a constant factor from the best possible subset-selection solution for a broad class of general objective functions. Our methods allow a direct control over the number of obtained features as opposed to regularization parameters that only implicitly control sparsity.

Joint work with Ethan R. Elenberg, Rajiv Khanna, and Alexandros G. Dimakis


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

Back to the full JSM 2017 program

 
 
Copyright © American Statistical Association