Polynomial-time algorithms are not always welcome – sparse PCA as a case study (Learning club talk by Dan Vilenchik from Ben-Gurion University)

Title: Polynomial-time algorithms are not always welcome – sparse PCA as a case study

When: October 27, Sunday, 12:00

Where: Gonda building, room 101

Abstract:

The taxing computational effort that is involved in solving some high-dimensional statistical problems, in particular problems involving non-convex optimization, has popularized the development and analysis of  algorithms that run efficiently (polynomial-time) but with no general guarantee on consistency.  In light of the ever increasing compute power and decreasing costs, a more useful characterization of algorithms is by their ability to  calibrate the invested computational effort with relevant characteristics of the input at hand. For example, design an algorithm that always guarantees consistency by increasing the run-time as the SNR weakens.