{'fraction_non_alphanumeric': 0.04698614751029577, 'fraction_numerical': 0.01416448271558717, 'mean_word_length': 4.32281634008635, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Robust Estimation for Nonparametric Families via Generative Adversarial Networks

We provide a general framework for designing Generative Adversarial Networks (GANs) to solve high dimensional robust statistics problems, which aim at estimating unknown parameter of the true distribution given adversarially corrupted samples. Prior work focus on the problem of robust mean and covariance estimation when the true distribution lies in the family of Gaussian distributions or elliptical distributions, and analyze depth or scoring rule based GAN losses for the problem. Our work extend these to robust mean estimation, second moment estimation, and robust linear regression when the true distribution only has bounded Orlicz norms, which includes the broad family of sub-Gaussian, sub-Exponential and bounded moment distributions. We also provide a different set of sufficient conditions for the GAN loss to work: we only require its induced distance function to be a cumulative density function of some light-tailed distribution, which is easily satisfied by neural networks with sigmoid activation. In terms of techniques, our proposed GAN losses can be viewed as a smoothed and generalized Kolmogorov-Smirnov distance, which overcomes the computational intractability of the original Kolmogorov-Smirnov distance used in the prior work.


Introduction
High-dimensional robust statistics focuses on estimating unknown parameters of high-dimensional distributions given corrupted samples. Formally, assume that the true distribution p ⋆ with dimension d is altered to some corrupted distribution p such that TV(p ⋆ , p) ≤ ǫ, where TV is the total variation distance. One takes n samples from p to form the empirical distributionp n . Given the empirical distribution and a loss function L, we aim to output a parameterθ(p n ) such that L(p ⋆ ,θ(p n )) is small. As a concrete example in the setting of robust mean estimation, one might take the loss function to be L(p ⋆ ,θ(p n )) = E p ⋆ [X] −θ(p n ) 2 , which is the ℓ 2 distance between the true mean and an algorithm's output.
To achieve robustness, it is necessary to impose nontrivial assumptions on the true distribution p ⋆ . Classical asymptotic statistical theory focused on minimum-distance functionals for Gaussian or elliptical distributions [1,4,9,11,[13][14][15]22]. Recent work has instead focused on computationally efficient algorithms that are based on weaker assumptions regarding the tail behavior of distributions [2, 3, 5-7, 16, 17, 19-21, 23]. Another recent line of work is more algorithmic, focusing on generative adversarial networks (GANs) as a promising framework for developing robust estimators. Theoretical work has shown that when the true distribution lies in the family of Gaussian or elliptical distributions, one can design specific GAN losses to achieve theoretical guarantee on robust mean estimation and robust covariance estimation [12,13].
In this work, we take the theoretical study of GANs for robust estimation further, moving beyond strong Gaussian assumptions and providing concrete sufficient conditions for robustness. Specifically, our main contributions are as follows: • We extend the design of GANs for robust estimation from Gaussian and elliptical distribution in [12,13] to a rich family of nonparametric classes of distributions, including the family of sub-Gaussian, subexponential and bounded moment distributions.
• We identify sufficient conditions for robust estimation which pinpoint a broad family of GANs that provably succeed in robust mean estimation, robust covariance estimation and robust linear regression.
• We provide computationally tractable methods for the "weaken the distance" approach in [21] by smoothing the Kolmogorov-Smirnov distance, which appears to be difficult to optimize.

Preliminaries
We begin by introducing basic notation. A function ψ : [0, +∞) → [0, +∞) is called an Orlicz function if ψ is convex, non-decreasing, and satisfies For a given Orlicz function ψ, the Orlicz norm of a random variable X is defined as We use A 2 = sup v =0 Av 2 / v 2 to denote the spectral norm of the matrix A. For univariate random variables X and Y , we say that Y stochastically dominates X (to first order) if P(X ≤ t) ≥ P(Y ≤ t) for all t ∈ R [18]. We define the generalized inverse of a non-decreasing function ψ as ψ −1 (y) = inf{x | ψ(x) > y}. We say a distribution r is an ǫ-deletion of another distribution p if r ≤ p 1−η . The inequality can be formally understood as dr dp ≤ 1 1−η , where dr dp is the Radon-Nikodym derivative, which can also be understood as r(A) ≤ p(A) 1−ǫ for any set A; an equivalent characterization is that r can be obtained from p by conditioning on an event E of probability 1 − ǫ.

Tasks considered in Robust Estimation
We focus on three tasks in robust estimation-robust mean estimation, robust second-moment estimation, and robust linear regression-throughout this paper. For robust mean estimation, we take the loss function to be L(p ⋆ ,θ(p n )) = E p ⋆ [X] −θ(p n ) 2 ; for second-moment estimation, we use the loss function L(p ⋆ ,θ(p n )) = E p ⋆ [XX ⊤ ] −θ(p n ) 2 , where the algorithm outputθ(p n ) is a matrix; and for linear regression, we take the loss function to be the excess predictive loss, When the outputθ is a parameter of a distribution, the losses can alternatively be written as distances between distributions. For mean estimation, the loss can be written as L(p ⋆ , q) = E p ⋆ [X] − E q [X] 2 ; for second-moment estimation, the loss can be written as and for linear regression, the loss function can be written as Note that the losses for mean and second-moment estimation admit a pseudonorm representation, When we state our main theorem we will assume that the loss admits this pseudonorm representation, and showcase how to deal with linear regression as an exception.

Generalized Resilience and Minimum Distance Functional
It is shown in [21, Section 3.2] that when the true distribution lies in a "generalized resilience" family, it is possible to design algorithms with robustness guarantees. In particular, when the loss function takes the form of a pseudonorm W F (p, q), the generalized resilience set can be expressed simply as: (1) For convenience of notation, we use G mean to denote G Fmean , and G sec to denote G Fsec . It is shown in [21] The generalized resilience set takes a slightly more complicated form for linear regression. However, it is also a superset of some bounded Orlicz norm family. We use G reg (ψ) to denote the following family: Working under the restrictive assumption that the true distribution lies in G, [21] study a projection algorithm and show that it achieves polynomial sample complexity for robust estimation. The algorithm projects the corrupted empirical distributionp n onto G under the generalized Kolmogorov-Smirnov distance TV H , defined as The distance TV H is smaller than the total variation distance TV because it takes a supremum over only the events defined by threshold functions in H, while TV takes the same supremum over all measurable events. The projection algorithm is analyzed for Guassian mean estimation in [10], with H = {v ⊤ x | v ∈ R d }, and extended to bounded Orlicz norm family for robust second-moment estimation, robust linear regression in [21]. Unfortunately, however, it is difficult to compute the TV H projection in practice due to the lack of differentiability of commonly used losses. We show how to circumvent this issue in the following section.

A Unified Framework for Design of GANs
In this section we show that a large family of smoothed loss function can be used as projection functionals and achieve favorable finite sample bounds. We define the smoothed generalized Kolmogorov-Smirnov distance as where we assume that T (x), after an affine transformation aT (x) + b, can be written as the cumulative distribution function (CDF) of some random variable Z; i.e., aT where we assume that there exist a, b ∈ R such that aT (x) + b can be written as the CDF of some random variable Z. Assume the distribution of Z is inside the resilience family of G mean (ρ Z ). Then there exist r p ≤ p 1−|a|ǫ and For the generalized KS distance TV F , Z ≡ 0 almost surely, and ρ Z = 0, which corresponds to Lemma [21,Lemma 3.3].
where X and Z are independent. Denotep as the distribution of X −Z when X ∼ p, andq as the distribution of X −Z when X ∼ q. Starting fromp,q, we delete probability mass of size ǫ corresponding to the largest points inp to get r p , and delete probability mass of size ǫ corresponding to the smallest points q to getr q . Equation (7) Denote the original distribution of Z as p Z . Note that the deletion process that yieldsr p andr q can be viewed as operating on the joint distribution of X, Z, such that the marginal distributions ofr p andr q are obtained as deletions of p Z . Rearranging, we obtain We now show that given the mean cross lemma for smoothed KS distance, the smoothed distance can be used to deliver a small statistical error for robust estimation under a pseudonorm-based loss function W F . We will show later how the analysis extends beyond pseudonorm loss functions by considering the special case of linear regression. Theorem 1. For any p * ∈ G F (ρ) in Equation (1), denote by p an observed corrupted distribution such that TV(p * , p) ≤ ǫ. Define Here D is some family of discriminator function pairs (d 1 , d 2 ). For some function T (x), let aT (x)+b be the CDF of some random variable Z. Assume the following conditions: 1. For all (d 1 , d 2 ) ∈ D, x ∈ R, we have |d 2 (x)| ≤ 1/2.

For any distribution pair
for some constant C > 0 and any ǫ < 1/C|a|.

The distribution of
Then the projection algorithm q = arg min q∈G F (ρ) A(q,p n ) guarantees whereǫ = 2ǫ + 2Ā(p,p n ), and Remark 1. The three conditions are weak enough to be satisfied for a large family of neural networks. The first condition on the magnitude of d 2 can be easily satisfied by setting the output of the neural network designed for d 2 to pass through a bounded activation function. The second condition is satisfied when d 1 simply takes the form of T . The third condition requires a careful design of T , and thus d 1 , which can also be easily satisfied when the network has a bounded activation function. For example, a simple sigmoid or tanh function gives a CDF whose induced distribution is sub-exponential, and a ramp function gives a CDF whose induced distribution is sub-Gaussian. In [13], it was shown that under mild conditions, one can produce valid (d 1 , d 2 ) using proper scoring rules and appropriate neural network architectures to ensure the three conditions. Our result, combined with [13], extends the results for mean and second-moment estimation in [13] to general resilient sets including sub-Gaussian and bounded k-th moments, while [13] gives guarantee for elliptical distributions as semi-parametric classes.
Proof of Theorem 1. The proof mainly focuses on verifying two important properties in [21].
1. Robustness to perturbation: For any distribution p 1 , p 2 , p 3 , we have Combining Equation (12), the fact q = arg min q∈G F A(q,p n ) and p ⋆ ∈ G F , one has 2. Generalized modulus of continuity: For any p, q ∈ G W F , from A(q, p) − A(p, p) ≤ǫ and condition 2) in Equation (9), we have From Lemma 1, we know that for any fixed From q ∈ G F (ρ), we have Therefore which finishes the proof.

