Theoretical  Characterization of Neural Network Generalization with Group Imbalance
Authors: Hongkang Li
Shuai Zhang
Meng Wang
Yihua Zhang
Pin-Yu Chen
Sijia Liu
Venue: Submitted to ICLR 2023 (2023)
Keywords: Group imbalance
Sample complexity
Generelization analysis
Gaussian mixture model
Empirical risk minimization

Abstract: Group imbalance has been a known problem in empirical risk minimization (ERM), where the achieved high \textit{average} accuracy could be accompanied by low accuracy in a \textit{minority} group. Despite various algorithmic efforts to improve the minority group accuracy, a theoretical study of the generalization performance of ERM on individual groups remains elusive. By formulating the group imbalance problem with the Gaussian Mixture Model, this paper quantifies the impact of individual groups on the sample complexity, the convergence rate, and the average and group-level testing performance. Although our theoretical framework is centered on binary classification using a one-hidden-layer neural network, to the best of our knowledge, we provide the first theoretical analysis of the group-level generalization of ERM in addition to the commonly studied average generalization performance. Sample insights of our theoretical results include that when all group-level co-variance is in the medium regime and all mean are close to zero,  the learning performance is most desirable in the sense of a small sample complexity, a fast training rate, and a high average and group-level testing accuracy. Moreover, we show that increasing the fraction of the minority group in the training data does not necessarily improve the generalization performance of the minority group.  Our theoretical results are validated on both synthetic and empirical datasets such as CelebA and CIFAR-10 in image classification.

Under review as a conference paper at ICLR 2023
THEORETICAL CHARACTERIZATION OF NEURAL NET- WORK GENERALIZATION WITH GROUP IMBALANCE
Anonymous authors Paper under double-blind review
ABSTRACT
Group imbalance has been a known problem in empirical risk minimization (ERM), where the achieved high average accuracy is accompanied by low accuracy in a minority group. Despite algorithmic efforts to improve the minority group accuracy, a theoretical generalization analysis of ERM on individual groups remains elusive. By formulating the group imbalance problem with the Gaussian Mixture Model, this paper quantifies the impact of individual groups the sample complexity, the convergence rate, and the average and group-level testing performance. Although our theoretical framework is centered on binary classification using one-hidden- layer neural network, to the best of our knowledge, we provide the first theoretical analysis of the group-level generalization of ERM in addition to the commonly studied average generalization performance. Sample insights of our theoretical results include that when all group-level co-variance is in the medium regime and all mean are close to zero, the learning performance is most desirable in the sense of a small sample complexity, a fast training rate, and high average and group-level testing accuracy. Moreover, we show that increasing the fraction of the minority group in the training data does not necessarily improve the generalization perfor- mance of the minority group. Our theoretical results are validated on both synthetic and empirical datasets such as CelebA and CIFAR-10 in image classification.
INTRODUCTION
Training neural networks with empirical risk minimization (ERM) a common practice reduce the average loss of machine lcarning task evaluated on a dataset. However, recent findings (Blodgett)
al., 2016 Tatman 2017 Hashimoto et al. 2018 Buolamwini & Gebru 2018 McCoy et al.. Sagawa et al. 2020 Sagawa" R et al. [020 Mehrabi et al. 2021) have shown empirical evidence about critical challenge of ERM, known as group imbalance, where well-trained model that has high average accuracy may have significant errors the minority group that infrequently appears in the data. Moreover, the group attributes that determine the majority and minority groups are usually be augmented by data augmentation
hidden and unknown during training. The training methods (Shorten Khoshgoftaar, 2019) with varying performance, such as cropping and rotation (Krizhevsky al. 2012),, noise injection (Moreno- Barea al. 2018), and generative adversarial network (GAN)-based methods (Goodfellow et al. 2014 Bowles et al. 2018 Radford et al.) (016)).
As ERM is prominent method and enjoys great empirical success, it is important characterize the impact of ERM on group imbalance theoretically. However, the technical difficulty of analyzing the nonconvex ERM problem of neural networks results from the concatenation of nonlinear func- tions across layers, and the existing generalization analyses of ERM often make overly simplistic assumptions and only focus on the average generalization performance. For example, the neural tangent kernel type of analysis (Arora et al. 22019) Allen et al. 2019b CCo & Gu 2019 Chen et al. 2020; Du al. 2019 Jacot et al.] 2018: /ou et al.] 2020 Zou & Gul 2019) linearizes the neural network around the random initialization to remove the nonconvex interactions across layers. The generalization bounds are independent of the feature distribution and cannot be exploited to analyze the impact of individual groups. Li & Liang (2018) provides the sample complexity analysis when the data comes from the mixtures of well-separated distributions but still cannot characterize the learning performance of individual groups. Another line of works (Du al. 2018a Ghorbani
et al. 2020 Goldt et al.) 2020 Li & Liang] 2018: Mei et al.) [0188] Mignacco et al. [2020] Yoshida
& Okada 2019) considers ame-hidden-layee neural networks because the ERM problem is already

---

Under review as a conference paper at ICLR 2023
(1%% landao)
ERM
Test accuracy
0.9
Minortty
0.88
Minarity-gropp aceurncy
Nose
Average nocumey
10
10
10
sug neriation
Noise level 8² (b)
(a)
Figure I: Group imbalance experiment. (a) Binary classification on CelebA dataset using Gaussian augmentation control the minority group co-variance. (b) Test accuracy against the augmented noise level.
highly nonconvex, and the analytical complexity increases tremendously when the number of hidden layers increases. In these works, the input features usually assumed to be ii.d. samples drawn from the standard Gaussian distribution, and this data model cannot differentiate the majority and minority groups.
Contribution:
To the best of our knowledge, this paper provides the first theoretical characterization of both the average and group-level generalization of one-hidden-layer neural network trained by ERM on data generuted from a mixture of distributions. This paper considers the binary classification problem with the cross entropy loss function, with training data generated by ground-truth neural network with known architecture and unknown weights. The optimization problem is challenging due to a high non-convexity from the multi- neuron architecture and the non-linear sigmoid activation.
Assuming the features follow a Gaussian Mixture Model (GMM), where samples of each group are generated from a Gaussian distribution with an arbitrary mean vector and co-variance matrix, this paper quantifies the impact of individual groups on the sample complexity, the training convergence rate, and the average and group-level test error. The training algorithm is the gradient descent following tensor initialization and converges linearly. Our key results include
(1) Medium-range group-level co-variance enhances the learning performance. When a group- level co- co-variance deviates from the medium regime, the learning performance degrades in terms of higher sample complexity, slower convergence in training, and worse average and group-level generalization performance. As shown in Figure Ta), introduce Gaussian augmentation control the co-variance level of the minority group in the CelebA dataset (Liu et al. 2015). The learned model achieves the highest test accuracy when the co-variance is at the medium level, see Figure [b). Another implication is that the diverse performance of different data augmentation methods might partially result from the different group-level co-variance introduced by these methods. Furthermore, although our setup does not directly model the batch normalization approach (Toffe & Szegedy) 20155] Bjorek al. 2018 Chai et al., 2020: Santurkar al. (018)) that modifies the mean and variance in each layer to achieve fast and stable convergence, our result provides a theoretical insight that co-variance indeed affects the learning performance.
(2) Group-level mean shifts from zero hurt the learning performance. When group-level mean deviates from zero, the sample complexity increases, the algorithm converges slower, and both the average and group-level test error increases. Thus, the learning performance is improved if each distribution is pero-mean. This paper provides a similar theoretical insight to practical tricks such as whitening CeiteningLeeCun et al. (1998). subgroup shift (Koch et al. 2022 Ma et al., (222)), population shift Biswws & Mukherjee 2021 Giguere et al. 2022] and the pre- pre-processing of making data zero-ment rean Leeunn al. 1998), that data mean affects the learning performance.
(3) Increasing the fraction of the minority group in the training data does not always improve its generalization performance. The generalization performance is also affected by the mean and co- variance of individual groups. In fact, increasing the fraction of the minority group in the training data can have completely opposite impact in different datasets.
2

---

