Robustness Implies Generalization via Data-Dependent Generalization Bounds

This paper proves that robustness implies generalization via data-dependent generalization bounds. As a result, robustness and generalization are shown to be connected closely in a data-dependent manner. Our bounds improve previous bounds in two directions, to solve an open problem that has seen little development since 2010. The first is to reduce the dependence on the covering number. The second is to remove the dependence on the hypothesis space. We present several examples, including ones for lasso and deep learning, in which our bounds are provably preferable. The experiments on real-world data and theoretical models demonstrate near-exponential improvements in various situations. To achieve these improvements, we do not require additional assumptions on the unknown distribution; instead, we only incorporate an observable and computable property of the training samples. A key technical innovation is an improved concentration bound for multinomial random variables that is of independent interest beyond robustness and generalization.


Introduction
Robust optimization (Ben-Tal & Nemirovski, 1998;Bertsimas et al., 2011;Gabrel et al., 2014) is an influential paradigm for dealing with noisy or uncertain data. Many optimization problems are sensitive to perturbations in their parameters. Using powerful concepts derived from convexity and duality, robust optimization aims to find a solution to these optimization problems that is feasible with respect to all possible realizations of noisy or unknown parameters. Essentially, this criterion solves the optimization problem for the worst-case choice of the possible parameters. Robust optimization has been successfully applied in a variety of fields, e.g., machine learning, to deal with inaccurately 1 National University of Singapore 2 Harvard University 3 University of Colorado Boulder 4 New York University. Correspondence to: Kenji Kawaguchi <kenji@nus.edu.sg>.
A learning algorithm A is said to be robust if the loss of the hypothesis A S (returned by the learning algorithm A under the training dataset S) behaves similarly on two samples that are near each other: Definition 1. A learning algorithm A is (K, (·))-robust, for K ∈ N and (·) : Z n → R, if Z can be partitioned into K disjoint sets, denoted by {C k } K k=1 , such that the following holds for all S ∈ Z n : ∀s ∈ S, ∀z ∈ Z, ∀k ∈ [K], if s, z ∈ C k , then | (A S , s) − (A S , z)| ≤ (S).
Here, a training dataset S = (z i ) n i=1 consists of n samples and : H × Z → R ≥0 is the per-sample loss, where H is a hypothesis space and z i ∈ Z is the i-th training data point. That is, a learning algorithm A is a mapping from S ∈ Z n to A S ∈ H.
The bound based on algorithmic robustness (Definition 1) has gained considerable interest in the community and has been discussed in much literature as listed above, partially because the dependence on the robustness term (S) is natural and intuitive. However, the square root dependence on the partition size (or covering number) K is problematic, because K can be prohibitively large in many applications, especially in high-dimensional data where the covering number can be exponential in the dimension (Van Der Vaart et al., 1996;Vershynin, 2018).
Indeed, the K dependence is one of the chief disadvantages of the robust algorithm framework and Xu & Mannor (2010;2012) conjectured that it would be possible to reduce the dependency on K via adaptive partitioning but remarked that extending their proof to achieve this is complex, leaving this issue as an open problem.
The proof of the algorithmic robustness bound relies on the concentration results for multinomial random variables, in particular the 1 deviations (Xu & Mannor, 2012;Wellner et al., 2013). Spurred by applications in learning theory, the concentration of multinomial random variables has been an active area of research by itself beyond algorithmic robustness (Weissman et al., 2003;Devroye, 1983;Agrawal & Jia, 2017;Qian et al., 2020), where a particular attention has been paid to the dependence of the bound on K -the number of possible outcomes in the definition of the multinomial random variable. In the robust algorithmic context, K corresponds exactly to K in Definition 1. In a paper previously published in NeurIPS (Agrawal & Jia, 2017), a significant improvement in the √ K dependence was claimed which was later refuted by Qian et al. (2020) with the refutation being acknowledged by the authors (Agrawal & Jia, 2020). Thus, to date, there has been no success in reducing the √ K term reported in the literature despite its importance and several previous attempts.
Importantly, Qian et al. (2020) established a lower bound that already scales as √ K; that is, we have matching upper and lower bounds in terms of K. Thus, it may seem that the open question posed in (Xu & Mannor, 2012) has been settled negatively and any attempts to reduce the √ K dependence is futile. However, similar to other lower bounds in machine learning, the lower bound given in (Qian et al., 2020) only means that there exists a worst-case distribution for which the (lower) bound cannot be further improved.
It is plausible that this worst-case distribution is neither representative nor commonplace. Thus, by incorporating information from the training data, it may be possible to extract the properties of the underlying distribution, which may allow one to reduce the √ K dependence. In fact, by probing beyond the worst-case analysis, we show that non-uniform and purely data-dependent bounds can greatly outperform these previous bounds (that are implicitly derived for the worst-case distributions). Here, a bound is said to be nonuniform if the bound differs for different data-distributions. Unlike the standard data-dependence through the outcome of the learning algorithm A S (e.g., in the robustness term (S)), a bound is said to be purely data-dependent if the bound contains a term that is independent of the algorithm A and differs for different training data S. We summarize our main contributions below: 1. In Section 3, we address the open problem of reducing the √ K dependence without making any additional assumptions about the data distribution. The key insight (and challenge) here is to prove an purely datadependent bound where the √ K dependence is replaced by an easily computable quantity that is a function of the training samples. This allows us to reduce the √ K dependence without presuming strong prior knowledge of the probability space and the learning algorithm.

