{'fraction_non_alphanumeric': 0.045511210998542655, 'fraction_numerical': 0.01483679525222552, 'mean_word_length': 4.394903855261911, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Provable Benefits of Overparameterization in Model Compression: From Double Descent to Pruning Neural Networks

Deep networks are typically trained with many more parameters than the size of the training dataset. Recent empirical evidence indicates that the practice of overparameterization not only benefits training large models, but also assists - perhaps counterintuitively - building lightweight models. Specifically, it suggests that overparameterization benefits model pruning / sparsification. This paper sheds light on these empirical findings by theoretically characterizing the high-dimensional asymptotics of model pruning in the overparameterized regime. The theory presented addresses the following core question:"should one train a small model from the beginning, or first train a large model and then prune?". We analytically identify regimes in which, even if the location of the most informative features is known, we are better off fitting a large model and then pruning rather than simply training with the known informative features. This leads to a new double descent in the training of sparse models: growing the original model, while preserving the target sparsity, improves the test accuracy as one moves beyond the overparameterization threshold. Our analysis further reveals the benefit of retraining by relating it to feature correlations. We find that the above phenomena are already present in linear and random-features models. Our technical approach advances the toolset of high-dimensional analysis and precisely characterizes the asymptotic distribution of over-parameterized least-squares. The intuition gained by analytically studying simpler models is numerically verified on neural networks.


Introduction
Large model size and overparameterization in deep learning are known to improve generalization performance (Neyshabur et al. 2017), and, state-of-the-art deep neural networks (DNNs) can be outrageously large. However, such large models are not suitable for certain important application domains, such as mobile computing (Tan et al. 2019;Sandler et al. 2018). Pruning algorithms aim to address the challenge of building lightweight DNNs for such domains. While there are several pruning methods, their common goal is to compress large DNN models by removing weak connections/weights with minimal decline in accuracy. Here, a key empirical phenomenon is that it is often better to train and prune a large model rather than training a small model from scratch. Unfortunately, the mechanisms behind this phenomenon are poorly understood especially for practical gradient-based algorithms. This paper sheds light on this by answering: What are the optimization and generalization dynamics of pruning overparameterized models? Does gradient descent naturally select the good weights? Contributions: We analytically study the performance of popular pruning strategies. First, we analyze linear models, and then, generalize the results to nonlinear feature maps. Through extensive simulations, we show that our analytical findings predict similar behaviors in more complex settings.

(a) Distributional characterization (DC):
The key innovation facilitating our results is a theoretical characterization of the distribution of the solution of overparameterized leastsquares. This DC enables us to accurately answer "what happens to the accuracy if X% of the weights are pruned?". (b) Benefits of overparameterization: Using DC, we obtain rigorous precise characterizations of the pruning performance in linear problems. Furthermore, we use, so called "linear gaussian equivalences", to obtain sharp analytic predictions for nonlinear maps, which we verify via extensive numerical simulations. By training models of growing size and compressing them to fixed sparsity, we identify a novel double descent behavior, where the risk of the pruned model is consistently minimized in the overparameterized regime. Using our theory, we uncover rather surprising scenarios where pruning an overparameterized model is provably better than training a small model with the exact information of optimal nonzero locations. (c) Benefits of retraining: An important aspect of pruning is retraining the model using the favorable nonzero locations identified during the initial training. We show that retraining can actually hurt the performance when features are uncorrelated. However, it becomes critical as correlations increase. Importantly, we devise the DC of the train→prune→retrain process (see Figs. 2 and 4 and the discussion around Def. 5 for details), and, we demonstrate that it correctly captures the pruning performance of random features that are known to be good proxies for understanding DNN behavior (Jacot, Gabriel, and Hongler 2018).
We anticipate that our techniques towards establishing the DC of the overparameterized problems might be useful, beyond the context of pruning, in other statistical inference arXiv:2012.08749v1 [cs.LG] 16 Dec 2020 the CIFAR-10 dataset with varying width (i.e. number of filters) and sparsity targets. The width parameter controls the overall model size. The solid (resp. dashed) lines are test (resp. training) errors. The blue line corresponds to training of a dense model with width-k. The other three curves correspond to sparsity targets s ∈ {5, 8, 10}, for which a dense model of width-k is first pruned to achieve the exact same number of nonzeros as a dense model of width-s and then retrained over the identified nonzero pattern. Surprisingly, all curves interpolate (achieve zero training error) around the same width parameter despite varying sparsity. The best test error is always achieved in the overparameterized regime (large width). Test error curves have two local minima which uncovers a novel double descent phenomena for pruning. The shaded region highlights the transition to zero training error, where the test error peaks. tasks that require careful distributional studies.

Prior Art
This work relates to the literature on model compression and overparameterization in deep learning. Neural network pruning: Large model sizes in deep learning have led to a substantial interest in model pruning/quantization (Han, Mao, and Dally 2015;Hassibi and Stork 1993;LeCun, Denker, and Solla 1990). DNN pruning has a diverse literature with various architectural, algorithmic, and hardware considerations (Sze et al. 2017;Han et al. 2015). The pruning algorithms can be applied before, during, or after training a dense model (Lee, Ajanthan, and Torr 2018;Wang, Zhang, and Grosse 2020;Jin et al. 2016;Oymak 2018) and in this work we focus on after training. Related to over-parameterizarion, (Frankle and Carbin 2019) shows that a large DNN contains a small subset of favorable weights (for pruning), which can achieve similar performance to the original network when trained with the same initialization. (Zhou et al. 2019;Malach et al. 2020;Pensia et al. 2020) demonstrate that there are subsets with good test performance even without any training and provide theoretical guarantees. However, these works do not answer why practical gradient-based algorithms lead to good pruning outcomes. Closer to us, (Li et al. 2020) derives formulas for predicting the pruning performance of over-parameterized ReLU feature-map φ(a) = ReLU(Ra). Here R has i.i.d. standard normal entries corresponding to the input layer of a shallow neural net and we regress the output layer. Solid lines follow from our distributional characterization and the markers are obtained by solving random feature regression, which exhibit a good match. The blue line is the performance of usual RFR with growing number of features p. The other lines are obtained by solving RFR with p features and pruning and retraining the solution to fixed sparsity levels (s, 2s, 4s) with s/n = 0.1. Importantly, the risks of the retrained models exhibit double descent and are minimized when p n despite fixed model size / sparsity. The slight mismatch of the red curve/markers is explained in Fig. 4. least-squares without proofs. In contrast, we provide provable guarantees, and, also obtain DC for more complex problems with general design matrices and nonlinearities. Benefits of overparameterization: Studies on the optimization and generalization properties of DNNs demonstrate that overparameterization acts as a catalyst for learning. (Arora, Cohen, and Hazan 2018;Neyshabur, Tomioka, and Srebro 2014;Gunasekar et al. 2017;Ji and Telgarsky 2018) argue that gradient-based algorithms are implicitly biased towards certain favorable solutions (even without explicit regularization) to explain benign overfitting (Bartlett et al. 2020;Oymak and Soltanolkotabi 2020;Du et al. 2018;Chizat, Oyallon, and Bach 2019;Belkin, Ma, and Mandal 2018;Belkin, Rakhlin, and Tsybakov 2019;Tsigler and Bartlett 2020;Liang and Rakhlin 2018;Mei and Montanari 2019;Ju, Lin, and Liu 2020). More recently, these studies have led to interesting connections between kernels and DNNs and a flurry of theoretical developments. Closest to us, (Nakkiran et al. 2019;Belkin, Hsu, and Xu 2019;Belkin et al. 2019) uncover a double-descent phenomenon: the test risk has two minima as a function of model size. One minimum occurs in the classical underparameterized regime whereas the other minimum occurs when the model is overparameterized and the latter risk can in fact be better than former. Closer to our theory, (Dereziński, Liang, and Mahoney 2019;Hastie et al. 2019;Montanari et al. 2019;Deng, Kammoun, and Thrampoulidis 2019;Kini and Thrampoulidis 2020;Liang and Sur 2020;Salehi, Abbasi, and Hassibi 2020;Ju, Lin, and Liu 2020) character-ize the asymptotic performance of overparameterized learning problems. However these works are limited to characterizing the test error of regular (dense) training. In contrast, we use distributional characterization (DC) to capture the performance of more challenging pruning strategies and we uncover novel double descent phenomena (see Fig. 1).

Problem Setup
Let us fix the notation. Let [p] = {1, 2, . . . , p}. Given β ∈ R p , let T s (β) be the pruning operator that sets the smallest p − s entries in absolute value of β to zero. Let I(β) ⊂ [p] return the index of the nonzero entries of β. I n denotes the n × n identity matrix and N (µ, Σ) denotes the normal distribution with mean µ and covariance Σ. X † denotes the pseudoinverse of matrix X.
coming i.i.d. from some distribution D. As an example, of special interest to the rest of the paper, consider random feature regression, where x i = ψ(Ra i ) for a nonlinear activation function ψ that acts entry-wise and a random matrix R ∈ R p×d with i.i.d. N (0, 1) entries; see Fig. 2. In matrix notation, we let y = [y 1 . . . y n ] T ∈ R n and X = [x 1 . . . x n ] T ∈ R n×p denote the vector of labels and the feature matrix, respectively. Throughout, we focus on regression tasks, in which the training and the test risks of a model β are defined as (1) During training, we will solve the empirical risk minimization (ERM) problem over a set of selected features ∆ ⊂ [p], from which we obtain the least-squares solution β(∆) = arg min For example, regular ERM corresponds to ∆ = [p], and we simply useβ =β([p]) to denote its solution above. Let Σ = E[xx T ] be the covariance matrix and b = E[yx] be the cross-covariance. The parameter minimizing the test error is given by β = Σ −1 b. We are interested in training a model over the training set S that not only achieves small test error, but also, it is sparse. We do this as follows. First, we run stochastic gradient descent (SGD) to minimize the empirical risk (starting from zero initialization). It is common knowledge that SGD on least-squares converges to the minimum 2 norm solution given byβ = X † y. Next, we describe our pruning strategies to compress the model. Pruning strategies: Given dataset S and target sparsity level s, a pruning function P takes a model β as input and outputs an s-sparse model β P s . Two popular pruning functions are magnitude-based (MP) and Hessian-based (HP) (a.k.a. optimal brain damage) pruning (LeCun, Denker, and Solla 1990). The latter uses a diagonal approximation of the covariance viaΣ = diag(X T X)/n to capture saliency (see (4)). Formally, we have the following definitions: • Magnitude-based pruning: β M s = T s (β).
• Hessian-based pruning: β H s =Σ −1/2 • Oracle pruning: Let ∆ ⊂ [p] be the optimal s indices so thatβ(∆ ) achieves the minimum population risk (in expectation over S) among allβ(∆) and any subset ∆ in (3). When Σ is diagonal and s < n, using rather classical results, it can be shown that (see Lemma 7 in the Supplementary Material (SM)) these oracle indices are the ones with the top-s saliency score given by Oracle pruning employs these latent saliency scores and returns β O s by pruning the weights of β outside of ∆ . We remark that our distributional characterization might allow us to study more complex pruning strategies, such as optimal brain surgeon (Hassibi, Stork, and Wolff 1994). However, we restrict our attention to the three aforementioned core strategies to keep the discussion focused. Pruning algorithm: To shed light on contemporary pruning practices, we will study the following three-stage train→prune→retrain algorithms.
2. Pruneβ with strategy P to obtainβ P s . 3. Retraining: Obtainβ RT s =β(I(β P s )). The last step obtains a new s-sparse model by solving ERM in (3) with the features ∆ = I(β P s ) identified by pruning. Figures 1 and 2 illustrate the performance of this procedure for ResNet-20 on the CIFAR-10 dataset and for a random feature regression on a synthetic problem, respectively . Our analytic formulas for RF, as seen in Fig. 2, very closely match the empirical observations (see Sec. 3 for further explanations). Interestingly, the arguably simpler RF model already captures key behaviors (double-descent, better performance in the overparameterized regime, performance of sparse model comparable to large model) in ResNet.
Sections 3 and 4 present numerical experiments on pruning that verify our analytical predictions, as well as, our insights on the fundamental principles behind the roles of overparameterization and retraining. Sec 5 establishes our theory on the DC ofβ and provable guarantees on pruning. All proofs are deferred to the Supplementary Material (SM).

Linear Gaussian Problems
We begin our study with linear Gaussian problems (LGP), which we formally define as follows. Definition 1 (Linear Gaussian Problem (LGP)) Given latent vector β ∈ R d , covariance Σ and noise level σ, assume that each example in S is generated independently as y i = x T i β + σz i where z i ∼ N (0, 1) and x i ∼ N (0, Σ). Additionally, the map φ(·) is identity and p = d.
Albeit simple, LGPs are of fundamental importance for the following reasons: (1) We show in Sec. 5 that our theoretical   framework rigorously characterizes pruning strategies for LGPs; (2) Through a "linear Gaussian equivalence", we will use our results for linear models to obtain analytic predictions for nonlinear random features; (3) Our theoretical predictions and numerical experiments discussed next demonstrate that LGPs already capture key phenomena observed in more complex models (e.g., Fig. 1). In Fig. 3, we consider LGPs with diagonal covariance Σ. We set the sparsity level s/p = 0.1 and the relative dataset size n/p = 0.3. To parameterize the covariance and β , we use a spiked vector λ, the first s entries of which are set equal to C = 25 1 and the remaining entries equal to 1. λ corresponds to the latent saliency score (cf. (4)) of the indices. To understand the role of overparameterization, we vary the number of features used in the optimization. Specifically, we solve (3) with ∆ = [k] and vary the number of features k from 0 to p. Here we consider the train→prune algorithm, where we first solve forβ ([k]) and obtain our pruned model β P s ([k]) by applying magnitude, Hessian or Oracle pruning (cf. P ∈ {M, H, O}). Since λ is non-increasing, the indices are sorted by saliency score; thus, Oracle pruning always picks the first s indices. Solid lines represent analytic predictions, while markers are empirical results. The vertical dashed line is the sparsity level s/p.
In Fig. 3a, we set Σ = I p and β = √ λ. Note, that the analytic curves correctly predict the test risk and the double descent behavior. Observe that the Hessian and Magnitude pruning coincide here, since the diagonal of the empirical covariance is essentially identity. In contrast, Fig. 3b emphasizes the role of the feature covariance by setting Σ = diag(λ) and β to be the all ones vector. In this scenario, we observe that Hessian pruning performs better compared to Fig. 3a and also outperforms Magnitude pruning. This is because the empirical covariance helps distinguish the salient indices. Importantly, for Hessian and Oracle pruning, the optimal sparse model is achieved in the highly overparameterized regime k = p. Notably, the pruning with retraining (red markers) and pruning with fresh samples (cyan markers/line). The setting here is exactly the same as in Fig. 2, but we only show the case of sparsity 4s for which the mismatch is observed. Observe that our analytical predictions accurately capture the risk of retraining with fresh samples. However, we observe a discrepancy with the true risk of retraining (without fresh samples) around the interpolation threshold. Also shown the risk of the original ERM solution before pruning (in blue) and of the magnitude-pruned model (before any retraining).
achieved performance at k = p is strictly better than the horizontal dashed line, which highlights the optimal risk among all underparameterized solutions k ≤ n and all retraining solutions (see also SM Sec. A). This has two striking consequences. First, retraining can in fact hurt the performance; because the train→prune performance at k = p is strictly better than train→prune→retrain for all k. Second, overparameterized pruning can be provably better than solving the sparse model with the knowledge of the most salient features as k = p is also strictly better than k = s.

Random Features Regression
We relate an ERM problem (3) with nonlinear map φ to an equivalent LGP. This will allow us to use our theoretical results about the latter to characterize the properties of the original nonlinear map. We ensure the equivalence by properly setting up the LGP to exhibit similar second order statistics as the original problem.
Definition 2 (Equivalent Linear Problem) Given distribution (x, y) ∼ D, the equivalent LGP(β, Σ, σ) with n samples is given with In Section 5, we formalize the DC of LGPs, which enables us to characterize pruning/retraining dynamics. Then, we empirically verify that DC and pruning dynamics of equivalent LGPs can successfully predict the original problem (3) with non-linear features. The idea of setting up and studying equivalent LGPs as a proxy to nonlinear models, has been recently used in the emerging literature of highdimensional learning, for predicting the performance of the original ERM task (Montanari et al. 2019;Goldt et al. 2020;Abbasi, Salehi, and Hassibi 2019;Dereziński, Liang, and Mahoney 2019). This work goes beyond prior art, which fo-cuses on ERM, by demonstrating that we can also successfully predict the pruning/retraining dynamics. Formalizing the performance equivalence between LGP and equivalent problem is an important future research avenue and it can presumably be accomplished by building on the recent highdimensional universality results such as (Oymak and Tropp 2018;Hu and Lu 2020;Abbasi, Salehi, and Hassibi 2019;Goldt et al. 2020).
In Fig. 2, we study random feature regression to approximate a synthetic nonlinear distribution. Specifically, data has the following distribution: Given input a ∼ N (0, I d ), we generate random unit norm β 1 ∈ R d , β 2 ∈ R d and set the label to be a quadratic function given by y = a T β 1 + (a T β 2 ) 2 . Then, we fix R i.i.d.
∼ N (0, 1) and we generate ReLU features x = ReLU(Ra), where R corresponds to the input layer of a two-layer network. The markers in Fig. 2 are obtained by solving RFR and pruning and retraining with varying sparsity targets (s, 2s, 4s with s/n = 10%). Here, d = 10, n = 200. For each marker, the results are averages of 50 R ∈ R p×d realizations and 10 iterations for each choice of R. The lines are obtained via our DC of the equivalent LGP (by using Defs. 4 and 5) where the latent parameter β , noise σ and the covariance Σ of the RFR problem are calculated for fixed realization of the input layer R (similarly averaged over 50 random R). Our theory and empirical curves exhibit a good match. The results demonstrate the importance of overparameterization for RF pruning, which corresponds to picking random features smartly. Here, the coefficients of least-squares act like a scoring function for the saliency of random features and capture how well they are aligned with the target function. The fact that the risk of the pruned models is minimized in the overparameterized regime implies that least-squares regression succeeds in properly selecting salient random features from a larger candidate set. In the context of deep learning, our discussion can be interpreted as pruning hidden nodes of the network. Predicting retraining performance. As discussed in Sec. 5 and Def. 5, for the retraining stage, our DC is accomplished by assuming that retraining phase uses n fresh training examples (i.e. a new dataset S fresh ). Let us denote the resulting model byβ RT fresh . Perhaps surprisingly, Fig. 2 shows that this DC correctly captures the performance ofβ RT with the exception of the red curve (4s). Fig. 4 focuses on this instance and shows that our DC indeed perfectly predicts the fresh retraining performance and verifies the slight empirical mismatch betweenβ RT andβ RT fresh .

Neural Network Experiments
Finally, we study pruning deep neural networks. Inspired by (Nakkiran et al. 2019), we train ResNet-20 with changeable filters over CIFAR-10. Here, the filter number k is equivalent to the width/channel of the model. As the width of ResNet-20 changes, the fitting performance of the dataset varies.
Here, we apply train→prune→retrain. Select s as the sparsity target and s-filter ResNet-20 model as the base model with N s parameters. First, we train a dense model with k filters and N k parameters, N k N s , and prune it by only keeping the largest N s entries in absolute value non-zero. N k grows approximately quadratically in k. Now, the sparse model shares the same number of parameters amenable to training as the base model. Finally, we retain the pruned network and record its performance on the same dataset and same configuration. In Fig. 1, we plot the training and test errors of dense and sparse models. All the neural experiments are trained with Adam optimization and 0.001 learning rate for 1000 epochs, with data augmentation. Green, yellow and red lines correspond to 5, 8 or 10 sparsity targets, with around 28,000, 70,000 and 109,000 trainable parameters, respectively. As the width k grows, the training and test errors decrease for all 5-,8-,10-filter base models, except for the shaded double descent range. These experiments again verify the main insight revealed to us by studying simpler linear and random-feature models, that is, training a larger model, followed by appropriate pruning, can preform better than training a small model from the beginning. Another worth-mentioning observation is that with appropriate sparsity level (here, 10) the pruned model has prediction performance comparable to the dense model. Finally and interestingly, the test error dynamics of the pruned model exhibit a double descent that resembles that of the dense model (previously observed in (Nakkiran et al. 2019)).

Further Intuitions on The Denoising Effect of Overparameterization
To provide further insights into the pruning benefits of overparameterization, consider a simple linear model (as in Def 1) with n ≥ p ≥ s, noise level σ = 0 and identity covariance. Suppose our goal is estimating the coefficients β ∆ for some fixed index set ∆ ⊂ [p] with |∆| = s. For pruning, we can pick ∆ to be the most salient/largest entries. If we solve the smaller regression problem over ∆,β(∆) will only provide a noisy estimate of β ∆ . The reason is that, the signal energy of the missing features [p] − ∆ acts as a noise uncorrelated with the features in ∆. Conversely, if we solve ERM with all features (the larger problem), we perfectly recover β due to zero noise and invertibility (n ≥ p). Then one can also perfectly estimate β ∆ . This simple argument, which is partly inspired by the missing feature setup in (Hastie et al. 2019), shows that solving the larger problem with more parameters can have a "denoising-like effect" and perform better than the small problem. Our contribution obviously goes well beyond this discussion and theoretically characterizes the exact asymptotics, handles the general covariance model and all (n, p, s) regimes, and also highlights the importance of the overparameterized regime n p.

Understanding the Benefits of Retraining
On the one hand, the study of LGPs in Fig. 3 and Fig. 7 of SM suggest that retraining can actually hurt the performance. On the other hand, in practice and in the RFR experiments of Fig. 4, retraining is crucial; compare the green β M and redβ RT curves and see SM Section A for further DNN experiments. Here, we argue that the benefit of retraining is connected to the correlations between input features. Indeed, the covariance/Hessian matrices associated with RF and DNN regression are not diagonal (as was the case in Fig. 3). To build intuition, imagine that only a single feature suffices to explain the label. If there are multiple other features that can similarly explain the label, the model prediction will be shared across these features. Then, pruning will lead to a biased estimate, which can be mitigated by retraining. The following lemma formalizes this intuition under an instructive setup, where the features are perfectly correlated.
For magnitude and Hessian pruning (P ∈ {M, H}) and the associated retraining, we have the following excess risks with respect to β Error due to bias The lemma reveals that pruning the model leads to a biased estimator of the label. Specifically, the bias coefficient 1 − ζ arises from the missing predictions of the pruned features (which correspond to the small coefficients of |λ|). In contrast, regardless of s, retraining always results in an unbiased estimator with the exact same risk as the dense model which quickly decays in sample size n. The reason is that retraining enables the remaining features to account for the missing predictions. Here, this is accomplished perfectly, due to the fully correlated nature of the problem. In particular, this is in contrast to the diagonal covariance (Fig. 3), where the missing features act like uncorrelated noise during retraining.

Main Results
Here, we present our main theoretical result: a sharp asymptotic characterization of the distribution of the solution to overparameterized least-squares for correlated designs. We further show how this leads to a sharp prediction of the risk of magnitude-based pruning. Concretely, for the rest of this section, we assume the linear Gaussian problem (LGP) of Definition 1, the overparameterized regime k = p > n and the min-norm model β = arg min β β 2 s.t. y = Xβ.
As mentioned in Sec. 2,β is actually given in closed-form asβ = X † y. Interestingly, our analysis of the distribution ofβ does not rely on the closed-form expression, but rather follows by viewingβ as the solution to the convex linearly-constrained quadratic program in (7). Specifically, our analysis uses the framework of the convex Gaussian min-max Theorem (CGMT) (Thrampoulidis, Oymak, and Hassibi 2015), which allows to study rather general inference optimization problems such as the one in (7), by relating them with an auxiliary optimization that is simpler to analyze (Stojnic 2013; Oymak, Thrampoulidis, and Hassibi 2013; Thrampoulidis, Oymak, and Hassibi 2015; Thrampoulidis, Abbasi, and Hassibi 2018; Salehi, Abbasi, and Hassibi 2019; Taheri, Pedarsani, and Thrampoulidis 2020). Due to space considerations, we focus here on the more challenging overparameterized regime and defer the analysis of the underparameterized regime to the SM.

Distributional Characterization of the Overparameterized Linear Gaussian Models
Notation: We first introduce additional notation necessary to state our theoretical results. denotes the entrywise product of two vectors and 1 p is the all ones vector in R p . The empirical distribution of a vector x ∈ R p is given by where the infimum is over all the couplings of µ and ν, i.e. all random variables (X, Y ) such that X ∼ µ and Y ∼ ν marginally. A sequence of probability distributions ν p on R m converges in W k to ν, where expectation is with respect to X p ∼ ν p and X ∼ ν. For a sequence of random variables X p that converge in probability to some constant c in the limit of Assumption 1 below, we write X p P −→ c. Next, we formalize the set of assumption under which our analysis applies. Our asymptotic results hold in the linear asymptotic regime specified below. Assumption 1 We focus on a double asymptotic regime where n, p, s → ∞ at fixed overparameterization ratio κ := p/n > 0 and sparsity level α := s/p ∈ (0, 1).
Additionally, we require certain mild assumptions on the behavior of the covariance matrix Σ and of the true latent vector β . For simplicity, we assume here that Σ = diag([Σ 1,1 , . . . , Σ p,p ]). Assumption 2 The covariance matrix Σ is diagonal and there exist constants Σ min , Σ max ∈ (0, ∞) such that: With these, we are ready to define, what will turn out to be, the asymptotic DC in the overparameterized regime. Definition 3 (Asymptotic DC -Overparameterized regime) Let random variables (Λ, B) ∼ µ (where µ is defined in Assumption 3) and fix κ > 1. Define parameter ξ as the unique positive solution to the following equation Further define the positive parameter γ as follows: With these and H ∼ N (0, 1), define the random variable and let Π κ,σ 2 be its distribution.
Our main result establishes asymptotic convergence of the empirical distribution of ( √ pβ, √ pβ , Σ) for a rich class of test functions. These are the functions within PL(3) that become PL(2) when restricted to the first two indices. Formally, we define this class of functions as follows For pruning analysis, we set Z = [Σ min , Σ max ] and define where g(·) is Lipschitz}. (12) As discussed below, F L is important for predicting the risk of the (pruned) model. In the SM, we prove that F L ⊂ F. We are now ready to state our main theoretical result. Theorem 1 (Asymptotic DC -Overparameterized LGP) Fix κ > 1 and suppose Assumptions 2 and 3 hold. Recall the solutionβ from (7) and let As advertised, Theorem 1 fully characterizes the joint empirical distribution of the min-norm solution, the latent vector and the covariance spectrum. The asymptotic DC allows us to precisely characterize several quantities of interest, such as estimation error, generalization error etc.. For example, a direct application of (13) to the function f (x, y, z) = z(y − x) 2 ∈ F L ⊂ F directly yields the risk prediction of the min-norm solution recovering (Hastie et al. 2019, Thm. 3) as a special case. Later in this section, we show how to use Theorem 1 towards the more challenging task of precisely characterizing the risk of magnitude-based pruning.
Before that, let us quickly remark on the technical novelty of the theorem. Prior work has mostly applied the CGMT to isotropic features. Out of these, only very few obtain DC, (Thrampoulidis, Xu, and Hassibi 2018; Miolane and Montanari 2018), while the majority focuses on simpler metrics, such as squared-error. Instead, Theorem 1 considers correlated designs and the overparameterized regime. The most closely related work in that respect is (Montanari et al. 2019), which very recently obtained the DC of the maxmargin classifier. Similar to us, they use the CGMT, but their analysis of the auxiliary optimization is technically different to ours. Our approach is similar to (Thrampoulidis, Xu, and Hassibi 2018), but extra technical effort is needed to account for correlated designs and the overparameterized regime.