Under review as a conference paper at ICLR 2023
2 BACKGROUND AND RELATED WORK
Improving the minority-group performance with known group attributes. With known group attributes, distributionally robust optimization (DRO) (Sagawa* et al. 2020) minimizes the worst- group training loss instead of solving ERM. DRO is more computationaly expensive than ERM and does not always outperform ERM in the minority-group test error. Spurious correlations (Sagawal et can be viewed as one reason of group imbalance, where strong associations between labels and irrelevant features exist training samples. Different from the approaches that address spurious correlations, such as Nown-sampling the majority (Japkowicz & Stephen 2002 Haixiang et al. 2017:
Buda ct al., 2018), up-weight the minority group (Shimodaira 2000 Byrd & Lipton 2019). and
removing spurious features (Garg et al. 2019 Elhabian al.. 2008 Zemel et al. 2013) this paper
does not require the special model of spurious correlations and any group attribute information.
Fairness in machine learning has received lot of interest recently (Barocas & Selbst 2016), and substantial body of work has been developed to enhance the fairness under various notions (Dwork
et al. 2012: Feldman et al. 2015 Hardt et al. 2016 Kleinberg et al. [2077] Kearns et al. 2018
Chen et al. 2018 Makhlouf et al.
2021]] [i et al. (021)) For example, DRO maximizes the welfare
of the worst group, satisfying the fairness notion of (Rawls 2001). Different from the majority of
these works, this paper solves ERM directly without group attribute information. Moreover, this paper focuses on characterizing the generalization performance of ERM as a function of the input distribution but does not attempt to evaluate fairees across groups.
Generalization performance with the standard Gaussian input for one-hidden-layee neural networks. BBrutzkus & Globerson] 2017 Du et al. (20T 8b, Ge et al., 2018 Liang et al. 2018 Li & Yuan 2017 Shamir 2018| [Safran & Shamir, 2018 Tian (017) consider infinite training samples. |018|SSffran
(Zhong et al. 2017b characterize the sample complexity of fully connected neural networks with smooth activation functions. Zhang et al. (2019) 2020b) extend to the non-smooth ReLU activation
for fully-connected and convolutional neural networks, respectively. [Fu et al. (2020) analyzes the
cross entropy loss function for binary classification problems. [Zhang et al. (2020a) analyzes the
generalizability of graph neural networks for both regression and binary classification problems.
Theoretical characterization of learning performance from other input distributions for one- hidden-layer neural networks. Yoshida & Okada (2019) analyzes the training loss with a single Gaussian with an arbitrary co- co-variance. Mignacco et al. (2020) quantifies the SGD evolution trained on the Gaussian mixture model. When the hidden layer only contains one neuron, Du al. (201 8a) analyzes rotationally invariant distributions. With an infinite number of neurons and an infinite input dimension, Mei et al., (2018) analyzes the generalization error based on the mean-field analysis for distributions like Gaussian Mixture with the same mean. Ghorbani et al. (2020) considers inputs with low-dimensional structures. No sample complexity is provided in all these works.
Notations: Z is matrix, and is vector. 2; denotes the i-th entry of z, and Zij denotes the (i. j-th entry of Z. [K] denotes the set including integers from to K. Ia and e; represent the identity matrix in Rdxd and the i-th standard basis vector, respectively. 5, (Z) denotes the i-th largest singular value of Z. The matrix norm || Z|| (Z). f(x) = Og((x) (or Mgg(x)). ((g(x))) means that f(x) increases at most, at least, or in the order of g(x), respectively.
PROBLEM FORMULATION AND ALGORITHM
We consider the classification problem with an unbalanced dataset using fully connected neural networks over n independent training examples {(x,, 14) J from a data distribution. The learning algorithm is to minimize the empirical risk function via gradient descent (GD). In what follows, we will present the data model and neural network model considered in this paper.
Data Model. Let a E Rd and y E R denote the input feature and label, respectively. We consider an unbalanced dataset that consists of L (L 2 2) groups of data, where the feature x in the group / E [L) is drawn from a multi-variate Gaussian distribution with mean /4 E E Rd and covariance
Σ, E Rdxd Specifically, x follows the Gaussian mixture model (GMM) [Pearson] 1894 Titterington
ct al.
1985 Hsu & Kakade 2013 Vempala & Wang 2004 Moitra & Valiant, 2010 Regev &
Vijayaraghavan 2017). 7, denoted as æ El A Ex). A E (0,1) is the probability of
sampling from distribution-I and represents the expected fraction of group-l data. ΣLe d
3

---

Under review as a conference paper at ICLR 2023
Group / is defined as minority group if X is less than 1/L. We use vP {A,, p4, E,, VI} to denote all parameters of the mixture mode We consider binary classification with label V generated by ground-truth -ruth neural network with unknown weights W wi.... w E Id activation function <(x)
and sigmoid
T+) where
K Σ
P(y= = 1/x) H(W x) = K
Tww x).
Learning model. Learning is performed over a neural network that has the same architecture as in (1. which is a one-hidden-layer fully connected neural network with its weights denoted by W Ra*k Given n training samples {æx, J where z; follows the GMM model, and y is from 1.. we aim to find the model weights via minimizing the nonconvex empirical risk fn (W) as
min WeRexa
(W = (WW WW; 3i)
(2)
where ((W; (i, yi) is the cross-entropy loss function, i.e., (1 vi) log(1 (W,,,))
E(W; æi, y:) yy -looo (W,
Note that for any permutation matrix P. WP corresponds permuting neurons of network with weights W. Therefore, H(W, x) = H(WP, P, x), and f. (WP) = ==((W. The estimation is considered successful if one finds any column permutation of W
The average generalization performance a learned model W is evaluated by the average risk
f(W)= = E AcN (W; æ, ki),
(4)
and the generalization performance on group is evaluated by the group-l risk
J((W)= Eg-N( E,) &W (i.
(5)
Training Algorithm. Our algorithm starts from initialization Wo R computed based on the tensor initialization method (Subroutine in Section B.T) and then updates the iterates W using gradient descent with the step sizei mo- The computational complexity of tensor initialization is O(Kdd). The per-iteration complexity of the gradient step is O(Kd)). We defer the details of Algorithm in Section of the supplementary material.
MAIN THEORETICAL RESULTS
We will formally present our main theory below, and the insights are summarized in Section 4.1 For the convenience of presentation, some quantities are defined here, and all of them can be viewed as constant. Define Fmax maX fll |x| à Jmin min || |1- Let Zmax We dmii
assume 7 = @(1), indicating that dmax and mmin are the same order. Let (W()) denote the i-th largest singular value of W Let 3x (W
(W') and define 1 II J
6.(W))
II practice, V can be estimated by the EM algorithm (Redner & Walker 1984) and the moment-based method (Hsu & Kakade 2013). The EM algorithm returns model parameters within Euclidean distance ) when the number of mixture components L is known. When L is unknown, one usually over-specifies an estimate
>>> L. then the estimation error by the EM algorithm scales as O(())²). Please refer to (o & Nguyen 2016
Ho et af. 2020 Dwivedi et al.] 20200 b) for details.
"The results can be generalized to any activation function øi with bounded ó. ø' and d". where o' is even.
Examples include tanh and erf.
All the weights in the second layer are assumed he fixed facilitate the analysis. This standard
assumption theoretical generalization analysis (Zhang et al. 2019 Fu at. [020] [Zhang et al. (2020a).
Algorithm] Saterittmmemme emmpllys constant step size. One can potentially speed up the convergence, i.c., reduce by using variable step size. We leave the corresponding theoretical analysis for future work.
4

---

Under review as a conference paper at ICLR 2023
Theorem 1. There exist (0, 2) and positive value functions (()) (sample complexity parameter), q( ) (convergence rate parameter), and & (V), E.) (V) (generalization parameters) such that
as long as the sample size satisfies
ni Z Rlac poly(co' : 17, K, 51 (W () d,
(6)
have that with probability at least 1 d= the iterates (Wi)-=1 returned by Algorithml 7 with
step size no = =0 ( [ }3)) } converge linearly with statistical error critical point W. with the rate of convergence v, i.e.
I|, Walls S (VV) WnllF + noC v(V)
vdK logn/n,
- = 1- K q(())
(8)
where = the upper bound of the entry-wise additive noise the gradient computation. Moreover, there exists a permutation matrix P such that
W P" S Ew poly(o, n, (W (K (1++) vdlogn/n)
(9)
The average population risk f and the group-l risk fi satisfy
f s. EVV) polyppo n,, (W ( (1+ /llgg//n
(10)
S E((V) poly(K, K,, 11, & K (1 + + Vdllg
(11)
The closed-form expressions of B, q, E. E, and & are in Section of the supplementary material and skipped here. The quantitative impact of the GMM model parameters ! on the learning performance varies in different regimes and can be derived from Theorem [ The following corollary summarizes the impact of V on the learning performance in some sample regimes.
Table 1: Impact of GMM parameters on the learning performance in sample regimes
Σ, changes
A changes, constact
[ equal
I's
[A changes
| = o(1)
| R(1)
|r|] min
ir |
B(W), sumple compl. Tue
O((E,11))
O 1*)
O(pol 14
o (1
0(1) (1+A,)²
com: rate ( ) x - (9()
ex[] (3)
1-61 I-
1-9( 1441
6 TFAT
e0 T=x
(V),)), W' Pll
o():))(()()))
o(TTE)))
0(1 + ll
O [an
0(1 vXD
E(P), inenge f
0(1)-0([E;1)))
O(IE))I)
O(1 + (1xy)?)
o( O
0(1) 1+A)
9()
0(1)-((();)))
OQDE)))
OC1 + (lp)?))
vX)
When vary one parameter of group I for any 1 E [T.] of the GMM model v and fix all the others, the learning performance degrades in the sense that the sample complexity nse- the convergence rate [,,, W P([F, average risk J and group-l risk In all increase (details summarized in Tuble 7). as long as any of the following conditions happens,
Corollary 1.
(i) E|El| approaches 0; (ii) [x||] increases from some constant; (ii) ||pe|]] increases from O,
(iv) A decreases, provided that ||Ee|] Piin ie.. group has the smallest group-level co-variance, where |ا are all constants, and [| for all i, E [L].
(v) X increases, provided that [E 0 2 iee. group has the largest group-level co-variance, where Σ are all constants, and ||m Il all i,j E [L].
To the best of knowledge, Theorem provides the first characterization of the sample complexity, learning rate, and generalization performance under the Gaussian mixture model. also firstly characterizes the per-group generalization performance in addition to the average generalization.
"poly([|mx<)) is || for ||m/||| |I and || for ||m

---

Under review as a conference paper at ICLR 2023
4.1 THEORETICAL INSIGHTS
We summarize the crucial implications of Theorem Tand Corollary 1 as follows.
(P1). Training convergence and generalization guarantee. The iterates W, converge a critical point Wn linearly, and the distance between W, and W is O(v n//n) for certain permutation matrix P When the computed gradients contain noise, there is an additional error term of O(E log n//n), where & is the noise level (5 0 for noiseless case). Morcover, the average risk of all groups and the risk of each individual group are both O(11 + /logg//)))))
(P2). Sample complexity. For a given GMM, the sample complexity is O(d d), where is the feature dimension. This result is in the same order the sample complexity for the standard Gaussian input in (Fu et al.) (020) and (Zhong et al., 2017b). Our bound almost order-wise optimal with respect to because the degree of freedom is dK. The additional multiplier of log* d results from the concentration bound in the proof technique. We focus on the dependence on the feature dimension and treat the network width K as constant. The sample complexity in (Fu et al. 2020
and Zhong et al. 2017b) is also d poly (K, log d).
(P3). Learning performance is improved at a medium regime of group-level co-variance. On the one hand, when | is (2)), the learning performance degrades as || increases in the sense that the sample complexity fisc. the convergence rate e, the estimation error W the average risk f. and the group-/ risk all increase. This is due to the saturation of the loss and gradient when the samples have large magnitude. On the other hand, when |] Σx]l is o11) the learning performance also degrades when ||
| approaches zero. The intuition that in this regime, the input data are concentrated on few vectors, and the optimization problem does not have a benign landscape.
(P4). Increasing the fraction of the minority group data does not always improve the general- ization, while the performance also depends on the mean and co- co-variance of individual groups. Take | = (1) for all group j, and | is the same for as an example (columns 5 and of Table Db. When || Ei is the smallest among all groups, increasing X improves the learning performance. When |ز is the largest among all groups, increasing X actually degrades the performance. The intuition is that from (P3), the learning performance is enhanced at a medium regime of group-level co-variance. Thus, increasing the fraction of a group with a medium level of co-variance improves the performance, while increasing the fraction of group with large co-variance degrades the learning performance. Similarly, when augmenting the training data, an argumentation method that introduces medium variance could improve the learning performance, while an argumentation method that introduces a significant level of variance could hurt the learning performance.
(P5). Group-level mean shifts from zero degrade the learning performance. The learning performance degrades as || increases. An intuitive explanation of the degradation is that some training samples have a significant large magnitude such that the sigmoid function saturates.
4.2 PROOF IDEA AND TECHNICAL. NOVELTY
Different from the analysis based generalized linear models, our paper deals with more technical challenges of nonconvex optimization due to the multi-neuron architecture, the GMM model, and a more complicated activation and loss. The main idea of proof to show that the nonconvex empirical risk fr. (W) in a small neighborhood around W (or any permutation W is almost convex with sufficiently large n.. Then if Wi can be initialized in any of these local regions, gradient-based iterates can be proved to converge to W (or W P). The idea of tensor initialization is to first find quantities (see Q, in 14) in the supplementary material) which are proven be functions of tensors of w." Then the method approximates these quantities numerically using training samples and then applies the tensor decomposition method on the estimated quantities to obtain Wo. which an estimation of W With large number of training samples the estimation Wo can be proved to be in the local convex region. The full proof in Section of the supplementary material.
Our algorithmic and analytical framework is built upon some recent works on the generalization analysis of seee-hidde--layee neural networks, see, e.g., (Zhong et al. 20176| Zhang et al. 2019 Fu et al.) 2020 Zhang et al. 2020a| 2021b), which assume that æ; follows the standard Gaussian distribution and cannot be directly extended to GMM. This paper makes new technical contributions
from the following aspects. First, we characterize the local convex region near 4 for the GMM

---

Under review as a conference paper at ICLR 2023
model, while existing results only hold for standard Gaussian data. Second, new tools including matrix concentration bounds are develped to explicitly quantify the impact Y on the sample comepixity. Third, design and analyze new tensors for the mixture model to initialize properly.
while the previous tensor methods in (Zhong et al., 2017b; Zhang et al. 2019) Fu et al. 2020) /Zhan et al. 2020a) utilize the rotation invariant property that only holds for mean Gaussian.
5 NUMERICAL. EXPERIMENTS
5.1
EXPERIMENTS ON SYNTHETIC DATASETS
We first verify the theoretical bounds in Theorem on synthetic data. Each entry of W E Rd generated from (0, 1). The training data (æ,, y/ Jr= generated using the GMM model and (1) not otherwise specified,
2, d = 5, and K go To reduce the computational time, we randomly initialize W instead of computing the tensor initialization(]
Sample complexity. We first study the impact of on the sample complexity. Let μ4 = Rd and let f4 O. Let Σ Σg = I. A X2 0.5. We randomly initialize M times and let ("")) denote the output Algorithm in the mtt trail. Let Wn denote the mean values of all (((m) and let Vw = =v V ||20g
w.. / denote the variance. An experiment successful Vi S 10-3 and fails otherwise. M set to 20. For each pair of and n, 20 independent sets of W and the corresponding training samples are generated. Figure (a) shows the success rate of these independent experiments. A black block means that all the experiments fail. A white block means that they all succeed. The sample complexity is indeed almost linear in d, predicted by (6).
samples
Number Samples
Number of Sumples
1K
10k
2K
20
10a1
I0
10
|
(a)
(b)
(c)
The sample complexity (a) when the feature dimension changes, (b) when one mean changes, (c) when one co-variance changes.
Figure 2:
We next study the impact on the sample complexity of the GMM model. In Figure 2 (b). En Σn I, and let μn = 14 1, μ22 = -1. |||||| varies from to Figure b shows that when the mean increases, the sample complexity increases. In Figure we fix μn 142 -1, and let
Σ o² and Σ₂ = I. varies from 10-1 to 10a The sample complexity increases both when E increases and when |Ei| approaches zero. All results match predictions in Corollary [
Convergence analysis. We next study the convergence rate of Algorithm I Figure a) shows the impact of || A1 X2 0.5, 14 14 C' 1 for positive C. and Σ, Σn A DA. Here A is generated by computing the left- left-singular vectors of x d random matrix from the Gaussian distribution. D diag(1, 1.1, 1.2, 1.3, 1.4). = 1 10*. Algorithm [ |aaways converges linearly when || changes. Moreover, as | increases, Algorithm converges slower. Figure
3 (b) shows the impact of the variance of the Gaussian mixture model. A1 Xa 0.5, la
-1 = Σg E o² 2 DTAA. n = 5 10a We change |Σ|| by changing a., Among
'Like Zhong et al. (017b)) Zhang et al. 2019);; Fu et al. (2020), we consider small-sized network in synthetic experiments to reduce the computational time, especially for computing the sample complexity in Figure Our results hold for large networks too.
'The existing methods based on tensor initialization all use random initialization in synthetic experiments to reduce the computational time. See Fu et al. (2020); Zhang et al. (2019) 2020al (02 as examples. We compare tensor initialization and local random initialization numerically Section B.1 of the supplementary material and show that they have the same performance.

---

Under review as a conference paper at ICLR 2023
the values we test, Algorithm converges fastest when |Σ|| 1. The convergence rate slows down when || Σ increases or decreases from 1. All results are consistent with the predictions in Corollary
I We then study the impact of K the convergence rate. Å X 0.5, li 1, A42 -
Σ Σσ = Figure (c) shows that, as predicted by (8). the convergence rate is linear in -1 -1/K2
1d
Relative stree
Convergence
Relsive
0.996
0.994
0.992
0.05
0.1
Number
=10'
Number
X10*
1/K²
(a)
(b)
(c)
Figure 3: (a) The convergence rate with different μr. (b) The convergence rate with different E. (c) Convergence rate when the number of neurons K changes.
0.03
Minority-group risk
0.5
Averagee
Test loss
Test loss
0.6
0.4
+ Minonity-groop risk Average risk
0.3
0.55
0-0
0
0.02
0.04
0.06
Tog
10"
10
[>a]
(a)
(c)
Figure 4: (a) The relative error of the learned model when changes (b) The cross-entropy test loss when the co- co-variance of the minority group changes. (c) The cross-entropy test loss when the mean of the minority group changes.
Average and group-level generalization performance. The distance between W. returned by Algorithm and W is measured by [W, W F. n ranges from 2 x 10s to 6 x 10a, Σ, = Σn 9I, p1 1, μ1 1. Each point in Figure 4 (a) is averaged over 20 experiments of different W and training set. The error is indeed linear in log(n)/n, predicted by (7)
We evaluate the impact of one aocan/co-varianee of the minority group on the generalization. n
2 x 10a. Let Å₁- = 0.8, A2 = 0.2, l -1, Σ; I. First, we let 142 /42 1 and Σ₂ I. Figure (c) shows that both the average risk and the group-2 2 risk increase as f2 increases, consistent with μl
(P5). Then
1, Σg o I. Figure 4 (b) indicates that both the average and the group-2 risk will first decrease and then increase as the increases, consistent with (P3).
Next, study the impact of increasing the fraction of the minority group. 141 l22 0. Let group be the minority group. In Figure (a). ) ΣS 10 and Σ, = I, the minority group has 0.5, both the average and group-2 risk decease. In Figure ()), (b), Σ; and Σn = 10 I, and the minority group has a higher-level of co-variance. Then when A increases from 0.3, both the average and group-2 risk increase. As predicted by insight (P4), increasing Xa does not necessarily improve the generalization of group 2.
smaller level of co-variance. Then when A increases from
5.2 IMAGE CLASSIFICATION ON DATASET CELEBA
We choose the attribute "blonde hair" as the binary classification label. ResNet 9 He et al. (2016) selected to be the learning model here because it was applied in many simple computer vision tasks Wu et al. 2018); Dutta et al. (2020). To study the impact of co-variance, we pick 4000 female (majority) and 1000 male (minority) images and implement Gaussian data augmentation to create additional 300 images for the male group. Specifically, we select 300 out of 1000 male images and add i.i.d. noise drawn from (00 52) every entry. The test set includes 500 male and 500
8

---

Under review as a conference paper at ICLR 2023
0.45
Minoriy-gruup risk Average risk
Test loss
Minority-group risk
Average risk
Test
0.4
0.35
0.3
0.1
0.3
0
0.1
0.2
0.3
2
X2
(a)
(b)
Figure 5: The test loss (cross entropy loss) of synthetic data with different X2 values. (a) Group has smaller level of co-variance. (b) Group has larger level of co-variance.
female images. Figure shows that when 6² increases, i.e. when the co-variance of the minority group increases, both the minority- group and average test accuracy increase first and then decrease, coinciding with our insight (P3).
Then we fix the total number of training data to be 5000 and vary the fractions of the two groups. From Figure 6| and (b), we observe opposite trends we increase the fraction of the minority group in the training data with the male being the minority and the female being the minority. This is consistent with Insight (P4). Due to space limit, our results on the CIFAR 10 dataset are deferred to Section A in the supplementary material.
0.9
0.91
Test aucuracy
Test accurney
0.89
Male group ROCHERCY Avungt sourracy
Averaee securacy
group accuracy
0.87
0.15
0.25
Fraction of female images
Fraction of male images (a)
(b)
Figure 6: The test accuracy on CelebA dataset has opposite trends when the minority group fraction increases. (a) Male group is the minority (b) Female group is the minority
CONCLUSIONS, LIMITATIONS AND FUTURE DIRECTIONS
This paper provides novel theoretical framework for characterizing neural network generalization with group imbalance. The group imbalance is formulated using the Gaussian mixture model, and this paper explicitly quantifies the impact of each group on the sample complexity, convergence rate, and the average and the group-level generalization. The learning performance is enhanced when the group-level covariance is at medium regime, and the group-level mean is close to zero. Moreover, increasing the fraction minority group does not guarantee improved group-level generalization.
Our results are limited to one-hidden-layer neural networks for binary classification problems. One future direction to extend the analysis to multiple-hiddde--layrr neural networks and multi-class classification. Because of the concatenation of nonlinear activation functions, the analysis of the landscape of the empirical risk and the design of proper initialization is more challenging and requires the development of new tools. Like many cxisting works, sample complexity analysis is also based on the sufficient condition for training success, although it is already almost order-wise optimal. Another future direction is formally characterize the iefommation-thoreeee lower bound of the sample complexity. We see no ethical or immediate negative societal consequence of our work.
"In Figure 6)a). when the minority fraction is less than 0.01. the minority group distribution is almost removed from the Gaussian mixture model in the analysis. Then the (11) constants in the last column of Table I have minor changes, and the order-wise analyses do not reflect the minor fluctuations in this regime.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. Advances neural information processing systems, pp. 6158-6169, 2019a.
Zeyuan Alue Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252. PMLR, 2019b.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In 36th International Conference Machine Learning, ICML 2019, pp- 477-502. International Machine Learning Society (IMLS), 2019.
Solon Barocas and Andrew D Selbst. Big data's disparate impact. Calif. L. Rev., 104:671, 2016.
Arpita Biswas and Suvam Mukherjee. Ensuring fairness under prior probability shifts. In Proceedings of the 202/ AAAI/ACM Conference on AI, Ethics, and Society, pp. 414-424, 2021.
Nils Bjorek, Carla P Gomes, Bart Selman, and Kilian Q Weinberger. Understanding batch normaliza- tion. In Advances in Neural Information Processing Systems, pp. 7694-7705, 2018.
Su Lin Blodgett, Lisa Green, and Brendan O'Connor. Demographic dialectal variation in social media: A case study of african-ammrrcaan english. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 1119-1130, 2016.
Christopher Bowles, Liang Chen, Ricardo Guerrero, Paul Bentley, Roger Gunn, Alexander Hammers, David Alexander Dickie, Maria Valdés Hernández, Joanna Wardlaw, and Daniel Rueckert. Gan augmentation: Augmenting training data using generative adversarial networks. arXiv preprint ar1iv: 10863, 2018.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 605-614. JMLR. org, 2017.
Mateusz Buda, Atsuto Maki, and Maciej A Mazurowski, A systematic study of the class imbalance problem convolutional neural networks. Neural Networks, 106:249-259, 2018
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Conference on fairness, accountabilityy and transparency, pp. 77-91. PMLR, 2018
Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning? In International Conference on Machine Learning, pp. 872-881. PMLR, 2019.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, pp. 10836-10846, 2019.
Elaina Chai, Mert Pilanci, and Boris Murmann. Separating the effects of batch normalization on enn training speed and stability using classical adaptive filter theory. In 2020 54th Asilomar Conference on Signals, Systems, and Computers, pp. 1214-1221. IEEF, 2020.
Chaofan Chen, Kangcheng Lin, Cynthia Rudin, Yaron Shaposhnik, Sijia Wang, and Tong Wang. An interpretable model with globally consistent explanations for credit risk. NIPS 2018 Workshop on Challenges and Opportunities for Al in Financial Services: the Impact of Fairness, Explainability, Accuracy, and Privacy, 2018
Zixiang Chen, Yuan Cao, Quanquan Gu, and Tong Zhang. A generalized neural tangent kernel analysis for two-layer neural networks. Advances in Neural Information Processing Systems, 33, 2020.
Simon S Du, Jason D Lee, and Yuandong Tian. When is a convolutional filter easy to leam? In International Conference Learning Representations, 2018a.
10

---

Under review as a conference paper at ICLR 2023
Simon S Du, Jason D Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns ane-hidden-layee cnn: Don't be afraid of spurious local minima. In International Conference on Machine Learning, pp. 1338-13477 2018b.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes pereparraeterized neural networks, In International Conference on Learning Representations. 2019. httpp://opeeaeeeee...eeeeeeooeee
Aritra Dutta, El Houcine Bergou, Ahmed M Abdelmoniem, Chen- Yu Ho, Atal Narayan Sahu, Marco Canini, and Panos Kalnis. On the discrepancy between the theoretical analysis and practical implementations compressed communication for distributed deep learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp.
2020.
Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Michael I. Jordan, Martin J. Wainwright, and Bin Yu. Singularity, misspecification, and the convergence rate of em. To appear, Annals of Statistics, 2020a.
Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Martin Wainwright, Michael Jordan, and Bin Yu. Sharp analysis of inpectation-maximizziin for weakly identifiable models. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 1866- 1876, Online, 26-28 Aug 2020b. PMLR.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Faimess through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226, 2012.
Shireen Y Elhabian, Khaled M El-Sayed, and Sumaya H Ahmed. Moving object detection in spatial domain using background removal techniques-staat-of-artt Recent patents on computer science, 1 (1):32-54, 2008
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubra- manian. Certifying and removing disparate impact. proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 259-268, 2015.
Haoyu Fu, Yuejie Chi, and Yingbin Liang. Guaranteed recovery of one-hidden-kaa layer neural networks via cross entropy. IEEE Transactions on Signal Processing, 68:3225-333 -235,, 2020.
Sahaj Garg, Vincent Perot, Nicole Limtiaco, Ankur Taly, Ed H Chi, and Alex Beutel. Counterfactual fairness in text classification through robustness. In Proceedings of the 2019 AAAI/ACM Conference on Al, Ethics, and Society, pp. 219-226, 2019.
Rong Ge, Jason D. Lee, and Tengyu Ma. Leariing one-hidden-layer neural networks with landscape design. In International Conference on Learming Representations, 2018. URL https:// openreview net forum? id id-BkwHODRR2
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, 33: 14820-14830, 2020.
Stephen Giguere, Blossom Metevier, Yuriy Brun, Philip S. Thomas, Scott Niekum, and Bruno Castro da Silva. Fairness guarantees under demographic shift. In International Conference on Learning Representations, 2022. URL http:htttt//prreeeeeeeee
net forum wtt.:e/eooouumoo-oooooobbo....m
Sebastian Goldt, Mare Mézard, Florent Krzakala, and Lenka Zdeborová. Modeling the influence of data structure on learning in neural networks: The hidden manifold model. Physical Review X, 10 (4):041044, 2020.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- fion processing systems, pp. 2672-2680, 2014.

---

Under review as a conference paper at ICLR 2023
Guo Haixiang, Li Yijing, Jennifer Shang, Gu Mingyun, Huang Yuanyue, and Gong Bing. Learning from blass-imbllanced data: Review methods and applications. Expert systems with applications, 73:220-253 2017.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In International Conference Machine Learning, pp. 1929-1938. PMLR, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Nhat Ho and XuanL.ong Nguyen. Convergence rates of parameter estimation for some weakly identifiable finite mixtures. Ann. Statist., 446))2226-775555, 12 2016. doi: 10.1214/16-AOS1444
URL /tt A08144444
Nhat Ho, Raaz Dwivedi, Koulik Khamaru, Martin Wainwright, Michael I. Jordan, and Bin Yu. Instability, computational efficiency and statistical accuracy. Arxiv preprint Arxiv: 2005. 11411, 2020.
Daniel Hsu and Sham M Kakade. Learning mixtures of spherical gaussians: moment methods and spectral decompositions. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pp. 11-20, 2013.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448-456, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Advances neural information processing systems, pp. 8571-8580, 2018
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Score function features for discriminative learning: Matrix and tensor framework. arXiv preprint 1412.2221 2014.
Nathalie Japkowiez and Shaju Stephen. The class imbalance problem: A systematic study. Intelligent data analysis, 6(5):429-449) 2002.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In International Conference Machine Learning, pp. 2564-2572. PMLR, 2018.
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determi- nation of risk scores. 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Ceasstuul-Libbii-zzeetee fuer Informatik, 2017.
Lisa M. Koch, Christian M. Schürch, Arthur Gretton, and Philipp Berens. Hidden in plain sight: Subgroup shifts escape OOD detection. In Medical Imaging with Deep Learning, 2022. URL
htttps://openxevviee net./ forum? iediid=aaaee add_zaauuyye2222222
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. tional neural networks. In Advances neural information processing systems, pp. 1097-1105, 2012.
Imagenet classification with deep convolu-
Volodymyr Kuleshov, Arun Chaganty, and Percy Liang. Tensor factorization via matrix factorization. In Artificial Intelligence and Statistics, pp. 507-516, 2015.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (6(11)62201))) 11:2278-2322 1998.
12