A crucial technical innovation is a series of non-
uniform and purely data-dependent bounds for multinomial random variables that greatly improve the classical bounds under certain conditions. A representative of our new bounds is stated in Section 3 (and others are presented in Appendices A and B). These bounds are likely of independent interest in the broader literature beyond robustness and generalization.
3. In addition to our main theorems, we provide abundant numerical simulations and several theoretical examples in which our bounds are provably superior in Sections 4 and 5. As a consequence of our improvements to algorithmic robustness, we can deduce immediate improvements to the many applications of algorithmic robustness listed above, ranging from invariant classifiers to numerical analysis and stochastic learning algorithms.

Preliminaries
This section introduces notation and previous results.

Notation
For an integer n, we use [n] to denote the set of integers 1, . . . , n. For a finite set B, we let |B| represent the number of elements in B. For a set S equipped with metric ρ, we defineŜ as an ε-cover of S if for all s ∈ S, there existŝ s ∈Ŝ such that ρ(s,ŝ) ≤ ε. We then define the ε-covering number as N (ε, S, ρ) = min{|Ŝ| :Ŝ is an ε-cover of S}.
We use 1(·) as an indicator function, and · p is the standard p-norm for a vector.

Problem Setting and Background
In this study, we are interested in bounding the expected loss E z [ (A S , z)], where E z denotes the expectation with respect to the sampling distribution. This is a quantity that cannot be computed or accessed. Accordingly, we obtain an upper bound by using the training loss 1 n n i=1 (A S , z i ), which is a computable quantity, and by invoking other computable terms. A previous study (Xu & Mannor, 2012) used algorithmic robustness (Definition 1) to achieve the following result: Proposition 1. (Xu & Mannor, 2012) Assume that for all h ∈ H and z ∈ Z, the loss is upper bounded by B i.e., (h, z) ≤ B. If the learning algorithm A is (K, (·))-robust (with {C k } K k=1 ), then for any δ > 0, with probability at least 1 − δ over an iid draw of n samples S = (z i ) n i=1 , the following holds: (1) For example, in the special case of supervised learning, the sample space can be decomposed as Z = X × Y, where X is the input space and Y is the label space. However, note that Z can differ from the original space of the data points. For example, if the original data point isz, we can use z = g(z) for any fixed-function g.
The previous paper (Xu & Mannor, 2012) also proves the same upper bound on 1 However, the empirical loss 1 n n i=1 (A S , z i ) can be minimized during training; hence, we are typically interested in the upper bound on E z [ (A S , z)] − 1 n n i=1 (A S , z i ). The focus on this quantity.
The relationship between algorithmic robustness and the multinomial distribution is apparent when we consider independent samples from the sample space of {C k } K k=1 . Then, the number of samples from each class, C k , is multinomially distributed with p k = P(z ∈ C k ). The actual values of p k are not available to us. Therefore, it is natural that the concentration of the multinomial values around these expectations is required in the argument.
The concentration of a multinomial random variable is of interest in theoretical probability and practical use in applied fields such as statistics and computer science (Van Der Vaart et al., 1996). Consequently, several concentration bounds have been proposed in the literature (Weissman et al., 2003;Devroye, 1983;Agrawal & Jia, 2017;Qian et al., 2020;Van Der Vaart et al., 1996), for example: Proposition 2 (Bretagnolle-Huber-Carol inequality). (Van Der Vaart et al., 1996, Proposition A.6.6) If X 1 , . . . , X K are multinomially distributed with parameters n and p 1 , . . . , p K , then for any δ > 0, with probability at least 1 − δ, Crucially, the bounds in the literature are uniform in the parameters p k , meaning that the right-hand side of the inequality is true for any set of parameters. A key step in our reduction of the √ K dependence in algorithmic robustness is the non-uniform (and purely data-dependent) enhancement of the above concentration bound, which may be of independent interest beyond algorithmic robustness.

Main Theorems
In this section, we record our improvements to Proposition 1 along with our upgraded bounds for the multinomial distribution. We discuss our main contributions and relegate the complete proofs of theoretical results to the appendices.