From DC to Risk Characterization
First, we consider a simpler "threshold-based" pruning method that applies a fixed threshold at every entry ofβ. Next, we relate this to magnitude-based pruning and obtain a characterization for the performance of the latter. In order to define the threshold-based pruning vector, let be the hard-thresholding function with fixed threshold t ∈ R + . Defineβ T t := T t/ √ p (β), where T t acts componentwise. Then, the population risk ofβ T t becomes In the second line above, we note that In the last line, we apply (13), after recognizing that the function (x, y, z) → z(y − T t (x)) 2 is a member of the F L family defined in (12). As in (13), the expectation here is with respect to (Λ, B, H) ∼ µ ⊗ N (0, 1). Now, we show how to use (14) and Theorem 1 to characterize the risk of the magnitude-based pruned vector β M s := T s (β). Recall, here from Assumption 1 that s = αp. To relateβ M s toβ T t , consider the set S t := {i ∈ [p] : √ p|β i | ≥ t} for some constant t ∈ R + (not scaling with n, p, s). Note that the ratio |S t |/p is equal to Here, 1 denotes the indicator function and the convergence follows from Theorem 1 when applied to a sequence of bounded Lipschitz functions approximating the indicator. Thus, by choosing it holds that |S t |/p P −→ α. In words, and observing that X κ,σ 2 admits a continuous density (due to the Gaussian variable H): for any ε > 0, in the limit of n, p, s → ∞, the vectorβ T t has (1 ± ε)αp = (1 ± ε)s non-zero entries, which correspond to the largest magnitude entries ofβ, with probability approaching1. Since this holds for arbitrarily small ε > 0, recalling t as in (15), we can conclude from (14) that the risk of the magnitude-pruned model converges as follows.
Corollary 1 (Risk of Magnitude-pruning) Let the same assumptions and notation as in the statement of Theorem 1 hold. Specifically, letβ be the min-norm solution in (7) andβ M s := T s (β) the magnitude-pruned model at sparsity s. Recall the threshold t from (15). The risk ofβ M s satisfies the following in the limit of n, p, s → ∞ at rates κ := p/n > 1 and α := s/p ∈ (0, 1) (cf. Assumption 1): where the expectation is over (Λ, B, H) ∼ µ ⊗ N (0, 1).

