- This event has passed.
Polynomial-time algorithms are not always welcome – sparse PCA as a case study (Learning club talk by Dan Vilenchik from Ben-Gurion University)
October 27, 2019 @ 12:00 pm - 1:00 pm IST
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
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.