Philippe Rigollet - Princeton University

Starts: 4:00 pm on Thursday, October 25, 2012
Ends: 5:00 pm on Thursday, October 25, 2012
Location: MCS 148

Title: Deviation optimal model selection using greedy algorithms. Abstract: A statistical problem of model selection for regression can be simply described as a stochastic optimization problem where the objective is quadratic and the domain finite or countable. To solve this problem it is now known that, contrary to the principle of empirical risk minimization, one should seek a solution in the convex hull of the domain. This idea is implemented by exponential weights that are known to solve the problem in expectation, but they are, surprisingly, sub-optimal in deviation. We propose a new formulation called Q-aggregation that consists in minimizing a penalized version of the original criterion but for which the penalty vanishes at the points of interest. This approach leads to efficient greedy algorithms in the spirit of Frank-Wolfe but for which stronger bounds can be derived.