Non-asymptotic DC and Retraining Formula
While Theorem 1 is stated in the asymptotic regime, during analysis, the DC arises in a non-asymptotic fashion.
The following definition is the non-asymptotic counterpart of Def. 3. We remark that this definition applies to arbitrary covariance (not necessarily diagonal) by applying a simple eigen-rotation before and after the DC formula associated with the diagonalized covariance.
Definition 4 (Non-asymptotic DC) Fix p > n ≥ 1 and set κ = p/n > 1. Given σ > 0, covariance Σ = U diag(λ)U T and latent vector β, setβ = U T β and define the unique non-negative terms ξ, γ, ζ ∈ R p and φ ∈ R p as follows: The non-asymptotic distributional prediction is given by the following U -rotated normal distribution . We remark that this definition is similar in spirit to the concurrent/recent work (Li et al. 2020). However, unlike this work, here we prove the asymptotic correctness of the DC, we use it to rigorously predict the pruning performance and also extend this to retraining DC as discussed next. Retraining DC. As the next step, we would like to characterize the DC of the solution after retraining, i.e.,β RT . We carry out the retraining derivation (for magnitude pruning) as follows. Let I ⊂ [p] be the nonzero support of the pruned vectorβ M s . Re-solving (3) restricted to the features over I corresponds to a linear problem with effective feature covariance Σ I with support of non-zeros restricted to I × I. For this feature covariance, we can also calculate the effective noise level and global minima of the population risk β I . The latter has the closed-form solution β I = Σ † I Σβ . The effective noise is given by accounting for the risk change due to the missing features via σ I = (σ 2 + β T Σβ − β I T Σ I β I ) 1/2 . With these terms in place, fixing I and using Def. 4, the retraining prediction becomes D σ I ,Σ I ,β I . This process is summarized below. Definition 5 (Retraining DC) Consider the setting of Def. 4 with σ, Σ, β and sparsity target s. The sampleβ RT from the retraining distribution D RT,s σ,Σ,β is constructed as follows. Sampleβ ∼ D σ,Σ,β and compute the set of the top-s indices I = I(T s (β)). Given I, obtain the effective covariance Σ I ∈ R p×p , population minima β I ∈ R p , and the noise level σ I > 0 as described above. Draŵ β RT ∼ D σ I ,Σ I ,β I .
Observe that, the support I depends on the samples S viaβ. Thus, our retraining DC is actually derived for the scenario when the retraining phase uses a fresh set of n samples to break the dependence between I, S (which obtainsβ RT fresh ). Despite this, we empirically observe that the retraining DC predicts the regular retraining (reusing S) performance remarkably well and perfectly predictsβ RT fresh as discussed in Figs. 2 and 4. Finally, we defer the formalization of the retraining analysis to a future work. This includes proving that β RT fresh obeys Def. 5 asymptotically as well as directly studyingβ RT by capturing the impact of the I, S dependency.