Algorithmic Robustness
One of the main contributions of this study is the following refinement of the algorithmic robustness bound: , then for any δ > 0, with probability at least 1 − δ over an iid draw of n samples S = (z i ) n i=1 , the following holds: Theorem 1 is a significant improvement over the previous bound (1) of Proposition 1 as (3) has a far better dependence on K. In terms of K, we have reduced Overall, if we ignore the log factor, K in the previous bound is replaced by |T S | in our bound. Here, |T S | is the number of distinct classes, C k , that actually appear in the single specific training dataset S; thus, |T S | ≤ K by the definition and it is shown to have |T S | K in many general cases later in Proposition 3 and Sections 4.2 and 5. For example, our experimental results in Section 5 indicate that |T S | K in many natural settings, where we see an exponential discrepancy in a variety of real-world data sets and theoretical models.
Intuitively, |T S | is likely to be significantly less than K when there are many sparsely populated classes C k . Therefore, it is improbable that many of these classes are represented in the sample data. Our theoretical and experimental and results demonstrate that such scenarios are prevalent in the field.
The following proposition shows that |T S | is indeed independent of K and only scales as ln n under a general mild condition on p k , proving that we have |T S | K and |T S | n in a general case: Proposition 3. Under the assumptions of Theorem 1, we denote p k = P(z ∈ C k ) where p 1 ≥ p 2 ≥ · · · ≥ p K . If there are some constants α, β, C > 0 such that p k decays as p k ≤ Ce −(k/β) α , and ln n ≥ max{1, 2/α} then with probability at least 1 − δ, the following holds: In Proposition 3, α controls the rate of decay for p k . For realworld data sets, we expect the data distribution concentrates on a lower dimension manifold or around small number of modes. In such settings, we expect the probability p k = P(z ∈ C k ) (arranging them in decaying order) exhibits fast decays. If α = ∞, p k concentrates on unknown β bins and we have |T S | ≤ β. If α < ∞, we have p k = 0 for all k ∈ [K], but |T S | is still upper bound by β times the constant up to a logarithmic factor and is independent of K.
Proposition 3 also demonstrates the fact that even with perfect prior knowledge of the data distribution, |T S | can be much smaller than K because |T S | is more adaptive according to the training data while K cells need to cover all the possible parts that the distribution has positive mass on. Without the perfect knowledge, |T S | can be more significantly smaller than K.
A crucial aspect of Theorem 1 is that T S depends exclusively on the training sample data and not the actual background distribution. Accordingly, our result is of practical value in statistical learning settings, where information about the actual distribution can only be obtained through the training sample data.
Although the main breakthrough in Theorem 1 is the reduced K dependence, there is also a substantially refined dependence on the upper bound of the loss value -the replacement of B with ζ(A S ), where ζ(A S ) ≤ B; i.e., we replace a maximum over the entire hypothesis space with the single hypothesis returned by the algorithm. This can be a significant advantage for common loss functions, such as square loss and cross-entropy loss. Note that B in the previous bound is defined to be larger than (h, z) for all h ∈ H, meaning that B is dependent on the entire hypothesis space H. In contrast, ζ(A S ) in our bound depends only on the single actual hypothesis, A S , returned by the specific algorithm for each data set S.
With a more refined analysis, we also prove a stronger (yet more complicated) version of Theorem 1: Theorem 2. If the learning algorithm A is (K, (·))-robust (with {C k } K k=1 ), then for any δ > 0, with probability at least 1 − δ over an iid draw of n examples S = (z i ) n i=1 , the following holds: k∈T S |I S k |/n ≤ |T S | by the Cauchy-Schwarz inequality. Thus, Theorem 2 is always as strong as Theorem 1. Furthermore, Theorem 2 significantly upgrades Theorem 1 approximately when Otherwise put, if the maximum expected loss of the classes is much larger than the typical expected loss or the distribution of samples in the classes is lopsided, Theorem 2 will be an even tighter bound.
The complete proofs of Theorems 1 and 2 are provided in Sections C and E of the Appendix. We remark that our proof of Theorem 1 proves a stronger theoretical statement, where ζ(A S ) is replaced by max k∈[K] E z [ (A S , z)|z ∈ C k ] (≤ ζ(A S )). This formulation may have advantages over that in Theorem 1 if the problem context reveals more information about the conditional expectation.

Concentration Bounds for the Multinomial Distribution
Let the vector X = (X 1 , . . . , X K ) follow a multinomial distribution with parameters n and p = (p 1 , . . . , p K ). As shown in the proof of Theorem 1, the key technical hurdle is to avoid an explicit √ K dependence as we upper bound a quantity of the following form: where a i is an arbitrary function with a i (X) ≥ 0 for all i ∈ {1, . . . , K}.
Importantly, a i (X) are functions of X 1 , . . . , X K , which makes this problem particularly challenging and further complicates the non-trivial correlations already present in X i . This difficulty is avoided in (Qian et al., 2020;Bellet & Habrard, 2015;Xu & Mannor, 2012) by using the global maximum of the loss function with the √ K dependence. Allowing a i (X) to depend on X is critical in our analysis and underpins the improvement from B in Proposition 1 to ζ(A S ) in Theorem 1, in addition to the improvement from √ K to √ ln K.
One example of our new multinomial bounds that are nonuniform is the following lemma.
Lemma 1. For any δ > 0, with probability at least 1 − δ, By comparing Lemma 1 to Proposition 2, in some range of parameters, we have essentially replaced If p i = 1/K for all i, then we recover (2). Conversely, in the other extreme case, if p 1 ≈ 1 and the remaining p i are near zero, then √ p i ≈ 1. Thus, our result interpolates between these cases, and there is a wide range of possible distributions in which our bound is significantly better than Proposition 2.
While Lemma 1 is of independent interest, it is likely difficult to be used directly in machine learning because it depends on the probability distribution p, which is typically unknown. To overcome this issue, we further refine Lemma 1 and remove the dependence on p. To keep the notation consistent, we write p k = P(z ∈ C k ) and being arbitrary in this subsection. Since {C k } K k=1 is arbitrary here, this still represents general multinomial distributions.
One of the main contributions of this study is the following refinement of the concentration bound on general multinomial distributions: Theorem 3. For any δ > 0, with probability at least 1 − δ, Further results of this nature and their technical proofs can be found in Sections A and B of the Appendix.