---

Under review as a conference paper at ICLR 2023
Yann LeCun, Leon Bottou, Genevieve B OII, and Klaus-Robes Müller. Efficient backprop. In Neural Networks: Tricks of the Trade, pp. 9-50. Springer, 1998.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances Neural Information Processing Systems, pp. 8157-81 16,, 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in neural information processing systems, pp. 597-607, 2017.
Yunqi Li, Hanxiong Chen, Shuyuan Xu, Yingqiang Ge. and Yongfeng Zhang. Towards personalized fairness based on causal notion. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1054-1063, 2021.
Shiyu Liang, Ruoyu Sun, Jason D Lee, and R Srikant. Adding one neuron can eliminate all bad local minima. In Advances in Neural Information Processing Systems, pp. 4355-4365, 2018.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes the wild. In Proceedings of the IEEE international conference computer vision, pp. 3730 7730-3738, 2015.
Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and fairness of graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
Karima Makhlouf, Sami Zhioua, and Catuscia Palamidessi. On the applicability of machine learning fairness notions. ACM SIGKDD Explorations Newsletter, 23(1): 2021.
Tom McCoy, Ellie Pavlick, and Tal Linzen. Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 3428-3448, 2019.
Ninarch Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey bias and fairness in machine learning. ACM Computing Surveys (CSUR), 54(6):1-35, 2021.
Song Mei, Yu Bai, and Andrea Montanari. The landscape of empirical risk for non-convex losses. arXiv preprint 1XXx::6677006344 2016.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 115(33)):76655-7777 2018
Francesca Mignacco, Florent Krzakala. Pierfrancesco Urbani, and Lenka Zdeborová. Dynamical mean-field theory for stochastic gradient descent in gaussian mixture classification. Advances in Neural Information Processing Systems, 33:9540-9550, 2020.
Ankur Moitra and Gregory Valiant. Setting the polynomial learnability of mixtures of gaussians. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 93-102. IEFF, 2010.
Francisco Moreno-Barca, Fiammetta Strazzera, José M Jerez, Daniel Urda, and Leonardo Franco. Forward noise adjustment scheme for data augmentation. In 2018 IEEE symposium series on computational intelligence (SSCI), pp. 728-734. IEEE, 2018.
Karl Pearson. Contributions to the mathematical theory of evolution. Philosophical Transactions of the Royal Society of London. A, 185:71-110, 1894.
Alec Radford, Luke Metz. and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. In 4th International Conference Learning
Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http:://xa org abs aaaas///111
John Rawls. Justice as fairness: restatement. Harvard University Press, 2001.
Richard A Redner and Homer Walker. Mixture densities, maximum likelihood and the em algorithm. SIAM review, 26(2):195-23, 1984.
13

---

Under review as a conference paper at ICLR 2023
Oded Regev and Aravindan Vijayaraghavan. On learning mixtures of well well-separated gaussians. In 2017 IEEE 58th Anmual Symposium on Foundations of Computer Science (FOCS), pp. 85-96. IEEE, 2017.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In Interaational Conference on Machine Learning, pp. 4430-4438, 2018.
Shiori Sagawa*, Pang Wei Koh*, Tatsunori Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. In International Conference on Learning Representations, 2020. URL https //openreview. feet//orumiidwaeee ryxGuus
Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparameteriratioo exacerbates spurious correlations. In International Conference on Machine Learning, pp. 8346-83555 PMLR, 2020.
Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch normal- ization help optimization? In Advances Neural Information Processing Systems, pp. 2483-2493, 2018.
Ohad Shamir. Distribution-speccffcc hardness of learning neural networks. The Journal of Machine Learning Research, 19(1): 111--113311,,, 2018.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
Connor Shorten and Taghi M Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of big data, 6(1):1-48, 2019.
Rachael Tatman. Gender and dialect bias in youtube's 's automatic captions. In Proceedings of the first ACL workshop on ethics in natural language processing, pp. 53-59, 2017.
Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 3404-3413, JMLR. org, 2017.
Michael Titterington, Adrian FM Smith, and Udi Makov. Statistical analysis of finite mixture distribations. Wiley., 1985.
Santosh Vempala and Grant Wang. A spectral algorithm for learning mixture models. Journal of Computer and System Sciences, 68(4):841-86) 2004.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3022 2010.
Bichen Wu, Alvin Wan, Xiangyu Yue, Peter Jin, Sicheng Zhao, Noah Golmant, Amir Gholaminejad, Joseph Gonzalez, and Kurt Keutzer. Shift: A zero flop, zero parameter alternative spatial convolutions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9127-9135, 2018
Yuki Yoshida and Masato Okada. Data-dependence of plateau phenomenon in learning with neu- ral network - statistical mechanical analysis. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Biché-Buc,, Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, pp. 1722-1730 1730. Curran Associates, Inc., 2019.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International conference on machine learning, pp. 325-333. PMLR, 2013.
Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. Fast learning of graph neural networks with guaranteed generalizability: One-hidden-layer case. In International Conference on Machine Learning, pp. 11 11268 111 11277. PMLR, 2020a.
Shuai Zhang, Meng Wang. Jinjun Xiong, Sijia Liu, and Pin-Yu Chen. Improved linear convergence of training cnns with generalizability guarantees: A one-hidden hwwhhhhddeeeeee -lyer case. IEEE Transactions on Neural Networks and Learning Systems, 2020b.
14

---

Under review as a conference paper at ICLR 2023
Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. How unlabeled data improve generalization self- training? a sae-hidden-llyee theoretical analysis. In International Conference on Learning Representations, 2021a.
Shuai Zhang, Meng Wang,
Sijia Liu, Yu Chen, and Jinjun Xiong. Why lottery ticket wins? theoretical perspective of sample complexity on sparse neural networks. Advances in Neural Information Processing Systems, 34, 2021b.
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden -lyeeddde-- relu networks via gradient descent. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 1524-1534. PMLR, 2019.
Kai Zhong, Zhao Song, and Inderjit S Dhillon. Learning non-overlapping convolutional neural networks with multiple kernels. arXiv preprint 1..04:07 2017a.
Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit Dhillon. Recovery guarantees for one-hioden-layer neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 4140 4149, 2017b. URL httpp://aarxiv.or////o
1706. 03175. pdf.
Difan Zou and Quanquan Gu. An improved analysis of training werr-parameterized deep neural networks. In Advances in Neural Information Processing Systems, pp. 2055-2064, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine Learning, 109()):467-492, 2020.
15

---

Under review as a conference paper at ICLR 2023
We begin Appendix here.
Section provides more experiment results as a supplement of Section
Section B introduces the algorithm, especially the tensor initialization in detail.
Section includes some definitions and properties as a preliminary to our proof.
Section D shows the proof of Theorem | and Corollary [ followed by Section E and G as
the proof of three key Lemmas about local convexity, linear convergence and tensor initialization, respectively.
A MORE EXPERIMENT RESULTS
We present our experiment resultson empirical datasets CelebA (Liu et al., 2015) and CIFAR-II 10 in this section. To be more specific, we evaluate the impact of the variance levels introduced by different data augmentation methods on the learning performance. We also evaluate the impact of the minority group fraction in the training data the learning performance. All the experiments are reported in a format of 2 deviation" with a random seed equal to 10. We NVIDIA GeForce RTX 2070 super GPU and work station with
9
implement our experiments cores 3.40GHz Intel i7 CPU.
A.1 TESTS ON CELEBA
In addition to the Gaussian augmentation method in Figure 7 (a) and Figure T (b). We also evaluate the performance of data augmentation by cropping. The setup is exactly the same as that for Gaussian augmentation, expect that we augment the data by cropping instead of adding Gaussian noise. Specifically, to generate an augmented image, we randomly crop an image with size w w x and then resize back to 224 224 x 3. One can observe that the minority-group and average test accuracy first increase and then decrease as w increases, which is accordance with Insight (P3).
Test accuracy
0.9
0.88
Minority-group accuracy
Average accuracy
100
140
180
220
Cropping window size w (a)
Figure 7: The test accuracy of CelebA dataset with the data augmentation method of cropping.
A.2 TESTS CIFAR-10
Group contains images with attributes "bird", "cat", "deer", "dog", "frog" and "horse." Group contains "airplane" images. In this setting, Group has a larger variance. Because each image in CIFAR-10 10 only has attribute, consider the binary classification setting where all images in Group are labeled as "animal" and all images are labeled as "airplane." This a special scenario that the group label is also the classification label. Note that results hold for general setups where group labels and classification labels are irrelevant, like our previous results on CelebA. LeNet Lecun al. 1998 is selected to be the learning model.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The CIFAR-10 dataset. www. wwronto.edd..u....
kri w/cifar. html

---

Under review as a conference paper at ICLR 2023
We first pick 8000 animal images (majority) and 2000 airplane images (minority). We select 1000 out of 2000 airplane images to implement data augmentation, including both Gaussian augmentation and random cropping. For Gaussian augmentation,
add i..d. Gaussian noise drawn from A 8²) to each entry [T0] For random cropping, we randomly crop the image with a certain size to x w x and then resizing back 32 32 3. Figure shows that when ó or increase, i.e., the variance introduced by either augmentation method increases, both the minority-growe and average test accuracy increase first and then decrease, which consistent with our Insight (P3).
Then we fix the total number of training data to be 5000 and vary the fractions of the two groups. One can see opposite trends in Figure If we increase the fraction of the minority group with the airplane being the minority and the animal being the minority, which reflects our Insight (P4).
Test accuracy
0.9
Test accuracy
0.8
Minority group aecuricy
Mincrity-grouy group accuracy
0.7
Average accuracy
0.7
Average accuracy
10a1
10
10
10a
20
Noise level (a)
Cropping window size
(b)
Figure 8: The test accuracy of CIFAR-10 dataset with different data augmentation methods (a) Gaussian noise (b) cropping.
0.9
0.9
Test accuracy
accuracy
0.8
Airplane group accurncy
0.8
Average accuracy
Animal accuracy
Average accuracy
0.6
0.2
0.3
0.4
Fraction of airplane images
Fraction of animal images (b)
(a)
Figure 9: The test accuracy of CIFAR-IU 10 dataset has opposite trends when the minority group fraction increases (a) Airplane group is the minority. (b) Animal group the minority.
B ALGORITHM
We first introduce new notations to be used in this part and summarize key notions in Table 2
write (*) I (Z)g(z) if [(x) (g)))) The gradient and Hessian function ((W) are denoted by VS(W) and V²f(W), respectively. A Z 0 means A is positive semi-definite
(PSD) matrix. A means that A =AA)². The outer product of vectors 2, R i [
is detined as T 2 8 ... X z: E _ X--xnn with T Th (z));, ... (z),. Given tensor T E R. Xn2 xna and matrices A E |nixd, B E Raaxdd, C Rnsxds the (1), 22, da)-th entry of the tensor T(A, B, C) is given by
A B Crg.is
(12)
In this experiment, the noise is added to the raw image where the pixel value ranges from 0 to 255, while in the experiment of CelehA (Figure (b)), the noise is added to the image after normalization where the pixel value ranges from 0 to 1.
2

---

Under review as a conference paper at ICLR 2023
Table 2: Summary of notations
Aa pM, Ei, E [T.]
The fraction, mean, and covariance of the /-th component in the Gaussian mixture distribution, respectively.
d, n, K
The feature dimension, the number of training samples, and the number of neurons, respectively.
W W.
W is the ground truth weight. We is the updated weight in the /-th iteration.
fn. f, e
fn is the empirical risk function. f is the average risk or the population risk function. l is the cross-entropy loss function.
v, maax: minn
v denotes our Gaussian mixture model (At, p4, Σt, Vl). mmax Tmax/ min- (W is the i-th largest singular value of W 1) and A. are two
max { E [] min min {| *I à
& ((WW), ) 7, Ki i E [K]
functions of W*
p(u,o), 0), I(V), (m
These items are functions of the Gaussian mixture distribution v used to develop our Theorem [
V,, {
Vs is the gradient noise. & is the upper bound of the noise level.
Q₁ J 1,2,3
2j 's are tensors used in the initialization.
B(D)
A parameter appeared in the sample complexity bound (6)
v(W), ((V)
vVV is the convergence rate (7). g( (V) a parameter in the definition
of v( ()) (8).
Eu (V), E, &
Generalization parameters. Enp (V) appears the error bound of the model 99. ((V) and ( are to characterize the average risk (10) and
the group-1 risk (11), respectively.
The method starts from an initialization Wo E RdxK computed based on the tensor initialization method (Subroutine I and then updates the iterates W, using gradient descent with the step size
Too To model the inaccuracy in computing the gradient, an i.dd. zero-mean noise [r E Rdx K
with bounded magnitude ((4))al < {j E [d]. k E [K] for some 2 0 are added in (3) when computing the gradient of the loss in 33.
Algorithm 1 Our proposed learning algorithm
1: Input: Training data {xx; y:) J the step size ((Et Ae(ll + 11=))))))-)))
the total number of iterations T
2: Initialization: Wo < Tensor initialization method via Subroutine [
3: Gradient Descent: for = 0, I,... T
n
W = We - :o
VIW Di yi) + v.)
(13)
n
We no V
(W)
n 14
Σ
4: Output: WT
Our tensor initialization method in Subroutine iis extended from Janzamin et al. (2014) and Zhong ct al. (0177)). The idea is to compute quantities (Q; in (14)) that are tensors of w and then apply the tensor decomposition method to estimate w.. Because Q, can only be estimated from training samples, tensor decomposition does not return w exactly but provides close approximation, and this approximation is used as the initialization for Algorithm [ Because the existing method on tensor construction only applies the standard Gaussian distribution, we exploit the relationship between probability density functions and tensor expressions developed in Janzamin et al. (2014) to design tensors suitable for the Gaussian mixture model. Formally,
Definition 1. For j = 1,2,3, we define
Q = Ea E/s, ma)l (-1)"--(a)
(14)
3

---

Under review as a conference paper at ICLR 2023
where p(z), the probability density function of GMM is defined as
L.
p(æ) Σ (2(2TT
E exp 1 مد)ا
1
pi)
(15)
1=1
the Gaussian mixture model is symmetric, the symmetric distribution can be written as
(W E.) NN(1,,,
L is even
x
1-1 \, E1)+ Σ (W(H,, Ed) + N- Ei))
(16)
L is odd
2j is a jith-order tensor of w., e.g., Q3 K Ex E E/= A,V(,, 10" (w; w) @3 These quantifies cannot be directly computed from (14) but can be estimated by sample means, denoted by Qj (j 1, 2, 3), from samples {æ;, M/ i= The following assumption guarantees that these tensors are nonzero and can thus be leveraged to estimate W
Assumption 1. The Gaussian Mixture Model in 166 satisfies the following conditions:
1. Q1 and Q3 are nonzero.
2. If the distribution is not symmetric, then Q2 nonzero.
Assumption is very mild assumptior 11 rare case that some quantities Q (i = 2, are zero, one can construct higher-order tensors in similar way in Definition D and then estimate W from higher-order tensors.
Moreover, indicated in Janzamin et al. (2014), in the
Subroutine I describes the tensor initialization method, which estimates the direction and magnitude of wf.3 E ]. separately. The direction vectors are denoted as W, w²/ /0//// and the magnitude
[|w]] || is denoted as 2j. Lines 2-6 estimate the subspace Ü spanned by {wi wik) using Q2 or, in the case that Q2 = O, a second-ordes tensor projected by Q3. Lines 7-8 estimate w by employing the KCL algorithm Kuleshov et al. (2015). Lines 9-10 estimate the magnitude 2z. Finally, the returned estimation of W i8 used as an intialization W, for Algorithm The computational complexity of Subroutine 1 is O(Knd based on similar caleulations those Zhong et al. (201bb).
B. NUMERICAL EVALUATION OF TENSOR INITIALIZATION
Figure 10 shows the accuracy of the returned model by Algorithm Here n = 2 x 10 d 50, K = 2, A = A2 0.5, μ -0.3 and μ22 O. We compare the tensor initialization with random initialization in a local region { { E dadx I|W - W < eJ. Each entry of W is selected from [-0.1, 0.1] uniformly. Tensor initialization Subroutine returns an initial point close to one permutation of W with relative error of 0.65. If the random initialization is also close to W e.g., 0.1, then initializations, and the linear convergence rate is the same. We also test random initialization with each entry drawn from (0, 25). The initialization is sufficiently far from W and the algorithm does not converge. On MacBook Pro with Intel(R) Core(TM) i5-7360U CPU 2.30GHz and MATLAB 2017a, it takes 5.52 seconds to compute the tensor initialization. Thus, to reduce the computational time, consider random initialization with 0.1 in the experiments instead of computing tensor initialization.
gradient descent algorithm converges to a critical point from both
C PRELIMINARIES OF THE MAIN PROOF
In this section, we introduce some definitions and properties that will be used prove the main results.
First, we define the nab-Gaussian random variable and Sab-Gassiin norm.
"B mild, we mean given L, if Assumption is not met for some Vo. there exists an infinite number of T in any neighhorhond of Vo such that Assumption holds for vV.
4

---

Under review as a conference paper at ICLR 2023
Subroutine Tensor Initialization Method
1: Input: Partition pairs of data {(r,, H into three disjoint subsets D1, D2, Ds
2: if' the Gaussian Mixture distribution is not symmetric then
3: Compute Q2 using D, Estimate the subspace Ü by orthogonalizing the eigenvectors with respect to the largest eigenvalues of Q2
4: else
5: Pick an arbitrary vector a E R", and use D1 to compute Q3 Ia a). Estimate Ü by orthogonalizing the eigenvectors with respect the K largest eigenvalues of
6: end if
7: Compute R3 = -ū,
U.
from data set D2
8: Employ the KCL algorithm to compute vectors {ūi)e(K)) which are the estimates of
(ÜT "; Ji=1- Then the direction vectors {w, ) can approximated by {Ūe
9: Compute Q1 from data set D3-
10: Estimate the magnitude / by solving the optimization problem
1 Σ 1
1
arg min aE
(17)
j=1
11: Return: Use ε as the jth column of Wo [K].
10a
10
10
10
Tensor Initialization
Random initislizatton, 0.1
Gaussian initialization from (0,
10
1000
1500
2000
Number of iterations
Figure 10: Comparison between tensor initialization, a random initialization near W and an arbitrary random initialization
We say X is sub-Gaussian random variable with nab-Gaussian norm K O. if (E|XP) $) < K for all p 1. addition, the sub-Gaussian norm of X, denoted [| defined X bbg supp211' $ (E]X)))
Definition 2.
Then we define the following three quantities. o( is motivated by the P parameter for the standard Gaussian distribution in Zhong et al.) (2017b), and we generalize an arbitrary mean and variance. We define the new quantities I'(V) and Dm (V) for the Gaussian mixture model.
Gaussian with
Definition 3. (p-function). Let N(u, Ia) E Rd. Define ag (i, u) = (u, 2,) 2,)2(1 and Bi u. E2,~N(,,,1)00 1n (0 21)2f] Vg E 1,2,, where 2; and us is the i-th entry and respectively. Define p(u, σ) as
az(i, u.
p(u,o) min (uu + ()(b( u, an u, u, 8, u, i.j
(18)
u² +
Definition 4. (T (T-function). With 78) and k, n defined in Section
we define
1 pl
T 14
T( = Σ
8k (k(W")
11-
(19)
7 k2
2
6x
||
1=1
5

---

Under review as a conference paper at ICLR 2023
Definition 5. (D-function). Given the Gaussian Mixture Model and any positive integer m, define (m)) as
p4:
Dm (V)
+ 1)mh
(20)
p-function defined compute the lower bound of the Hessian of the population risk with Gaussian input. I' function is the weighted sum of p-function under mixture Gaussian distribution. This function is positive and upper bounded by small value. goes zero if all || or all d; goes to infinity. D-function is a normalized parameter for the means and variances. It is lower bounded by 1. D-function is an increasing function of || and a decreasing function of or
Property 1. Given W UV E Rd where any μa E R., can find an orthogonal decomposition of based on the colomn space of W i.e. = + p. If we consider the recovery problem of FCN with dataset of Gaussian Mixture Model, in which D. N(us, Σn) for some h E [T.] the problem is equivalent to the problem of FCN with a; ~ N ER). Hence, we can assume without loss of generality that pr belongs to the column space of W for all E [L].
BA the orthogonal basis of W For
Proof: From and 3)
the recovery problem can be formulated as
min g(W" 2t yr)
W'
For any ~ (H En), æ; can be written as
= z + 1b
where z ~ N(0, E.). Therefore,
W x W (z T pn) W PUx + () w (x
pun)
The final step is because W MU_ 0. So the problem is equivalent to the recovery problem of FCN with æ; ~ (HUN, mn).
Recall that the gradient noise vi E Rdx is zero-mean, and each of its entry is upper bounded by <>
Property 2. We have that ||a|| is nab-Gaussian random variable with its nub-Gaussian norm bounded bu Ev dK.
Proof:
(BI < (K]VaKE)) SevaK
(21)
We state some general properties of the function defined in Definition in the following. Property 3. p(u, o) in Defimition 3 satisfies the following properties,
1. (Positive) p(u, o) > 0 for any u E Rdd and a + O.
2. (Finite limit point for zero mean) p(u, σ) converges to positive value function of a as goes to O, ie. lim p(u, a) (a)
3. (Finite limit point for zero variance) When all u; # 0 (i E [d]), p ( o) converges to strictly positive real function of u goes to O, i.e. limg- pl ( 0) = C.(u). When = for some E [d], limo-00 p( 0.
4. (Lower bound function of the mean) When everything else except |ud is fixed, lower bounded by strictly positive real function, 00x (W") 500g( (W*)), which is monotonically decreasing as lui increases.
p( W
[W Gōx (ōx(W*))
Lm (AW") " Au

---

Under review as a conference paper at ICLR 2023
5. (Lower bound function of the variance) When everything else except is fixed, pl W (ox is lower bounded by strictly positive real function,
La( W Tok( (W*),, which satisfies the following conditions: (a) there exists &y' > 0, ( odx (W*)) is increasing function of when (0,C.)): (b) there exists Ç. 0 such that L.( (ox odx (ox()))) is a decreasing function of a when (Ss, +00).
ook(
such that C W uu .
Proof:
(I) From Cauchy Schwarz's inequality, we have
E2 (o 2:)1 s / /EanNiu.nnldP(0 zi)l
(22)
Na, 2))2; 2/ S V B Be, 1622 2,)2f]
(23)
Bai 10 2,) /
The equalities of the 22 and 23
hold if and only if d' is constant function. Since that & is the
sigmoid function, the equalities of (22) and (23) cannot hold.
By the definition of p(u, σr) in Definition we have
Bu(i, 0) ag u. 0) > 0,
(24)
ag(i, u, 0) 0.
(,)
(25)
u
Therefore,
p(u,o)>0 >0
(26)
(2) We can derive that
lim 4,
-))
22
00 (27) - exp( || uill? )dz;
lim
1)(
a
|| - uell )d
é'lo 22 - expl
2
u 6 +11
60 22) 1 exp(
|| 2
)dz
/
é'(a (2))) exp(
| )dz;)
2
2
(27)
where the first step is by Definition and the second step comes from the limit laws. Similarly, we also have
1
lim us
(B2(i, u. uZ + (i u, O)
||= -1il3 )dz;
lim uy
(o (2m) exp(
|| - 12
B'aa 2x 22)=((2TT) - exp(
)dz,)
2
( 21)
21) 2 (2m)
1 expl
||:|| 2
)dz
11 21(0
exp(
|
)dz; )2
2
(28)
Since that 27 and 28 are positive due to Jensen's 's inequality, we can derive that p(u, σ) converges positive value function of u, goes i.c.
lim p(u, σ) = C. (a)
(29)
u=+0
7

---

Under review as a conference paper at ICLR 2023
3)) When all u, + 0 (i E [d),
1
lim (B2(i,
00
a .0)
0))
o -
o +1
0
||
||?
lim
2 (a 22))((2))))))
exp(
)dz;
2
||5 21 112
o' 222
$ exxp(
)dzz) 2
0²
120 - 111
lim
exp(
ddx;
0-0
2
0²
|| 111
42
d'(u: 24)
0²
(2
exp(
2 2
)dr,)
24
(30)
u2
u
lim 0 (u:)
(
0²
4²
a²
-lim o-0
12
02
1 1
= lim (u;, a-1
1
(w))
The first step of (30) comes from Definition 3 from some basic mathematical computation and the limit laws. The third step of (30) is by the fact that the Gaussian distribution goes Dirac delta function when goes 0. Then the integral will take the value when 2; = 1. Similarly, we can obtain the following
The second step and the last three steps derived
lim
BBoli.
σ _ .0)
-) azli, u
o 0
| 31 112
lim
l0 22
exp(
)dz;
(31)
||
|
8 22
expl
)dz;
2
= (u,) = 0
8

