In a regression setup with deterministic design, we study the pure aggregation problem and introduce a natural extension from the Gaussian distribution to distributions in the exponential family. While this extension bears strong connections with generalized linear models, it does not require identifiability of the parameter or even that the model on the systematic component is true. It is shown that this problem can be solved by constrained and/or penalized likelihood maximization and we derive sharp oracle inequalities that hold both in expectation and with high probability. Finally all the bounds are proved to be optimal in a minimax sense.

@misc {Rig12,
AUTHOR = {Rigollet, P.},
TITLE = {Kullback-Leibler aggregation and misspecified generalized linear models},
YEAR = {2012},
NOTE = {To appear in the Annals of Statistics},
}

Motivated by problems of anomaly detection, this paper implements the Neyman-Pearson paradigm to deal with asymmetric errors in binary classification with a convex loss. Given a finite collection of classifiers, we combine them and obtain a new classifier that satisfies simultaneously the two following properties with high probability: (i) its probability of type I error is below a pre-specified level and (ii), it has probability of type II error close to the minimum possible. The proposed classifier is obtained by solving an optimization problem with an empirical objective and an empirical constraint. New techniques to handle such problems are developed and have consequences on chance constrained programming.

@article {RigTon11,
AUTHOR = {Rigollet, P. and Tong, X.},
TITLE = {Neyman-Pearson classification, convexity and stochastic constraints},
JOURNAL = {J. Mach. Learn. Res.},
FJOURNAL = {Journal of Machine Learning Research (JMLR)},
VOLUME = {12},
YEAR = {2011},
PAGES = {2831-2855 (electronic)},
}

In high-dimensional linear regression, the goal pursued here is to estimate an unknown regression function using linear combinations of a suitable set of covariates. One of the key assumptions for the success of any statistical procedure in this setup is to assume that the linear combination is sparse in some sense, for example, that it involves only few covariates. We consider a general, non necessarily linear, regression with Gaussian noise and study a related question that is to find 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 \emph{Exponential Screening} 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 ($\ell_0$ norm) or in terms of the global weight of the combination ($\ell_1$ norm). The power of this adaptation result is illustrated by showing that Exponential Screening solves optimally and simultaneously all the problems of aggregation in Gaussian regression that have been discussed in the literature. Moreover, we show that the performance of the Exponential Screening estimator cannot be improved in a minimax sense, even if the optimal sparsity is known in advance. The theoretical and numerical superiority of Exponential Screening compared to state-of-the-art sparse procedures is also discussed.

@article {RigTsy11,
AUTHOR = {Rigollet, P. and Tsybakov, A.},
TITLE = {{E}xponential {S}creening and optimal rates of sparse estimation},
JOURNAL = {Ann. Statist.},
FJOURNAL = {The Annals of Statistics},
VOLUME = {39},
YEAR = {2011},
NUMBER = {2},
PAGES = {731--771},
}

Motivated by problems of anomaly detection, this paper implements the Neyman-Pearson paradigm to deal with asymmetric errors in binary classification with a convex loss. Given a finite collection of classifiers, we combine them and obtain a new classifier that satisfies simultaneously the two following properties with high probability: (i), its probability of type~I error is below a pre-specified level and (ii), it has probability of type ~II error close to the minimum possible. The proposed classifier is obtained by minimizing an empirical objective subject to an empirical constraint. The novelty of the method is that the classifier output by this problem is shown to satisfy the original constraint on type~I error. This strict enforcement of the constraint has interesting consequences on the control of the type~II error and we develop new techniques to handle this situation. Finally, connections with chance constrained optimization are evident and are investigated.

@article {RigTon11colt,
AUTHOR = {Rigollet, P. and Tong, X.},
TITLE = {Neyman-Pearson classification under a strict constraint},
JOURNAL = {J. Mach. Learn. Res.- W&CP},
FJOURNAL = {Journal of Machine Learning Research (JMLR) - Workshops and Conference Proceedings},
VOLUME = {19},
YEAR = {2011},
PAGES = {595-614 (electronic)},
EE = {http://jmlr.csail.mit.edu/proceedings/papers/v19/rigollet11a.html},
}

We consider a bandit problem which involves sequential sampling from two populations (arms). Each arm produces a noisy reward realization which depends on an observable random covariate. The goal is to maximize cumulative expected reward. We derive general lower bounds on the performance of any admissible policy, and develop an algorithm whose performance achieves the order of said lower bound up to logarithmic terms. This is done by decomposing the global problem into suitably ``localized'' bandit problems. Proofs blend ideas from nonparametric statistics and traditional methods used in the bandit literature.

@inproceedings{RigZee10,
author = {Rigollet, P. and Zeevi, A.},
title = {Nonparametric Bandits with Covariates},
booktitle = {COLT},
year = {2010},
pages = {54-66},
crossref = {colt10},
}

@proceedings{colt10,
editor = {Adam Tauman Kalai and Mehryar Mohri},
title = {23rd Annual Conference on Learning Theory - COLT 2010, Haifa,
Israel, June 27-29, 2010},
booktitle = {COLT},
publisher = {Omnipress},
year = {2010},
}