PROOF IDEAS AND CHALLENGES
The proof of Theorem 1 can be divided into three phases. In the first, we prove (a stronger version of) Lemma 1. Next, we invoke Lemma 1 to prove Theorem 3. Finally, we deduce Theorem 1 from Theorem 3. Thus, the first obstacle is to establish Lemma 1, which supplants Proposition 2. After this key step, the next challenge lies in going from Lemma 1 to Theorem 3, which requires us to remove the i √ p i term in Lemma 1 without incurring the Similarly, if we apply Jensen's inequality, which relies on the concavity of the square root function in this domain, we find that and find an upper bound on the second term 1 − i∈T S p i by using a lower bound on i∈T S p i − Xi n . That is, The second line of (7) is a conceptually crucial step where we convert the question of upper bounding i / ∈T S p i to that of lower bounding i∈T S p i . If we directly upper bound i / ∈T S p i , it will sustain a cost of K − |T S |, resulting in a √ K dependence. This step of decomposing the sum and of converting the upper bound to a lower bound is designed to avoid the √ K dependence. Now, the problem has been reduced to finding tight lower and upper bounds on these quantities, which is still nontrivial and is described in Appendices A and B.

PSEUDO-ROBUSTNESS
Xu & Mannor (2012) also introduced a more general notion of pseudo-robustness which relaxes algorithmic robustness by only requiring the nearness of the loss functions to hold for a subset of the training samples: , such that for all S ∈ Z n , there exists a subset of training samplesŜ with |Ŝ| =n(S) and the following holds: ∀s ∈Ŝ, ∀z ∈ Z, ∀k = 1, . . . , K : For pseudo-robustness, we have proved the following analog of Theorem 1: Theorem 4. If the learning algorithm A is (K, (·),n(·)) is pseudo-robust (with {C k } K k=1 ), then for any δ > 0, with probability at least 1 − δ over an iid draw of n examples S = (z i ) n i=1 , the following holds: and Theorem 2 exhibits an analogous generalization. A precise statement and proof can be found in Appendix F. These theorems offer concomitant improvements to the pseudorobustness bounds attained in (Xu & Mannor, 2012).

Examples
Our contributions augment the abstract framework of algorithmic robustness. We do not use application-dependent information nor do we append any restrictive assumptions, and, therefore, can deduce improvements to the many applications that employ the structure of algorithmic robustness. After presenting known examples in Section 4.1, we provide new theoretical comparisons via examples in Section 4.2.

Robust Algorithms
Although our Theorems 1 and 2 are applicable to a wide range of applications, this section provides only a few simple examples from (Xu & Mannor, 2012) to which our Theorems 1 and 2 can be applied. When we have the decomposition z ∈ Z = X × Y with X as the input space and Y as the output space, we let z (x) ∈ X and z (y) ∈ Y denote the X and Y components of a sample point z, respectively, with z = (z (x) , z (y) ). We also write S = (s 1 , . . . , s n ). Example 1. (Xu & Mannor, 2012) (Lipschitz continuous functions) Broad classes of learning problems are set in spaces with natural metrics. If the loss function is Lipschitz, which is a simple and natural condition, then the algorithm is robust. More precisely, if Z is compact with regarding a metric ρ and (A S , ·) is Lipschitz continuous with Lipschitz constant c(S), that is, We assume that Z is compact, and we use the loss function (A S , z) = |z (y) − A S (z (x) )|. Lasso can be formulated as an optimization problem.
then finding the first d principal components via the optimization problem: with the constraint that w j 2 = 1 and w i w j = 0 for i = j is (N (γ/2, Z, · 2 ), 2dγB)-robust, for all γ > 0.
Theorems 1 and 2 can be used as a black box mathematical tool for many more of the existing applications cataloged in the introduction.

