Obtaining minimax lower bounds: a review

Abstract

Minimax lower bounds determine the complexity of given statistical problems by providing fundamental limit of any procedures. This paper gives a review on various aspects of obtaining minimax lower bounds focusing on a recent development. We first introduce classical methods, then more involved lower bound constructions such as testing two mixtures, two directional method, and global metric entropy method are provided with various examples including manifold learning, approximation sets and neural nets. In addition, we consider two different types of restrictions on the set of estimators. In particular, we consider the lower bounds when the set of estimators is required to be linear, and a private version of minimax lower bounds is discussed.