Conclusions and Future Directions
This paper sheds light on under-explored phenomena in pruning practices for neural network model compression. On a theoretical level, we prove an accurate distributional characterization (DC) for the solution of overparameterized least-squares for linear models with correlated Gaussian features. Our DC allows to precisely characterize the pruning performance of popular pruning methods, such as magnitude pruning. Importantly, our DC combined with a linear Gaussian equivalence, leads to precise analytic formulas for the pruning performance of nonlinear random feature models. On the experimental side, we provide a thorough study of overparameterization and pruning with experiments on linear models, random features and neural nets with growing complexity. Our experiments reveal striking phenomena such as a novel double descent behavior for model pruning and the power of overparameterization. They also shed light on common practices such as retraining after pruning.
Going forward, there are several exciting directions to pursue. First, it would be insightful to study whether same phenomena occur for other loss functions in particular for cross-entropy. Second, this work focuses on unregularized regression tasks and it is important to identify optimal regularization schemes for pruning purposes. For instance, should we use classical 1 / 2 regularization or can we refine them by injecting problem priors such as covariance information? Finally, going beyond pruning, using DC, one can investigate other compression techniques that process the output of the initial overparameterized learning problem, such as model quantization and distillation.

Potential Ethical Impacts
While deep learning is transformative in wide swath of applications, it comes at a cost: State-of-the-art deep learning models tend to be very large and consume significant energy during inference. The race for larger and better models and growing list of applications exacerbates this carbon footprint problem. Thus there is an urgent need for better and more principled model compression methods to help build environmentally friendly ML models. This work responds to this need by establishing the fundamental algorithmic principles and guarantees behind the contemporary model compression algorithms and by shedding light on the design of lightweight energy-and compute-efficient neural networks. We do not see an ethical concern associated with this work.      Figure 1 the blue line corresponds to training dense models with width k. As for the red and green lines we choose 4and 8-width models as base models respectively and prune k-width dense model to corresponding sparsity targets. (a) shows both training and test errors after magnitude-based pruning and retraining. In (b) solid and dotted lines are test errors of magnitude-and random-based pruned models with retraining. To verify the importance of retraining in neural networks we present the test errors of magnitude-based models without retraining in (c).