Theoretical Comparisons
Here, we further demonstrate the advantage of using our bounds in Section 3 over the bounds provided by Xu & Mannor (2012) and the bounds obtained via uniform stability (Bousquet & Elisseeff, 2002), using Lasso, least square regression, neural networks, and discrete-valued neural communication as examples.
In the next example, we can see that our bound is much tighter than the bound obtained via uniform stability when there are outliers in the data: Example 5 (Regularized least square regression). We refer to the example in (Bousquet & Elisseeff, 2002) for regularized least squares regression. Specifically, (2002) observe that 0 ≤ (w, z) ≤ B/λ, and establish the stability bound β ≤ 2B 2 λn . Now, consider the following distribution on z: z (y) = w * · z (x) + 1(| | < B). In addition, z (x) follows a continuous distribution on [0, 1], for instance, a uniform distribution on [0, 1], and ∼ N (0, σ 2 ). Without loss of generality, let w * = 1. In this example, we can possibly observe some large outlier with small probability. One can check that by suitably chosen σ, Proposition 3 holds with β = 2/ν and α = 2. Thus, there exists a threshold N such that for any n > N , there exists ν > 0, σ > 0 and δ > 0, with a probability of at least 1 − δ, |T S | = Θ(2ν). Thus, if B 2 /λ 2/ν, the bound in Theorem 1 is a far more precise bound than that obtained via uniform stability. For details of the proof, we refer the reader to Appendix G.
Although Example 5 compares our robustness bound and the uniform stability bound, we emphasize that robustness and stability are very different properties and have distinct strengths and weaknesses: i.e., one setting prefers the robustness framework and another setting favors the stability approach. For example, a learning algorithm may be robust but not stable, e.g., lasso regression (Xu et al., 2009), and vice versa. Accordingly, this paper focuses on the fundamental advancements of the robustness framework and of the statistical bound for general multinomial distributions.
Furthermore, the following examples illustrate some of the immediate improvements for robust margin deep neural networks and discrete-valued neural communication: Example 6 (Robust margin deep neural networks). The previous paper (Sokolic et al., 2017b) uses Proposition 1 (in our paper) with the -covering of X for robust margin neural networks. Our new theorem (Theorem 1 or Theorem 2) immediately improve their bounds by replacing in their bounds with |T S |. In our paper, the comparison of K v.s. |T S | for the -covering of X is shown in Figure 3 for the real-life datasets. By plugging these values of K and |T S | into the previous bounds and our versions, we yield exponential improvements over the previous bounds for robust margin deep neural networks.
Example 7 (Discrete-valued neural communication). The bound in (previous) theorem 3 of the recent paper on discrete-valued neural communication (Liu et al., 2021) scales at the rate of L G (which is the size of the discrete bottleneck). Since their proof uses Proposition 2 (in our paper) to bound the left-hand-side of (6) (in our Theorem 3), by applying our Theorem 3, we yield an improvement by replacing L G with |T S | for discrete-valued neural communication.

Experiments
This section establishes the advantage of our new bounds via experiments using both synthetic data and real-world data. We generated synthetic data by sampling from beta distributions and Gaussian mixture distributions with a variety of hyperparameters. For real-world data, we adopted the standard benchmark datasets: MNIST (LeCun et al., 1998) shows the mean and one standard deviation of 10 random trials. We still have |TS| < K with random projections to reduce K. and our bound in all the experiments. To choose the partition {C k } K k=1 , in addition to other examples, we used the -covering of the original input space X as our primary example, as this is the default option in (Xu & Mannor, 2012). The data space is normalized such that X ⊆ [0, 1] d for the dimensionality d of each input data. Accordingly, we used the infinity norm and a diameter of 0.1 for the -covering in all experiments. See Appendix H for more details on the experimental setup. Figure 1 shows the values of K and |T S | for the synthetic data with the partition {C k } K k=1 being the -covering of X . Here, Beta(α, β) indicates the Beta distribution with hyperparameters α and β, and Gauss mix (σ) means the mixture of five Gaussian distributions with a standard deviation σ. Appendix H presents more results with different distributions, showing the same qualitative behavior in all cases.

Synthetic data
While the -covering of the original input space X is the default example from the previous paper (Xu & Mannor, 2012), in Figure 1 we see that K grows rapidly as d increases. Therefore, to reduce K significantly, we also propose utilizing the inverse image of the -covering in a randomly projected space. That is, given a random matrix A, we use the -covering of the space of u = Ax to define the prepartition {C k } K k=1 . Then, the partition {C k } K k=1 is defined by C k = {x ∈ X : Ax ∈C k }. We randomly generated matrix A ∈ R 3×d in each trial. Figure 2 shows the values of K versus |T S | for the synthetic data with the partition {C k } K k=1 being the inverse image of the -covering in randomly projected spaces. As can be seen, even in the case where K is reduced via random projection, we have |T S | K. Thus, in both cases, our bounds are significantly tighter than the previous bound for these synthetics data. Figure 3 shows the values of K versus |T S | for the realworld data with the partition {C k } K k=1 being the -covering of X . All the training data points of each dataset were used. As can be seen, we have |T S | K for the real-world data.

Real-world data
To reduce the value of K, we additionally propose the following new method; i.e., as we have unlabeled data in many applications, we propose to use them to help define the partition {C k } K k=1 . The key idea here was that the choice of partition {C k } K k=1 had to be independent of the labeled data used in the training loss in Theorems 1 and 2, but it could depend on the unlabeled data. Otherwise expressed, given a set of unlabeled data points {x k } K k=1 , the partition {C k } K k=1 is defined by the clustering with the unlabeled data as C k = {x ∈ X : k = argmin k ∈ [K] x −x k 2 }. Following the literature on semi-supervised learning, we split the training data points into labeled data points (500 for Semeion and 5000 for all other datasets) and unlabeled data points (the remainder of the training data). . The values of K versus |TS| with real-world data and the clustering using unlabeled data. With clustering to reduce K, we still have |TS| < K. Here, |TS| was close to zero for Semeion. Figure 4 shows the values of K versus |T S | for the realworld data with the partition {C k } K k=1 being the clustering with the unlabeled data. As can be seen, even in this case with the significantly reduced K, we still have |T S | K. Figure 5 shows the values of K v.s. |T S | for real-life datasets with the partition being the inverse image of the -covering in randomly projected spaces. The random projection was conducted in the same manner without unlabeled data as in Figure 2. The projection reduced the value of K significantly, and yet we still have |T S | K. Thus, in all three cases, our bounds are significantly tighter than the previous bound for these real-world data.