Application of Theorem 1 for Robust Estimation
Now we demonstrate how Theorem 1 leads to concrete designs of GANs for robust mean estimation, second-moment estimation and robust linear regression.

Mean estimation
We start with the problem of mean estimation. Recall the choice of function We show that different choices of A(p, q) give similar performance guarantees in terms of robustness. For the convenience of notation, let   which represent one-and two-layer neural networks, respectively, with sigmoid activation functions. Here v j , v are d-dimensional vectors, t, t j ∈ R, and w is a l-dimensional vector. We consider the following design of dis-tances A(p, q): where A 1 can be viewed as a simple one-layer discriminator, A 2 is a twolayer discriminator, and A 3 is a two-layer discriminator with loss chosen as log score, which is analyzed for Gaussian and elliptical distributions in [13].
Remark 2. Corollary 1 recovers [21, Theorem 3.2] up to an additive term ǫ log(1/ǫ). As a direct result of Corollary 1, one can see that if p ⋆ is inside the sub-Gaussian family, the projection algorithm guarantees a rate of C · ǫ log(1/ǫ), which is nearly optimal up to logarithmic factors compared to the result for Gaussian [13]. When p ⋆ has bounded covariance, the rate becomes (ǫ + d/n + log(1/δ)/n) 1/2 , which is optimal in terms of the dependence on ǫ, but sub-optimal in dependence with respect to d, n.
Compared to the interpretation of proper scoring rules and appropriate network structures in [13], our analysis provides a different view in which robustness is achieved by controlling the tail of the induced distribution of T (x). The results in Corollary 1 also generalize to deeper neural networks with bounded outputs where the three assumptions are more readily satisfied.
Although projection to G is not exactly computable for general G, in practice one may use a subset of Orlicz-norm bounded distributions which can be parameterized using neural networks, or turn the constrained optimization problem into a regularized optimization problem by adding the Orlicz norm as a regularizer in the loss function.
Proof of Corollary 1. Since scaling the distance does not change the final projection q, it suffices to verify the three assumptions in Theorem 1 for scaled distances A 1 /2, A 2 /2, A 3 /2. For the first assumption, one can see that the three distances all satisfy |d 2 (x)| ≤ 1/2 due to the fact that |g 1 | ≤ 1, Now we verify the second assumption. Taking w 1 = 1, w j = 0, ∀j > 1 in g 2 and applying triangle inequality, we have These imply that A 1 , A 2 , A 3 satisfy assumption 2) in Theorem 1 with particular choices of T : T 1 (x) = sigmoid(x), T 2 = sigmoid(T 1 (x)), T 3 = log(T 2 (x)). We now verify the third assumption. For CDF T 1 (x) = 1 1+exp(−x) , the corresponding random variable Z is sub-exponential since max(P(X ≤ −t), P(X ≥ t)) ≤ exp(−t)/2 for any t ≥ 0. For T 2 , T 3 , we can verify that after scaling the CDF, E[exp(|Z|/10)] ≤ 1. This shows the induced random variables from T 2 , T 3 are also sub-exponential. From [21] we know the distribution of Z lies in the set of G mean (ǫ log(1/ǫ)).