Organization of the Supplementary Material
The supplementary material (SM) is organized as follows.
1. In Section A we provide additional experiments on neural networks and linear models further supporting the main results.
2. In Section B we prove our main Theorem 1.
3. Section C provides our analysis and results on magnitude and Hessian pruning. 4. Section D provides further supporting technical results used in our proofs. 5. Section E provides our asymptotic analysis of overdetermined problems complementing our main results on overparameterized problems.
6. In Section F we prove Lemma 1.

A Further Experiments and Intuitions
A.1 Further discussion and experiments on CIFAR-10 First, we provide further discussion on Figure 1. Recall that, in this figure, we apply train→prune→retrain to obtain the sparse neural networks. The test error and the training errors for the sparse models are evaluated at the end of the retraining phase. Thus, it is rather surprising that sparse models manage to achieve zero training error around the same width parameter k as the dense model because while parameter count of the dense model increases in k, it is fixed for sparse models.
Secondly, we complement Figure 1 with two additional experiments. The first experiment assesses the benefit of pruning compared to using a random nonzero pattern with the same sparsity. The second experiment assesses the benefit of retraining by comparing the curves in Fig 1 with the test errors obtained without retraining. These two experiments are shown in Figure 5a and 5b and all of them are trained over same dataset and configured as given in Section 3.3. Instead of applying magnitude-based pruning, dotted red and green lines in Fig 5a are sparse models over 5 or 10 sparsity targets, pruned randomly to achieve same number of nonzeros as magnitude-based pruning strategy. Although the double descent phenomenon and downward trend are still present on the dotted lines, the performance is worse than magnitude-base pruning method. Fig. 5b shows how retraining benefits pruning ResNet-20 models. The results agree with our intuition that the non-retrained (dotted) lines achieve much bigger test error than retrained (solid) lines and overparameterization does not help in improving performance.

