ROBUST ESTIMATION AND GENERATIVE ADVERSARIAL NETWORKS
Robust estimation under Huber's -contamination model has become an important topic in statistics and theoretical computer science. Statistically optimal procedures such as Tukey's median and other estimators based on depth functions are impractical because of their computational intractability. In this paper, we establish an intriguing connection between f -GANs and various depth functions through the lens of f -Learning. Similar to the derivation of fGANs, we show that these depth functions that lead to statistically optimal robust estimators can all be viewed as variational lower bounds of the total variation distance in the framework of f -Learning. This connection opens the door of computing robust estimators using tools developed for training GANs. In particular, we show in both theory and experiments that some appropriate structures of discriminator networks with hidden layers in GANs lead to statistically optimal robust location estimators for both Gaussian distribution and general elliptical distributions where first moment may not exist.
The paper considers the problem of robust high dimensional estimation in Huber’s contamination model. The algorithm is given samples from a distribution (1 - eps) * P + eps * Q, where P is a “nice” distribution (e.g. a Gaussian), eps is the fraction of contaminated points, and Q is some unconstrained noise distribution. The goal is then to estimate parameters of P as well as possible, given this noise. The settings they primarily consider in this paper are when P is a Gaussian with unknown mean and identity covariance, or when it is a Gaussian with unknown covariance. Classical estimators such as Tukey depth or matrix depth for these problems achieve optimal minimax rates, but are computationally expensive to compute. However, recent work of [1,2] propose efficient estimators for this problem that (nearly) achieve these rates.
This paper considers a different approach to this problem. They observe that in the case when P is a Gaussian, these classical depth functions (or minor variations thereof) can be written as the asymptotic limits of certain types of GANs. They then demonstrate that for specific choices for the architecture and regularization of the discriminator, the global optima of this GAN objective achieves minimax optimal error and rates in Huber’s contamination model. Unfortunately, they do not prove that their algorithm achieves these global minima. As a result they do not have any provable guarantees for their algorithms. However, they show experimentally that against many choices of noise distribution, their algorithms obtain good error, both for mean estimation and covariance estimation (at least, the JS-GAN seems to consistently succeed. They acknowledge that the TV-GAN seems to be unstable in certain regimes).
Pros: 
- I think the question of finding algorithmic equivalents of Tukey median is a very interesting question, and this is an interesting attempt.
- I did not replicate their experiments on GANs, but the experimental numbers seem promising. However, I have some mixed feelings about this (see below).
Cons:
- A clear disadvantage of the approach to prior algorithmic work is that the algorithms proposed in the paper do not have provable guarantees. For settings such as secure machine learning, the lack of such guarantees is problematic. Given that previous works give efficient (i.e. practical) algorithms for these problems with provable guarantees, I am unclear how much impact this will have in practice.
- Given that TV-GAN is known to fail (as shown in Table 6), it is unclear how useful the numbers for it are in Table 1. Without these numbers, it then appears that JS-GAN and the filtering algorithm often achieve comparable results, although it is very interesting that JS-GAN is consistently slightly better.
- I feel that the authors fall short of their goal to make a good algorithmic analog of these depth-based estimators. This is a subtle but important point, so let me justify this. As the authors explain, the major advantage of such estimators would be that they are model-free: they should give robustness for a number of settings, not just Gaussians, but also elliptical distributions, sub-gaussian distributions, etc. However, the correspondence that the authors derive to their GAN formulation of depth heavily leverages the Gaussianity of the underlying distribution. Specifically, it leverages the fact that the Scheffe set between two Gaussians is a half-plane, which clearly fails for more general distributions. As a result, it appears to me that this variational formulation of depth succeeds only in a very model-specific setting. As a result, from a theoretical perspective it is unclear what advantage this formulation has. 
Questions:
- How long does it take to train the GANs? Is it comparable to the runtime of the other algorithms?
- Can these algorithms work in the stronger notions of corruption considered in [1, 2]?
Overall conclusion:
The paper proposes a novel framework for robust estimation. However, in light of the previous provable and much simpler algorithms for robust estimation, in the end it seems to me that deep learning is an unnecessarily complicated approach to this problem. While the authors demonstrate some experimental improvement in the test cases they tried, the lack of provable guarantees for their approach limits the theoretical appeal of their paper. More conceptually, I am unconvinced that their approach is the correct approach to understanding algorithmic notions of depth, for the reasons described above.
[1] Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pp. 665–674. IEEE, 2016.
[2] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. arXiv preprint arXiv:1703.00893, 2017.