Quantized Estimation of Gaussian Sequence Models in Euclidean Balls
A central result in statistical theory is Pinsker's theorem, which characterizes the minimax rate in the normal means model of nonparametric estimation. In this paper, we present an extension to Pinsker's theorem where estimation is carried out under storage or communication constraints. In particular, we place limits on the number of bits used to encode an estimator, and analyze the excess risk in terms of this constraint, the signal size, and the noise level. We give sharp upper and lower bounds for the case of a Euclidean ball, which establishes the Pareto-optimal minimax tradeoff between storage and risk in this setting.
The authors consider Pinsker's theorem on the minimax rate in nonparametric estimation with squared error risk of normal means in an L2 ball. They extend this theorem to a rate-distortion-like setting, where there is a bound on the number of bits used in estimation. For bitrates (nr of bits used per outcome) bounded by B, the authors derive exact formulas for the n -> infinity limit of the minimax risk. As one would expect, the resulting formula becomes Pinsker's formula as B -> infinity, and degenerates to the radius of the L2 ball as B -> 0. QUALITYThe paper seems technically sound (though I did not check all details). While the techniques used are, in the end, variations on standard techniques in rate distortion theory (Theorem 2) and 'establishing-minimax risk lower bounds'-literature (Theorem 1), the specific details are quite different from earlier works and seem pretty nontrivial, in fact quite difficult.   CLARITYThe paper is really quite well-written. Inevitably it requires some prior knowledge on the readers' part but the authors did their best I think. ORIGINALITYTo the best of my knowledge (note though that I am not very familiar with the recent literature) the results presented here are new.Still (and this is my one qualm with the paper), the techniques on which they build are not new at all, and little insight is given in how much of the current work is already 'almost known' or 'rather to be expected' given earlier work. In this respect I think that the third paragraph in Section 5, Discussion, is really far too restricted and, should the paper be accepted, should be much elaborated on - even if this means cutting some other material. In fact, I checked the Yang and Barron (YB) paper quoted by the authors in Section 5 and found that the connections seem to run deeper than suggested. Specifically, the YB proof of the YB Theorem 1 is quite similar to the line of reasoning followed by the authors to prove the author's Theorem 1. Let me elaborate on this: while in the classical minimax risk lower bounds as established by YB, there are indeed no constraints on the nr of bits used to store/communicate the estimator (so in this sense the authors are correct that they 'pursue a different direction'), YB's *proof* of such unconstrained bounds does proceed by first looking at restricted set of potential 'truths' (one puts an \epsilon-net on the set \Theta_n) and putting a discrete prior w on them, and giving (via Fano's inequality) a lower bound on the risk of the estimators which are optimal relative to w. Such estimators will *automatically* be representable in a restricted nr of bits (log of the size of the \epsilon-net, to be precise), and thus automatically satisfy a constraint of the type the authors impose. This leads one to wonder whether there isn't already 'implicit rate distortion' going on in classical minimax risk lower bounds, and whether the results in the present paper cannot be more easily re-derived as simple corollaries of existing results. I found it strange that none of this is discussed in the paper. So all in all I would say that the *details* of the paper are certainly original - the result is new, the precise proofs are new and highly nontrivial, but the 'general type of result' is less new than the authors suggest; this is not a reason for rejection per se but it definitely needs more attention. SIGNIFICANCEFor the same reasons I gave as to the originality, I think that while there is reasonable significance, it is not perhaps as high as the paper suggests.PRO/CON-AnalysisPRO: well-written, highly nontrivial and useful result.CONTRA: builds heavily on earlier work, and precise relation to it is not discussed very wellCOMMENT ON IMPACT SCORE: I had a hard time choosing, I'm not really happy there are just two options here. In the end I chose 'incremental' because, while the setting is different and quite novel (marrying rate distortion and minimax nonparametric analysis), the way this is analyzed is *very* similar to existing methods in both fields ; and that these methods are interrelated was already quite well-known. So, mathematically speaking, the term 'incremental' seems justified.