A.2 MNIST Experiments with two layers
In Figure 6 we train the simplest neural model with only 2 fully-connected layers over MNIST with various number of nodes to explore properties of magnitude-based pruning, random pruning and non-retraining on simple neural networks. Here, the number of nodes is equivalent to the width of the model, which directly controls the model size. Same as in Section 3.3, we select an s-width model as base model and prune trained dense models to the same sparsity. All experiments are trained with Adam optimization, 0.001 learning rate and 200 epochs under MNIST. Solid red, green and blue lines in Figure 6 correspond to test error of 4-, 8-sparsity targets and dense models. In Figure 6a dotted lines are training errors of dense and s-sparse models. As the width k grows, the training and test error decrease for all dense and sparse models. The behavior is similar to Figure  1 and training larger models benefit pruned-model accuracy however double descent is not really visible. We suspect that this may be because of the simpler nature of the MNIST dataset and LeNet architecture compared to the CIFAR10 dataset and ResNet-20 model. In Figure 6b, dotted lines apply randomly pruning. Different to magnitude pruning, where training bigger models and then pruning results in better performance, randomly pruning hurts when the sparsity level s/k is relatively low. This is because under magnitude-based pruning, we can identity most of optimal entries of weights from trained dense model and retraining with these entries achieves lower errors. In constrast, random pruning learns nothing from the trained model and as the sparsity level decreases, the probability that random operator selects the limited optimal entries by chance also decreases, leading to worse performance. Dotted lines in Figure 6c show test errors of sparse models before retraining which educes the same conclusion in Section A.1, that is retraining is crucial to improve the performance in neural networks.