Second-moment estimation
Using the same technique as mean estimation, we can show similar results for second-moment estimation by changing F mean to F sec in TV F . Let A 1 , A 2 , A 3 be the same as mean estimation in Equation (15), (16), (17) except that we set Following the same proof as Corollary 1, we have 1 Corollary 2. Assume the true distribution p ⋆ ∈ G sec (ρ). Let the projection algorithm q 1 = arg min q∈Gsec A 1 (q,p n ), and q 2 , q 3 be the projection algorithm that projects under distance A 2 , A 3 . We have with probability at least 1 − δ, Remark 3. When the true distribution lies in the set of sub-Gaussian distributions, the projection algorithm guarantees a rate of C ·ǫ log(1/ǫ), which is near optimal up to logarithmic factors compared to the result for Gaussian [13].

Linear Regression
For linear regression, we adopt a difference family of F in TV F , which takes Let A 1 , A 2 , A 3 be the same as mean estimation in Equation (15), (16), (17) except that we set Although the loss for linear regression is not pseudonorm, and thus Theorem 1 is not directly applicable, we show below that under slight modification of the analysis in Theorem 1 that invokes the general property of generalized resilience in [21], the projection algorithm under the distances A 1 , A 2 , A 3 still guarantees robust regression.
The rest of the proof follows directly from that of Corollary 1 by verifying the three assumptions in Theorem 1.