Conclusion
Since its introduction in 2010, algorithmic robustness has been a popular approach for analyzing learning algorithms (Xu & Mannor, 2010;2012;Bellet & Habrard, 2015;Jolliffe & Cadima, 2016). In the original manuscript, which initiated the study of algorithmic robustness, Xu & Mannor (2010;2012) pointed out that one disadvantage of their method is the dependence of the bound on the covering number of the sample space. To the community, they posed the open problem of finding a mechanism to improve this dependence. Despite the popularity and several unsuccessful attempts, no significant progress has been made in this regard (Qian et al., 2020;Agrawal & Jia, 2017;2020).
MNIST CIFAR10 CIFAR100 SVHN FMNIST KMNIST SEMEION 0 50 100 K | S | Figure 5. The values of K versus |TS| with real-world data and random projection. With random projection to reduce K, we still have |TS| < 30 < K = 100 < n ≈ 60, 000 for the real-life datasets. Here, n is the full train data size of each dataset: e.g., n = 60, 000 for MNIST.
In this study, we provide tighter bounds for algorithmic robustness and general multinomial distributions. Our results establish natural and easily verified conditions in which the dependence of K can be greatly reduced. Additionally, we demonstrate that the expected loss can be controlled by examining the single hypothesis returned by an algorithm, whereas in (Xu & Mannor, 2012), the entire hypothesis space has to be analyzed. This is a considerable gain against several common loss functions.
Our bound is both practical and effective in the machine learning setting, as it depends only on the training samples. Furthermore, we provided theoretical and numerical examples in which our bounds proved superior to those of Xu & Mannor (2012) and those that follow from uniform stability (Bousquet & Elisseeff, 2002). Our experimental simulations show that on common datasets and popular theoretical models, this bound is exponentially better than the algorithmic robustness bound (Xu & Mannor, 2012). These improvements to the foundations of algorithmic robustness have immediate impacts on applications ranging from metric learning to invariant classifiers.
The main limitation of our approach is that we cannot know the values of the bounds until specifying training data; i.e., |T S | in our bound is data-dependent, whereas K in the previous bound is data-independent. This data-dependence might not be preferable in some applications, where we may want to compute a bound before seeing training data.
Agrawal, S. and Jia, R. Posterior sampling for reinforcement learning: worst-case regret bounds. arXiv update as a correction of the NeurIPS 2017 paper of the same authors, 2020.

A. Multinomial Concentration Bounds with Probability Distribution Dependence
Let the vector X = (X 1 , . . . , X K ) follow the multinomial distribution with parameters m and p = (p 1 , . . . , p K ). We wish to upper bound the following quantity: where a i (X) ≥ 0 for all i ∈ {1, . . . , K}. Recall that a i (X) depend on X 1 , . . . , X K , which is the heart of the problem.
In this section, we first establish concentration results for scaled multinomial random variables, in other words with a i (X) fixed independent of X. This is the first step towards dealing with the dependent coefficients in the above equation. After this first step, we will analyze the quantity with the dependent a i .

A.1. Multinomial Distribution with fixed a
In this setting, we obtain the following sharp lower and upper bounds.
Lemma 2. Letā 1 , . . . ,ā K ≥ 0 be fixed such that K i=1ā i p i = 0. Then, for any M > 0, By Markov's inequality, the following holds for any ν > 0: To evaluate the moment generating function, we use the probability mass function of the multinomial distribution and the multinomial theorem to find that where the sum in the first two lines is taken over all possible values of the random variable (X 1 , . . . , X K ) (i.e., this is the sum in the definition of the expectation on the left-hand side of the equation). Pugging this into (9), we conclude that We recall the following simple bounds for exponential functions: Then, for 0 < ν ≤ m a ≤ m ai , using (12)-(13), we have that Pugging this into (11), we deduce that Here, we have β : We consider two possible cases. If M ≤ β a , we take 0 < ν = mM β ≤ m a , which yields in (14): If M ≥ β a , we take 0 < ν = m a , which yields in (14): Combining these conclusions yields For the other tail, we establish the following estimate.
Lemma 3. Letā 1 , . . . ,ā K ≥ 0 be fixed such that K i=1ā i p i = 0. Then, for any M > 0, Proof. By Markov's inequality, the following holds for any ν < 0: Using (10) from the proof of Lemma 2, we have We recall the following bounds for exponential functions: for any x ≤ 0 e x ≥ 1 + x for any x ∈ R Using these bounds, Combining what we have so far,

A.2. Multinomial Distribution without a
In this section, we establish some bounds for a i = 1 which is of special interest in applications.
Lemma 4. For any δ > 0, with probability at least 1 − δ, the following holds for all i ∈ {1, . . . , K}: In other words, for any M > 0, We now consider the two cases on the value of p i for an arbitrary δ > 0.
Case p i ≥ ln(K/δ) 4m : in this case, we set M = pi ln(K/δ) m . Then, we have that M ≤ 2p i since the condition p i ≥ ln(K/δ) 4m implies that 4p 2 i ≥ pi ln(K/δ) m and hence 2p i ≥ pi ln(K/δ) Case p i ≤ ln(K/δ) 4m : here, we set M = 2 ln(K/δ) m . Then, we have that M ≥ 2p i since the condition p i ≤ ln(K/δ) Taking union bounds over all i ∈ {1, . . . , K}, we have that for any δ > 0, with probability at least 1 − δ, the following holds for all i ∈ {1, . . . , K}: In other words, we have that for any δ > 0, with probability at least 1 − δ, the following holds for all i ∈ {1, . . . , K}: We have a simpler statement for the other tail.
Lemma 5. For any δ > 0, with probability at least 1 − δ, the following holds for all i ∈ {1, . . . , K}: We conclude the proof by taking a union bound over all i ∈ [K].