A.3 Experiments on LGP
In Figure 7, we carry out the identical experiments as in Figure 3. The difference is that we display two more figures which are the retraining curves for Magnitude-and Hessian-based pruning strategies shown in purple and yellow lines respectively. Figure  7a is the counterpart of Figure 3a and Figure 7b is the counterpart of Figure 3b. The main message in these experiments is that retraining hurts the performance. This performance degradation is more emphasized in the overparameterized regime. Specifically, both retrained versions of Magnitude and Hessian pruningβ RT,M andβ RT,H perform consistently worse compared to their pruning-only counterpartsβ M andβ H . Observe that, the only regime where retraining outperforms the pruning-only approach is at the peak of double descent. This is the region where pruning-only risk diverges to infinity whereas retraining attains finite risk. This is because the retraining stage solves a well-conditioned problem and avoids the ill-conditioning occurring at n = k. Recall that, in light of Lemma 1, unlike the rank-one covariance case, retraining hurts because covariance is diagonal; thus, features are uncorrelated and do not have overlapping predictions.

B Proofs for overparameterized least-squares
In this section, we assume the linear Gaussian problem (LGP) of Definition 1, the overparameterized regime k = p > n and the min-norm modelβ of (7). We prove Theorem 1 that derives the asymptotic DC ofβ and we show how this leads to sharp formulae for the risk of the Magnitude-and Hessian-pruned models.

B.1 Notation and Assumptions
For the reader's convenience, we recall some necessary notation and assumptions from Section 5. We say that a function f : x − y 2 (See also Section D). We say that a sequence of probability distributions An equivalent definition is that, for any f ∈ PL(k), lim p→∞ E f (X p ) = E f (X), where expectation is with respect to X p ∼ ν p and X ∼ ν (e.g., (Montanari and Venkataramanan 2017)). Finally, recall that a sequence of probability distributions ν n on R m converges weakly to ν, if for any bounded Lipschitz function f : lim p→∞ E f (X p ) = E f (X), where expectation is with respect to X p ∼ ν p and X ∼ ν. Throughout, we use C, C , c, c to denote absolute constants (not depending on n, p) whose value might change from line to line.
We focus on a double asymptotic regime where: n, p, s → ∞ at fixed overparameterization ratio κ := p/n > 1 and sparsity level α := s/p ∈ (0, 1).  For a sequence of random variables X p that converge in probability to some constant c in the limit of Assumption 1 below, we write X p P −→ c. For a sequence of event E p for which lim p→ P(E p ) = 1, we say that E p occurs with probability approaching 1. For this, we will often use the shorthand "wpa 1".

B.2 Asymptotic distribution and risk characterizations
In this section, we prove our main result Theorem 1. Recall thatβ is the min-norm solution. Since the distribution ofβ depends on the problem dimensions (as it is a function of X, y), when necessary, we will useβ n notation to make its dimension dependence explicit. Letβ P = P(β) be a pruned version of the min-norm solutionβ. Recall from Section 5.2, that the first crucial step in characterizing the risk L(β P ) is studying the risk L(β T t ) of a threshold-based pruned vector. To keep things slightly more general, considerβ g defined such that √ pβ g = g( √ pβ), where g is a Lipschitz function acting entry-wise onβ (for example, g can be the (arbitrarily close Lipschitz approximation of the) thresholding operator T t of Section 5.2). Then, the risk ofβ g can be written as where in the last line, we defined the function f as f = f L ∈ F L ⊂ F given by f L (x, y, z) := z(y − g(x)) 2 where g is Lipschitz.
Here, recall the definition of the families F L in (12) and F in (11).
The following theorem establishes the asymptotic limit of (16). For the reader's convenience, we repeat the notation introduced in Definition 3. Let random variables (Λ, B) ∼ µ (where µ is defined in Assumption 3) and fix κ > 1. Define parameter ξ as the unique positive solution to the following equation Further define the positive parameter γ as follows: With these and H ∼ N (0, 1), define the random variable X κ,σ 2 := X κ,σ 2 (Λ, B, H) : and let Π κ,σ 2 be its distribution.
Theorem 1 (Asymptotic DC -Overparameterized LGP) Fix κ > 1 and suppose Assumptions 2 and 3 hold. Recall the solutionβ from (7) and letΠ Σi,i) be the joint empirical distribution of ( √ pβ, √ pβ , Σ). Let f : R 3 → R be a function in F defined in (11). We have that Before we prove the theorem, let us show how it immediately leads to a sharp prediction of the risk behavior. Indeed, a direct application of (13) for f = f L to (16) shows that We further remark on the following two consequences of Theorem 1. First, since (13) holds for any PL(2) function, we have essentially shown thatΠ n (y, X, β , Σ) converges in Wasserstein-2 distance to Π κ,σ 2 ⊗ µ, where recall that Π κ,σ 2 is the distribution of the random variable X κ,σ 2 .
Second, the theorem implies that the empirical distribution of √ pβ n converges weakly to Π κ,σ 2 . To see this, apply (13) for the PL(2) function f (x, y, z) = ψ(x) where ψ : R → R is a bounded Lipschitz test function.