---

Under review as a conference paper at ICLR 2023
u [Soli,
σ - - ag u _.1))
lim
o-0
do
||,; Uil )dæ;
lim
(x;) (2TO22) - cxp(
a-0
do
20
0 (2T)) ) exp(
12, - -ull2
)drz) )2)
-
21 = a. 24
20²
|1:; - usl1?
lim
(x:) (I:) exp(
)( 1- + | will? 3)des
-1
a=0
20
(32)
|
uil1
2(
d'(x,)(2TO0)) exp(
)dzz;)
20²
|
u4ll
o' (2TT) - exp(
1-0 + 1| o 2)dx))
20²
-202 (us) 15' (((ui) (u:)
(u:))
lim
0
-
lim -
+00
Therefore, by L'Hoopital's rule and 31
32
we have
lim
+ (Bo((i _ aoli, .))
0 +0
u
u u , - aoli, ..)))
(33)
lim
(Bo
- 20 do
30
Combining 33 and (30. we can derive that pl _ o) converges to positive value function of u as a goes 0, i.e.
u _ 0) = Cu( lim pl
(34)
When u, for some [d]. lim, 00 1)(Boli 0) a² -a o)) by 31 Then from
the Definition B we have
lim pl 0)
(35)
σ o
(AW') "ox[WW-] o0x (W") as
(4) We can define Lm
(AW*) Au
p( (AW') Av
L.ml
σdx (W*) .dxx (ox(((")) (W"))= min e.E(0,u
(Wo)(W') ,6xx (oxx(())) (W")) : = uj for all j #
(36)
Then by this definition, we have
0 Cm (AW Au
σdx (W*) oō (W")) p( (AW*)TA Au
crōx(W>) gō (W*))
(37)
Meanwhile, for any 0 S u/ S ui since that [0, ug] C [0, u²], we can obtain
Lm (AW*)T Au
(dx(W.) σō (W")) 2 Lm (AW*) Au
(ox) ,ōxx (W") (W)),
(38)
Hence, Lm (AW*)TMM
(W" od (W*) is strictly positive real function which is monotonically de-
creasing.
(5) Therefore, we only need to show the condition (a).
When (W+ u); * for all i [K].
W u
lim pl 0
(ox oox(W")) = C.(u) > 0.
(39)
9

---

Under review as a conference paper at ICLR 2023
Therefore, there exists Ça > O, such that when 0 < o Ss:
( (ox))))x(W"1)) > Co(W*Tu) u)
W oOk (W+)
p
(40)
2
Then we can define
L σōx (W-) (wx( = Cx w) o²
W u
(41)
25.
such that o Lo, W
(W" (W (0xx(")) is an increasing function of below
P WTTu (W-)) (
When (W- u); = for some E [K], then
W u oōx (W.) (w*() = 0.
lim pl a
(42)
We can define
W u C.(
min {pr W v welard (ox))00x(W))) by # uj for all j #
(43)
Then,
T u Lal
W v m.((u.C,)) oδx (W+) od ( : oy (W"( ūj for all f1}
min {st
odx (W*j Rdx (W"))
(44)
For any 0 E u/ S un Ev,, since that [ur, Sor) [u/, (3r we obtain
W u (ox((w)) (w.)).ox(W""))
W
LLal Lal
σōk (W.)* oōx (W*))
(45)
Therefore, derive that 0- Lo o-
L W
(xx(1x σox (W+) is monotonically increasing. Following
the steps in (4), we can have that o -1 W
[dx oō (W*) is a strictly positive real function
which is upper bounded by pl W
(W* 00 (W*)). In conclusion, condition (a) is proved.
w For condition (b), since that Go 0, pl a oōx (W*)) is continuous and positive, we can obtain
W pl
(ox(W.) σōk (W"))
>0 0
(46)
o=c.
Then condition (b) can be easily proved as in (4).
We then characterize the order of the p function in different cases follows.
Property 4. To specify the order with regard the distribution parameters, plu, σ) in Definition 3 satisfies the following properties,
1. (Small variance) lim, p(u,o) O(o*).
2. (Large variance) For any limm- p(u,o) -(
3. (Large mean) For any 0, lim p(u, x) 2 O(e lny T
10

---

Under review as a conference paper at ICLR 2023
Proof: (1)
Boli, u, 0) -aoli, u, o)²
=BewN(an 1 (a: =)] - (Ra~M(u.))0'00 (o. =
1
c0 (e d2)
e
d2 -
(a 2)
6
2m
2T
0c
1
12
1
a nol
)
2x
dl
4
16
96
1mT
(t-ue)
(47)
20
di)²
16
V2TT
7
11²0² + +
+
(30" 4 + 61²00 + + +xO0))+ + ...)
16
32
768
0²2 + 0²
30 + 6p20 + 1²04 )
192
1204
0"
+
64 + +o(o"), as a + 0+
128
The first step of (47) by Definition The second step and the last steps come from some basic mathematical computation. The third step is from Taylor expansion. Hence,
0t + 1²o
lim (Bold. u) - auli, u,)))
1
+ o(o0)
(48)
128
64
Similarly, obtain
32(1,u,)) a2li, 0)
112 +1
(Ee-Nio.110'0 2)23)) 2)
-E,_No.1110 (0 10. 2)2
=E
12 +1
la x)
1
(a 20
=)
dz
dz)²
2
12 +
22T
t
3
5
)
(t-pat? 2 dt
40
16g
96g
V2TT
(49)
1
11 no
20
dt)
112
4g
16
960
V2TO
1+112
30
+
6p
+ 02
+...)
16
32
1 +
2
150 + 45 02 + 15p 02 + 802
+...)²
1
1
32
9
33
13
2
+
11
12
1
2 o(o²),
0+
64
Hence,
a2 u, 0)
9
lim (82(1, -+0
0² o(02)
(50)
12 21
64
Therefore,
lim p(u,o) min {uu + 1)} a
(51)
je(d,u,7p
128

---

Under review as a conference paper at ICLR 2023
(2) Note that by some basic mathematical derivation,
1
(2-p)2
1
1
(m-p)2
s (a .2)
2
dz
2
dz
-0- (ea.s
+23
2
00
1
(otlui)2
2
2
de
1662
12T
0
(52)
2lu10+202
00
1
(e120)
2 dz
22T
00
21p
e
dt
8/2
p|+22
We then provide the following Claim with its proof to give lower bound for [u]+20 e
52)
Claim:
dt > e 222lloo-00 20 -k1 logo for ki > 1.
Proof: Let
f(0) = f
/ E - dl - e 21ulo---00 200 logo
(53)
Then,
-(a)=e = ((2uul + 40 + ho 10 jo- 22 - 2n²).
(54)
when large enough if k 1. Combining that lim,-+o f(a) = 0, we have f(a) > when is large enough by showing the contradiction the following:
can be easily verified that for given ||| 2 0. (a)
Suppose there is a strictly increasing function f(x) 0 with som f(x) 0 when is large enough. Then there exists To > 0 such that for any e > 0, (x) < e for x > 20. Pick = f(xo) >
then for 11 > To. [xx1) > J (xo) Contradiction! Similarly, we also have
1 é' (002) 2)
(--
2 de
dz
2T
6
+
6-0
+2 2TT
1
(z-w)²
22
E
dz
0
60
22T
(55)
clu
2
dz
22
2 elulo+
12
T
dl,
2TT
Inlto
dt e - 10 b2 and the Claim: MM e-
-22 logo for h2 to give upper bound for (55)
Therefore, combining [2 55 and two claims, we have that for any 0,
1
Boli, u, o) - on(i, u. 1), 2 8T o
2T 2 2
(56)
gl-e
(The above inequality holds for any 2kg > h1 where h > 1 and l2 1.) Similarly,
f 8² ())
20
22
1
(m-p))
2 dz
dz
V 2T
(e
+ 0.2 + 2)2 /2T
z²
dz
(57)
16620.8
V2T
1
cIll0+202
(t (c-20)2--t dt
8v 2T
2/14+20
Claim: [|att2 (t - 20)2-- 12
dt
22uuoo--2
2 log if kı
3.
Proof: Let
f(0) 1
00
(t 20-20)2e
3 dt
2 20 -
(58)
1u|220
12

---

Under review as a conference paper at ICLR 2023
('())= 88
/ - -
dl --1ulo-2 (Aot-hi + 111-1-kk + -2/14/0
k: 4e 20- (59)
|a|t20
We need (o) < 0 when a is large enough. Since that ('()) - 0, (0) - O when a is large, we
need (0) and (r' 0 recursively. Hence,
(o) =e 20 20 (64g 3- + 96 2-h + 16(3k) - 3 + 11 j + 8u(-1² - -3 6k1)
4kg (3k: / )0 -1 + 2kg (1 kn (1x + 2) 2 2
+ 1/ + (2) + 11)0 3- - 16e 1²² < 0
(60)
requires hn >> 3. Similarly, we have
[ d'(o 2)²
1
c x dz 2
2
1
22
4 d2
2 20²
[
(1 (1-o) of (1-o}e
4 dt
V2T
0
20 V2T
22T
(61)
and the Claim: Jo -0)o 1/2 dt < ee=
o/²
bg logor Hence,
a2(i, 0)
2
1
82 u,
2
(62)
112 + 8T th tu² + 1) 2
03.1
(The above inequality holds for any 2kg > K1 where b > 3 and l22 < 3.)
Therefore, by combining (56) and 622) for any > 0
lim puu, σ) 2 0 (itt))
(63)
(3) Let a be fixed. For any > 0, following the steps in (2), we can obtain
[ 00
8 (0 2) 22x
e (--p)²
d2
1
(m-p)²
dz
-00 (e
0 +
+2)2
22x
1
cotlum)
2
2
de
16
22T""
0
(64)
c 21p|0+200
000
E -
dt
8
ul+20
>
e
8
2n
ul+e
1
(a-p)
1
1
(o-p))
(a 2)
2
de
dz
v2 2m
2
e
a-
+ /2T
1
(s k)
dz
(65)
6.5
V
2T
2
V2T
n1--c
Similarly,
(a
2)2²
1
(z=p²2 4
dz
2
1
T
2
(66)
v 2m
8
2
uste
2)²
2
1
dz <
2
2
2
1
(67)
/ 2m
V
2m
313-E
lu|2
We can conclude that lim plu, σ) > O(e
[u
3tr.
Property 5. If function fxx an even even function, then
Be-N(e. (S(
(68)
13

---

Under review as a conference paper at ICLR 2023
Proof:
Denote
g(w) - (2) exp(p= 2(10 -1)= (x 1))
1
(69)
By some basic mathematical computation,
g (a = - ... -.../ g(01 ... ra) ... daa
Bx [[)=)]
xERd
g(21.22, 22. .. ra)d( xn )dz2 .. daa
g 11 82 aa)drrdr2 drd -00
(70)
g( ((=))d
BERd
[(xx) 2) expl_ 1
11 1i) (x + 11)
WEER
Therefore, have
Be = (N (((
(71)
Property 6. Under Gaussian Mixture Model x diag(of, ... old) we have the following upper bound.
El NwN Ex) where Σ, =
E EL A.)G, x)
[ S (2t 1)!!//u
+ ||
(72)
Proof:
Note that
L
Ee (.ii)))( x)²* = Σ XrE E 1 = Σ Ar piu " 1y
(73)
where the last step is by that u æ NNu n.u u Enr) for NWw, Ei). Et). By some basic mathematical computation, we know
E By~N(uT unu E.u) 2
1
(y-u T m.)
(y u T Mi + 21)22
2u En
dy
v 2 Enu
2t
(u-u m2)²
(u (2)
2t
u 1
2u Eig dy
V 2 Enu
21
2t
1u T 21)
is odd
(74)
(w-1)!!(u E)u)
p is even
P=0
21
(2t)
5 p=0
1u [11
(1 2 1)!! 2 Ejre z
<(21
14 1e2" Ever 2 1) 14 T
<(2t 1)!!||u 20 (1 + | 2
where the second step is by the Binomial theorem. Hence,
Eanyi A (u ) < (2t 1)
(l +| 2)
(75)
14

---

Under review as a conference paper at ICLR 2023
Property 7. With the Gaussian Mixture Model, we have
A Al + -1
EL XI - (2t - 1)!!
(76)
Proof:
E Re AoN( E,)l
d
E B (H. x.)
x
i=1
d
=E =E, Et A. Ex) [d"
2
d
1=1
21
<
Eis E
A,)( 1d
i=1
(0t m1
(xs
Maj + Myx)) 21
X,
exp(
dx
20
(77)
2t
0
k is odd
1:
(1:
1)!lo
k is even
2t
(2t - 1)!!
10
k=1
Xy A + (2)) 1)!!
im1 jml
<d 1)!! Σ) (|ll||l [|||||++||22 +|
In the 3rd step. we apply Jensen inequality because fx) = x" is convex when x 2 0nd t Z 1. the 4th step we apply the Binomial theorem and the result of k-order central moment of Gaussian variable.
Property 8. Under the Gaussian Mixture Model x Ei XrN Ex) where E, AT DiAL we have the following upper bound.
Ex XoN( (u x))* S (21 (21-1))!||au 2 A Aelllall + 1|
(78)
Proof:
If æ MM,, Ed), then u x NNu He, To Er²) (((AA)) T Aipi (Aru) Di(Aru)). By Property 6 we have
E (m Ex) (u 2)) S (2t 1) + || +| 11)
(79)
Then we can derive the final result.
Property 9. The population risk function F(W) is defined as
f(W) = 13 b Ao,
x.) (.n
n
E E3 )oN(M
eWW vi))
(80)
F. Ba A (WW; y:)
15

---

Under review as a conference paper at ICLR 2023
For any permutation matrix P. where {T{1))5 is the indices permuted by P, we have
H(WP P. x)
Σ
o(w+(1)
xx)
K
n (
K
(81)
(ww xx)
K
H(W x))
Therefore,
f(W) - ((WP)
(82)
Based 7 and
derive its gradient and Hessian as follows.
d( N(Waa3 30, v)
1
y HW)
K H(W) (1 H(W) 8 ('(w] x) ((W) x
(83)
Pe((W x.
Eイ11 xx
(84)
Ow ow,ūhw;
R2. Φ' [ )) (' x) H(W) 2 H
j 1
(.(W -
H= W (WW(W)
R2 [w) (w) x) HP H(W K 0 [w) x) H[W](-HHWW)
+ HIW)
j=l
(85)
Property 10. With Dm (gr defined in definition 5 we have
(i) Dm (T) (D) (V) Dsm V
(86)
(it)
< D2m (1)
(87)
Proof:
To prove 86 we can first compare the terms E dras El= Aea and Ele daae where 2
i E [L] and Ei >== 1.
Σ xja; Σ Asa
Σ Xea (0} 13--x - 2ya3)
iml
j=l
Σ
Apa ((1 - -xe)a²
Σ Xyaz)
xml
ISiST.j7i
Σ Apa
Σ
Aja
Σ )za3)
iml
15iSL.f41
1SiSL,fi
(88)
Σ Aras (
Σ
Xj(a - -G3))
1S/EL,J
Σ
(NAdaaiaa) -a3) + - -3))
Σ
a,)a,-a,) + ta) 20
The second to last step is because we can find the pairwise terms \ąa; >y - at) and Ajaz
\1(a - a²) in the summation that can putted together. From (8) we can obtain
I.
Xja;
<
\ja
(89)
i=
16

---

Under review as a conference paper at ICLR 2023
Combining (89) and the definition of Dm in can derive (86)
Similarly, to prove 87 we can first compare the terms (E x,a;)² and E d. where
a, 2 1, i [2] and 2i=1 X
Asa
)xai)
Σ Xeac (a: )yas)
5=1
Aa; - (11=>
Σ )ja;)
Arai
Σ
2ya: -
E )zaz)
==1
15J$L,#i
1515L,
(90)
Σ
Maa
Σ 1y(a- a,))
ISishjfi
E
(A:)aa;(a; - -0,) + +Nddyaslaz -a:))
=
E
Adyla, a,,² 20
The derivation of (90 close to
888)
By (90) we have
)a,,)²
2
Aa
(91)
Combining 91 and the definition of Dm V in we can derive 87
D PROOF OF THEOREM 1 AND COROLLARY
Theorem is built upon three lemmas.
Lemma shows that with OddK' log² d) samples, the empirical risk function is strongly convex in the neighborhood of W
Lemma 2 shows that initialized the convex region, the gradient descent algorithm converges linearly to a critical point W., which is close to W
Lemma shows that the Tensor Initialization Method in Subroutine initializess Wo RRdx in the local convex region. Theorem follows naturally by combining these three lemmas.
This proving approach is built upon those in Fu et 2020). One of our major technical contribution is extending Lemmas T and to the Gaussian mixture model, while the results in Fu et al. (2020) only apply to Standard Gaussian models. The second major contribution is new tensor initialization method for Gaussian mixture model such that the initial point is in the convex region (see Lemma 3 Both contributions require the development of new tools, and our analyses are much more involved than those for the standard Gaussian due to the complexity introduced by the Gaussian mixture model.
To present these lemmas, the Euclidean ball B(W" P p*,r) is used to denote the neighborhood of W P where r is the radius of the ball.
B(W P .)) ( daxk K
W W P | Sr}
(92)
The radius of the convex region is
CzEn L X
E E-11
k pl
w mi
8x W >1> -1-
(93)
K
Ar(l +
|| a Et. Xe(1 + |3 1)8
17

---

Under review as a conference paper at ICLR 2023
with some constant C3 > O.
Lemma 1. (Strongly local convexity) Consider the classification model with FCN 4 and the sigmoid activation functiio. There exists a constant C such that as long as the sample size
n C1
Ae + 12 1)?)
(94)
W IA
A1 117
pl
OR (W
d log"
K R2
5k (W
1--1-
1=1
for some constant Ci all W E (WW.r))
O, En E (0. 4), and any fixed permutation matrix P E RKXK we have for
1 - 2c0
W #
n p(
òR (W
Lak
K2
8x (W Σ 11-
(95)
V2 (W)) 3 C2 Σ
Aelliiillo + | I1)a Iak
with probability at least 1 1- d for some constant C2 > 0.
Lemma 2. (Linear convergence of gradient descent) Assume the conditions in Lemma 7 holld Given any fixed permutation matrix P E x* if the local convexity of BB( W P,r) holds, there exists critical point in IB( BB P, ,r)for for some constant C3 > O, and en (0, 2) such that
K V EL Ac[laalll || (1
dlog n
W W'P 0
|1--11 111 El A x*
W-TH: m - (k || 11-
pl,
(96)
If the initial point Wo E B(W rr)). the gradient descent linearly converges to W i.e.
Σ
6x 31 E, 21| 2 5x (W*)
W
E )))))
1)
I|: Wallr S (1 (1- -
W Wnlle
K EL A well + | l)
(97)
with probability at least 1 - d0
Lemma 3. (Tensor initialization) For classification model, with (V) defined in Definition have that if the sample size
we
n k 12 - log d.
(98)
then the output Wo E R satisfies
d logg n
W. - W'P S k KKK3
(Do(V))
(99)
with probability at least 1 - (2(5) for a specific permutation matrix P E RKKK
Proof of Theorem
From Lemma and Lemma by the tensor method in the region B B(W*P, P.r), then the gradient descent method converges to critical point W,, that is sufficiently close to W*, To achieve that, one sufficient condition is
3 know that if is sufficiently large such that the initialization Wo
dlog TI
| - W P F & VKIW P'P'1
< k "
DD
W P
Cscn V J
(100)
Kł (EE >e((| +
|Σ M Et
(1 + ΣΣ ())$)
18

---

Under review as a conference paper at ICLR 2023
where the first inequality follows from || W for W R the second inequality comes from Lemma B and the third inequality comes from the requirement to be in the region B(W* p. That is equivalent to the following condition
n 200 2 12
ID)
Aelll + -1
(101)
1=1
(6, D( - dlgg
where Co max 2. By Definition obtain
A Allll --)))))))) * S (V))
Mell + |
(102)
1=1
1=1
From Property
10
we have that
D
(103)
S D12( v1
D12(W) = D12
Plugging
102
103
into 101 we have
n 2 Coep 2 12 K (i ( dlog2
(104)
Considering the requirements on the sample complexity in (94), (8), and (044).
104) shows
sufficient number of samples. Taking the union bound of all the failure probabilities Lemma and
3 104 holds with probability 101
By Property 4, pl
can be lower bounded by positive and 6x (W 5K (W >|= 11-
w
monotonically decreasing functions Lm
óN (W) 12 F. ŌR ||
(A W. )
when everything
else except |اا is fixed, La(
w
òR W E, 11 when everything else except
6x (W>))| >|=)"
| is fixed. Then, by replacing the lower bound of pl (w
W
8x (W*) > 1 || with x '1
these two functions in [(V), we can have upper bound of (a ( (2 12 (T) 122 (T). denoted as B))). To
be more specific, when everything else 6x (W*) | 11 is plugged in B(V). Then since that (12(T) and Ax (W+)| F. 8x W increasing function of [Ar
except
p
is fixed,
Li
(A:W") A
(I 1
Cm
(A,W)) i
Σ 11- are both increasing function of |uoo B(V) is an
When everything else except
| is fixed, if
/ = max C.. then 02 o 12 D12 (T) is an w
increasing function of
|| Since that Ls(
ŌR |1> 1 òk (W')) b) is decreasing [
function, C.(
W
(x(
-1 is an increasing function of ||> ||. Hence,
6k (
B(D) is an increasing function of | decreasing functions of ||. 22 2 C,( |>
Σ Ser and go to 0, two Moreover, when all
w be the dominant term of (()). Therefore, B(T) increases infinity all E I''s go 0. In sum,
(x(W "11 8x (W-)
| -2 and (12(1) will
19

---

Under review as a conference paper at ICLR 2023
can define universe ( as:
B(V)
(Imax (W*))22
E1=1
Au M
(A/W 6k 11 -2
(V) S fixed
El=
Lol
(AIW
6K W > || 5)
no max
6x (w [1
DD22( M is fixed
(amax (
EL
Au E '11
(A.W))
(k( |د | 11 -2
no max
6x(
(V), otherwise
(105)
where Lmm L, and D12 are defined in 38 Hence, have
43) and Definition 5 respectively.
n 2 p Ki (B) dog
(106)
Similarly,
by
replacing
P (w >| F (x((())) 11
with
5x W- -1, 11 8x
() Pi
when everything else except |حم(ز]| is fixed, or E +- - (or | (w 111
L.s
W
8x
w 6x (W (W')
6K (W >112;
11-
for 12,11 11-1 1) when everything else except E is fixed, (97)
also be transferred to another feasible upper bound. We denote the modified version of the convergence rate as 1-K---g(V) Since that q( is ratio between the smallest and the largest singular value
of 2 f(W*), we have ((V) E (0, 1). Hence, we can obtain 1 K K-2g(V)
(V) E (0. by K 2 1. SK ( Σ -
(A.W*)
When everything else except |Pre is fixed, since that Lma 6xc(W >
monotonically decreasing and Σls A(Ipa + || increasing as
| increases,
is increasing function of li)()) to 1. Similarly, when everything else except | is fixed where
3 2 max (1, (s).
Σ (1ll) decreases as |E|] increases. We replace
W (1, 8x (W*) 11- by | ||C.
w my òK 6k("") E, 1113) and
pl then
6x 61
W T
1 -1E, C11C(
11
6K (k( "
ōx (
| 11
(107)
W+T T
=ha
111
8x 8x( (W
5K
(W+)
Σx 11
decreasing function less than pl
w
Therefore, v is an 11, (.). When everything else except
(W*)
8x(W") x
increasing function of || to when Σ
max
all Σ < Cars go to O. all La(
w
I 8x W (W > will decrease and all
6x (W>))
E I
will decrease to O. Therefore, increases
EL Ae +| 2
20

---

Under review as a conference paper at ICLR 2023
q( can then be defined as
q( wV)
Ti 1= Els de ko
fmnl (A, (w0))) (1
Nx 01 41-
52(
}),
EL (1lll ID)
if S is fixed
Els At "
5x (x (W")) (1=)1=)))
22
Σ/_ (| II)
if M is fixed and all
7 || S Eo'
(108)
A
w T
Sx (W)))) +)+ Digr (1,
<i("-IE 1
- A x I1)a
if M is fixed and one
|Σ, 2 max 1, So}
Ef A1 uy K pl
8x (W>>)
SK( ME
'11-
Eler Ae |+|| 1)
otherwise
12 N pl where r(Ar, M1, Ex, W X
ox (W- ||ا 1 8R (W*) 1 Note that here the
w
p(-) function is defined in Definition
3
Lm (-) and (-(-) are defined in (38) and 43 respectively.
The bound of WW W Pll is directly from 96 We can derive that
Σ
M0l |2 II)
E. (V) = O
(109)
Σ Au
12 1
pl
6k 111 11-3 W
w n4
(1
Σ > M + | 11)
E(V) O
(110)
Σj=1 dull 1 1p pl
5x (W 112, 11 8x W (
W My
+ [ (1 + Ex b))
E(V)= = 0 E/=
(111)
\v 2 111 (x >|>
w-
5g
|| 11
The discussion of the monotonicity of Ew (V), (VV) and & (M) can follow the analysis of g( (V). We finish our proof of Theorem here. The parameters B(V), (()), En (V), E(V), and & (T) can
be found in 105
108
109
110
and 111 respectively.
Proof of Corollary I
The monotonicity analysis has been included in the proof of Theorem In this part, we specify our proof for the results in Table For simplicity, we denote
= pl W in (W"))
6x (W
2 is fixed, if Exll o(1), by some basic mathematical When everything else except E computation, then we have
Acll + +12211)) ( (6((W)))
Ns =CoE 2. 12 16 X (e
|2 ID
)2 d log² d
E d ES 11 pt
Spoly(e) n. J, K. K, 8, (W*)) dlog² d O()r
| 1
(112)
21

---

Under review as a conference paper at ICLR 2023
12 11
1==1
Pt
0 4 =
K2
P 1 X
+ || 11)3)
(113)
(11
K2
K3 Ei= A + | (1) +5)
d n
W. - W'P'|| 0
Li=1 X 17 x²
1 ||
P(
w- pr
5K (W )| || 8)
8x <x(W>>>>>,"
dllog n
$ poly(n, ni T. T, (W
K² +) 0(1 - |
n
(114)
((W.) ((W.) k((w)) K
((F(()))
<
E
(we())) ((0c()--Wi) - w
Oron
k=1
W.
W p P*1[([|ma|| + ||
Ej=1 ( + |Σ (1| + [Σ,|(T]
dlogn n
m nr²K3(11 +))
(115)
Σj A3 || Pj
dllog
S poly(n, (x(x)))))))))))
K K2 + 5) 0 1+ Σ 3
n
d dllog k2 + 0(1) ((1E)))))
poly(n, K6, 6x
n
The first inequality of (155) is by the Mean Value Theorem. The second inequality of (15)) is from Property 88 and the third inequality is derived from (96 97). The last inequality is obtained by the condition that EE]] || = o(1. We can similarly have
K
a((W.)) ) (Wi(()) - wwi
f(We) < E
Orus
S
d n
K² () 0
(116)
1+ |Σ 1
dlogn K² ()) 0(1) +( ()
S To (W"))
n
E -(1), we have
Nsc S R. K, dlog² d (1(((E)))))
7.
(117)
v(v) <1 22
(118)
Σ
d d n K (1 +) v Σ
W.. - W'P s bx
(119)
d k² + |
h(W.) S po (W
(120)
n
dlog 2² + +() |
( 1, n, 8x (W"))
(121)
n
22

---

Under review as a conference paper at ICLR 2023
When everything is fixed except ||l|| by combining (4 and (011)
we have
[O(l
1+,
if
<
Noe S poly(co' .775, R. K, (x
d 2 d-
(122)
[0(1
12),
if Iall 2
1
1
K2 k 162 v(V) S W W I=
0
(123)
+ ||,4111
dlog K x1 + E) (1 (1+11 m|
(124)
n
alog nh d
f(W)) S R,,
K² + [) (1+ ++|ll111)))
(125)
7
f(W)) A (, K. 5x (W v) dlog n1
K²(1 + E) . (1 + 1|
(126)
When everything else is fixed except '1, A2, ,r. where |ارك| = 9(1. j E [L] and | = |pill i,j [L] if | < |ا J E [4], we have
Spoly(co 1 13, k, K, 81 ()*)) dlog²d d. (a1 + azd2 + azd1 + asd + aas)
Tacc
)sp;)²
Spoly(c5' .,, k. K, 61 (W*)) dlog² d. (Et=1 )op,)²
a5
(127)
Spoly(co 17, k. K, 6, (W*)) dlog² d. ((11 + A11 2)
where a = ||, "|00" 1|
80 (1 | 11)
43 = (1 || + 1) و
اا1اا + |Σ 1/ " اا
+ (
+ "
+ 1) 01 = Σ 1/
+ + +
E
| || }0))
+
0s = (Efe >3 [a
+ Σ م +
E,
+1)0
The second step of 127 is by a; 0
1 I A
0 0.
(128)
K2nT x2
dlog K (1+ 0
1
I W'P |F S 76
(129)
n
1+ I+
d dlogn T1
((W.) S 7,, 61 (W')) f(W.) S poly(n K, (6
v
k² (1++)))((- -0
(130)
n
I+
d logg n k² ()) 0
1
(131)
1+x
If | 2 |اا1, j E [Z]. we can similarly derive that
Nae Spoty(Eo" ",, K. K, (W")) -llogd d. (ai + az22 + az + and + as)
1//=1 )xps)²
(132)
Spoly(Eo' n,, .n, K, (W")) dlog² d. (0(1) - 0((1 + -x)
1
a < 1
(133)
K2nr x²
1+>
dlogg n
W - W'P F S poly(7, K, 6, (W"))
K (1++ - + VAi
(134)
n
dlogn n n
S 5 K,, (,6,,,,,,6"))
k2 0(1+ Vxi
(135)
dlgg
((1)
F(W.) - poloy(,, K,, 7, 6 (W"))
1+
(136)
23

---

Under review as a conference paper at ICLR 2023
E PROOF OF LEMMA T
We first state some important lemmas used in proof in Section E.1 and describe the proof in Section
E.2
The proofs of these lemmas are provided in Section E.3 E.7 in sequence. The proof idea
mainly follows from Fu et al. 2200)). Lemma shows the Hessian V f(W) of the population risk
function is smooth. Lemma illustrates that (=) is strongly convex in the neighborhood around
14.. Lemma
8 shows the Hessian of the empirical risk function f2 (W") " is close to its population risk f( in the local convex region. Summing up these three lemmas, we can derive the proof of Lemma Lemma is used in the proof of Lemma Lemma 5 is used in the proof of Lemma 8
The analysis of the Hessian matrix of the population loss in Fu et al. (2020) and Zhong et al. 201 7b) can not be extended to the Gaussian mixture model. To solve this problem, we develop new tools using some good properties of symmetric distribution and even function. Our approach can also be applied to other activations like tanh or erf. Moreover, if we directly apply the existing matrix concentration inequalities in these works in bounding the error between the empirical loss and the population loss, the resulting sample complexity bound loose and cannot reflect the influence of each component of the Gaussian mixture distribution. We develop
version of Bernstein's
inequality (see (208) ) that the final bound is Old log" d).
Mei et al. ( showed that the landscape of the empirical risk is close to that of the population risk when the number of samples is sufficiently large for the special case that K = 1. Focusing on Gaussian mixture models, our result explicitly shows how the parameters of the input distribution, including the proportion, mean and, variance of each component will affect the error bound between the empirical loss and the population loss in Lemma g
E.1
USEFUL LEMMAS IN THE PROOF OF LEMMA
Lemma 4.
E (N((mTa) rr,T d' xx)) o[
(137)
where p(1,, o) is defined in Desinition 3 and R = (r,,.. ,n) E Baxk is an arbitrary matrix.
With the FCN model 7 and the Gaussian Mixture Model, for any permutation matrix P. for some constant C12 > O, we have we have
Lemma 5.
V22(W x) V2((W', xx)I
E EL (.((EE
sup WWW'E
I W'IF
(138)
SC12 dd K
Σ
aelllll + 1E Σ AOlA ||E
Lemma 6. (Hessian smoothness of population loss) In the FCN model 7 for some constant Cs. > 0, for any permutation matrix P. we have
[[V2 - V-J(W-P))
(139)
<Os K². A((ll
E
DI Σ
11 +1
W|W
W Pllr
Lemma 7. (Local strong convexity of population loss) In the FCN model 1 for any permutation matrix P, i W PllF S r for an eo (0, }), then for some constant C4 0.
4(1 - 60)
pl
W
14
8x (
(W")127711)) Iak
K2
R R2
(
E 11-
1=1
(140)
>V = C4 Σ A + Σマ Iak
24

---

Under review as a conference paper at ICLR 2023
Lemma 8. In the FCN model (1) for any permutation matrix P. as long as 2 C² dK log dK for
some constant C² > 0, we have
dk logn
sup We
S Co Ellall + |3 112
(141)
n
with probability at least d=10 for some constant Co
E.2
PROOF OF LEMMA
I
From Lemma and
with probability least 1 d=
2 (n(W)
2 f(W) - [(V) - v2 (wW)ll I
Ω
60)
E
pl
W T M
8k (W")
2, -1
K2
TpT
K
òx W
11
-
Co
Σ
Al + | dK log n
n
1=1
(142)
As long as the sample complexity is set to satisfy
+ || 112
dK log
Ce
1=1
(143)
W μ1I
60
TjT K x² pl
8K [ ))
K2
ux (x (l
ie.,
2016
2
X ((all + || 1)3)
(144)
L
1- 1) dk>
A
pl
5k
W
x2
8k
1
1=1
for some constant C₁ >
O, then we have the lower bound of the Hessian with probability at least
1 d010 10
V fW) =
2c0
L
Pl
W E
8k( ()=)) (145)
K2
K
5R
140 and By
141
we also derive the upper bound follows,
f..
dK log
C4
X M||
2 2 + Co
Σ Acllmll
1))
n
(146)
S C² Σ
Aa + マ 1))
1=1
for some constant C2 > 0. Combining
145) and (16). we have
2 1 - 2e0
A1
1|-
pl
W #4
8x
W
I (1)
K2
K
5x W
Σ 1|
(147)
SV 3 C2 Σ >0 +
1))
25

---

Under review as a conference paper at ICLR 2023
with probability at least d=10
E.3
PROOF OF LEMMA
Following the proof idea in Lemma D.4 of Zhong et al. (2017b), we have
B pa
r a d'(o 2:))²]]
Ag Bo
(148)
k
Ao Pew.NNNi
r, x 2 . xz) xx. rz)
(149)
i=1
Bo = Pew.A.Wie...
Σ
r o' 21)00(0 x1) xx Ini)
(150)
it
In Ao. we know that Bew.3N(u..d))+33((m..) 0. Therefore, by some basic mathematical computation,
Σ E E Mon.) Pi (T:(0((00 x.) (x) + Exaa(eeee
Ao
j71
teje,) + ΣΣ x,zieeeT)
k
r. (0= 1z) afeee + Eojeze
(151)
Eg M 2,)aū1r? e,e""
E Em Bow
z:)rr x;)rrTeeee5.r
j
&
32 u. σ) +
G0ll 0) (1+)
In Bp. 0n (i, p,
E Egg (e (.t.:d))))3(((..))) (r 0. By the equation in Page 30 of Zhong (0177)) have
al.
E m~ NNN 12) WNC (T. (o'o(((00))))) (6 2:)0(a (ffeee +afere zaileee] +
B, Σ
ele,)) + Σ T + Σ Ex + Σ Σ 2 m|
#
171
(o (.)) + Σ pu 13)
(152)
26

---

max Under review as a conference paper at ICLR 2023
Therefore,
A
a2(i, u. σ)
&
ag u.
Ao + Bo =
Σ
1
1+ k
i=1
==1
k
Σ
c0 (1, μ4 01 14²) +
11, σ) + Σ Σ
iz So He, (1) + +43)
1=1
i=1 jpi
(2. 02
2
Σ 2
0)) (4) (1+ 13)
14
19
2 o( R
(153)
E.4 PROOF OF LEMMA
Following the equation (92) in Lemma 8 of Fu et al. (2020) and by (85
K
(a( Ex.((W)) 1//000
(154)
By Lagrange's inequality, we have
(W) (,,(W') < (max (Tra,d)
-1))))1120]) ||z||| VKI W - W
(155)
k
From Lemma we know
[T S C7
(156)
k
By Property 7 we have
E EN Ae ا|حام|| 21 S d'(2t - 11!!! Σ
Acllmul + E
(157)
1=1
Therefore, for some constant C12 > 0
V v2((W0I1
E EE AoN((H:
sup W*W'
S K ||
W
W
<K?
Aelllalllcc + |E|)))?
3d
Acll + |
(158)
2m1
Σ 1=1
C2 dēk3
AClumulbo + +1
All + +|E
1=1
E.5 PROOF LEMMA
Let .a..... a T v'j(W*P) P) RRR xdk
E RaK Let Dj Raxd be the (j,l)-t block of v²j(W)
By definition,
[V V'J(W*))]
max Σ Σ a
A i
(159)
|||||
27

---

Under review as a conference paper at ICLR 2023
Denote P (P1,'.. .PK) RRxX
By the mean value theorem and (85
8 ((W)
8 PS(WP))
A Sw
E La) - E5,(W*P)) ax:
F dwij
(W')
.wk W W'Ps' xx
Or
k=1
K
E/ E.)
(TeLk 2. Wp Wpph) >p)) xx
k=1
(160)
(WW"
where W' W + (1-1) W P for some (0, 1) and Tj.t, is defined such that
Ber
TyLR x E R. Then we provide an upper bound for Ena- Since that 1 or O, we first compute the case in which y 1. From (85) we can obtain
R² [w] (w) x) "2 ( x) x) H t (w x) H(W)
i
Sy)(W) {
(161)
j=l
We can bound (W) by bounding each component of 161 Note that we have
1
[(w))
2))((( w x)) (1 ((w) x)) (ww xx))
K2 0 [w] ()) x)) H2(W) S K2
<
R= (ww) x σ) w x))
(162)
((w) x))(1 20( x:)) 1 (ww a:)(1
p" x) HW)
(163)
K
K
t2 [ x)
where 162 holds for any j. [K] The case = 0 can be computed with the same upper bound by
substituting (I-H(W)) 1 (1 (ww x)) for ((W in (161) 162 and 163). Therefore,
there exists constant Cp 0, such that
ky)( S C.
(164)
We then need to calculate Tykkk. Following the analysis of E (W), we only consider the case of y 1 here for simplicity.
Tiak K3H3(W1) O (mo) (w'' x)o (w' where j, l, k are not equal to each other
-2
(165)
KJH De (w') 2r)d' (wo) an (wo (n)' k- p"(w!) ())0(( ax), 2 (0'
1 k
Tyjjk
( (w0) x))² Rना 6" (w', x) (wo x)) d"
KH(W', j k
(166)
28

---

Under review as a conference paper at ICLR 2023
a. Anyr E DL Et E.)
> k=1
1.1. (ar, w
W px)) (a] () x)]
K
K
E B M(m,
T2
E
(ax, wo - W'px)) (a (a x))
j.kll
k=1
1=1
K
K
E E/ Man,E)) Ex)
T.
BB((ws - "'pp) x.) /B((aTa) xa) x)91
k=
K
K
Cs
E Eaw Ele M(n,En) En)
Σ 1=
1 - W'pa 11a.1111111111 ||r
k=1
L
|2 11)
Ac(ll + ||
(167)
for some constant Cs > 0. All the three inequalities of 167 are derived from Cauchy-Schward inequality. Note that we have
2 K3H (d' (o[ 2)) s ww] x1( o [ww o( x)(1 oww x))
K3 x 2 x)) (
x 2 ó0 ( x)) 22
(168)
-2
8 )(w,] x) (w) x) (w]x)) x) $2
(169)
K3H3(W)
3
K²H²(W)) 6" ("ww] x 06 ww x²)
30 [ x1 [ x) x))(1 20( 2))((() (1 - x))
(170)
K2 Kz (w x )b 10 x)
3(1 [ww] )1 2 x)) x))(1 [1 pww T x)) 33
8" (w x))
(1nn) (1 c x:) )1 - 6 x)) + 6 (10 x:)
VI
<1
(171)
(HWW)
K K 1 w a))
Therefore, by combining [165). (166) and (168)
to 171
we have
[T S C7 J.ik S
C7, 1, [K],
(172)
for some constants C7 >
0. By
159p.
(60).
167
172
and the Cauchy- Inequality, we
have
[ V2J(W* P)|
L (l + ||
<C CC& C W- w Pllr
1D Σ
K K
max |a|l=1
|al122|ai|la
SC&/ CFK. W - W PlP
Allal + |
Al + (2211)))) !
( ==1
K
||alll )²
X + +11 |1) Σ (1 122 1
<Ca/CRK' C2K3.
|
W W'lll
(173)
29

---

Under review as a conference paper at ICLR 2023
Hence, we have
(WW) F(W P)1l
<CgK
Aallaal + + 11) Σ Mlll +1
W|
W~P
(174)
for some constant C > 0.
E.6
PROOF OF LEMMA 7
From Fu et al. 2020), know
K
V'((W'))
= min 4
K2 De
AnN( Ei) (
(E
(w ())(at())))) ] Lak
||||=1
(175)
K
||||= K2 Be A.N(
min
Σ
x (wj
{a]
Lak
with a = (aT :.... a E RddK, where P a specific permutation matrix and (T*()) the indices permuted by P. Similarly,
K
v'j(W*P)
max a T VV/j(W"))) Iak 3 Ca. max E |a|l=1
Σ
2))))
T
Iak
|||||
==1
K Σ (a x))
C4 max E B A. ||||=]
Iak
j=l
(176)
some constant C4 > 0. By applying Property 8 we can derive the upper bound in (76) as
K Lak - C4
C4 A.-B-EELAANNN A.V(H. D.)
E(a
Milleel + +||
Lax
(177)
1=1
To find a lower bound for 175 to the weight sum the expectations over general Gaussian distributions.
first transfer the expectation of the Gaussian Mixture Model
min BE AnV ||]==
E.)
(Σ
Σ
8 (wn (a) mn) )
==1
(178)
K
"x)(aa)))) a:) )
min A. Di)
d'(w3
Denote U E pdxk as the orthogonal basis of W For any vector a; E Rd there exists two vectors b, E R and c; E dd-k such that
a, Ub: U.G
(179)
30

---

Under review as a conference paper at ICLR 2023
where U1 (d denotes the complement of U. We also have U. p4i 0 by Property Plugging (179) into RHS of (178). and then we have
Σ a a d'w,i [ ) 21
E Ne Et)
(180)
k
(U; + Ulci) ''ww; x(w;TT)) -o)o(==)²² x))²
-EE 2.)
= =++B+C
K (
T U a (aaaa)))))) 2))9
A BL Ei)
b
(181)
i=1
K
K
C = E
2
Σ
c
T. U "' T(w
(Σ Z x "e;;
1=1
E N )
2c, UT x EanNiN b U p'(w, x)0((u œ))
(182)
K
2c, U pi Bm-N(n
b.uu x "'w," T >)²((;; [o]]]]]]]]] =0
=1j=1
where the last step is U.P, pi by Property I
B = B-BB-N(WI ((),
c
UU w. ø' o'w; x))²²
1m
-Bo En)((" s)
by defining t Σ
ø'(w, x). B8-K and s U-
K
BiG 21
Σ
Eltity81311
itj
Σ
oi +
E mI)
Σ
[lt (UTM)) (UIM)),
Σ
(U LU)Ro
+ Bi( U.Pm) E
Σ
Σ U
Roo
(183)
The last step is by U. μ1 The 4th step is because that s; independent t, thus B[44,8,3,] = E[sss]][ssss]]]
UUI)) (U i E[s1s}] = (UTw)) i (U.)a. ifi=j
(184)
Eie r.Tor xc á' .x:)) 2 we have
Since
is function for any r; E Rd i [k)], so from Property
& r x (o-2
E Ee
Em ((n.
r x- (o=0(()
(185)
Combining Lemma and Property 5 next follow the derivation for the standard Gaussian distribution in Page 36 of Zhong et al. (2017b) and generalize the result to a Gaussian distribution with arbitrary mean and variance follows.
31

---

Under review as a conference paper at ICLR 2023
k
A Eg-NiH Ei)
(2
U x.
p'w,"" 22)
1=1
k 2 (2T) $ 10 E
(Σ
by z. p
(=)TT))) 2))9 )
exp (
(-21
(-
1
|||= - UT 12112)
2
1=1
= -(2m2 $ 10 1U
(2m)
Σ b, vt (
exp (
s (-11
1 (-
"|| V UT me der(vi))at
2 / (2T) -2(m)
$
b vt 8. (((())))
1 (W+)
V mill? /di((vt))at do
exp
2 / (2T) $ T "
b, (Ōx( | 11
'1 9.) )
1=1
v E liw
1g
exp
6x( (W
det
(et( / 11, (W*)
2
|
Eg
(b) T VI ox Ox(
1)g 11 (W*) 9
|Σ 1-1 7 R2n p(
W MI
E 1--11110 1/12
1
20x (W*)
(186)
The second step is by letting- = = UT x NNU μ1, U ΣU), y - S |2 ||ly| for any y E RRKK The third step by letting s = VTz. z. The last to second step follows from w.
9= 1 where g ~ ~V E (W-- Ik) and the last inequality is by Lemma 4
Similarly, we extend the derivation in Page 37 of Zhong et al. (2017h) for the standard Gaussian distribution to a general Gaussian distribution as follows.
Eا nyT
W. 14
B
Σ k=1
U Hoooo
E
N
|||
|
Pl
| 10xx (W*))
k
x2
11
$ (8x)(W+)'
(187)
Combining (80)-
183).
186
and 187
we have
min
E. Nim E,)
Σ
k
a
x
((w; 2)}²}
2
Σ
pl
W k1
5x (W*)
||||||
n kx² x²
8x
(W
Σ ||
(188)
For the Gaussian Mixture Model
E/_ Nuw, E). we have
min E
E XnN(Le
a x p'(w;" x))²]
a|| |||=1
1=1
(189)
Σ
W 141
pl
8x (W (W
k
x²
5k (.
1113 /
1=
Therefore,
Σ
W T
pl
5x (W.) Σニ -1 5x (x Iax
R2
TpT
K n²
(190)
()) Cs Σ Mllll + | 1)) Lak
32

---

Under review as a conference paper at ICLR 2023
From 139 obtain
in Lemma 6 since that we have the condition | W.Plp | and 93 we can
|| f(2 f(W)
F(W P)1l
<OsK3
Allllalll + |2 ID
M + 11W W Pll
(191)
4eg
W 14
A1
pl
5K (W
K
nyt n²
8K (W-)
-1-11--""
1=1
where eo E (0, 1)) Then we have
[(V) 2 F|V2 P)I - P)Ll
4(1
60)
W 1
5x (W") (1-)) (192)
A
pl
K2
th
x²
6x | 1
| S
v"A(W" P)I
W-T Mi
$ C4
1p R2 pl
8x (W') [
K2 1=1
(x | $11
s C4
Melllm + 1)
(193)
The last inequality of 193 holds since C. Eizı Aell
+ | 1)2
2m {|E,,
Ka
Ele 4
Av
| ||
k
p(
6x (W
E|
1- 8x (W E -1-
O
maxi [ill
K²
and
((max { [+ 0
max:
Eill
Combining
192 and
193
we have
4(1 60)
w
pl
8K (W
K2
T/T Kr R2
5K (W
1=1
(194)
<V Ct Σ +
+ +
E.7 PROOF OF LEMMA
Let N₂ be the e-covering number of the Euclidean ball B(W+P,r). It known that log N. < dK log( är) from Vershynin (2110). Let W. = {W1,... Wv. be the e-cover set with N. elements. For any W E W.T), ( = arg min W Waw)lle S for all W B(W* P.r).
jE[N.]
Then for any W E B(W P, r),, we have
2 fn (W) S(WIl
(((W: - VPe(W (w):W)())
(195)
V2 vee(W (((Ws()):z;)) - -EE-E A.N(H, E.) ( (WW x|)]
+ +11 A.N(H. ('
- B A/ V
Hence, we have
PP
sup P...
v² I|V
SP(A)) + +((.) + +(C.))
(196)
33

---

Under review as a conference paper at ICLR 2023
where A,, Be and C are defined
12 1 Σ
A: =
sup WEB(W 7
2 (w;:) V2e(W J(W) 2x)
(197)
1=1
4
B₁ = sup
-=
(W
( (W);
E DE A Ex) [22( (()) x;]]1
W [:]::))]]]]
WEB(WW P,r)
n
3
(198)
C. { sup WEB(W-P.r)
E Els ( s(W);
(199)
E ( E,)
(2((W;;:;)
Then we bound P(A.). and P(C,) separately.
1) Upper bound on P(..). By Lemma 6 in Fu et (2020), we obtain
n 2 (2( :x;)
EL AN 22 xx)
(200)
< sup vVV.
v. n
V'((Wax,) E Ea Ani E,) E,) (
where Vi is a cover of the unit-Euclidean-oen norm ball (B(0, 1) with log IV S dK log 12. Taking the union bound over We and Vg. we have
1 Σ G 2
P(B.) <P
sup WEV
1=1
(201)
3r
Σ G. 6
< <exp(dK
log 12))
sup WEW,.vEV
P(|
6
where G. (V2((W, xx.)
Ba E x;)][i) and [[G.] 0. Here
v = (u] ... [k) E dRd
K K
G..
Σ
S xa Rewt AnV (n (E axx ui)
j=1 1=1
(202)
K $
K
Cg
[ x) + Σ
E
Lt,
AuN (u)T
j=1
for some C. > 0. The first step of (202) is by Inequality.
84).
The last step is by (164) and the Cauchy-Schwand
34

---

Under review as a conference paper at ICLR 2023
K [ J x) |r
( Co Et Am
E G|
S
K
Ba E/' X: 2x))) p-1
K
Σ
Cg C3
1
E BE ANV(HEEE
E
11
II x) 20
[ 's j=1
4
E El Ao, E a1))) p-1
K
Co Σ
F E/ 1, (u]] 2r))()]
II 1=11 1j
11+-+xxx-
==1
Σ
R Bo Aen Ex) [2] 2x)3)
(203)
Co.
Σ
Σ E B E/e [u, 2)))
K
(-
EL NuN (1) xx)) 0-1
R
K
Ea AnN E,) (2] (2))))
C.
j=l
S Cg
11!||u/11 2
x x +122)))))
A + +
S Cg
where the first step is by the triangle incquality and the Binomial theorem, and the second step comes from the Multinomial theorem. The second to last inequality in (203) results from Property g The
last inequality because E V₁. E | = ||0||2 <
OPE G
[lexp(0G.))] = OB. +
Σ
p!
p=2
|00|
(elllpull + +12))1112)
<1+>
Co
(204)
pp
2=2
Al + | 1)?) 2
$1+ Co |
where the first inequality holds from pl > (g) and 203 and the third line holds provided that
(x
| 11) P+1
(m+1)(++1
-
+
m P22
15 2
(205)
c0
ELe 1 >e([]
[||lma|++++20 +11
F
35

---

Under review as a conference paper at ICLR 2023
Note that the quantity inside the maximization in 2055 achieves its maximum when p 2, because it is monotonously decreasing. Therefore, (205) holds if 0 -
27 4e
Ei= (l + | II)a Then
G
t 6
exp(() Σ
G.) 2 exp(
not
S e
née
n
B Blexp(OG;:)
(206)
n01
s exp(Cioof
Aell +
for some constant C10 > 0. The first inequality follows from Markov's Inequality. When = E Ar + | })) we have modified Bernstein's
minf
12C10
Els x(II m))
Inequality for the Gaussian Mixture Model as follows
n G
Cient
P
6
s
exp
max
144 Ein Ac(lleuel + ||Σ 11)²) 2
1=1
(207)
1
Cin
Σ
Melll + / 11) .t})
for some constant Cn > O. We can obtain the same bound for IP( Gj as G Therefore, we have
E G3 2 ( by replacing
n G 2 ) s 2 exp
Ciont
P(
maxf
Aell + | 11) 2
144
El=
(208)
Cun
Σ x(llaal
| I)> t}}
1=1
Thus, as long as
dK log 36r + logg 4
dK log 3Gr + llog } (209)
t 2 C. max
(amll + | 1)3
El= Ae(llauell + | 1))
for some large constant C. > 0, we have P(B:)) I
2) Upper bound on (P.,) and (P))).. From Lemma 5 we can obtain
sup WER(W P.r)
E |B A.V F,) (V [[W) E IL AdTion E, [<;
| EE AnV V [[])==]] BeNE E,) /
< sup WeB(W-P.7 P.r)
W,(w)
sup WeB(W-P.r)
W Ws(w)lle
< C12 k
Al + +1 Σ Aclllull + +|
(210)
Therefore, C, holds if
t C12 d K
Σ Al +
+1 11) Σ A (l + +
(211)
36

---

Under review as a conference paper at ICLR 2023
We can bound the A as below.
1
P
sup WEB(W-
V (W (w)) - << x.
3 n- Dl (N)
sup WEB(W- p.r)
3
B
sup WEB(W-P.
(w))
<((WW=>)))
3
V (W) x2) V x.)|
E sup
sup
W
WowwllF
W.B(W-P.)
Wi(wlllF
W.B(W-P.))
C12 K K
El= A + | 1 A - 1 1))
(212)
where the first inequality is by Markov's inequality, and the last inequality comes from Lemma Thus, taking
5
C1 b..dkkt Eter (e + E Aclllo + | I)
(213)
ensures that IP(AA) < 2.
3) Final step
Let
and dd-10, tthen from
C1 v² Et=, (1 +| 1) st Arcller + ma
209 and 211 we need
L Σ 1=1
1. max
Cs
(llleel +
| 1)
ndK
dK log(36rnd T0 KI Et Aellluulloo || D Aellee + || (]) 1)4))) + log
72
dK 1og K3. VEL delllmello || 11) Σド Aell + 1) + log
Σín Aell + | 11
(214)
So by setting t = 1: + || 1 AK log as long 2 C' dK log dK, we have
dK log n
P( sup Prr(W
[V <2F(W)11 2 C. Σ Acl + 11
< 10
n2
(215)
F PROOF OF LEMMA 2
We first present lemma used in proving Lemma in Section F. and then prove Lemma 2 in Section
F2
37

---

Under review as a conference paper at ICLR 2023
F.1 A USEFUL LEMMA USED IN THE PROOF
Lemma 9. Ifr is defined in (93) for E (0, }),, then with probability at least d=10, we have 12
d +
sup WEB(WW-Pr)
f. (W) Vf(W)Il S C1s
n (1+ (216)
for some constant C13 > where P is a permutation matrix.
Proof:
Note that ff = VW) + E My v(W))v(()++]lM (WW). Therefore, we have
sup WEB(W-P.)
(W)
sup Pr
V
Σ all (217)
Then, similar to the idea of the proof of Lemma
8 we adopt an e-covering net of the ball B B(W*,
build a relationship between any arbitrary point in the ball and the points in the covering set. We can then divide the distance between V fn W and V (W) into three parts, similar to 195). 218 (220) can be derived similar way as 197) (199) with "V2" replaced by "V". Then we need to bound P(A)), PB)) and IP(C)) respectively, where Al. By and C₁ are defined below.
A/
sup WEB(W- P,r)
V((W:::)) V((W (w)); 51
(218)
B = sup WWB(W-P.r
VE(W (w));;; - E BE ANV VE(W 2;
(219)
C =f sup |E E ALN E. WEB(W-
VE(W (w))
(220)
E EL AW E, V((W:
(a) Upper bound of PBB)). Applying Lemma 3 in Mei (016)). we have
VE(W - EaWDE A.N /V2 (w))
(221)
<2 sup vEVi
Ve(W (WW):;) BaNE A.N
We( (ww):
Define G v. (VE(W, 2;) E A.
V(( .+)))) Here Rd. To compute
V W. 22),, we require the derivation in Property 9
Then we have upper bound of ((W) in
83
d(w m)(1 -(
K H(W) o' (w) x))
1 1
< 1, =
<(W)
K x o(w x)
(222)
R -
0 (w. x))
6(w) () Ø))
K K. ow x))
1,
y
0
Then have upper bound of G/:
G = 1 x BE Av An Ez) E æ0]
(223)
< 1 x + E St Au mz) 0100 x]]
"V f.() is defined 1 Σi, (VI(W, 3. vi) 24) in algorithm
38