A.3. Proof of Lemma 1
The proof of Lemma 1 is obtained by combining the results thus far: Proof of Lemma 1. Lemma 5 implies Lemma 1 by summing up both sides of (15) with the coefficients a i (X) ≥ 0. That is, since a i (X) ≥ 0, Lemma 5 implies that for any δ > 0, with probability at least 1 − δ, the following holds for all i ∈ {1, . . . , K}: This then implies that for any δ > 0, with probability at least 1 − δ,

B. Multinomial Concentration Bounds with Data Dependence
Recall that T S := {k ∈ [K] : |I S k | ≥ 1} with I S k := {i ∈ [n] : z i ∈ C k }. Additionally, we defined a T S (X) = max i∈T S a i (X) and a T c S (X) = max i∈T c S a i (X) where T c S = [K] \ T S . Let the vector X = (X 1 , . . . , X K ) follows the multinomial distribution with parameter n and p = (p 1 , . . . , p K ), where p k = P(z ∈ C k ) and X k = n i=1 1{z i ∈ C k }. We want to upper bound the following quantity: where a i (X) ≥ 0 for all i ∈ {1, . . . , K}. Here, the a i (X) depend on X 1 , . . . , X K .

B.1. Basic Version
In this subsection, using our new results from Appendix A, we prove Theorem 3, which is restated as Lemma 6 in the following and further refined in Appendix B.2: Lemma 6. For any δ > 0, with probability at least 1 − δ, the following holds: 2|T S | ln(2K/δ) n .
Proof. By using Lemma 4 and Lemma 5 and takeing union bounds for the two, we have that for any δ > 0, with probability at least 1 − δ, the following holds for all i ∈ [K], and Recall that T S := {k ∈ [K] : |I S k | ≥ 1} with I S k := {i ∈ [n] : z i ∈ C k }. Summing up both sides of (18) over i ∈ T S and using i∈T S Xi n = 1, where I 1 = {i ∈ T S : p i > ln(K/δ) 4n } and I 2 = {i ∈ T S : p i ≤ ln(K/δ) 4n }. This implies that Using Plugging (17) in the first term and (19) in the second term, 2|T S | ln(2K/δ) n .

B.2. Tighter version
Lemma 7. For any δ > 0, with probability at least 1 − δ, the following holds: Proof. We start with (20) from the proof of Lemma 6: i.e., for any δ > 0, with probability at least 1 − δ, Instead of using the Cauchy-Schwarz inequality to bound the two terms i∈T S a i (X) √ p i and i∈I1 √ p i (which is done in the proof of Lemma 6), we now derive and use another probabilistic bound to bound these terms. For any Thus, by setting I = T S as well as I = I 1 and a i (X) = 1,

C. Proof of Theorem 1
This section culminates in the proof of Theorem 1 using our new results on multinomial distributions from Appendices A and B. We define We start with the proof of the following lemma that relate the gap to the concentration of the multinomial distributions: Lemma 8. For any h ∈ H and z i ∈ Z for all i ∈ [n], Proof. We first write the expected error as the sum of the conditional expected error: where z k is the random variable z conditioned on the event z ∈ C k . Using this, we decompose the generalization error into two terms: The second term in the right-hand side of (23) is further simplified by using

Substituting these into equation (23) yields
The second term in the previous lemma is bounded by the following lemma using the robustness: Lemma 9. If a learning algorithm A is (K, (·))-robust, then the following holds for any S ∈ Z n : Proof. By the triangle inequality, Furthermore, again by the triangle inequality, We now suppose that a learning algorithm A is (K, (·))-robust. Then, sup z∈Z∩C k ,s∈S∩C k | (A S , z) − (A S , s)| ≤ (S) for all k = 1, . . . , K by the definition of a learning algorithm A being (K, (·))-robust. Thus, we have that Using these lemmas and our new concentration bounds on multinomial distributions from Appendices A and B, we can complete the proof of Theorem 1 as follows: Proof of Theorem 1. From Lemma 8, By using Lemma 6 with a k (X) = α k (A S ) and noticing that a T S (X), a T c S (X) ≤ ζ(A S ), we have that for any δ > 0, with probability at least 1 − δ, Invoking Lemma 9, By combining (24)-(26), we obtain the desired statement.

E. Proof of Theorem 2
In this section, we refine the proof of Theorem 1 to obtain a tighter bound by using a tighter version of our new concentration bounds on multinomial distributions from Appendices A and B.
Proof of Theorem 2. The proof begins in the same manner as in the previous section, but uses the sharper multinomial bound. From Lemma 8, By using Lemma 7 with a k (X) = α k (A S ), a T S (X) = α T S (A S ), and a T c S (X) = α T c S (A S ), we have that for any δ > 0, with probability at least 1 − δ, Applying Lemma 9, By combining these, we have that for any δ > 0, with probability at least 1 − δ,