B.3 Proof of Theorem 1
Let X ∈ R n×p have zero-mean and normally distributed rows with a diagonal covariance matrix Σ = E[xx T ]. Given a groundtruth vector β and labels y = Xβ + σz, z ∼ N (0, I n ), we consider the least-squares problem subject to the minimum Euclidian norm constraint (as κ = p/n > 1) given by It is more convenient to work with the following change of variable: With this, the optimization problem in (7) can be rewritten as where we setX = XΣ −1/2 i.i.d. ∼ N (0, 1). First, using standard arguments, we show that the solution of (20) is bounded. Hence, we can constraint the optimization in a sufficiently large compact set without loss of generality. Lemma 2 (Boundedness of the solution) Let w n := w n (X, z) be the minimizer in (20). Then, with probability approaching 1, it holds that w n ∈ B, where Proof First, we show that the min-norm solutionβ = X T (XX T ) −1 y of (18) is bounded. Note that κ > 1, thus XX T is invertible wpa 1. We have, But, wpa 1, σ min (X)/ √ n ≥ 1 2 ( √ κ − 1) . Furthermore, y 2 ≤ X Σ 1/2 β 2 + σ z 2 ≤ σ max (X) √ Σ max β 2 + σ z 2 . Hence, wpa 1, where we used the facts that wpa 1: z 2 / √ n P −→ 1, σ max (X) < √ 2n( √ κ + 1) and by Assumption 3: Put together in (21), shows that Recalling that w n = √ Σβ n − √ Σβ , we conclude, as desired, that wpa 1, Lemma 2 implies that nothing changes in (20) if we further constrain w ∈ B in (20). Henceforth, with some abuse of notation, we let Next, in order to analyze the primary optimization (PO) problem in (23) in apply the CGMT (Thrampoulidis, Oymak, and Hassibi 2015; Thrampoulidis, Abbasi, and Hassibi 2018). Specifically, we use the constrained formulation of the CGMT given by Theorem 2. Specifically, the auxiliary problem (AO) corresponding to (23) takes the following form with g ∼ N (0, I n ), h ∼ N (0, I p ), h ∼ N (0, 1): We will prove the following techincal result about the AO problem. Lemma 3 (Properties of the AO -Overparameterized regime) Let the assumptions of Theorem 1 hold. Let φ n = φ(g, h) be the optimal cost of the minimization in (24). Defineφ as the optimal cost of the following deterministic min-max problem The following statements are true.
(iii). The max-min optimization in (25) has a unique saddle point (u * , τ * ) satisfying the following: In particular, this holds for all functions f ∈ F defined in (11).
(v). The empirical distribution ofβ AO n converges weakly to the measure of X κ,σ 2 , and also, for some absolute constant C > 0: β AO 2 2 < C wpa 1.
We prove Lemma 3 in Section B.4. We remark that Assumption 3 on W 4 -convergence of the joint empirical distribution of [p] is required in the proof of the statement (iv) above. More generally if W k -convergence is known for some integer k, then statement (iv) above holds for test functions f ∈ PL(k − 1). This is the first place in the proof of Theorem 1, where we use the assumption f ∈ F; indeed, we show in Lemma 4 that F L ⊂ F ⊂ PL(3). The second part is in proving the perturbation result in (33) below. Unlike the former, when proving the perturbation result, the requirement f ∈ F cannot be relaxed (e.g. to f ∈ PL(k − 1)) by simply increasing the order of W k -convergence in Assumption 3.
Finalizing the proof of Theorem 1: Here, we show how Lemma 3 leads to the proof of Theorem 1 when combined with the CGMT framework (Thrampoulidis, Oymak, and Hassibi 2015; Thrampoulidis, Abbasi, and Hassibi 2018). Let f : R 3 → R be a function in F, where F was defined in (11). For convenience, define Fix any ε > 0 and define the set With this definition, observe that, it suffices to prove that the solutionŵ n = √ Σ(β n − β ) of the PO in (18) satisfiesŵ n ∈ S wpa 1.
In what follows, we explicitly findφ,φ S , η such that the three conditions above hold.
Satisfying Condition 3: Next, we will show that the third condition holds for appropriateφ. Letŵ AO n =ŵ AO n (g, h) be the unique minimizer of (24) as per Lemma 3(i), i.e., 1 2 Σ −1/2ŵAO n + β 2 2 = φ(g, h). Again from Lemma 3, the minimization in (24) is 1/Σ max -strongly convex in w. Here, Σ max is the upper bound on the eigenvalues of Σ as per Assumption 3. Thus, for anyε > 0 and any feasible w the following holds (deterministically): Now, we argue that wpa 1, for all w ∈ S it holds that w −ŵ AO n 2 ≥ε, for an appropriate value of a constantε > 0.
Next, we study the fourth summand. First, note that In the last line, Λ is a random variable as in Definition 3. Also, we used Assumption 3 together with the facts that h is independent of Σ and that the function (x 1 , x 2 ) → x 2 1 (x −1 2 + u/τ ) −1 is PL(3) assuming x 2 is bounded (see Lemma 5 for proof). Second, we find that Here, Λ, B are random variables as in Definition 3 and we also used Assumption 3 together with the fact that the function (x 1 , x 2 ) → x 2 1 x −1 2 (x −1 2 + u/τ ) −1 is PL(3) assuming x 2 is bounded (see Lemma 5 for proof). Third, by independence of (β , Σ) from h Putting these together, the objective R(u, τ ) in (39) converges point-wise in u, τ to Note that R(u, τ ) (and thus, D(u, τ )) is convex in τ and concave in u. Thus, the convergence in (44) In the proof of statement (iii) below, we show that the saddle point of (45) is (u * , τ * ). In particular, τ * is strictly in the interior of T , which combined with convexity implies that This, together with the first display above proves the second statement of the lemma.
Proof of (iii). Next, we compute the saddle point (u * , τ * ) by studying the first-order optimality conditions of the strictly concave-convex D(u, τ ). Specifically, we consider the unconstrained minimization over τ and we will show that the minimum is achieved in the strict interior of T . Direct differentiation of D(u, τ ) gives Multiplying (47b) with τ u and adding to (47a) results in the following equation Thus, we have found that the ratio u * τ * is the unique solution to the equation in (48). Note that this coincides with the Equation (8) that defines the parameter ξ in Definition 3. The fact that (48) has a unique solution for all κ > 1 can be easily seen as F (x) = E 1 (xΛ) −1 +1 , x ∈ R + has range (0, 1) and is strictly increasing (by differentiation). Thus, we call ξ = u * τ * . Moreover, multiplying (47b) with u leads to the following equation for τ * : (49) Again, note that this coincides with Equation (9) that determines the parameter γ in Definition 3, i.e., τ 2 * = γ. By definition of T and of τ * , it is clear that τ is in the strict interior of T .
Proof of (iv). For convenience, define Recall from (40) the explicit expression forŵ AO n , repeated here for convenience.