Exponential Screening and Optimal Rates of Sparse Estimation

• Activity Number: 327
• Type: Invited
• Date/Time: Tuesday, August 2, 2011 : 10:30 AM to 12:20 PM
• Sponsor: IMS
• Author(s): Philippe Rigollet*+ and Alexandre Tsybakov
• Companies: Princeton University and Laboratoire de Statistique, CREST
• Keywords: high-dimensional regression ; aggregation ; adaptation ; sparsity ; sparsity oracle inequalities ; minimax rates

Abstract

We consider a general, non necessarily linear, regression problem with Gaussian noise and study an aggregation problem that consists in finding a linear combination of approximating functions, which is at the same time sparse and has small mean squared error (MSE). We introduce a new estimation procedure, called Exponential Screening (ES) that shows remarkable adaptation properties: it adapts to the linear combination that optimally balances MSE and sparsity, whether the latter is measured in terms of the number of non-zero entries in the combination or in terms of the global weight of the combination. The power of this adaptation result is illustrated by showing that ES solves optimally and simultaneously all the problems of aggregation in Gaussian regression considered previously. Tight minimax lower bounds establish optimal rates of sparse estimation and that the ES procedure is optimal. Finally, a numerical implementation of ES that results in a stochastic greedy algorithm is discussed and compared to state-of-the-art procedures for sparse estimation.