The landscape of empirical risk for nonconvex losses (Q1991675)

In study of the complexity of M-estimators, the landscape of the empirical risk, namely its stationary points and their properties are examined. Uniform convergence of the gradient and Hessian of the empirical risk to their population counterparts is established, as soon as the number of samples becomes larger than the number of unknown parameters (modulo logarithmic factors). A characterization of the empirical risk landscape under a nearly information-theoretically minimal condition is provided. The result is as follows, if the number of samples exceeds the sparsity of the parameter vector (modulo logarithmic factor), then a suitable uniform convergence result holds. The paper is organized as follows: good definitions, nice theorems, attractive examples, such as nonconvex binary classification and robust regression in very high dimension.