F.1. Simple Version
Our first theorem is the analogue of Theorem 1.
Theorem 5. If a learning algorithm A is (K, (·),n(·)) pseudo robust (with {C k } K k=1 ), then for any δ > 0, with probability at least 1 − δ over an iid draw of n examples S = (z i ) n i=1 , the following holds:

F.2. Stronger Version
The following statement is the analogue of Theorem 2 and is a strengthening of Theorem 5.
Theorem 6. If a learning algorithm A is (K, (·),n(·)) pseudo robust (with {C k } K k=1 ), then for any δ > 0, with probability at least 1 − δ over an iid draw of n examples S = (z i ) n i=1 , the following holds:

F.3. Proof for pseudo robustness
We now prove Theorems 5 and 6.
Lemma 10. If a learning algorithm A is (K, (·),n(·)) pseudo robust, then the following holds for any S ∈ Z n : Proof. DefineÎ k := {i ∈ [n] : z i ∈Ŝ, z i ∈ C k }. Then Combining this with Lemma 8 gives We now have all the tools necessary to complete the proofs of the main theorems.
Proof of Theorem 5. By Lemma 10, By using Lemma 6 with a k (X) = α k (A S ) and noticing that a T S (X), a T c S (X) ≤ ζ(A S ), we have that for any δ > 0, with probability at least 1 − δ, Proof of Theorem 6. By Lemma 10, By using Lemma 7 with a k (X) = α k (A S ), a T S (X) = α T S (A S ), and a T c S (X) = α T c S (A S ), we have that for any δ > 0, with probability at least 1 − δ,

G. Proof of Theoretical Comparisons
Proof of Example 4. First, in order to show the bound in Theorem 1 is tighter than the that of Proposition 1, we must show that It is not hard to see for any given δ, when n > 2|T S | ln(2K/δ), |T S | K, and 2K > 1/δ, the above inequality holds.
Proof of Example 5. Recall the bound in Theorem 1 implies that On the other hand, the bound obtained via uniform stability is: When n and B are large, the dominating term is B λ ( √ 2 + 1) |T S | ln(2K/δ) n and 4nβ ln(1/δ) 2n , where we take β = 2B 2 /(λn) as in Bousquet & Elisseeff (2002). We can divide z (x) into equal sized ν-length intervals (again with the possible exception of the last interval): If there is no noise, i.e. z (y) = w * z (x) , then all the points will fall on the line segment (z (x) , z (x) ). When we have a Gaussian perturbation over z (x) , by suitably choosing the variance parameter σ > 0, and concentration of Gaussian variables, we can let most of the data mass covered in the union of {C i }, where C i = {(x, y) : (x − iν 2 ) 2 + (y − iν 2 ) 2 ≤ ν 2 2 } is a circle with radius √ 2ν 2 and its center is on the line segment (z (x),z (x) ). We then have |T S | ≤ Θ(2/ν). Thus, when B 2/ν, our bound is strictly less than the uniform stability result (42).

H. Additional Experimental Results and Details
We report the additional experimental results in Figures 6, 7, and 8, where we can observe that our new bounds provide the significant improvements over the previous bounds.
For the real-world data, we adopted the standard benchmark datasets - MNIST (LeCun et al., 1998) (Srl & Brescia, 1994). We used all the training samples exactly as provided by those datasets. For the synthetic data, we generated them by sampling the input x ∈ X from beta distributions and Gaussian mixture distributions with a variety of hyperparameters. Beta(α, β) indicates the Beta distribution with hyper-parameters α and β. Gauss mix (σ) means the mixture of five Gaussian distributions with a standard deviation σ. Beta mix (α, β)-(σ) represents the mixture of beta distributions generated by the following procedure: where v 0 is drawn from the uniform distribution on [0, 1], v 1 ∼ Beta(α, β), and v 2 ∼ Beta(σ, σ). Similarly, beta-Gauss (α, β)-(σ) represents the mixture of distributions generated by the following procedure: where v 0 is drawn from the uniform distribution on [0, 1], v 1 ∼ Beta(α, β), and v 2 is drawn from the Gaussian distribution with a standard deviation σ. For all the synthetic data, we generated and used 1000 training data points.
For the partition {C k } K k=1 , we consider the division of the input space X because we can either (1) assume that there exists a functionŷ such that y =ŷ(x) or (2) notice that the partition {C k } K k=1 of the input space X can be dictated by the label y ∈ Y; i.e., K = |Y| × K where K is the size of the partition of the input space X , which is used in the previous paper (Xu & Mannor, 2012). Thus, we can focus on partition of the input space X for the purpose of comparing K and |T S |.
We then defineC k to be the flatten version ofC k1,...,k d ; i.e., {C k } K k=1 = {C k1,...,k d } k1,...,k d ∈ [10] . Finally, the partition {C k } K k=1 is defined by C k = {x ∈ X : Ax ∈C k }. In this study, we randomly generated matrix A ∈ R 3×d in each trial. For the clustering with unlabeled data, given a set of unlabeled data points {x k } K k=1 , the partition {C k } K k=1 is defined by C k = {x ∈ X : k = argmin k ∈ [K] x −x k 2 }. Following the literature on semi-supervised learning, we randomly split the training data points into labeled data points (500 for Semeion and 5000 for all other datasets) and unlabeled data points (the remainder of all the training data).