---

Under review as a conference paper at ICLR 2023
Following the idea of 203 and 204). and by UE E Vi. have
+ || 1)²) $)
B|G S 0 +
(224)
E(exp(OG - 1 + 01009 a + || 11}²)
(225)
where 225) holds i <
27 E Ae(lleeell + |E(1) Following the derivation of 201 and
206
(209). we have
P( G
2
1=1
(226)
Ciant
52exp maxx
{
C15
|| | 11) 11) A
144 E (l + 2
11)
for some constant C14 0 and C1s O. Moreover, we can obtain P(
S 2 long
dK log
+ log
dK log 18r + log +
t 2 C13 max
(ell + | D
1=1 Ae(llmill
| 11)
(227)
(b) For the upper bound of (P())) and PP(C)), we can first derive
Ve((W x) ve(W", xx)1 =((W"x)))
E EE A.NAM.E
sup
W
[W- W'
<(W) ((W')) - -|ae||
<B <B Et ANV(MNE))
sup
P.)
W W
maxis (15, ||x|||
[ W - W'
<B <B E.)
sup (W-P))(W-P.n)
W W
Cg || W W
<B <Bensh EI A.)
sup WwW
IW W
.Cg.3Vdd Σ All
(228)
The first inequality is by (83). The second inequality by the Mean Value Theorem. The third step by (164). The last inequality is by Property 7 Therefore, following the steps in part (2) of Lemma g we can conclude that Cy holds if
L 2 3Cg VKd. Σ
Aelleall + 11
(229)
Moreover, from (113 Lemma g we have that
18Cy VKd. EL A + [
(230)
8
ensures P(A)) S 3. Therefore, let 18C, V Al endkk
d and
== Ciav we have
K EL >1((11ae)1 + +| dlog if C dk log dK for some constant C"
d d
PP
sup W WEB(WW P.r)
|/V -/())I C13
K
Acllmal + +1
< dd-10
(231)
39

---

Under review as a conference paper at ICLR 2023
By Hoeffding's inequality in Vershynin (201) and Property
we have
dK log n
P
MillE 2 C13
Aell + || 1
==1
L
(1ll + | 1)2 22 logn
(232)
2 <exp(- -xpplCCaa> Σ
dKE2
Sd-10
Therefore,
(V) - v((W)]]
sup W Pir)
d n
SC13
K
(l + 1 V
|pll|
i=1
(233)
d dlog n
SC13
K
(l +1 1D? VDv
|
1=1
d log n
SC1a
K (llll + |2) 1)a²
(1 + E)
F.2
PROOF OF LEMMA 2
Following the proof of Theorem in Fu et al. 2020), first, have Taylor's expansion of fn(W,,
Ju (..) =f [..( veo vec - W'P))
(234)
2 vec Vec((W, Wn W f
W'P)
Here W is on the straight line connecting W P and W... By the fact that fn (W,) S (n P).
we have
1
vec W. W
Ivee
W'P) V[ WW, W.P) (235)
2
From Lemma 7 and Lemma 9
have
4
W 11I
p
8x
)
W, W'P
K2 T/T k 2
6 W
Σ 11-
(236)
s, vec(W,,
W. W P)V fn. vec W. W+P)
and
(W vec W,, W'P)
f W,, P
(( (W P) Vj(W P)Il ( [) IW W.Plp
(237)
50s K A |1
d log n
(1 + t) W, - W
The second to last step 237 comes from the triangle inequality. and the last step follows from the (236) and (237).
fact v/(W*P) P) 0. Combining 235
have
40

---

Under review as a conference paper at ICLR 2023
W, - W'P & 50(
Kå, Ei=ı Ml +1Σ 11) + 5)
d n
21=1 A 1e I|
n²² pl W-Tu:
6k 11- 6K ( )|
n
(238)
Therefore, we have concluded that there indeed exists a critical point W in (( P,r). Then we show the linear convergence of Algorithm as below. By the update rule, we have
1 Σv) (W, (oV W+++- W, W. 7O (W,)
71
(239)
= -11- 110 / ve (W, - -w,)
i=1
where W(1) = >>,, + (1 - W, for YE E (0. Since W(1) E B(W P. P.r), by Lemma | have
we
H mmin
I= 2 (W (n)) S maxx
(240)
where Hmin
22 n" Ei= A
12 of
" pl
6k 11> 3 5K (W*) 11)++ Hmax C4
w
Elen Aclll + | Therefore.
W - Walle = = 1 / (2(((( W, - W. r + 170 Σ villı
1=1
(241)
$ (1 no Hmin min
W. W FF +1|
770
Mc ||
n
By setting To Hmxx = 0
Σ1. Ac(|| E/] we obtain
Wi+1 WallF S
Hmin
W| WallF +
770
> |klle n
(242)
Hmax
Therefore, Algorithm I converges linearly the local minimizer with extra statistical error. By Hoeffding's 's inequality in Vershynin (2010) and Property 2 we have
n
dK log () x exp(p=
<2d log
P
x d
(243)
n
dKg2
Therefore, with probability
d-10 we can derive
Hmin y H
Hmax Hmin
dK log
W. Wallr (1
Walle +
(244)
G PROOF OF LEMMA 3
We need Lemma 10 to Lemma 14 which are stated in Section G.1 for the proof of Lemma Section
G.2 summarizes the proof Lemma 3 The proofs of Lemma 10 to Lemma 12 are provided in Section G.3 to Section G.5 Lemma 13 and Lemma 14 are cited from Zhong et al. (2017b). Although Zhong et al. (2017b) considers the standard Gaussian distribution, the proofs Lemmal and [4
hold for any data distribution. Therefore, these two lemmas can be applied here directly.
The tensor initialization in Zhong al. (2017b) only holds for the standard Gaussian distribution. We exploit a more general definition of tensors from Janzamin et al. (2014) for the tensor initialization in algorithm. We also develop error bounds for the initialization.
41

---

Under review as a conference paper at ICLR 2023
G.1 USEFUL LEMMAS IN THE PROOF
Lemma 10. Let Q2 and Qa follow Definition 1 Let S be a set i..dd samples generated from the mixed Gaussian distribution Eiz (H E1). Let Q2, Q3 be the empirical version of Q2. Q3 using data set S, respectively. Then with a probability at least 2n 2n-60( we have
Q2 - Q211 dllog
-1 70 D
(245)
n
if the mixed Gaussian distribution is not symmetric. We also have
dloo
1Q2(La, a.) Q2s(La. S V 61 (1 (V
(246)
for any arbitrary vector a IRd, if the mixed Gaussian distribution is symmetric.
Lemma 11. Let U EdxK be the orthogonal column span of W Let a be fixed unit vec- t. Define R3- = =Q( Ū), where Q3 is defined in Definition 7 Let R3 be the empirical version of Rs using data set S, where each sample of S is i.i.d. sampled from the mixed Gaussian distribution Et= NN E,). Then with a probability least n - -D(5"(W))) we have
for and Ú Baxk denote orthogonal matrix satisfying
-
log
R (1 (F
(247)
n
Lemma 12. Let Q1 be the empirical version of Q1 using dataset S. Then with probability at least 2n Q(d) we have
dllggn
@2: - Qill (F
(248)
Lemma 13. (Zhong el al. 2017b), Lemma E.6) Let Q2 Q3 be defined in Definition i and Q2. Q3 be their empirical version, respectively. Let U E RR be the column span of W Assume ||Q2 Q211 (x(Q2:) for non-symmetric distribution cases and [|Qa(La Ia, a Q3 A.Ia,Laa Ia, a))l s 6xc (a.) for symmetric distribution cases and any arbitrary vector a E Rdd. Then after 10
(()g(?)) iterations, the output of the Tensor Initialization Method 1 Ü will satisfy
[ Q211 5k (Q2)
100 -UU
+e.
(249)
which implies
II(I - Jo 1 1Q Q211 =)llw?
(250)
(x()2)
if the mixed Gaussian distribution is not symmetric. Similarly, we have
L 11 ||Qa(La, Ia, Ia, Q3 La a0ll +C,
(251)
(x(Qu(La,I,,0)
which implies
[I(I I S |Qa Ia, La ( Ia ax)l + +
(252)
(k(Qu
if the mixed Gaussian distribution is symmetric.
Lemma 14. (Zhong et al. (2017b), Lemma E. E.13) Let U BRxk be the orthogonal column span
of W Let Ú E RRdxK be an orthogonal matrix such that |UUT T -ū S 71 S क.र For each i E [K], let 6; denote the vector satisfying |/;: TTū;;"1 S S W... Let Q1 be defined
in Lemma 12 and Q be its empirical version. If [| Qill S 73ll|1 $ Qill then have
|||0;||| āss < (k K (>1 + 72) + R² 222K's |w71
(253)
42

---

Under review as a conference paper at ICLR 2023
G.2 PROOF OF LEMMA 3
By the triangle inequality, we have
[w ~,,,ب
3 wwj
1, + w 00 -,
< 103 |wj1(00) 8/
+ , 2,00,
||5|||
w 00, + ||w||| /. |0,,1|
||5|||| 15 - 00 w5 + UÙ wj - 03
|||ر|||| ay |
2 81 (W (11,) (1100'
00 u ; ÜT "0;" UT1;"" - -0:() + wلحس - وي
(254)
From Lemma 10 Lemma
13 5x (Q2)
83 (W*) and 5σ (Q:(1 La, Id, a)) 2 8x (W*) for any
arbitrary vector Rd we have
QQ2 Ø21
S dlog n
5, (W
w 00
S
WW* -7 (2(
8K (Q2)
(255)
d 22 7 D2
n
if the mixed Gaussian distribution is not symmetric, and
jay" ŪÕT w. || ||qs I, Q3 (I. Ia aill ōx (r,Qa(a,, a))
- x2 76 D2)
dlogn
n
(256)
the mixed Gaussian distribution is symmetric. Moreover, we have
1 w OT=;"' - 8/
Ki W
Ra R&ll S x2 (7 (DVV))
K3 log
(257)
n
in which the first step by Theorem By Lemma 14 we have
Kuleshov et al. (015), and the second step by Lemma
11
||w||| az
< (x* K (n +2) *** k W'll
(258)
Therefore, taking the union bound of failure probabilities in Lemmas 10 and 12 and by D2 (V) < (V) from Property 10
we have that if the sample size n K" d d, then the output Wo E gd satisfies
De VT).
dlog
I|, W W " DD
W
(259)
with probability at least n (W")))
G.3 PROOF OF LEMMA TO
From Assumption I if the Gaussian Mixture Model is symmetric probability distribution defined in (16), then by Definition have
43

---

Under review as a conference paper at ICLR 2023
(Q,
Q3( a))l
- Σ
a
1
Vi p(x))
(2 Σxl) - exp( - ( -1- (ar - -i))
83 ((x - μبب م ) ودحة )) (I,I, ((x - أورا 1)
(260)
E v. p(x))
(2 | $ exp( 2 (2 Mi)ii (0 mi)
1
((x M1)
83 (a- (1== (1,
Following Zhong et al. 2017bb, X is defined such that for any E Rdh and Z E Rdixds
d2
2 Z
8 vD)
(261)
where z; is the i-th column of Z. By Definition 1 we have
V. p(x) Σ (2 | $ exp( 11-(-- - " (x - Hi)
1=1
((0x ((x0-1122; 03 ((x mi) 1 أ (1, (1,
Σt= 22(2T) E $ exp( - 1) (0 mi) ((00 11) 82 (2 xa (x 1i))
Σ (2 | expl
( -
1 (x= -m))
|lomin (x ax) ox)a
(262)
The first step of 262 is because (x - (0-م4)ー1 μ1} 82 (a (z (x- is the dominant term of the entire expression, and y I
1. The second step is because the expression can be considered as normalized ) (ax E-1(x 1x) and (x= (x:Ta) at).x. T is its dominant term.
weighted summation of ((x: - mi) M1)E)) 82
Define (x) (-1)m p(m(
p(x) where p(x) is the probability density function of the random
variable æ. From Definition
I we can verify that
Q = Ely (m)) jE (1,2,3)
(263)
Then define Gp: (v, ([y Sa(x)) (Ia, Ia. a
E [ (x; (Ta Ia, a b)). where ||a||
then E[[pp] = 0. Similar to the proof of (202). 203 and 204 in Lemma 8 we have
GGp IP S i (x)] (2) w)² E EL. N(H E.) (o miii (o) (x(xT)))1) o)'1
(264)
B|GGp, - (Ew (1. Ei) mia (2) (2, 1))1)²
6p E Et Nm E.) [(x T B DL N Nin 1 uuy < o min
B
(265)
< op / D2 (M))
[PE[[ppil $1+)
E(exp((GGp:) S 1
p!
1
(266)
p=2
p=2
$
1 + 2
12
D2 v D. (V)
Hence, similar to the derivation of 206). we have
Σ Gp, 2t) < exp (- not + (=
(-nft
(267)
44

---

Under review as a conference paper at ICLR 2023
for some constant Cis 0.
Let 0
201a (2 and 8l(W))
(FVDD(VV)D((V) V dllg n then we have
[Ia La o.) Q3 Ia, ai) (w ( (F))Da(V)) (F
d logn
(268)
n
with probability at least 1 - 2n -W")))
the Gaussian Mixture Model is not symmetric distribution which is defined have a similar result as follows.
T6). we would
||Q2 Q21l = || Σ yss
S2(2:) - Ely S2(1))]
(269)
k
111: S2(x:)l1 S 11 min K
1
Σ
6(w) x; x,)"" I1
(270)
Then define Gp/
v)). where ||a|| 1, then [[ Similar to the proof of 202 (203 and (044 in Lemma we have
(v. (Ly,
(xx )]
18 y/: S2 (x;)
0.
|Gy4
o (x) 27
E ((H. min
(271)
B| B||
(LL EL. Nin 0 l (2x u) <TDDD2(1))
(272)
1 O +
100 4p (V))
E E(exp((Gr4)
pl
p2
(273)
p=2
p=2
2 + 0 D2 (1)
Hence, similar to the derivation of (06).. we have
1
Gp: 21) S Sexp (-not+ I-n0l+Cirnl' (r)2))++))))))
(274)
i=1
for some constant C17 > 0. Let 0
201r (F)((())()))) and l. = O?(W*) (+1D2(V))
dlog n
then
we have
dlog n
@ Q21l - (7(W*) D2D
7
(275)
Sv dlog n of(W") 7 "VV"))>//>((V)DDD... (D(
n
with probability at least
2n (W')))
G.4 PROOF OF LEMMA II
We consider each component of y + ΣK plw; T x).
Define T, (x:): IRd K such that
T T (x) (o(w;" x) (,(x))
(276)
We flatten (z) : Rd + kxxxx K along the first dimension to obtain the function B (w)
Rd +
Kx Similar to the derivation of the last step of Lemma E.8 in Zhong et al. (011bb), we can obtain [[T[(=]]| < [x)]]] By 260p. we have
1 K
[x)(l] S a min K
Σ
Mww x;)(ūTT)) 2)3
(277)
j=l
45

---

Under review as a conference paper at ICLR 2023
Define Gr. (v. (, (x))) B (ax; lu)), where ||aa| 1, so E[Gr.] 0. Similar to the proof of
(202) 203) and (204) in Lemma we have
[ min |Gr,l X mo (v' U x)² + mn N(H,
(v 0 >>'
(278)
E Gr - EL Mi)
1 min
(0
x) 1) S - DD((v)
(279)
x O P]
|e0 Da(
Elexp(OGr,))
11+1
p! I 1 8 (
(280)
Do DD(V)) )))
Hence, similar to the derivation of 206]. we have
P
Gr. 2t) S exp ( (- n0t + ( (F
-nnt
(281)
for some constant Cis > O. Let 0-
t
and 1 t= 8f(WW) (+8 DD(V))
logn
Cia (Ia(Fe/Do(V)
then we have
logn
RR3 Rall 2 81 (W*)2 (7 (D(V))
(282)
n
with probability at least
2n (W")))
G.5
PROOF OF LEMMA 12
From Definition ! we have
1| - -1l1-111-10 Σ [ys (xr) - Bly - ((
(283)
Based on Definition I
1 Ardr (2tr II o expl -xp(-1(0= m1) (x mi) (x -
| S1(x))
<
Σl 21 Ix=1 R - #exp(- 1 (2x m1) (x 11))
2
plw T xz))x;
0 min K
(284)
Define Gg: t, (1y S1 (ar:)
E [m S (xx [] b)). where ||a||| = 1, so R(Gq] = 0. Similar to
the proof of 202 , (00). and (004 in Lemma we have
[Gqil" 12 $ l m (x. v) + E Em NIm,
(0 min (2) w)}l
(285)
[[) (PewD N Mm m,) 00 mman (o. w)))
S 2p D2(
(286)
[PE[IG P1
|00 D2())
Elexp(0Gq.) S 1+
S1+)
p!
pp
(287)
2=2
<1 0² D2)
Hence, similar to the derivation of (06). we have
PP Σ Gq. 2 t) S exp
not + (+V
(288)
46

---

Under review as a conference paper at ICLR 2023
for some constant C19 > 0. Let 0
and == (22))
dlog then we
Cis Cio (FVDVV))))))
have
dlog n
@ Qill - (7² V D2(
(289)
n
with probability at least
2n 2
47


Reviews:
[{"review_id": "XMPZh0kowde", "reviewer": "Reviewer_n1W9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proves a group imbalanced generalization result for a one-hidden-layer neural network under the Gaussian mixture model assuming that the labels are generated by a ground truth model of the same structure. With this result, the paper argues that the learning performance is the best when the spectral norm of the co-variance of each Gaussian component is at a medium regime (neither too big nor too small), and increasing the fraction of the minority group data does not improve the test performance if the spectral norm of its co-variance is large. The authors then conduct synthetic and realistic experiments to verify this result.", "summary_of_the_review": "Overall, I think this paper provides some interesting insights (I especially like (P4)). However, the main result does make a lot of strong assumptions, and some insights drawn from the main result ((P5) and (P6)) are questionable, so I am concerned that these insights might not be generalizable to a more realistic setting. Moreover, it seems to me that all results and discussions in this paper are based on Theorem 1. While the proof of Theorem 1 is indeed not easy, I am concerned that the contributions might be insufficient for ICLR acceptance, especially given that Theorem 1 requires too many strong assumptions. I think the authors should also include robust training methods, such as importance weighting, in their result. I believe that this paper can benefit from another round of edition, so I recommend weak rejection.", "strength_and_weaknesses": "Strength: The proof of the main result (Theorem 1 and Corollary 1) has some technical novelty, and the result leads to some interesting insights. For example, I think (P4) is a very interesting catch. The authors also validate the result with experiments.\n\nWeaknesses: The main concern I have is that the main result (Theorem 1) only works for a very limited setting, and the insights might not be generalizable to a more general setting. While it is understandable that such a theoretical result requires some strong assumptions, I feel that the assumptions made in Theorem 1 are way too strong, and some insights drawn from the result (especially (P5) and (P6)) are questionable.\n\nSpecifically, Theorem 1 assumes that:\n- The inputs are sampled from a specific Gaussian mixture model\n- The model is a specific 1-hidden-layer neural network\n- The labels are generated by a ground truth model of the exact same structure as the model used for training\n- $\\sigma_{min}$ is bounded away from zero, which is actually a very strong assumption: It is well known that in most tasks, the data lies on a low-dimensional manifold in a high-dimensional space, in which case $\\Sigma_l$ could even be non-invertible. And even if it is invertible, $\\sigma_{min}$ should be very close to zero.\n\nFurthermore, the main result (Theorem 1) only considers ERM, i.e. minimizing the average risk. It does not discuss any robust training method. One thing I believe the authors should add to the paper is ERM with importance weighting, i.e. minimizing the weighted average of the empirical risk. This should not be too different from ERM. Even better, the authors could also consider DRO, group DRO, etc.\n\nRegarding the insights, (P5) suggests that the performance would be the best if all Gaussian components have zero means, in which case the groups largely overlap with one another (provided that $\\tau = \\Theta(1)$). This seems rather vacuous. If all groups have the same mean and the same co-variance then of course the performance would be the best given that the groups share the same labeling function. However, in real tasks such as a fairness task, the groups are very different. Plus, I think the real reason why the groups need to have zero means is that the model does not have a bias term: It’s $\\phi(w^{\\top} x)$ rather than $\\phi (w^{\\top} x+b)$.\n\n\nMoreover, I cannot see how (P3) and (P5) lead to (P6). In this paper’s setting, batch normalization mixes the samples from different Gaussian components and potentially messes up the data structure. (P6) is only valid when all the samples in the batch come from the same component, or when the components largely overlap with each other as in (P5).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Wktbxbq0qR", "reviewer": "Reviewer_LoT6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors theoretically investigate the generalization performance of the one-hidden-layer neural network under a mixture of Gaussian. The main focus of this paper is to analyze the effect of group imbalance on the generalization ability. To simulate the group imbalance, their model can vary the group-wise Gaussian parameters. As a result, they demonstrate that the medium magnitude of the covariance achieves the highest generalization ability. This result also implies that increasing the minority group data does not always improve the generalization ability. The empirical evaluations also demonstrate the claim obtained in the theoretical result.", "summary_of_the_review": "This paper is well-written and easy to follow. Investigation of group imbalance is in high motivation as group imbalance is a crucial issue in deep learning. The provided insights are interesting and helpful for understanding the effect of the group imbalance. I hence recommend the acceptance.", "strength_and_weaknesses": "Strength:\n-  Well-written and easy to follow.\n- The insights regarding the effects of the group-wise covariances help understand the effect of the group imbalance.\n- The introduced analysis techniques look novel \n\nWeakness:\n- Lack of empirical evaluations with a deeper model. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AfiTHjGdYp6", "reviewer": "Reviewer_PYh3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a Gaussian mixture model (GMM) for binary classification problems with imbalanced groups. The labels are generated according to a ground truth neural network. Authors mention a few observations according to the theoretical analysis and provided empirical evidence using CelebA and CIFAR datasets.", "summary_of_the_review": "I think although this paper is well-written, there are some issues with its theoretical model and empirical evidence as mentioned above. Therefore, I don't think its contribution is significant enough to qualify as an ICLR paper.", "strength_and_weaknesses": "Strength:\n\nThe paper is clearly written and overall easy to follow. I did not check the details of the proof but the theoretical results seem to be sound.\n\nWeakness:\n\nI think the theoretical model is quite restrictive and unnatural. The input distribution is assumed to follow a GMM, and the labels are generated using a true network, which is a strong assumption. The training algorithm involves a tensor initialization step which is not usually used in practice. These assumptions limit the significance of the theoretical contributions.\n\nThe empirical evidence supporting the theoretical results seems to be weak. All the test accuracy numbers in Figure 1(b) and Figure 6 are within 1~2 percentage points. The authors use a very small training dataset so it is likely that these numbers are all within confidence intervals, i.e., the results are not statistically significant. Moreover, the authors did not report error bars in their plots. Therefore, I think the practical implications of the results are also weak.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5dZ6Aq8HJ0n", "reviewer": "Reviewer_MquM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the convergence, average population risk, and average per-group population risk of empirical risk minimization (ERM) with gradient descent (GD). They study these phenomena under the assumptions that:\n\n* the input data features come from a Gaussian mixture model (GMM) with mixing coefficients equal to the fraction of the data collected for that group, \n* the input data labels are obtained with a neural network of the same architecture and some unknown weights,\n* the gradient descent is applied under a neural network with a single hidden layer, and\n* the task is a binary classification and the loss is the binary cross-entropy.\n\nTheir main result is Theorem 1, which provides some insights into when the performance is best:\n\n* having a group mean close to zero (in fact, low norm $\\lVert \\mu_l \\rVert$) is beneficial for training,\n* having the group co-variance close to the medium co-variance is beneficial for training, and\n* increasing the fraction of the minority group does not always increase the performance (it can degrade performance when the co-variance is far from the medium co-variance).\n\nAnother contribution that is not explicitly in the main text is new results on GMMs' concentration.", "summary_of_the_review": "This paper studies the convergence and generalization properties of ERM with GD on the expected population and expected per-group population risks for binary classification in logistic regression with the binary-cross entropy loss.\n\n They consider a rather artificial set-up where the input features data comes from a GMM with mixture representatives equal to the fraction of the observed group data and a balanced spectrum of the co-variances (i.e., $\\tau = 1$). Then, the labels come from a linear (or one hidden layer) network with a known number of units and unknown weights.\n\n Under this setup, they obtain convergence and generalization bounds that provide insights on which are the elements that help or don't help improve the training of unbalanced datasets. In particular, low norm means of each group and covariances close to the medium are key.\n\n Overall, the insights obtained from the paper are interesting but are very limited in the setting they consider. Unfortunately, as mentioned in the weaknesses, the paper does not successfully try to see if these insights carry on in practice in a convincing way. Also, one can not verify the available experiments with an available code. Moreover, there are some parts of the main text and proofs that seem to have some mistakes that need addressing or explaining. \n Therefore, for these reasons, I must incline towards rejection at the moment.\n \n On another note, not to the authors fault though, the paper and especially the proofs are very long and having a proper review and proof-check is complicated in the time window given for a conference, and maybe a journal would be a more appropriate venue for this work. \n\n\n**Some minor comments and nitpicks that did not impact the score of the review**\n\n* Many times you start sentences with a citation using citep, it should be citet.\n\n* In the introduction before the contribution. Please clarify: \"In these works, the input features are usually assumed...\"\n\n* In the notation, please, clarify \"The matrix spectral norm is $\\lVert Z \\rVert = \\delta_1(Z)\"$.\n\n* In Section 3. \"an unbalanced dataset\"\n\n* When you refer to works themselves and not the authors, you should youse citep instead of citet. For instance, right before Section 5.\n\n* The second and third paragraphs in Appendix A.1. are repeating themselves, don't they?\n\n* Before (12), you used one $\\times$ instead of $\\otimes$.\n\n* The $\\Gamma$-function $\\Gamma(\\Psi)$ should also contain a dependence on $W^*$.\n\n\n", "strength_and_weaknesses": "**Strengths**\n\n* The paper tackles an important problem: convergence and generalization of GD with imbalanced data.\n\n* The insights from the main theorem are interesting and potentially useful to develop fairer learning algorithms.\n\n* Some new results regarding GMMs' concentration are given in the appendix.\n\n**Weaknesses**\n\n* The learning model assumption seems a little artificial and restrictive.\n\n  * It is mentioned that a one hidden layer model is assumed, but then we are provided with the model in (1), which is standard logistic regression (that is, a linear layer followed by a sigmoid activation function). \\\n  It is mentioned that the weights in the second layer are assumed to be fixed to facilitate the analysis. This is an artificial setting by itself, which even if other works have employed it, needs some justification as is quite uncommon and its utility is unclear to me. But also the second layer weights are not appearing in (1).\n\n  * The assumption that the real function from features to labels is also strong. Is it also assumed that they come from the arg-max after a linear layer?\n\n* There are some parts of the text where the claims seem incorrect or potentially incorrect:\n\n  * Why do you say that GD converges linearly in the introduction? In the Theorem 1 we see that it converges at a rate $\\mathcal{O}(\\sqrt{d \\log n / n} / K^{1.5})$. That's not linear in any parameter.\n\n  * Why does that group-level mean shifts from zero justify the pre-processing of making the data zero-mean? Note that this pre-processing will make the overall data have a mean of zero. Since it is assumed that the data comes from a mixture of distributions, it is not guaranteed it will have a beneficial effect on a minority group (indeed, it can be harmful if the mean of the group shifts away from zero after the average centering). \\\n  The same problem occurs with (P6). Unless the batch normalization is applied per group, which is not the case in this paper, it does not necessarily help as the means and variances are updated to normalize the whole batch considered as a unimodal distribution.\n\n  * In Section 3, it is said that $x$ follows a GMM $\\sum_{l=1}^L \\lambda_l \\mathcal{N}(\\mu_l, \\Sigma_l)$. This assumes that the fraction of the data from each group exactly matches the influence in the real mixture model. In practice, if one has a GMM $\\sum_{l=1}^L \\lambda_l \\mathcal{N}(\\mu_l, \\Sigma_l)$ one will observe $\\tilde{\\lambda}_l n$ samples of each group with $\\tilde{\\lambda}_l \\to \\lambda_l$ as $n \\to \\infty$. How does this affect your results?\n\n  * The assumption that $\\tau \\in \\Theta(1)$ seems strong and potentially not true in most cases.  I did some checks with random matrices $A \\in \\mathbb{R}^d$ generating potential covariances matrices $\\Sigma = A^T A$ and it seems that $\\tau \\in \\Theta(d)$. This can be problematic since in the proofs the dependence with $\\tau$ (and hence potentially $d$) can be as high as $\\tau^{12}$. \\\n  You could check how this condition holds up taking natural images of different sizes and assuming they are Gaussian. Compute their covariances per group and see if $\\tau$ grows or not with the dimension to see if this assumption would hold or not in practice.\n\n  * In Corollary 1, how do conditions (i) and (ii) be true simultaneously? Consider $\\Sigma_l^{(1)}$ and $\\Sigma_l^{(2)}$. Each is worse than the other since one has a spectral norm closer to zero (condition (i)) and the other has a larger spectral norm (condition (ii)). The idea is further explained in (P3), but needs a more formal statement here.\n\n  * In (P4) it is mentioned that $\\lVert \\Sigma_l \\rVert$ is the smallest among all groups, increasing $\\lambda_l$ improves the learning performance since the learning performance is enhanced at a medium regime of group-level co-variance. But if it is smallest, as in the case where it is largest, the medium-level covariance may change, thus also decreasing the performance. It would only increase performance when $\\lVert \\Sigma_l \\rVert$ is close to the medium level.\n\n  * In the appendix, you use that $\\nu_i$ ar i.i.d. zero-mean Gaussians but also assume they have bounded magnitude. How is this possible? I believe you can still recover some of your results by saying that this happens with a certain probability using some tail bounds on Gaussian random variables, but as of now, I do not understand how can this happen.\n\n  * When applying l'Hôpital's  rule in (33) if I am not mistaken you are using that both $f(\\sigma) = 1 / (u_j^2 / \\sigma^2 + 1) \\to 0$ and $g(\\sigma) = \\beta_0(i, u/\\sigma, \\sigma) - \\alpha_0(i, u/\\sigma, \\sigma) \\to 0$ as $\\sigma \\to 0$. However, when applying the rule $\\partial f(\\sigma) / \\partial \\sigma = 2 u_j^2 \\sigma / (u_j^2 + \\sigma^2)^2$ and not $u_i^2 / (2 \\sigma)$. Hence, (33) ends up being a situation of $0 \\cdot \\infty$ and it is not determined. \\\n  This affects other properties like Property 3 (4) which builds upon the fact that $\\rho > 0$.\n\n  * I don't follow the equality after the inequality in (52). Where did the $e^{-|\\mu|^2 / 2}$ term go?\n\n  * Many of the lemmata leading to the main results are based on approximate inequalities ($\\gtrsim$). This is concerning since if the approximation error is not quantified it may have important effects on the final results.\n\n* There are some parts of the text that are not clear to me:\n\n  * In Figure 3 (c), it is not clear to me how the convergence rate is calculated.\n\n  * In Figure 4 (b) the test loss of the minority group is lower than the average risk. How is this possible? That would mean that the largest group has a larger loss.\n\n  * Why are the results in Figure 6 consistent with (P4)? In order to have this consistency it would be good to know which are $\\lVert \\Sigma_{\\text{male}} \\rVert$ and $\\lVert \\Sigma_{\\text{female}} \\rVert$, even if only empirically, and then observe how it is indeed the case that when the performance increases or decreases is for the reasons outlined in (P4).\n\n  * Similarly, the results with increasing $\\delta$ or $w$ are not clearly showing what they intended. We would need an estimation of $\\lVert \\Sigma_{\\text{male}} \\rVert$ and $\\lVert \\Sigma_{\\text{female}} \\rVert$ to see that effect. Similarly, one could also test doing a subtraction of the mean and increasing the mean of these means to see if the results are better when this happens and they get worse as they diverge. \n\n* Sometimes some important details are left:\n\n  * In (29) note that we know that (27) and (28) are positive due to Jensen's inequality. \n\n  * In the proof of Property 3 (3) note that we can use the assumption that the Gaussian behaves like the delta due to the Dominated Convergence Theorem (DCT).\n\n* The bound, though interesting, seems fairly vacuous.\n\n  * Note the potential dependence on $d$ of $\\tau$. In this case the number of samples required would explode with increasing dimensions. Even in the artificial case when $\\Sigma_1 = \\Sigma_2 = I$, for feature dimension 100, 3 units, and 2 classes, one needs more than 150k samples for the results to apply (Figure 1 a). Note that this is far less than the MNIST data samples (60k), where the feature dimension is 256.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3_O-y2vDKE", "reviewer": "Reviewer_XNZ2", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "I informed the area chair that I cannot review this paper.", "summary_of_the_review": "I informed the area chair that I cannot review this paper.", "strength_and_weaknesses": "I informed the area chair that I cannot review this paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject