Beyond Convexity: Robustness and Optimality in the Gaussian Sequence Model

The Gaussian sequence model (GSM) is a deceptively simple problem: estimate an unknown mean given a set of noisy observations. This thesis studies statistically optimal (i.e., minimax) procedures to estimate this mean, but with a broad class of shape constraints imposed on the mean, namely, star-shaped or convex sets. In one sense, this seemingly adds more information to the problem and thus makes it more tractable. But in actuality, we are making the solution harder: the statistically optimal procedure must flexibly handle a vast class of possible constraints, including the classic unconstrained problem. Moreover, we’d like our estimators to withstand broader noise assumptions, such as sub-Gaussian distributions.

The first chapter of this thesis produces an optimal estimator for a star-shaped constrained sub-Gaussian sequence model (SGSM) applied to a function class. The second chapter derives necessary and sufficient conditions for the popular least squares estimator to be statistically optimal in the convex constrained GSM. The third chapter gives an optimal estimator for an adversarially corrupted, star-shaped?constrained SGSM with an unknown sub-Gaussian noise distribution. The main techniques of the thesis exploit the local geometry of the constraint sets, using progressively finer packings and coverings of the set.