Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization
Authors: Milad Sefidgaran
Kimia Nadjahi
Abdellatif Zaidi
Venue: NeurIPS 2025 oral ()
Keywords: generalization error
information theory
conditional mutual information
CMI
learning theory
projection
memorization
Primary area: theory

Abstract: In this paper, we leverage stochastic projection and lossy compression to establish new conditional mutual information (CMI) bounds on the generalization error of statistical learning algorithms. It is shown that these bounds are generally tighter than the existing ones. In particular, we prove that for certain problem instances for which existing MI and CMI bounds were recently shown in Attias et al. [2024] and Livni [2023] to become vacuous or fail to describe the right generalization behavior, our bounds yield suitable generalization guarantees of the order of $\mathcal{O}(1/\sqrt{n})$, where $n$ is the size of the training dataset. Furthermore, we use our bounds to investigate the problem of data "memorization" raised in those works, and which asserts that there are learning problem instances for which any learning algorithm that has good prediction there exist distributions under which the algorithm must "memorize'' a big fraction of the training dataset. We show that for every learning algorithm, there exists an auxiliary algorithm that does not memorize and which yields comparable generalization error for any data distribution. In part, this shows that memorization is not necessary for good generalization.

Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization
Milad Sefidgaran', 1
Kimia Nadjahi 2, Abdellatif Zaidi 1.3
Paris Research Center, Huawei Technologies France CNRS, ENS Paris, France Université Gustave Eiffel, France
milad. www.sagaaaaannaaaeei.cccomm kimia. simia.nadjall naijaieens.. fr, abdellatif wwidieumiv-eiffelll.
Abstract
this paper, we leverage stochastic projection and lossy compression establish new conditional mutual information (CMI) bounds the generalization error of statistical learning algorithms. It is shown that these bounds are generally tighter than the existing ones. In particular, and CMI bounds were recently shown in Attias et al. [2024] and Livni [2023] to become vacuous fail to describe the right generalization behavior, generalization guarantees of the order of O (R), where n. is the size of the training dataset. Furthermore, use our bounds to investigate the problem of data "memoriza- tion" raised in those works, and which asserts that there are learning problem instances for which any learning algorithm that good prediction there exist distributions un- der which the algorithm must "memorize" big fraction of the training dataset. We show that for every learning algorithm, there exists an auxiliary algorithm that does nor memorize and which yields comparable generalization error for any data distribution. part, this shows that memorization not necessary good generalization.
prove that for certain problem instances for which existing MI
bounds yield suitable
Introduction
One of the major problems in statistical learning theory consists in understanding what really drives the generalization error of learning algorithms. That is, what makes an algorithm trained a given dataset continue to perform well on unseen data samples. Historically, this fundamental question has been studied independently in various lines of work, using seemingly unconnected tools. This includes VC-dimension theory [.]. Rademacher complexity approaches (2), stability- -baled analysis B and, more recently, intrinsie-dimensin 3 and information-thcorude approaches 21 It is only until recently that the above various approaches were shown to be possibly unified
p P
using variable-length
compressibility technique, which is aate-distortion-theerrte in nature.
In the context of statistical learning theory perhaps one can date back intemmation-theoretie approaches the PAC-Bayes bounds McAllester (4 25 which were then followed by various extensions and ramifications 39) The mutual information (MI) bounds of [9] and [T0] have the advantages to be relatively simpler comparatively and of offering somewhat clearer insights into the question of generaliza- tion. Roughly, such bounds suggest that a learning algorithm generalizes better its output model reveals less information about the training data samples, where the amount of revcaled information is measured in terms of the Shannon mutual information.
However, MI-based bounds are also known to sometimes take large (infinite) values and become vacuous, such as for continuous data and deterministic models. This shortcoming has been identified in number of works, including 40 [T.. The issue was believed to resolved by the introduction [2]
impor- tant framework of conditional mutual information (CMI). The CMI setting introduces a "super-sample" construction which an auxiliary "ghost sample" is used conjunction with the training sample; and sequence of Bernoulli random variables determines which data samples among the super-sample
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

used for the training. It is shown that a bound on the generalization error involves the mutual information between the Bernoulli random variables and the hypothesis (e.g., model parameters), conditionally given the super-sample [2 Theorem 2]. Because the entropy of Bernoulli random variables is bounded, the resulting bound bounded. Many follow-up works have proposed extensions and improvements the original CMI bounds, including using randomized subser and individual sample techniques, disintegration, and fast-rate variations in regimes in which the empirical risk small See 42 for more on this.
CMI-type bounds were largely believed to be exempt from the aforementioned limitations of MI bounds until was recently reported that examples can be constructed for which the standard CMI-based bound and its individual-sample variant fail [1 43 46]. The (counter-) examples of [46] are in the context of Stochastic Convex Optimization (SCO) problems; and those of F3 involve carefully constructed Convex-Lipschite Lipschitz- bounded (CLB) and
convex- Lipschht (CSL) instance problems.
These limitations were sometimes extrapolated to the extent of even questioning the utility of information- theoretic bounds for the analysis of the generalization error of statistical learning algorithms more gen- erally [47]. In this context, we mention [23 Appendix A] in which it was shown that, when applied to the counter-cxample of [47] a lossy version of MI bounds yiclds generalization bounds that are of order (1/n), instcad of (1(1) in the case of standard (lossless) MI bounds The idea of lossy compression was
also used
49
In this paper, essentially, we show that the aforementioned limitations are in fact not inherent to the CMI framework; and, actually, the CMI framework can be adjusted slightly by the incorporation of suitable stochastic projection and a suitable lossy compression to cope with those issues. Also, leveraging the utility of CMI and membership inference to study the problem of memorization and its relationship generalization in machine learning, we use our results to revisit the necessity of memorization for SCO problems claimed in (43. We show that memorization is not necessary for good generalization; and, as such, the result contributes to a better understanding of what role memorization plays in machine learning, a problem which yet to be fully understood. Specifically, our contributions are as follows.
We introduce stochastic projection in conjunction with lossy compression in the CMI framework, and we use them to establish new CMI-based bound that is generally tighter than the CMI bounds of [1].
We show that, in sharp contrast with classic CMI- based bounds which fail when applied to the afore- mentioned CLB, CSL and SCO problem instances of 443 (6) and may not even decay with the number of training samples, our new CMI bound yields meaningful results and decays with the number of train- ing samples as (1///n).
By applying them to generalized linear stochastic (non-convex) optimization problems, in the appen- dices we demonstrate that our bounds remain non-vacuous even beyond the convex case previously studied in [50]. The generalization is shown to come at the expense of slower decay with n in our case: namely, (11 /n) instead of (()/v)) if the functions are convex as in [50]
We leverage the key ingredients of stochastic projection and lossy compression in the framework of CMI to study the "memorization" issue identified and studied in [43] Specifically, 43) has demon- strated that, for a given problem instance and every E e-learner algorithm, there exists a data distribution under which the algorithm "memorizes" the training samples. We show that for any learning algorithm A that memorizes the training data, one can find (via stochastic projection and lossy compression) an alternate learning algorithm A with comparable generalization error and that does not memorize the training data for any data distribution. In part, this means that memorization is not necessary for good gencralization in SCO.
In the appendices, we use our general bound to study the generalization error of subspace training algorithms. Specifically, we investigate the setting in which the training is performed using SGD or SGLD; and we derive new bounds based on the differential entropy of Gaussian mixture distributions. This entropy depends on the gradient difference for the training and test datasets, the noise power, the learning rate, and the uncertainty of the index of the training dataset within the super-dataset.
'The authors of 43 do not evaluate the performance of variants of CMI such as chained CMI 44 evaluated
CMI and f-CMI 20
2
45
on their counter-ee examee..
'The counterexample of 47 has also been addressed by Wang and Mao 48 using a different technique called SSampe-Conditionn Hypothesis Stability".

---

2 Notation and Background
Let be some random variable with unknown distribution yr and taking values some alphahet Let Sn & (Z1,..., Zn) E z" he set of data samples drawn uniformly from the distribution L.e, Sn Ps. = 1 _. the framework of statistical learning, a (possibly) stochastic learning algorithm A: 2 - takes the training dataset Sn input and returns hypothesis W E W R We assume that A is randomized, in the sense that its output W _ AA(Sn) is a random variable distributed according to Pwis.- We denote the distribution induced on (S.. W) as Ps,, PwIs, Pss. Pw]s. & p0
For given function é: x >> R. the loss incurred by using hypothesis w E W for sample evaluated as f(=, m). A statistical learning algorithm seeks to find hypothesis whose population risk R(w) A Ezzz,(E(2 w)] minimal. However, since the data distribution μ is unknown, direct computation of the population risk R(w) is not possible. Instead, one resorts minimizing the empirical risk Rsn,, w) -.- (zi, w) a regularized version of it. Throughout, if 8n is known from the context, we will use the shorthand notation R. (w) R(sn, w).
The generalization error induced by a specific choice of hypothesis w E W and dataset 8n is evaluated as gen(sn, w) _ R(w) - (w);;
and the expected generalization error of the learning algorithm A is obtained by taking the expectation over all possible choices of (8n, w), as
gen(p, A) - Eps., (S., W)] = EPs,, (R(W)-R((W)) (W)).
2.1 Conditional Mutual Information Framework
Let $ _nnx2 be a super-sample composed of 2n data points Zz, that are drawn uniformly from the distribution μ., where a vector of n independent Bernouli(1122) random variables, all drawn independently from S. Let Š, = [2I.J. Z2.Ja..... .n,,.. ). In what follows, S5 plays the role of the training dataset S... \ $5 plays the role of a test or "ghost" dataset S/ and a shuffled version of the union of the two. For an algorithm A: n + W. CMI with respect the data distribution is defined as
{0, 1} and i E [n]. Also, let J (JI.....Jr) {0, 13" be
CMI(H, A) (((()))J($)).
The CMI captures the information that the output hypothesis of the algorithm A trained on SJ provides about the memhership vector J given the super-sample S. Equivalently, the CMI measures the extent to which the training and test datasets as well as the trained model. In its simplest form, it is shown in [12] that the generalization error of an algorithm for bounded loss in the range [0, 1] can be upper-bounded as
distinguishable given the shuffled version of the union of the two,
gen (p, A) S AM)
Furthermore, for a Convex-Lipschhtz-Boune Boundeed (CLB) whose formal definition will follow, the generaliza- tion error of A was shown in 47 to be upper-bounded as
gen(u, A) LR CM)
(1)
Definition (SCO Problem). A stochastic convex optimization (SCO) problem a triple (W, 2, where W E IR is convex set and f(2,,) W - R is a corvex function for every z E Z.
Definition 2 (Convex-Lipschite-oumee Bounded (CLB)). An SCO problem is called CLB if i) for every w W. ||w||| < R. and ti) the loss function is convex and L-Lipschitz. i.e., 4z 2, Vwn, W: [[(z, w1) E(z, w2)l | < L Lllw2- will. We denote this subclass of SCO problems by CL,R-
3 New CMI-based bounds via stochastic projection and lossy compression
While the CMI-based bounds are known to be generally tighter than the corresponding MI ones and even tight in some settings [12 [4] they can become vacuous in some cases. This includes Stochastic Convex Optimization (SCO) examples constructed in the recent works 43 46), which we will discuss in
3

---

more detail in Section 4 For these (counter- Jexamples. it was shown in [43 46 that CMI-type bounds do not vanish, so they fail accurately describe the generalization error. In this section, we show that such limitations are not inherent to the CMI framework. In fact, by combining stochastic projection with lossy compression (analogously to [4). which addressed the case), we derive new CMI-hased bounds that do not suffer from such limitations. For instance. when applied to the SCO examples of [ show Section 4 that our new bounds resolve the limitations of other known CMI-based bounds as identified therein. These bounds are also shown in the appendices apply to the analysis of the generalization error for subspace training algorithms trained with SGD or SGLD.
Our new bounds involve two main ingredients, stochastic projection and lossy compression.
Stochastic projection. Let θ E Dxx be random matrix with entries distributed according to some joint distribution Pe. chosen independently of S. In our approach, similar to 49 instead of considering the hypothesis W W - R which lies in D-dimensional space, we consider its projection e W R" onto smaller d-dimensional space, with d << D.
Lossy Compression. Let é R be given. An e-lossy algorithm a (possibly) stochastic map Å: Z" DDxd + W that maps pair (Sn, θ) to compressed hypothesis or model W E W C R" generated according some conditional kernel PWiss. s..e that satisfies
BP w Wis.. [gen(S.. W) gen(Sn., (wo)S,.,W)) sc.
This constraint guarantees that, when projected back onto the original hypothesis space of dimension D, the compressed model W has an average generalization error which is within at most from that of the original model W. In a sense, one works with compressed model W which lies in much smaller dimension space, but with the guarantec that this causes almost no increase in the generalization error. In effect, the auxiliary projected- model OW substitutes the original model W.
The concept of a lossy algorithm, also referred to as a "surrogate" or "compressed" algorithm, was in- troduced in [37 51 52 and shown therein to be key obtaining tighter, non-vacuous, generalization bounds. In this paper, we consider a particular lossy algorithm that involves a suitable stochastic projection followed by quantization. Specifically, we constrain the general conditional Pwijs,,e to take the specific form P Wwetww w. where W = A(S.). Formally, one imposes the Markov chain (S.., 6, W) TTW W W or equivalently Pwiss, w Pwrerw w In other words, we let A(Sn, θ) λ(e T A(S.)), where W is defined via the Markov kernel PWieTA(S..
A: Rd
Our generalization bounds that will follow are expressed in terms of disintegrated CMI, defined as follows. Let a super-sample Š and a stochastic projection matrix given. The disintegrated CMI algorithm A: z" + W is defined as
C (S, A) & S. ();),,
where A(Ss, 6)
A A(S.)) W and S.. (Á(S), J): is the CMI given instance of $ and O, computed using the joint distribution P3 @ P Pwis, & PWieTW w with P3 = Bemn(1
The next theorem states our main generalization bound and is proved in Appendix E
Theorem 1. Let learning algorithm A: 2" + W where T every d E N, and every projected model quantization set W C B we have
RD be given. Then, for every R,
2A ($, 9)
CMI tG,
gen(j,, A) < inf inf EE
(2)
PwieTw
Pe
where W. W. θ Dxd the infima over all arbitrary choices of Markov kernel Pw e w and distribution Pe that satisfy the following distortion criterion:
E B Po Pwis [gen(Sn,, W) (nn,,),, sc.
(3)
and the term de (S, θ) is given by A (Š, θ) EEP w Pw Tw
Σ ie(n) (e(Zi,a, 0W²) -((,,,,,,)1))))
(4)

---

Observe that Pwis: Er, Er,(Pwis, Also, if E(..)) E [O, CJ for some non-negative constant C' E R.,, then it is casy to see that the term (S, () is bounded from the above as A (S, 9) < C².
The result of Theorem T essentially means that the generalization error of the original model is upper bounded by term that depends on the CMI of the auxiliary model W plus an additional distortion term that quantifies the generalization gap between the auxiliary and original models. The rationale is that, although the (worst-case) CMI term still depends on the dimension d after stochastic projection, this di- mension corresponds to subspace of the original hypothesis space and can be chosen arbitrarily small in order to guarantee that the bound vanishes with n. Also, the term in left-hand-side (LHS) of equation represents the average distortion (measured by the difference of induced generalization errors) between the original model and the one obtained after projecting back the auxiliary compressed model onto the original hypothesis space. The analysis of this term may seem non-easy; but visible from the proof, it is not. This is because, defined as a difference term, its analysis does not necessitate accounting for statistical de- pendencies between S and W. Instead, one only needs to account for the effect of the following sources of randomness: i) the stochastic projection matrix, ii) the quantization noise, and iii) discrepancies between the empirical measure of S and the true unknown distribution J.. As shown in the proofs, the analysis of the distortion term involves the use of classic concentration inequalities. Furthermore, the construction of W allows us to consider the worst-case bound for the CMI-terms of the RHS of equation 2 without losing the order-wise optimality in certain cases.
We close this section by noting that is well known that CMI-type bounds can be improved by application of suitable techniques such as sudom or individual sample lechniques or in order to get fast rates These same techniques can be applied straightforwardyy to our bound of T'eorrm to get improved ones. For the sake of brevity, we do not elab- orate on this here; and we refer the reader to the supplements where a single-datum version of Theorem is provided.
(11/n) for small empirical risk regimes, see, e.g., 20 53
4 Application to resolving recently raised limitations of classic CMI bounds
Prior works [43 46 have recently reported carefully constructed counter-example learning problems and have shown that classic MI-based and CMI-based bounds fail to provide meaningful results when applied them. this section, we show that the careful addition of our stochastic projection along with our lossy compression resolves those issucs, in the sense that the resulting new bound (our Theorem D which is still of CMI-type, now yields meaningful results when applied to those counter-examples. In essence, the im- provement is brought up by: (i) noticing that the aforementioned negative results for standard (MIIbased generalization error bounds rely heavily on that the dimension of the hypothesis space grows fast with (over-parameteriieed regime), e-g., 2(n n) in the considered counter-examples of [43), which calls for suitable projection onto smaller dimension space in which this does not hold, and (ii) properly accounting for the distortion induced in the generalization error after projection back to the original high dimensional space.
First, we recall briefly the counterexamples mentioned in [43] and [6); and, for each of them, we show how our bound of Theorem [ applies successfully to Recall the definitions of a stochastic convex optimization (SCO) problem and a Baanee--Lipxchizz-Bundee (CLB) SCO problem given, respectively,
Definition 0 and Defimition 2
Definition 3 (s-learner for SCO). Fix c > 0. For given SCO problem 2. A = [An)n21 is
called an E-learner algorithm with sample complexity N: R R + N if the following holds: for every 8 (0, 1] and n > N(,, 6) we have that for every l E M1 (Z), where Mı(2) denotes the set of probability measures on 2. with probability at least - over S. ~ μ and internal randomness of A,
RSA))S
min R(w) S. wEW
(5)
4.1 Counter-example of Attias et al. [2024] for CLB class
Denote by (D) the D-dimensional ball of radius E R+, Definition& 4 (Problem instance P(D)) ). Let L, R E ER,, Z C (D(1), and W = BD(R). Define the loss
functioon& E: Z x W + R as
le w) = - L(W,
We denote this SCO problem instance as P(D) It is easy to see that this optimization problem belongs to the subclass CT,R of SCO problems as defined in Definition 2
5

---

For this (counter-) example learning problem. 43 have shown that for every e-learner there exists data distribution which the CMI bound equation T for the optimal sample complexity. which θ ((4 (LR))² as shown in [50), scales just as e (LR). For instance, that CMI-bound on the generalization does not decay with the size n of the training dataset!
Theorem (CMI-accuracy tradeoff, [43 Theorems 4.1 and 5.2)). Let eo (0, 1) be universal constant. Consider the above defined Pere problem instance with parameters (L, R). Consider any S cu and for any algorithm A = hne that e-learns P(Di with sample complexity N(::). Then, the following holds: i. For every 8 E, 2 5), and D 2 (n" log(n)) there exists 2 C (I) and data distribution μ Mi(Z), denoted por,, such that (MI(u, 12 (2((E)))) i. In
particular, considering the optimal sample complexity (c, = θ =² the CMI generalization bound of equation equals (.)) 6) (LL)).
For this example, was further shown [43 Corollary 5.6] that application of the individual sample tech- nique of [55 56] (which traditionally used to avoid the unbounded-ness issue as instance of so called randomized-suiree techniques wherein the linearity of the expectation operator is used to obtain an average bound for the loss on randomly chosen subsets the training set rather than the loss averaged over the full training set) actually yields the very same bound order-wise; and, thus, it does not resolve the issue for this counter-example.
Furthermore, as shown in 43
Equation 1J. the expectation of the LHS of equation 5 can be bounded as
min R(w) < LR SCMI(H,AA) R. (An. min Rr (w))
[(((An
(6)
WEW
wEW
Thus, while the LHS of this incquality is bounded from above by by assumption, its right-hand side (RHS) is ((LR) by Theorem 2 This means that the CMI bound of cquation ] fails to describe well the excess error of the LHS. In [43]. this was somewhat extrapolated to negatively answer the question about "whether the excess error decomposition using CMI can accurately capture the worst-case excess ervor of optimal algorithms for SCOs".
The above applies for any s-learner of the problem instance P when 2 (#1/VD) and Up (z) IPP
(LVDDAPE for all = (zI...., 2D), where p" = .ppp.....p) E [-
The next theorem shows that when applied to the aforementioned counter-example, our new CMI-bound of Theorem [ does not suffer from those shortcomings. Also, this holds true for: (i) arbitrary values the dimension D E N including n-dependent ones, (ii) arbitrary learning algorithms (including the e-learners of P(D)), (iii) arbitrary choices of Z C (1) and (iv) arbitrary data distributions p.
Theorem 3. For every learning algorithm A: zn + W of the instance P(D) defined as in Definition the generalization bound of Theorem wields
8LR
gen(H, A) S
Vn
In particular, setting N(e, = (1212) x²
for e-learner algoritlums we get
gen(u, (s).
The proof of Theorem is deferred to Appendix F2
Some remarks in order. First, while when applied to the studied counter-example the CMI bound of equation I yields a bound of the order ((LR), i.e., one that does not decay with n, our new CMI- based bound of Theorem I yields that decays with OLRR/ vn). Second, when specialized to the
'The arXiv version of 43 requires smaller increase of D with namely. D Q (n² log(n)). Here, consider values of L) that are mentioned in the published PMLR version of the document, i.c., D 52 (m log(n)); ; but the approach and results that will follow also hold for D Ω (n² log(n)).
'In the construction of [43), by changing n. the data distribution changes, but, for better readability, we drop such dependence in the notation.

---

( ((+R)²) we get bound the
case of e-learner algorithms and considering the sample complexity @ generalization error of the order O (E). Using this bound, we can write
B.... w (R(A.. min R(w) < O (+) + E P.... (R.(An())))- WEW
min (u) weW
(7)
Contrasting with equation and noticing that the second term of the summation of the RHS of equa- tion 7 (ontimization error) is small then both sides of equation 7 are O(c), it is clear that now the excess error decomposition using our new CMI-based bound can accurately capture the worst-case excess error. Third, as it can be from the proof, stochastic projection onto a one-dimensional space, i.e., I, is sufficient to get the result of Theorem 3] In essence, this is the main reason why, in sharp contrast with projection- and cossy-compression- free CMI-bounds, ours of Theorem || does not become vacuous. That is, one can reduce the effective dimension of the model for the studied example even if the original dimension D allowed to grow with n as Q log(n)) as judiciously chosen in 45 for the purpose of making classic CMI-based bounds fail. Furthermore, it is worth noting that, for this problem, the pro- jection performed using the famous
Linissoonnidddesttrauusss [57] dimension reduction algorithm. Since this dimension reduction technique is "lossy". controlling the induced distortion is critical. To do so, we introduce an additional lossy compression step by adding independent noise in the lower-dimensional space. This approach is reminiscent of lossy source coding and allows to obtain possibly tighter bounds on the quantized, projected model. Finally, we mention that for bigger class problem instances or for the memorization problem of Section projection
one-dimensional spaces may not be enough get the desired order O(LR/ vn). In Appendix B it will be shown that for generalized linear stochastic opti- mization problems, one may need d (Vvn). Similarly, in Section and Appendix C projections with d = n 3r-11 < 1 and d = O(log n) are used.
4.2
Counter-example of Attias et al. [2024] for CSL class
The question of whether classic CMI-bounds and individual sample versions thereof may still fail if one considers more structured subclasses SCO problems was raised (and answered positively!) in Attias et al. 43 For convenience, we recall the following two definitions.
Definition 5 (Convex set-Strongly Convex-Lipschitz (CSL)), An SCO problem is called CSL if the loss function is L-Lipschitz, and ii) the loss function is X-strongly convex, i.c., Vz E Z, Ywi, w2 E W: E(2, w2) 2 f(2, w1) + (dE(z, w1), W2 w1) + À llw2 will", where df(z, w1) is the subgradient of E(z,)) )) at wr. We denote this subclass by Ct,
2
Definition (Problem instance P(D)) Let X, R R4, C BD(1), and W BD( Define the loss function f: Z x W -> IR as (zo w) = Lo 2) + 1.ll We denote this SCO problem as Peece
which belongs to CL,A, with L Le AR.
Setting X = Le R = 1. On" log(n)), 6 011n2²,, 2 (+1//D3 and for particular data distribution that is carefully chosen therein (not reproduced here for brevity), 43 Theorem 4.2] states that for any learning algorithm that e-learns the problem instance (D))
(M, = S2
Morcover, the application of the andividual-sampe technique does not result in better decay of the bound order-wise 43 Corollary 5.7].
Noticing that (i) the loss (z,(2, w) LL 2) + ||/ considered in Definition 6 differs from that
(z, w) = =L(ww, 22) of Definition essentially Desseitl through the added squared magnitude of the model and (ii) that addition does not alter the generalization error a given learning algorithm, then it easy to see that Thcorem also applics for the problem P(D) at hand; and, in this casc, it gives a bound the order O(I/Vn). This is stated in the next proposition, which is proved in Appendix F3
Proposition 1. For every learning algorithm A: 2n - W of the instance P ((P) defined as Definition the generalization bound of Theorem yields
SLER
gen A)
Vn
In particular, choosing I.. I. R= and setting N(e, 8) = - for some non- non-negative constant c E IR+
for the ERM algorithm (which is e-learner see, e.g., 50 Theorem 6]). one gets gen(j, A) = O (VE).
7

---

4.3 Counter-example of Livni [2023]
The counter-example of [46] the same as the problem instance of Definition with the one difference
that the loss function is taken to be the squared distance instead of the inner product, Lee, {(2, w) = -L --llw - =1l² for some non-negative constant E R Livni [46] has shown that the MI bound of I (which is single-datum bound) fails and becomes vacuous when evaluated for this particular learning problem. However, since E(2, w) = L ||=]| L || 2 + 2 x) and noticing that the squared norm terms do not alter the generalization error relative when computed for loss function given by only the inner-product term, it follows that Theorem 3 still applies and gives a bound of the order (1//vn) for this problem instance. In addition, for the optimal sample complexity, the bound is OEe). In essence, this means that unlike the MI bound of [T]] our new CMI-hased bound of Theorem D does not become vacuous when applied to the problem hand.
In Appendix B we apply the bound of Theorem I to a wider family of generalized linear stochastic optimization problems. In particular, we show that counter-example could be found for which the bound of Theorem doee not vanish, even if one considers the bigger class of generalized linear stochastic optimization problems in place of the SCO class problems of [43]
5 Memorization
Loosely speaking, learning algorithm is said "memorize" if by only observing its output model, an adversary can correctly guess elements of the training data among given super-sample. For the CLB and CSL subclasses of problems studied in Section 4 Attias et al. [43] showed that there are problem instances for which, for any e-learner algorithm, there exists data distribution under which the learning algorithm "memorizes" most of the training data. This is obtained by designing an adversary capable of identifying a significant fraction of the training samples.
In this section, we show that given learning algorithm A that memorizes the training samples, one can find (via stochastic projection and lossy compression) an alternate learning algorithm A with comparable generalization error and that does not memorize the training data
Definition 7 (Recall Game 43 Definition 4.3]). Given A= = {An let Q: R x 2 x M2 x - (0, 1) be an adversary for the following game. For i [n), given a fresh data point Z ~ p independent of W), let Z,, = Zi and Z,, = Z4. Then, the adversary is given Ki where K; ~ Bern(1 is independent of other random variables. The adversary declares K, 2 Q(W, Ki, U)) as its guess of K,,
The game consists of n rounds. At each round i E [ni. a pair (Zi,o, Z,,1) is considered and the adversary makes two independent guesses: one for the sample Zi, the other for 4,,,,
Definition 8 (Soundness and recall 43 Definition 4.4)). Consider the setup of Definition 7 Assume that the adversary plays the game in n rounds. For every round i E [m]. the adversary plays two times, in- dependently of each other, using respectively (W, Zs, (4) and (W, Zi,1, (1) as imput. Then, for a given S E [0, 1], the adversary is said to be É-sound if (# E [n]: Q(W, 74,0 11) 1) S. Also, the adver- sary certifies the recall of m samples with probability g E [0. iP (Ere(m) Q(W, 2,,1, H) 2 m 2 q. both conditions met, we say that the adversary (m, 9. E)-traces the data.
Clearly, the concept of (m, q, )-tracingg the data by adversary is most interesting for values of (m, g, E) that are such that: & is small (i.e., the adversary makes accurate predictions), m is large and q is non- negligible (i.e., the adversary can recall significant part of the training data). As Lemma []] which is stated in Appendix C asserts, certain values of (m, q, {) can be attained even by "duumy" adversary that makes guesses without even looking at the given data sample.
For the problem instance P(D), , Attias et al. [43] have shown that, for every e-learner algorithm, there exist a distribution and an adversary that is capable of identifying a significant portion of the training data.
Theorem 4 43 Theorem 4.5)), Consider the P!P) problem instance of Definition 4 with L = R = 1. Fix arbitrary & E (0, 1] and let Z = {=1/VD}D. Let E (0, 1) be a universal constant. Let e 0 such that < Eo. 8 < s. Then, given any s-learner algoritlum A with sample complexity N N(e, =
(log(1/8))/e), there exist a data distribution Hay and an adversary such that for n N(e, 8) and D = Q2 log(n/E)) the adversary (S(1/=²)) 1/3, E) -traces the data.
'The memorization problem has also been studied in (58) via some examples in which the data distribution is not fixed and comes from a meta- meta-distribution i.e. μ ~ Py.. Instead of using the recall game, (58 measured the amount of memorization by (S; W W|p).
8

---

A key implication of Theorem 4 is that, for some fixed q > 0. the result holds even when & E (0, 1] is arbitrarily small and m = (2(z) (by choosing ε = (01/vn) In other words, for the considered class of problems Peoz with data drawn from My", the constructed adversary can provably trace an arbitrarily large part of the training dataset.
We show that the stochastic projection and lossy compression techniques used in the CMI framework can partially mitigate this memorization issue, a sense that will be made precise in Theorem To this end, we first establish a general result on memorization.
Theorem 5. Consider any learning algorithm A = Am2 such that CMI(H, = o(n). Then, for any adversary for this learning algorithm that (m, q, E)traces the data, the following holds: i) m o(n) or & 2 9. ii if. for some O E (0. 1) and no E NN,, m 2 on/for every 2 na. then for any E (0, a) it
holds that: Σie(m) Q(W, Zi o: p)) 2 ml) 2 (a c)q. where m' (
o(n) = (n)).
Theorem 5 whose proof is provided in Appendix G.1 applies to any learning problems. In particular, it is not limited to P the CLB subelass. The argument relies on Fano's inequality for approximate recovery [59] Theorem 2]. We construct a suitable estimator of the index set based on the adversary's s guesses, and we show that if this estimator can correctly recover fraction c > 2 of the membership indices J. then An) = (n)).
Theorem 5 i) means that if the CMT of learning algorithm is of order then any adversary that recalls non-neghiible fraction of the training datasel with some probability q (i.e.. m (n)) is g-sound at best. This means that, in this regime, no adversary can do better than dummy that makes random guesses independently of the data (See Lemma [ in Appendix [C. for what is attainable by a dummy adversary). Theorem 5 ii) means that if an adversary recalls (2()) training samples with some probability, then it must also incorrectly guess the membership of (()) test samples with some non-negligible probability.
Next, we use the result of Theorem for Pler to show that while the output model W of any e-learner algorithm must memorize a significant fraction of the data (for some distribution) as asserted in Theorem 4 the auxiliary model OW (which is obtained through suitable stochastic projection and lossy compression), achieves comparable generalization error without memorizing the data!
Theorem 6. Consider the PL02 problem instance of Definition 4 with L = R =1 For every > 0 every Z C (1) and every learning algorithm A: 2n + R there exists another (compressed) algorithm A zn IRP, defined as (S.) & Δ A(S.)) = OW, where the projection matrix @ E B. DDxd, d = 500r log(n), is distributed according to some distribution Pe independent of (Sn, W), such that for any data distribution μ. the following conditions are met simultaneously:
i) the generalization error of the auxiliary model OW satisfies
EP w PiPT [gen(S,, W) - gen(Sn, =0
(8)
ii) if there exists adversary that by having access to both & and W (and hence OW) (m, q, E)
traces the data, then it must be that: a) m = o(n) or E 2 q. and b) for some a E (0.1) and no E N
an for every 2 no. then for any E (0, it holds that:
PP Eiem 2(OW, Zs,o, (4) 2 m') 2 (a - e)g. where m' (179fca) o(n) = 2(n).
Theorem 6 proved in Appendix G.2 holds for θ being stochastic and shared with the adversary. In essence, it asserts that for any algorithm A(5)= = W. one can construct a suitable projected quantized model A( = W from which no adversary would be able to trace the data, for any data distribution p.. is appealing contrast this result with that of [43 Theorem 4.5] the necessity of memorization. Consider the SCO instance problem with (I)) convex-Lipschitzz loss defined over the ball of radius one 43 Theorem 4.5] and let e-learner algorithm A with output model W and sample complexity ((s 5) (log(11/))
in IR considered in
with D = 2(n2 log(n/E)) be given. The result of [3 Theorem 4.5] states that there cxists a data distribution for which the algorithm A must memorize big fraction of the training data. Applied to this particular instance problem. Theorem 6 asserts that if random is chosen and shared with the adversary then the auxiliary model @W has the following guarantees: (i) for any data distribution, generalization error arbitrarily close to that of the original model W. At first glance, this may seem to contradict the necessity of memorization stated in 43 Theorem 4.5). It is important to note, however,
adversary can trace the data, and (ii) average over θ the associated

---

that the auxiliary algorithm does not satisfy the conditions required in 43 Theorem 4.5]: and, so, the latter does not upply to OW. particular, while 44 Theorem 4.5] requires the model to be bounded, in our construction for every w we have E [Ww] R w but Bw,e |ow]] increases roughly as d D
(see Lemma 2 in Appendix C.4.I. As discussed after Lemma this causes Wi ||| [*] to grow as ((n2)) ) when = 22nn (n) i... becomes arbitrarily large as n increases. Intuitively, this is what prevents an adversary from guessing correctly whether sample has (or not) been used for training, and which makes some key proof steps of Attias et al. fail when applied to the auxiliary model OW. These steps are discussed in detail in Appendix CC.42
A somewhat weaker version of Thcorem 0 which is stated in Theorem g in Appendix C.2 holds for the projection matrix & being deterministic. In sense, it provides stronger guarantce the generalization error of the auxiliary model, in that the closeness to the performance of the original model holds now for the given @ and not only in average over @ as in Theorem 6 However, this comes at the expense of the auxiliary algorithm being dependent on the data distribution. A consequence of this is that the result does preclude the existence of other distributions for which there would exist adversaries capable of tracing the data. Moreover, in Theorem / in Appendix C.3 we show that a similar result holds if one considers the closeness in terms of the population risk, instead of the generalization error.
Summarizing, neither of the results of Theorem 6 and Theorem g contradict those of 45 In essence, they assert that for any learning algorithm A one can find an alternate auxiliary algorithm via stochastic projection combined with lossy compression for which no adversary would be able to trace the data; and, yet, the found auxiliary algorithm has generalization error that is arbitrarily close to that of the original model. Appendix
C.3 extends this closeness to the population risk.
6 Implications and Concluding Remarks
Sample-compression schemes
Formally, learning algorithm is a sample compression scheme of size k E N if there exists pair of mappings (o, x)) such that for all samples S = (Zi,..,, Zn) of size n 2 k, the map e compresses the sample into length-k: sequence which the map uses to reconstruct the output of the algorithm, i... A(S) = (S).. Steinke and Zakynthinou [12] establish that if an algorithm An, is a sample- compression scheme (Ø) 1)) of size k, then it must be that the associated CMI is bounded from above as CMT(AA)) < & 1og(2n). The finding of [43 that, for certain SCO problem instances, every s-learner algo- rithm must have CMI that blows up with n (faster than n) was used therein to refute the existence of such compre-compressoon schemes for the studied SCO problems. The results of this paper may constitute a path to obtaining such schemes when the definition is extended to involve approximate reconstruction (in terms of induced generalization error) instead of the strict A...)) (.) = v(((()) of Littlesone and Warmuth [60]
Fingerprinting codes and privacy attacks
[T,, the authors study the problem of designing privacy attacks on mean estimators that expose a fraction of the training data. They show that a well-designed adversary can guess membership of the training samples from the output of every algorithm that estimates mean with high precision. Our results suggest that stochastic projection and lossy compression might be useful to construct differentially private codes that prevent such fingerprinting type attacks. For instance, while noise would naturally be one constituent of the recipe in this context, its injection in suitable smaller subspace of the summary statisties might be the key enabler of privacy guarantees in such contexts.
Concluding remarks
In this work, we revisit recent limitations identified in conditional mutual information -aaeiod----eeddeee generalization bounds. By incorporating stochastic projections and lossy compression mechanisms into the CMI frame- work, we derive bounds that remain informative stochastic convex optimization, thereby offering a new perspective the results in 4 rization phenomenon described in 4 by showing that for any algorithm and data distribution, one can construct alternative model that does not trace training data while achieving comparable generalization.
46
Our approach also provides a constructive resolution to the memo-
Like prior work on information- intooeation-theoretiee theoretic bounds, our analysis applies to stochastic convex optimization. A natural, open question is whether and how these results can be extended to more general learning settings. Another key direction is to translate our theoretical findings into actionable design principles for learning algorithms with controlled generalization and compressibility
10

---

Acknowledgments
The authors thank the anonymous reviewers for their many insightful comments and suggestions. Their feedback and the ensuing discussions led to the alternative variants of Theorem g (i.e., Theorem O and Theorem 9 and greatly shaped some the paper's discussions. Kimia Nadjahi would also like to thank Mahdi Haghifam for the helpful discussions.
References
[1] VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264, 1971.
[2] Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. Annals of Statistics, pages 1497-1537, 2005.
[3] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability
and uniform convergence. The Journal of Machine Learning Research, 1 1:2635-26777 2010.
[4] Umut Simşekli, Ozan Sener, George Deligiannidis, and Murat Erdogdu. Hausdorff dimension, heavy tails, and generalization in neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5138-5151, Curran Associates, Inc., 2020.
[5] Tolga Birdal, Aaron Lou, Leonidas Guibas, and Umut Şimgekli. Intrinsic dimension, persistent homology and generalization in neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2021.
[6] Liam Hodgkinson, Umut Simsekli, Rajiv Khanna, and Michael Mahoney. Generalization bounds us- ing lower tail exponents in stochastic optimizers. In International Conference on Machine Learning, pages 8774-8795, PMLR, 2022.
[7] Soon Hoe Lim, Yijun Wan. and Umut Şimşckli. Chaotic regularization and hcavy-tailed limits for deterministic gradient descent. arXiv preprint arXiv:2205. 2022.
[8] Yijun Wan, Mclih Barsbey, Abdellatif Zaidi, and Umut Şimşekli. Implicit compressibility of over- parametrized neural networks trained with hcavy-tailed SGD. In Proceedings of the 41st Interna- tional Conference on Machine Learning, pages 49845 2024.
[9] Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 Proceedings of Machine Learning Research, pages 1232-12400 Cadiz, Spain, 09-11 May 2016. PMLRR
[10] Aolin Xu and Maxim Raginsky. Information-theouee ing algorithms. Advances in Neural Information Processing Systems, 30, 2017.
analysis of generalization capability of learn-
[11] Yuheng Bu, Shaofeng Zou, and Venugopal V. Veeravalli. Tightening mutual information based bounds generalization eттor. IEFE Journal Selected Areas in Information Theory, I(I):
121-130, May 2020. ISSN 2641-87700.
[12] Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual in- formation. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 Proceedings of Machine Learning Research, pages 3437-3452.
PMLR, 09-12 Jul 2020.
[13] Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. Generalization enror bounds via R f-divergencess and maximal Icakage, 2020.
[14] Mahdi Haghifam, Gintare Karolina Dziugaite, Shay Moran, and Daniel M. Roy. Towards unified information-thhoretiic framework for generalization. In Thirty-Fifth Conference on Neural Informa- tion Processing Systems, 2021.
[15] Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M. Roy. theoretic generalization bounds for stochastic gradient descent, 2021.
Information-
[16] Gholamali Aminian, Yuheng Bu, Laura Toni, Miguel Rodrigues, and Gregory Wornell. An exact characterization the generalization error for the gibbs algorithm. Advances in Neural Information Processing Systems, 34:8 10--811811 18, 2021.

---

[17] Ruida Zhou, Chao Tian, and Tie Liu. Individually conditional individual mutual information bound on generalization enor. IEFE Transactions on Information Theory, 68(5):334433166 2022. doi:
10.1 109/TTT:2022.:144461
[18] Gábor Lugosi and Gergely Neu. Generalization bounds via convex analysis. In Conference on Learning Theory, pages 3524-3546. PMI.R, 2022.
[19] Saeed Masiha, Amin Gohari, and Mohammad Hossein Yassaee. f-divergences and their applications in lossy compression and bounding generalization envor. IEEF Transactions Information Theory, 2023.
[20] Hrayr Harutyunyan, Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan. Information -hthoorttccc generalization bounds for black-box learning algorithms. Advances in Neural Information Processing Systems, 34, 2021.
[21] Fredrik Hellström and Giuseppe Durisi. new family of generalization bounds using samplewise evaluated cmi. Advances in Neural Information Processing Systems, 35:10108-1012) 2022.
[22] Milad Scfidgaran, Romain Chor, and Abdellatif Zaidi. Rate-distortion thcoretic bounds on gener- alization error for distributed learning. Advances Neural Information Processing Systems, 19687-19702, 2022.
[23] Milad Sefidgaran and Abdellatif Zaidi. Data-dependent generalization bounds via variable-size com- pressibility. IEEE Transactions on Information Theory, 2024.
[24] David McAllester. Some PAC-Bayesian theorems. In Proceedings of the eleventh annual confer- ence on Computational learning theory, pages 230-234, 1998.
[25] David A McAllester. PAC-Bayesian model averaging. In Proceedings of the twelfth annual confer- ence on Computational learning theory, pages 164-170, 1999.
[26] Matthias Seeger. PAC-Bayesian generalisation error bounds for gaussian process classification. Jour- nal of machine learning research, 3(Oct):233-22)) 2002.
[27] John Langford and Rich Caruana. (not) bounding the true envr. Advances in Neural Information Processing Systems, 14, 2001.
[28] Olivier Catoni. PAC-Bayesian approach adaptive classification. preprint, 840, 2003.
[29] Andreas Maurer. A note the pac bayesian theorem. arXiv preprint cs/041 1s/0411199, 2004.
[30] Pascal Germain, Alexandre Lacasse, François Lavioletie, and Mario Marchand. PAC-Bayesian learn- ing of linear classifiers. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 353-360 2009.
[31] Ilya O Tolstikhin and Yevgeny Seldin. PAC- BaC- bemsttii inequality. Advances in Neu- ral Information Processing Systems, 26, 2013.
[32] Luc Bégin, Pascal Germain, François Laviolette, and -ean-Francis Roy. PAC-Bayesian bounds based the rényi divergence. In Artificial Intelligence and Statistics, pages 435 444. PMLR, 2016.
[33] Niklas Thiemann, Christian Igel, Olivier Wintenberger, and Yevgeny Seldin. A strongly quasiconvex PAC- A.C-Bayesian bound. In International Conference on Algorithmic Learning Theory, pages 466-492.
PMLR, 2017.
[34] Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:/703. 1008, 2017.
[35] Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-Bayesian approach to spectrally-normaliiee margin bounds for neural networks, 2018.
[36] Omar Rivasplata, Ilja Kuzborskij, Csaba Szepesvári, and John Shawe-Taylor. PAC-Baycs analysis beyond the usual bounds. Advances in Neural Information Processing Systems, 33: 13:16333-16845, 2020.
[37] Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. defense uniform convergence: Generalization via derandomization with an application to interpolating predictors. In International Conference on Machine Learning, pages 7263-7272. PMLR, 2020.
[38] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M. Roy. Information -hoorati generalization bounds for SGLD via deta-dependent estimates, 2020.
12

---

[39] Paul Viallard, Pascal Germain, Amaury Habrard, and Emilie Morvant. A general framework for the disintegration of PAC-Bayesiad bounds. arXiv preprint arXiv:2102.08644 2021.
[40] Racf Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, and Amir Ychudayoff. Learners that use little information. In Algorithmic Learning Theory, pages 25-55. PMLR, 2018.
[41] Ido Nachum, Jonathan Shafer, and Amir Ychudayoff. A direct sumn result for the information com- plexity of learning. In Conference On Learning Theory, pages 1547-1568. PMLR, 2018.
[42] Fredrik Hellström, Giuseppe Durisi, Benjamin Guedj, Maxim Raginsky, et al. Generalization bounds: Perspectives from information theory and PAC-Bayes. Foundations and Trends@ in Machine Learn- ing. 18(1):1-223, 2025.
[43] Idan Attias, Gintare Karolina Dziugaite, Mahdi Haghifam, Roi Livni, and Daniel M. Roy. Infor- mation complexity of stochastic convex optimization: Applications to generalization, memorization, and tracing. In Proceddngss of the 41 International Conference on Machine Learning, volume 235
of Proceedings of Machine Learning Research, pages 2035-2068. PMLR, 21-27 Jul 2024.
[44] Hassan Slaeez-Kolah Zeinab Golgooni, Shohreh Kasaei, and Mahdieh Soleymani. Conditioning and processing: Techniques to improve information--thoorte generalization bounds. Advances in Neural Information Processing Systems, 33:16457-16465 2020.
[45] Ziqiao Wang and Yongyi Mao. Tighter information- theoretic generalization bounds from supersam- ples. In Proceedings of the 40th International Conference on Machine Learning, pages 361 1-36137, 2023.
[46] Roi Livni. Information theoretic lower bounds for information theoretic upper bounds. In Proceed- ings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
[47] Mahdi Haghifam, Borja Rodríguez- Gálvez, Ragnar Thobaben, Mikael Skoglund, Daniel M Roy, and Gintare Karolina Dziugaite. Limitations of information- theoretic generalization bounds for gradient descent methods in stochastic convex optimization. In International Conference on Algorithmic Learning Theory, pages 663-706. PMLR, 2023.
[48] Ziqiao Wang and Yongyi Mao. Sample-conditionel hypothesis stability sharpens information- thcoretic generalization bounds. Advances in Neural Information Processing Systems, 36:49513- 49541, 2023.
[49] Kimia Nadjahi, Kristjan Greenewald, Rickard Brüel Gabrielsson, and Justin Solomon. Slicing mutual information generalization bounds for neural networks. In International Conference on Machine Learning, pages 37213-37253 PMLR, 2024.
[50] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex opti- mization. In COLT, volume 2, number 4, page 5, 2009.
[51] Yuheng Bu, Weihao Gao, Shaofeng Zou, and Venugopal Veeravalli. iioommation-heorretii under- standing of population risk improvement with model compression. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 34, pages 3300-3307, 2020.
[52] Milad Sefidgaram, Amin Gohari, Gael Richard, and Umut Simsckli. Rate-distortion theorctic gen- eralization bounds for stochastic learning algorithms. In Conference on Learning Theory, pages 4416-4463, PMLR, 2022.
[53] Peter Grunwald, Thomas Steinke, and Lydia Zakynthinou. PAC-Bayes. mac-bayes and conditional mutual information: Fast rale bounds that handle general ve classes. In Conference on Learning Theory, pages 2217-2247. PM 2021.
[54] Milad Sefidgaran, Abdellatif Zaidi, and Piotr Krasnowski. Minimum description length and general- ization guarantees for representation learning. In Thirty-seventh Conference Neural Information Processing Systems (NewrlPS), 2023.
[55] Borja Rodríguez-Gáávee Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. On random subset generalization error bounds and the stochastic gradient langevin dynamics algorithm. In 2020 IEEE Information Theory Workshop (ITW), pages 1-5. IEFF, 2021.
[56] Ruida Zhou, Chao Tian, and Tie Liu. Individually conditional individual mutual information bound on generalization error. IEFE Transactions on Information Theory, 68(5)333043316, 2022.
[57] William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space
26. Contemporary mathematics, 26:28, 1984.
13

---

[58]
Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar. When is memorization irrelevant training data necessary for high-accuracy learning? In Proceedings of the 53rd annual ACM SIGACT symposium theory of computing, pages 123-132, 2021.
[59]
Jonathan Scarlett and Volkan Cevher. An introductory guide to fano's inequality with applications in statistical estimation. arXiv preprint arXiv:1901.0055 100500050.........1 2019.
[60]
Nick Littlestone and Manfred Warmuth. Relating data compression and learnability. Citeseer, 1986.
[61]
Cynthia Dwork, Adam Smith, Thomas Strinke, Jonathan Ullman, and Salil Vadhan. Robust trace- ability from trace amounts. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 550,669,200 2015. doi: 10.1 N0.1109FFOCS.205..4
[62]
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes. Springer Science Business Media, 2013.
[63] Ankit Pensia, Varun Jog, and Po-Ling Loh, Generalization emoor bounds for noisy, iterative algo- rithms. 2018 IEEE International Symposium on Information Theory (ISIT), pages 546-550, 2018.
[64] Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. Sharpened generalization hounds based on conditional mutual information and application noisy, iterative algorithms. Advances in Neural Information Processing Systems, 33:9925-9935, 2020.
[65] Borja Rodríguez Gálvez, Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. On random sub- set generalization error bounds and the stochastic gradient langevin dynamics algorithm. CoRR, abs/2010. 10994, 2020.
[66] Hao Wang, Yizhe Huang, Rui Gao, and Flavio Calmon. Analyzing the generalization capability of SGLD using properties of gaussian channels. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 24222-24234. Curran Associates, Inc., 2021.
[67] Hao Wang, Rui Gao, and Flavio Calmon. Generalization bounds for noisy iterative algorithms using properties of additive noise channels. Journal of machine learning research, 24(26): 2023.
[68] Sejun Park, Umut Simsekli, and Murat Erdogdu. Generalization bounds for stochastic gradient descent via localized s-covers. Advances in Neural Information Processing Systems, 35:2790-2802, 2022.
[69] Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and Markov chains, 2018.
[70] Leo Kozachkov, Patrick M Wensing, and Jean-Jacques Slotine. Generalization in supervised learning through riemannian contraction. arXiv preprint arXiv:2201 20l.022200.66666, 2022.
[71] Allan Grønlund, Lior Kamma, and Kasper Green Larsen. Near-tight margin-bused generalization bounds for support vector machines. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3779-3788. PMLR, 13-18 Jul 2020.
[72] Jean Gallier. Discrete mathematics. Springer Science & Business Media, 2011.
[73] Robert G Gallager. Information theory and reliable communication, volume 588. Springer, 1968.
[74] Ziqiao Wang and Yongyi Mao. On the generalization of models trained with SGD: Information- theoretic bounds and implications, 2021.
14

---

NeurIPS Paper Checklist
Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We proved several theoretical results showing the effectiveness of the projection and quantization technique and discussed it in detail. In particular, we showed how this can be used resolve the recently raised concerns the Clormatioo-theoretii bounds.
Guidelines:
The answer NA means that the abstract and introduction do not include claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contri- butions made in the paper and important assumptions and limitations. A No or NA answer this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected generalize to other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We clearly stated the problem instances and classes for which we demonstrated that this approach results in good generalization bounds. We also stated all assumptions needed for each result.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to vi- olations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datascts or with a few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover lim- itations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in de- veloping norms that preserve the integrity of the community. Reviewers will specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
15

---

Question: For each theoretical result. does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: In this paper, we stated all results rigorously, along with the assumptions used and detailed proofs in the supplements. The proofs are rigorous with enough details provided for the reader follow.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the thcorems, formulas, and proofs in the paper should be numbered and cross- refereneed.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does paper fully disclose imental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
information needed reproduce main exper-
Answer: [NA]
Justification: Our work a theoretical paper with rigorously proven claims, and not involve any experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments. No answer this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided or not.
the contribution a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, may be nec- essary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., the case a large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
Depending on the contribution, reproducibility
While NcurIPS does not require relcasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe architecture clearly and fully.
(c) If the contribution is a new model (e.g., large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (c.g., with open-source datasct or instructions for how to construct the dataset).
(d) recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case
16

---

of closed-source models. it may be that access to the model is limited in some way (e.g., registered users), but should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
Our work does not involve any experiment.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (attpe://nnis..c/ppulll for more details.
guides/ https///oooduuuusssiiooooo.ooo
While encourage the release of code and data, understand that this might not be pos- sible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts reproduce all experimental results for the pro- posed method and basclines. If only a subsct of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code is permitted.
Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., ., data splits, hyperparame- tets, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our work does not involve any experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental ma- terial.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about statistical significance of experiments?
Answer: [NA]
Justification: Our work does not involve any experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, least for the experiments that support the main
claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for ample, train/test split, initialization, random drawing some parameter, or overall run with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, boolstrap, etc.)
The assumptions made should be given (c.g., Normally distributed crrors). It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error than state that they have a 96% CI, if hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For cach experiment, docs the paper provide sufficient information on the computer resources (type compute workers, memory, time of execution) needed reproduce the exper- iments?
Answer: [NA]
Justification:Our work does not involve any experiment.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required each the individual exper- imental runs well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does research conducted the paper conform, in every respect, with NeurIPS Code of Ethics
Answer:
[Yes]
Justification:
Our work is theoretical paper on learning theory and does not violate any code of cthics.
Guidelincs:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require devi- ation from the Code of Ethics.
The authors should make sure preserve anonymity (e.g.. if there is special consideration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts the work performed?
Answer: [NA]
Justification: Our work is theoretical paper on learning theory and does not have any direct negative socictal impact.
Guidelines:
The answer NA means that there is societal impact of the work performed.
the authors answer or No, they should explain why their work has no socictal impact or why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (c.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), pri- vacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, lct alone deployments. However, if there direct path any negative applications, the authors should point it out. For example, it is legitimate to point that improvement. in the quality of generative models could be used generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the techmology.
If there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
Our work does not involve any experiment.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with nec- essary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model implementing safety filters.
Datascts that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, we encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Our work does not involve any experiment.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi haperswithcode thcode. comooddd...c////////eeeeeee/teee datasets has curated licenses for some datascts. Their licensing guide can help determine the license datasct.
For existing datasets that are re-packuged, both original license and the license the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Are new assels introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: Our work does not involve any experiment or any new asset.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/coodemmoddll as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Our work is theoretical paper on learning theory.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material fine, but the main contribution of the paper involves human subjects, then much detail as possible should be included in main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should paid at least the minimum wage the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/revieww based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: Our work does not involve crowd sourcing nor any research with human subjects.
Guidelincs:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects rescarch. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code Ethics and guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is an important, original, non- standard component of the core methods this research? Note that if the LLM used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We have used LLMs for this work.
Guidelines:
The answer NA means that the core method development in this research does not involve
LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neur http://rpppppceooceeeeeeee/////p /ttp://hh/////////oooocccoo///// LLM) for what should or should not be described.
21

---

Appendices
The appendices are organized follows:
Appendix A we present some extensions Theorem 1 that are used in the subsequent sections.
The results of Section 4 have been extended wider family of generalized linear stochastic opti-
mization problems in Appendix B
Further results on memorization are presented in Appendix C In particular
In Appendix C.1
we discuss what values (m, q: {) can achieved by "dummy adversary".
In Appendix C.2
we consider the case where the projection matrix θ is fixed and shared with the
adversary.
we discuss how to provide guarantees on the closeness in terms of the popula- tion risk between the projected-quantized model to the original model.
In Appendix C.3
Appendix C.44. we provide technical lemmas used in main text on reconciliation of our results with those of [
The generalization error of subspace training algorithms is investigated in Appendix D In particular, in Appendix D.I] we develop generalization bounds the case where iterative optimization algorithms such SGD and SGLD are used for the optimization of the subspace training algorithms.
The proof of Theorem is presented in Appendix
In Appendix present the proofs of the results presented in Section and Appendix B regarding the
applications Theorem D to resolving recently raised limitations classic CMI bounds. In particular,
a general Jdhnson-Lindenstrane projection scheme [I, Cwn v) is introduced in Appendix F.I which is used in the following subsections, with different choices of (d, Cur, v),
Theorem proved in Appendix
Proposition proved Appendix
Theorem proved Appendix
F.4
and Lemma is proved in Appendix
F.5
Appendix G contains the proofs of the results in Section 5lndd Appendix C about the memorization. More precisely,
Theorem proved in Appendix G.I
Theorem proved Appendix
G.2
Lemma proved in Appendix G.3
Theorem proved in Appendix
0.4
Theorem proved in Appendix
G.5
Lemma is proved in Appendix G.6
and Lemma is proved in Appendix
G.7
Lastly, Appendix contains the proofs of the results of Appendix Dn the generalization error of subspace training algorithms when trained using SGD SGLD. More preciscly,
Lemma is proved in Appendix
Theorem 10 is proved in Appendix
Theorem 13 is proved in Appendix
and Lemma is proved Appendix H.4
A Extensions of Theorem
3 Theorem can be improved several ways, similar to those proposed in Here, state only the single-datum version of Theorem | which is used in Appendix followed by a remark about extending Thcorem I and its corollary to more general lossy compression algorithms. Denote
As mentioned in Section
20 53 54]
$ (p =S) (Zz.0 Za.).
22

---

Corollary 1. Consider the setup of Theorem 7 Then,
Aen(u,,) S inf inf Σ PwiaT w Pe vE(n]
Bpg Pe
(. te,
(9)
and
A) S inf inf 1 PWoTTW Pa
Σ Erg
PaPss
(S) (S.A)
ta
(10)
n
vE(n)
where the infima are over Pwier and Pe that satisfy the distortion criterion
E B. Po PeP
[gen(Sn, W) () -gen(S,, ew]e
(11)
and where
(MII((S,A4) 21 (A(S,,
CMI C (S, 2.S.J_..0 (A(Ss,
(A J:)
Ala, 0) EE w Tw
(e(Z),, eW) - ((2,,,
To derive inequality 9 first note that by equation 11 it sufficient to show that
gen A) inf inf Pe n
EpgPo
(2, (Š.
PiiOO
kE|m]
Next, using the linearity of the expectation,
write
E Eigen (Sn; W)]
Σ
Elgen Elgen([Zi) (Zi).W)
72
iE(n)
Σ
Eg Ez., F22.w(gg [gen( (Zi), w)]
(12)
iE[n]
Then applying Theorem for each of the terms Ez, w (gen(( (Zii,, W)] yields equation The inequality can can be achieved similarly, by considering
(S,, W)] - Σ Es w [ f (gen(g (()), W)]
n *E(m)
instead of equation 12
The results Theorem [ and, consequently, Corollary D are valid for a broader class of learning algo- rithms, A, and lossy compression algorithms, A, discussed in the remark below and shown in the proof of Theorem[]] inn Appendix
Remark 1. As shown Appendix El the bounds of Theorem ? and consequently Corollary D Thold if learning algorithm A is aware of the projection matrix O i.e., if A: 2" x R Dxd W takes both the dataset S and the projection matrix as input order to learn the model W. Moreover, the results of Theorem [ and Corollary D are valid if the quantization step also depend
S, θ and A(S, θ). In W. This setting trivially includes the case in which A: 2" + W and the quantization depends only on A(S,9). For the ease of the exposition. we found it better not state the result in its most general form.
this general case, W A(S,9) Å(e, S, A(S,
B Generalized linear stochastic optimization problems
In this section, show that our bound of Theorem I can be applied successfully to get useful bounds on the generalization error a family generalized linear stochastic optimization problems that wider than the ones considered previously in related prior art.
23

---

Definition 9 (Generalized linear stochastic optimization). Let L. B, R. R, and W = (D(R). Define the loss function ggt: W + as
lai w) = ((w, +))
where g: X 2 - R is L-Lipschitz with respect the first argument. &: 2 BD(B) and W R
some arbitrary function Denote this problem as P(D)
giso'
This class of problems is larger than the considered in 50 For instance, while the results of 50 require the L-Lipschitz function g(:s-) and the function r(-) to both convex to hold, our next thcorem applies to arbitrary L-Lipschitz functions g(:.)) and arbitrary functions r(.).
Theorem 7.
For every learning algorithm A: n +
W of the instance problem P(P) glau defined in
Definition 9 the generalization bound of Theorem 7 Dields
gen(u, A) O (
LRB V
The proof, stated in Appendix [.44 based on Theorem In order find proper stochastic projec- tion and quantization, we use the LinneonnLindenstrauss (JI.) dimensional reduction transformation in a space dimension Then, we apply lossy compression the projected model. Thanks to the com- bined
the disintegrated CMI can be bounded casily in the d-dimensional space. However, there are two main caveats using JL Lemma directly. First, one needs bound the term A6 (S, θ) (see equation 4). This is particularly difficult since the JL Lemma does not guarantee distance preservation the original space dimension /) after projecting back the quantized model. Second, bounding the distortion term is less easy than in Theorem 3 since using the Lipschitz prop- erty requires bounding the absolute value the difference hetween inner products the original and projected-quantin models. In essence, this is the reason why, by opposition to JL transformation for which suffices to take log(n), here one needs higher-dimensional projection space comparatively, with vn.
Theorem shows that no counter-example could be found which the bound Theorem does not vamish, even if one considers the bigger class of generalized lincar stochastic optimization problems of Definition in place of the SCO class problems [43 The convergence rate ((1/ /m) of Theorem is. however, optimal. A better rate, (1)/vи), seems to be achievable using Rademacher analysis and Talagrand's contraction lemma 62 Using a more refined analysis, the same rate might be possible to achieve using our Theorem ! More precisely, in the part of the current proof of Theorem that analyses the distortion term, we do not account for the discrepancy between the empirical measure of and the true distribution μu; and, instead, we consider worst-case scenario. finer analysis that takes such discrepancy into account should lead to a sharper expected concentration bound for the distortion term, and, so, a better rate.
C Further results on memorization
In this section, we provide further results on memorization. In Appendix "dummy" adversary can trace the data for some values of (m, g) In Appendix C.2 we study the case where the projection matrix θ is deterministic. In Appendix C.3 we provide another variant of Theorem which we can guarantee the closeness of the projected -uanttize model to the original model terms of population risk (instead of the generalization error considered in Theorem R). Finally, in Appendix C.4 we present some technical lemmas used in the discussions Section [ on the relation our results with those established in 43
C.I wc show that even a
C.1 Dummy adversary
In this section, we show that certain values of (m,, g, are attainable "dummy" adversary who makes guesses without even looking at the given data sample.
Lemma 1. Given a learning algorithm An: n - W. there exists an adversary that (m, 9, -trrae the
data for some E [0,m] and q [0, 1] one of the following conditions holds: i) & 2 q. ti) there
exists C [0, 1 n [0, 1) such that / 1-a 1
2n log
(1-0//1-00)
< I.
24

---

This lemma, proved in Appendix G.3 trace the data several cases: when f is small, when q is large, or when & is small and q is large, provided that m = (n)).
implies in particular that even a dummy adversary can (m, 9, E)-
C.2 Deterministic projection
In this section, wc show that in Theorem 6 can allow @ to be deterministic. However, this comes the cost of being specific to a given data distribution.
Theorem 8. Consider the PeDd problem instance of Definition 4 with L = R = 1. For every r < 1, every 2 C (1()), every data distribution μs, and every learning algorithm A. there exist projection matrix OE R Dxd with d = [n= 2r '1, Markov Kernel P Wije w and compression algorithm Ag: z" 4 R",
defined as (b(ss)) 2 λ TOeTTAC A(S.)) = W, such that the following conditions are met simultaneossly
the generalization error of the auxiliary model OW satisfies
EP... FwieTw [gen(S., W) gen(S,,,, (W)) =0
(13)
where the expectation is taken over (Sn, W, W) Pss.,w Wwrssw.
ii if there exists adversary that by having access to both O and W (and hence OW) (m, q, q)
traces the data, then must be that: a) m = o(n) or E 2 q. and b) if. for some a E (0, and no E N P. (ie(m) Q(OW, Z., (1) 2 m²) z (a c)q where m' = (1/oicaa)n )n- o(n) = 2(n).
an for every 2 no. then for any
(0, it holds that:
As shown in the proof in Appendix G.4 the constraint on the difference generalization error can be re- placed with one with a faster decay with n, namely
Eps.. Tw geen(S.. W) gen(S... -
for some C [R] and d = 500r log(n). Also, if n = N(e, 6), then m. m' = 52 (1/e2), which means that any adversary who (m, 9: tracces the training data deemed to misclassify any arbitrary big part of the test samples.
For the proof of Theorem we first upply the projectionnqqumiizztionn approach of Theorem S Then, for a proper θ that satisfies the distortion criterion of equation 13 and for which the CMI is o(2) we apply Theorem 8 Note two important differences with Theorem B First, because one now deals with absolute value of the average difference of generalization errors one also needs to lower bound the average
distortion. Also, for > 1/2 a faster convergence rate of On ") is required. This renders the analysis
trickier and requires projection on space of dimension n2 2r
C.3 Guarantees on the population risk
In this section, we demonstrate that the closeness guarantec of the projectedl-quaniized model and the original model can also be provided in terms population risk.
Theorem 9. Consider the p(D) problem instance of Definition 1= R= 1. For every r < 1/2, ev- ery 2 (1),), every data distribution μ. and every learning algorithm A. there exist a projection matrix E Dxd with d = [n²"), Markov Kernel Pw w and compression algorithm Ab: : 2" + R", defined as (S,))) 2 Ā(e T A(S.)) W, such that the following conditions are met simultaneously:
the generalization error of the auxiliary model OW satisfies
EPs.. w P T w [C(W) - [(eW))]]]] O (n
where the expectation is taken over (Sn, W, W) Ps.., S......
ii if there exists adversary that by having access to both & and W (and hence OW) (m, q, E traces the data, then it must be that: a) Either m = o(n) or E 2 g, and b) if m = Q()) then there exists m' 2(1) and q' E (0, 1] such that for sufficiently large it holds that
P (Eie(n) QOOW, (4) 2 m') 2g
25

---

This result is proved in Appendix G.5 Furthermore, similarly to Theorem 8 the constraint on the differ- ence of population risks can replaced with one with a faster decay with n, namely
18 Ps, w (E(W) [(()) o (n=*).
(14)
for some [R] and d 500r log(n).
C.4 Reconciliation with results of Attias et al. 2024
this section, we provide the technical lemma showing that the norm two of the projected-quantized model, used in our results, is unbounded. Furthermore, we discuss in detail the steps of the proofs in 43 where this bounded assumption needed.
C.4.1 Uboundedness of the norm two of the projected-quantize model
In this section, for the pogjecedd-quntizzn algorithm eW. used in Theorem and Theorem 6 show that Ew.e ||ow]] blows-up with when D/d grows with n. This lemma is proved Appendix G.6
Lemma 2. Consider the JL(d, Cw, v) transformation described in Appendix F1 with some d C N Ow E c1..v5%1 and (0, 1]. Then, for every W.
Ba.v, |
D + d+1
||
D d DdD
| |w|| -0.1d(c (dd(c(-1) -1)²
d
d3
D d
Consider |||||| and let D n² log(n/{) considered in 43 used in corresponds to notation /) in this paper.
Theorem 4.5). We note that the notation
Then, considering the constructions used for Theorem and Theorem 6 we have 1.1 and 0.4. Moreover, is chosen either as
500r log(n),
d = n 2r-1 <L
Using Lemma 2 with these choices give
Fe ||o01 27 = 52 (n²)
and
||wi|11 (n= 22 log(n)) log(n)).
Ea,v,
|wwl? grows least as fast as 12(22))
respectively, Hence, in both cases Ee.v.
C.4.2 Details of needed boundedness assumption in Attias et al.
As discussed before, 43 Theorem 4. and 43 Theorem 4.5] require the model to be bounded. However, shown in the previous section, this assumption does not hold for the projected-quanteee algorithm θWf when D/ p/d and d grow with n. In this section, we discuss preciscly where the bounded model assumption necessary in the proofs of the impossibility results of
Proof of 43 Theorem 4.1] and recall analysis in the proof of 443 Theorem 4.5), part, relies established upper bound Ω ((1/s") on the term E[[Z]] where the set I is the subset of columns supersample such that one of the samples has a large correlation with the output of the algorithm and the other one has small correlation with the output of the algorithm.
26

---

To establish this upper bound, in the last inequality of Page 19 of 43 it is assumed that the norm model is bounded. Now, when working with the model OW, the right-hand side of this inequality needs to he replaced by the D) dddependent quantity 8s 2 d + 2 12(n2) when D = (2(=)) and d o(n). This has to be contrasted with the actual bound 8="n" + 2 when the bounded model's norm assumption holds. Thus, one important issuc is that, this quantity now being non-negligible, the LHS of (9) no longer be lower- bounded by the RHS of the inequality (9).
Another step. used for establishing the upper bound on E[ is the step that upper bounds (EE)) (1/nn², for the event defined top of Page 19 of [43). In this again, in the set of equations before equation (12), it is assumed that the norm of the model is bounded to derive ||A0'|| < 144" However, since norm two of eW is (2(m)), ), then these steps are ot valid and hence the analysis does not give P ((E) (1/n2² anymore.
Another proof step of 43 Theorem 4. used also in the soundness analysis in the proof of 43 Theorem 4.5], relics on upper bounds for the error event Go defined on [43 Page 18] as the probability that the correlation between the model output and the held-out samples is significant.
These upper bounds, [43 Equations 11] in the proof [43] Theorem 4.1] and also on [4] 29] in the soundness analysis in the proof of [43 Theorem 4.5], are based
application of 44
Lemma 88 and by assuming that the norm two of the model is bounded by 1. These steps again
fail if the norm two of the model grows (2DDdd) ()
D Random subspace training algorithms
The generalization bounds Theorem and Corollary I apply any arbitrary learning algorithm. In this section, we show how this bound can be applied to random subspace training algorithms. Then, we consider the case where they are trained using an iterative optimization algorithm.
Let St(d, D) = (O c Pxd T [a] be the Stiefel manifold, equipped with the uniform distri- bution Pg. Moreover, for given O C R Pxd let We,a _ (w R 3w' Rd s.t. Ow'). Random subspace training algorithms first randomly generate an instance of e according to Pe, which kept frozen during training. A random subspace training algorithm (()) z IR We,a a learning algorithm that takes the dataset S and the projection matrix θ as input, and chooses model W E Wa, at by choosing W Rd.
In other words, (S, θ) ew', alternatively, since θe la W' -e A θ). Hence, using Corollary [ and by noting Remark D we can obtain the following result. Corollary 2. Consider random subspace training algorithm and loss function ł: Z x RD -> [0, C1. Then, for any R and the quantization set W Rdd have
gen(H,, 5 inf
EpoPa
Σ sE(m)
(2CMI9(S.V))
+c.
Paiwre.s
n
and
C Σ
gen(u,, A (1))
< inf Parwrr.s
EPoPyPo
v 2CMI (8, w) t
(15)
kE[m)
where W E W and the infinum are over all Markov kernels Pwij'rs, that satisfies the following distortion criterion:
Ep, EpsPoPwiise P www.s. ss. gen(S,, ow") gen(S, )w?e s.
(16)
This bound is used in following subsection, when SGD or SGLD are used for random subspace training. Note that the above bound includes the case of W W' and 0, which results in
the lossless bounds gen(u, (d)) S EppPo Po Eiemn / /2CMI wi) and A(n(),,A(d)) S C
EppPo [ EVEN / (,,
The results presented in the next section are extensions and improvements in some aspects, upon previous work on bounding the generalization error of SGLD without projection 38 63 67).
27

---

D.1 Generalization bounds for SGD and SGLD Algorithms
this section, we consider subspace training algorithms that are trained using an iterative optimization al- gorithm such us mini-batch Stochastic Gradient Descent (SGD) or Stochastic Gradient Langevin dynamics (SGLD).
Let b N bet the mini-batchi size, and let
Ve (ie.1.....,2.))) de,b);
be the sample indices chosen at time t E [T], ie. given S E gxx and J = (J,,...,Jn.) the chosen indices at time are Sv..a _ Sv.Jv. A Lin Ziennde
Furthermore, denote
R(V,, W) &
Σ iEV
(( W).
We also the notation V (V1,..., VT) and recall that J-; _ [n]]/i)>
The considered noisy iterative optimization algorithm consists of the following steps:
(Initializatiin)) Sample Pxd and set the initial model's parameters to Wo OW, where
W c _
(Iterate) For t [T], apply the update rule
W Proj [Wi ne R(V,, OW(_) + t
(17)
with 7js >> (the learning rate), ar 2 0 (the variance of Gaussian noise), and E ~ (Oaa, La) (the isotropic Gaussian noise). Here. the projection is optional operator often used keep the norm the model parameters bounded.
(Oudput) Return the final hypothesis WT = OWW
Note that here, we train on subspace of dimension d < D defined by (randomly picked at initialization and fixed during training). Note also that when 0 for all C [T], this algorithm reduces the mini- batch SGD (with projection).
D.1.1 Mutual information of mixture of two Gaussians and the component
To state our results, we start by defining two useful functions. Suppose that
x= (1 (1- JYYi + JY2,
where (J, Y1, Y2) are independent real-valued random variables defined follows: J ~ Bern(p), Y1 No,, 1), and Y2 NN(a, 1), for some R. Then, it casy to show that ((x:)) = fa, p), where the
function f: R j0, 1] + [0, log 2] is defined a
S(..p) p) A (c)) log( v 2ne)) = (x.,(()) [log(gn.((x)) log(v
(18)
Here, :a.p: Rx 00, + R, is defined as mixture of two scalar Gaussian distributions with probabilitics p and
pt
(x. A
pe pe- + +(1 p)e
(o-o)²
(19)
22T
The following lemma, proved in the supplements, establishes some properties of the function f(a, p)- Lemma 3. i) For every p [0, 1}, f(0,
ii) For every p E [0, 1]. f(a.p) f(-a,p) and f(a p)
is an strictly increasing function of a in the range [0, co). iii) lima- (a,p) = log(2)ho(p). iv) For every R. f(, f(a, - p) and for # 0, f(a, p) strictly increasing with respect to p the range [0, 1/2].
All logarithms considered to have the base of e.
28

---

D.1.2 Lossless generalization bound
We start by stating our bound in its simplest form.
Theorem 10. Suppose that [0, C). Then, the generalization ertor of random subspace training algorithum, optimized using iterations defined in 17 is upper bounded as
CV2 ic(n]
[ ((
gen(u,,A
Σ
E V.
Σ 4:
Aess Pt.
bos
where
A - | w/ (W 1, 2..) Vw (oW; 1, 21,1,
Pe. - P J, = V. W 1.
(20)
This result is proved in Appendix H.2
Pt.i, is increasing function with respect to 2. Ar. and a decreasing function with respect to |pt.: - 1/2]. As t increases, the learning algorithm "memorizes" of the dataset; therefore, [pt, 1/2 increases and thus these terms decrease. Furthermore, the learning rate decreases, causing this term to decrease more.
In the bound of equation 20 the term
Note that by Lemma 3 f(-P)) is maximized for 1. Hence, simpler upper bound from Theorem 10 can be achieved by replacing Pt, by
D.1.3 Lossy generalization bound
The bound of Theorem 10 has clear shortcoming: whenever is very small, the bound becomes loose. In particular, for SGD where oz = O, the bound becomes vacuous. In this section, to overcome this issue, consider lossy version of the above bound. While the lossy bound be stated without any further assumptions, for a more concrete bound, we make the following assumptions.
Assumption 11 (Lipschitzness). The loss function is Lipsshhitz. i.e. for any w/, wh Bd any E Z, and any θ E St(d, D), we have | (z, Qwi) (z, Owb) I Sllwi - wLll.
Note that since T o la, then ||wq wi2l = ||Ow] Ow1ll-
A ssumption 12 (Contractivity). There exists some a E IR aRt such that for any wh, wh E W', ZE 2, and θ E St(d, D), we have
(ww L(z, Qw1)) - (w/ (x, S a [|w w/
Whenever a < 1, we say the projected SGLD is a-contractive.
Similar assumptions have been used in previous works, such as [68] In fact, the contractivity property of SGD has been thcorctically proved under certain conditions, such as when the loss function smooth and strongly convex (78.
addition being sensitive cases where d; for the "forgetting" effect the iterative optimization algorithms: the information obtained by Wy about Jr in the initial iterations will eventually fade out, T increases. To account for this effect, similar to [66] 67), we assume that W = ( for some R C R+.
lh is very small, the bound Theorem 10 does not account
Theorem 13. Suppose that ( C), W (D)R). for some R E R+, and Assumptions /1 and 12 hold with constants & E R- and a S 1, respectively. Then, for any set of (vehter, such that V E R.,, the generalization error of random subspace training algorithm, optimized using iterations defined in
17 is upper bounded as
gen (
C
Σ Bs,.
Ae, Ae.Ep...iiu t: ieVs
Σ
{
d.. Dr.s bōt
Ttt
2 2/22T
Σ T tE[T]
(21)
In this setup. for w E W", Proj (w') = w' and otherwise Proj (w') R w' Tw
29

---

where
Á & /i/ (W (,,0 V. ( Za.1)
Dr, P Jj = V. V.J.;,
- Vo8 + +Vg
R + n
at 1 20
Öt
A
dr:
re(t+1:T|:: ig.,
where We are random variables that satisfy
W. w/ S Σ ur
rEid]
foret (No,,, Ia), which auxiliary additional noise, independent of all other random variables, and I exp(-y² /2)dy is the Gaussian complementary cumulative distribution function
where (xx) 2 5e
V2
(CCDF).
This theorem is proved in Appendix H.3 Here, we discuss some remarks.
First, the "gained" information from the initial iterations fades T oc, when q 1 (note that always a: S 1).
Second, we note that, unlike in Theorem 10 where Pi, depends on all past iterations in which sample i used, this theorem, pr,; depends only on immediate past iteration. can shown that similar result can be achieved for Theorem 13 ie., allowing Pt, depend all past iterations, at the expense of replacing all {ge} ht by 1.
Third, it can be observed that if At Pr.i. that can be adjusted at the expense of replacing all {4: t by as explained above. Furthermore, by increasing the second term in equation 21 i.e. the "distortion" term, increases; but the first "rate" term decrcases since f Vo?+u? Pr, decrcases. Therefore, general, the lossy bound can outperform
[T]: 14 = O, we recover Theorem 10 except for the definition of
The
the lossless bound. In particular, for SGD, i.e., when a; = O, the lossless bound and previous works (for the case of no projection) 388 63 become vacuous, while the lossy bound does not.
Lastly, achieve this bound, we considered a sequence of parallel "perturbed" iterations. each of these auxiliary iterations, we introduced an additional independent noise V:s', where & ~ (0,,, Iz). It can be seen that for the contractive SGD/SGL.D DD the effect of added perturbation as T - Therefore, once again, it can be seen that the effect of the increase in mutual information from the initial iterations eventually fades.
initial iterations vanishes
E Proof of Theorem
prove the theorem its most general form stated in Remark [ This means that we assume that the learning algorithm A is also aware of the projection matrix θ, i.e., A: z" x IR Dxd + W takes both dataset S,, and the projection matrix & as input learn W. Moreover, we allow Sn, A(, 9)). We
quantization
step depend S, O, and A(Sn, θ). In this general case, W Á(S, θ) denote this general compressed algorithm by Pw]s.,W.e. Note that Pwre w a special case of this more general setup.
Fix some e R and the quantization set W. Consider any Markov kernel Pw]ss, we and Pe that satisfy the following distortion criterion:
Eps, Po Po gen(S... W) gen(Sn, }mn) Sc. Using this condition, it sufficient to show that
(S, CMI
gen (4, A) EEss, Po P ww
[gen(S,,, [w]] SEP&Po
30

---

where
Ae (5, 0) -B Pwis s. [1 E sc(n) (e(Z),0, @W) ((Z,,,
Denote the marginal distribution of (Sn, θ W) under Ps., Pa.PPPWae W.W,s. by P3 e, and conditional distribution W given (Sn; () by Pw: e Hence, Ps.... Ps,, Pe Wis.. P and gen A) =E Pen Po Piriso
gen(Sn, θwe
R(SJ OW) - R(SS,,
PaPP Piris
It is hence sufficient to show that for any S and O
2 ($. θ) Epy R(SS,, - Re(S,, (wn SV
CMI (S.
n
Denote Piris Ep pw and P.Wes & PsPwis & Pys.o. Pw
sis s, the condi-
tional distributions of (J, W) given (S, O). Note that the marginal distribution of under Pj, e is Ps. iee.
E [Pas....w]] P3.
Now, fix some
* that will be determined later. have
Bp B
- RR,,,, 9n!]
1 log Eps ((((S)e R(S),8W1))
DKL (Ps (P +
(PJ (P P2) + X log [Ep, e (
A DRt
1 DRL (Pss.Wool Ps) + 1 Σ
P - ((2,,02,,0
2n
VE[N]
where (a) follows from Donsker- Varadhan's inequality and (b) by the inequality { + +e")= S 1t
Hence,
R(SS, ((5)),, - (w))
Ep, P
-BPwRo Paaa
Ri(S)- θw R(,,, owi)
< DEL (Pris,o Pl
1
1 (e(Zi,0, Qw e(Zi, 01Tee
E.we.e
2n
VEIn
1
+ Adh (8,
X DEL (PW Pas. Ps PsPiis,))
2n
(S,
DKL. |I [P3 +
2n
CMI (S | AAla (S, O)
2n
2AP (S, 9)MMI (S.AA)
n
where the last step is followed by letting
A A
ACc. (8,0)
This completes the proof.
31

---

F
Proofs of Section 4 and Appendix B: Application to raised limitations of CMI bounds
For the proofs Section and Appendix B we always consider the normalized sctup, i.e., = 1, = (for Theorem 3) Le I (for Proposition D. and B (for Theorem 7p. The proof applies for arbitrary values of (R, L, Le, B). by simply scaling the constants.
All proofs are based on Theorem D with particular class of choices of Pe and WwieT>> called the [, v 1//5// and E (0, 1]. described in Appendix F. For a given II,(d, Cw, v), we then use Theorem for some suitable E IR:
choices from the scheme [L(dd, Cw; v) for some N, Cwe
20 (S,0), θ) CMI te.
gen(M,, SI
(22)
Recall that the term 16م (S, θ) is defined as
A (S, θ) EE W Pare a
Σ
(e(Z θW) E(2,,,, ((11))
ic|m
and the choices of Pe and P Wwe should satisfy the distortion criterion
BP... w Po Paje Tw
genn(Sn, W) - gen ew]] c.
(23)
For brevity, we oflen the notation
AWW, θW; S..) = gen S.. W) gem(Sn; oW).
Furthermore, denote the D-dimensional ball of radius E R++ and center w P by (D v). Op, for simplicity write (p v) = (D(v), where Op designates the all-zero vector in R.
JohnsonnLLnndenttruuss projection scheme
Fix some constant Cwo E 1, [ 4
and v E (0, 1]. Let d C N' and @ be a matrix of size D x d whose elements are i.i.d. samples from (0, 1/d). For given O and W =A(S,), in the scheme JL.dd Gws v),
let
- W, if I Gw: U
(24)
Oa:
otherwise.
Let V. he random variable that takes value uniformly over Ba (v). Let W E W = Ba(cw + v) be defined
= U V..
(25)
This means that W a random variable that takes value uniformly over Ba (U,
Unif (Ba (U,+)).
other words, we define W as a quantization of W' = Tww W obtained as follows: [|@TW]] < Cas then W uniformly sampled from Ba (OTW, W, v): quantization has been previously used in [2 to establish generalization bound for the distributed SVM learning algorithm.
otherwise, W uniformly sampled from Ba (v). Such
Disintegrated CMI bound: be upper bounded as
The disintegrated CMI bound CMI (M, in the scheme [L cw., v)
CMI AMI A)
8.e (W) 1 (W]J) =h 8.
(a)
2 8.9 (.8 ) (
5.0 (W) ) h(we w)
(c)
< log (Volume (Ba(cw + v))) - log (Volume (Ba(r)))
(Cw +
=d dog
(26)
32

---

where
h 8.0 (W) is the differential entropy of W Puis, h 000 ( (J) = Ey (wr)) and
h 1 (W) is the differential entropy of W Pwisse.J
(a) follows from the fact that conditioning does not increase the entropy,
(b) yields due to Markov chain W T W (S.e,J,W) W).
and (c) holds since i) |[W]| S + by construction and hence h (W)) is upper bounded by the differential entropy random variable taking value uniformly over Ba + v), and ii) since given θ W. W chosen uniformly over a d-dimensional ball either around 02 or θ W, depending on ||eT Wi].
F.2 Proof of Theorem
As explained in Appendix F we consider the case I= R 1, and use Theorem | using the Jl.(d, Cwe, v)
transformation described in Appendix F.1, with some E N+ Cu E [1, /5/4// and v E (0, 1]. To do
so, we start by bounding CMI AS, the distortion equation 23 and Eg, ( (S, 0)].
Bound on the disintegrated CMI: It is shown in equation
26 that
CMI =d
Cw
(27)
Bound on the distortion:
Next, we bound the distortion term. By definition, and using the linearity of expectation, we obtain
AWW, WWW.WW:S,, gen(Sn. W) gen(Sn. @W)
EZzzpl (W, 2)
Σ (W, Z.) + Ez~z Z)]
1
Σ ew Z,)
n
7
Zz) + (OW Ez- -(W,Ez-nl Σ
Σ Zi)
i=1
i=1
-WW + (W,00 %)
(28)
where 2 A EZ) 1 Σn Zi.
Additionally, since for any (x, _ x
x, T y)l TT) = (2, then
Ew.,.ws,, | (W. ow: S.)l = =Bw,e (-W, Z) + (W.e" Σ>
(W,
=Ew.e.w.s. (-0 (0 T w,e T2) ( e TT
=Bw,,, (W θ wwe' Wze]
Let & be the event that ||e W|| > Cu and denote by E the complementary event of E. By the law of total expectation,
TT www.e.ss..ff (AWW, N.: ) = B( - θ @w,eeT2, 2) EJP(E) + El(W e W. e 2) PE)))
(29)
By definition of W. EW- under E, E[W] = θ W otherwise. Therefore, equation 29 be simplified as
E W.e.w.s,IWW...o S..)] E| (0 W. 0 2) (JI((E)
=E W. θ 2)
E|ll@ w @| (E))
(30)
< E // wir" [[ "
(31)
where equation 30 follows from Cauchy-Schward inequality, and equation 31 results from Hölder's in- cquality.
Now, we bound each of the terms Ell[oT 2113), E[[[@ W|l+], and [1[1 {8)].
33

---

Since the elements of Q E R are i..d. from (00 1/d). then for any fixed vector x IR each entry of /ile is independent random variable distributed according (0 1). [
Hence, Va v
| is chi-squared random variable with d-degrees of freedom, and
have
B B d.
This concludes that for any 2,
B o =|l3] ||=11
Moreover, since Vz is a chi- distribution with dl-degrees of freedom, we have that
B B = [V] + [V= E[V=])* = dd 2d.
Hence for every w E W
1
vde T
Ee
|
w||
Es
d²
10
||
v.2
d2
2
||0||
By 77 Lemma 9], for any (D(1), if E [1, 1/A),
I(E) < e 0.21d(c. -1
(32)
More precisely by [7 Lemma 9] we have for any 1 C [0, 1/4) and any C Ba(1),
(10 w|| - ||m|| > { w
0.21
We note that this incquality is "single-sided" tail bound version of [7 Lemma 9] (while therein stated as "double-sided sidedd tail bound). This explains why RHS of the inequality in [7] Lemma 9] is 2c 0.21dt" while here have c 0.21dt"
Next, note that (t + w|| s (t + 1), hence
PP (1e] will - ||l|| > t|]w=l?)) = PP (10TT w0l > (t+ 1)]()(1))) > (10 wol2
(10Tw]l > +++)
Thus, by letting 2 for ou [1, 5544, have
P (loe
w|ll cw < 0.21dt -021d(((-
Combining the above upper bounds on e T 2
E W and ([1(E)) we obtain,
E Ew.,,w.s, |A(W, < |||
e T w|r 1/4 -
< |[|| |[]
1|| [
Ew
+
2
2
W|||
111 (1+
2
1/4 m2n
(33)
where equation
33 follows from assuming that W S (n()).
34

---

It remains then to upper bound 2| By definition of 2 and the linearity of expectation, we have
" E [||B 2| Σ
|[|12|
[1]
i=1
Elll
Σ [B|Z] zz)ll
Σ (B 21) )
E
(E[2) 23)
72
i=1
E
Σ
E 2 2.) (B|2) T 23)
2
E
E Z Z.)
T
(B 2.) + Σ
B[|Z]
(B Zz)
1=1
1/3
E
|E| Zil²
Σ
Cov(Zi, 2z))
n
ifi
|||
Zell?
(34)
4
(35)
n
where equation 34 results from Cov( (Zi, 2,) for i j since Zi, Zn are independent, and equation (1) (thus, for any [E[2] Z:|l S 2).
35
follows from 2
Combining equation 33 and equation 34
conclude that the distortion is bounded by
W. w.e.wsss, (AW,,W;; < Vn (1 (1+ 2 d
1/4
221 22
(36)
Bound on Eg (S, (S, O)]: We have
Epg Ae (S, θ)] = PaP PaP
(((2,,0, (W)))
71
iE|n]
WWOT (3i,0 -Zaaa)
=I0 Ep Po Pwie
72
cc|m
T (Zi,0 1,,i)1?11ii111??
Ep PoP PwreT
72
ic(n]
2 (cw + v) 2)
|10T (Z.,0 (2.,0 - 20,1)1
sE(m)
(c) 2 24cc v
(37)
where (a) follows by Cauchy-Schward inequality, (b) is derived since || (cw + v). and (c) since for an independent random variable distributed according (0 )) and
any fixed z, each entry of T hence
Eg TT=z
22
|==|²² < 4,
since 2 Zi,1| 2.
35

---

Generalization Bound: Now, let
2 Vn
(1+
1
2
1/4
e
221 d(c -1)
Inequality 36 shows that the above choices of Pe and PWieTw (according to the scheme JL,(d, Cw, D)) satisfy the distortion criterion equation 23 Hence, equation 22 gives
gen(u, A) EBpgPu
2A (S. θ) (S.A
+
2 Vn
(1
1
2
1/4
e
9.23
-1)
d(
1))
(a)
2AP (S, ②) llg
Car +
2
2
1/4
22 172
E Ep Po
1
c
vn
WV A3
2d Brggg Po
Ae 65)
Cw +V) v)
( + 2 1/4
4 221 d(c
log
+
n
vn
d
8d Cv + v)² Cw + V
1+ 2
1/4
0:21 d d(c, 1)²
log
n where (a) is achieved using equation 27
Vn
d
(b) by Jensen incquality and due to the concavity of the function
Vir and (c) is derived using equation 37
The proof is completed by letting
d 11 Cw ===,, == 0.4.
F.3 Proof of Proposition
1
As explained in Appendix
it sufficient to consider the case Lec = R 1. We have gen(p, A) =Eps..w w (R(W) [W)]
EP [Ez W)] (sc W)]
cc|m
(a)
E Ps 1Bz-pl- (W, 2 + (W, Z
(6)
EP w [Ez=plo(22,W)) (.(
:E(n]
(c) 8
Vn'
where (a) by definition of (z, w) = (w, 2) + 2 ||m||| 2 by Definition 6 (b) holds since by Definition 4
we have La(2, w) -(w,, 2). and (c) follows by Theorem 3
F.4 Proof of Theorem
As explained Appendix we consider the case = B 1. First, note that similar to the proof of Proposition the generalization error does not change, if we consider the loss function fgim w) A g (ww, (x))) 2) g (0, 2) instead of fgr(z, w) = g ((w, d(z)) 2) + r(w). More precisely, gen(p, A) = -EPs.. [R(W) - (W))
Σ
Eps... (Z W)] (Z, W)]
iE(n)
Ep [Zz (W, ((Z))(()))))))))))))) .2) r(W)] 9 ((W, ((2)) 2,) r(W)
ie(n]
EPS,. w Ez~plg (WW, (W, ((Z)) Z)] g (W, ((z)) Za)
[
36

---

[a)
Epsn.
Ez ((W,((WW)))))))))))))))))))))))) 2) - g 2) - (WW (())) 2,) (0,
π iE(x)
EP
(2, W]] fglm (Z,, W)],
ic(x)
where (a) follows since Ez~N (0( 2)] = Ez,~, (0,, 2:)].
Hence, for the rest of the proof, we consider the generalization with respect the following loss function:
lytm w) _ g ((w, ((z)) 2) - (0,
Note that due the Lipschitzness of the function g(++) with respect its first argument, for every 2 E Z and w E W, we have
getn (z, w)) = lg ((we, (z)) 2) - 9 (0, - (w,, x(x))
(38)
Furthermore since ||m|l [[{()]] < using Cauchy-Schwarz Schwarz incquality yields
Kett (z, u²) (=),)) S 1.
Now, we proceed to establish a generalization bound with respect to the loss function fgrm (2, w). use Theorem | with the [Ld cw. v/) transformation described in Appendix F.11 for some d E N Cw E
(2. We
I. 15/4 and v E (0, 1]. To do so, We start by bounding (M, A), the distortion equation 23 and Es,a/Ae (S, e)..
Bound on the disintegrated CMI: is shown in equation 26 that
C (S. =Id log Cu +
Bound on the distortion: Next, we bound the distortion term.
AWW, oW; S.) =gen( Sm, W) gen(Sn; OW)
= =EZzz Igtn (7, W)] Σ
1
gl 14,, W) - Bzzmulfamm (2
1
Σ
ggm (Zi, θW
n i=1
1=1
=1Ezzn (g .z)
!
Σ
i=1
1zzz [9 ((BW,0(2)) :2)]
1 Σg 9 ((BW, .25)
i=1
<Eznn ((W.&(Z)) .2) > ((6)).0(2)) ]
(((W, 2.) -9 ((oW) ((2))) .z)]
(a) Ez
[W--ww ww. (w.o(z))| 1 Σ (w ow, ((.))
(39)
sEIn
where (a) holds due to Lipschitzness the function with respect to its first argument. Hence,
E W.W.w.ss
A(W, S.)
sup W e PanaT
ow (ww
2,10
[ (w,))())) - (W. e d(>)))|
susup E PwP. w.
(Ee [/w o(=))
(U d()i\| +Ev, || (Ve, o ((=
<2 sup
2,10
(40)
37

---

where the last step follows since by equation 25 W = U + Ve.
In the rest, we fix and to and upper bound each of the terms in the right-hand side of equation 40
C Po (w))())) o())) (o,oTo(=))]
C2
Let & be the event that ||eTw]| cw and denote by E the complementary event of
We start by bounding C1.
C1 = Ee
(w, (1)) ())T)(=))
118} Ee (w, Ø(z)) (o=TT(()))) [169] (0a, 0T o(2) 1[8]] + Ee [()))
@ 10
(w,
(o w, o" d(z))| [[)7]
(R,e, (=))((=)))))) (E)) + I8 (()) (oTw: w. A o(=))
1e [1{ + Ee (un, (x)) - (OT w. θ do){)>]]]]
<e u.
(w,, xxz)) (oT w. θ Te ||
+ Ee
(41)
where (a) holds since by equation 24 under E, U = Oa. and under E U = θ W, (b) is derived since I [ I| < and hence, Sauchy-Schwaad incquality yields Kw,, (2))) < 1, and (c) derived by
TW,,
equation 32
Thus, to bound Ct, it remained to bound Ee [| (w,, ((2)) (OT w. o (=)))]- We use trick borrowed from [7 Proof of Theorem 9]. Note that || |ø{=)]| < 1. Hence, to upper bound
IE [[(w, ((2)) - ue, To.TTTofe [[]]))]]]_ is sufficient consider the case where ||w|| = ||ø(=)]] 1.
Let
A w (w, d())){(z).
A
|
It is easy to verify that (v, ((=)) = 0. Hence, since (=2) 1 v. we have
|||||| | |2 (w, (()))² [0{2)] v1- (w, xxz))² < 1.
Now, for every r E [d]. denote the r'th row of θ T E RdxD by T, and let
X, - (T=))
Y, A (Tr, 0)-
Since Ø(2) 1 v and since the Gaussian distributions are rotationally invariant, we have that X1...., XX, Yi...., Ya are i..d. Gaussian random variables distributed according to (0 1/d).
Hence, using the identity w v (w, ((2))()))))))))))) (z)). we can write
(w.((=)) d(z)) (0T Tww θ (()))
= (w. ((=)
T (u + (w, ((=)))())))))))))))))))))))))))) d(=))
- |0 x(z) 1') - | 0,
(w, (2))
TT²))( o(z))
(a)
((=)) 2
1 + 10 c, eT d(=)
o T d(x)
||
1 Σ X,Y,
(42)
rE|d] where (a) is derived using the inequalities (w, ((=)) and |||||| $ 1.
We bound the expectation over è of each of these terms, denoted respectively
C1 AE
((z)
C1 A
Σ X,Yr
rEld
38

---

Note that the distribution of
d a||0T T o(=)
a chi-squared distribution (d) with d-degrees of freedom. Moreover, asymptotically as ->
oo, x (d) converges (d,, 2d). Equivalently, asymplotically, (d) (O 2d). Combin-
ing this asymptotic behavior with the fact that for Gaussian random variable 3 ~ WN o²). with
E R4, we have that B[] V yield
C1,1 SO (V2))
(43)
To bound the term C1,2, notice that Σre dj X, converges to a random variable with Gaussian distribution (0,, 1/d), as d + 0o. Hence, once again using the fact that for Gaussian random variable 3 ~ M/ )² E|3 = o 3.2 yield
C1 Be
Σ x,Y, rC[d]
0
4 Vdl
Combining equation
41
equation
42
and equation
45 gives
C - Ea-
(w, o(=)) (U (()) Se 0.21d(1--c)) +0
[1(())
||
(44)
vd
0.21d(1 o2 +0
(45)
Vd
Now to bound C2, let V2 (V2,1, , .... Vn,a).
[< Vv. (T..oT(())]]
C2 =Ee Po By, Unitorm (a))
Bg-ro Bv, BV -inion (1))
|1, d(=)
Po |10 T 6(=)] By,-Unitomm(B,())) [V21,
(b)
Byc-utnffom(B(((C [[V,,]]]
o d+1 + +
2
TT d-1
2 1)
(4)
v
(46)
vm(d+1)
where (a) holds by the symmetry of the distribution of V., (b) holds since Ee- [l[oT d(=)l]]
<
Eew [[[@] (x)))11) [|ø())]] & 1. (c) holds by Lemma 4 proved in Appendix R.5 and (d)
holds since by using Gautschi's inequality have T(z-1/2)
[(++1)
V
Lemma 4. Let Ve (Ve.1...., Vv (niform(Ba(v)) Then, Uajoom [[2a]]]
Combining equation 39 equation 45
and equation 46 gives
A(W, ow:, se 0.21d(1 e0)² +0
Eww.w.s.
(47)
Bound on E. A (S,
We have
Retm (2, Qw)]
< 1(0w, o(=))
= =|< o d(z))
_ (<))l
x (cw I w)l ((=))1,
(48)
39

---

where (a) holds by equation 38 and (b) since by construction
||a]|| I Cu
Hence,
Es (s.elA(((S
=Bp PoPiip PwioT
(Cetm (Zi,0; (W) -gii (2,,
n vE(m]
(o)
< (Cw + v1 PoiTw
(1e@ ((z,,)) |1 + +110* o(za1))))
KE|n
=(w + v) Epp
Σ
(1l@) T ((7.0)) + +1 ((z11)11))
:c|n]
=Aco + v) sup Eps
(()))
@ 4(w + 2) sup |1((2)
<A(cw + +2)
where
(a) follows from equation 48
(b) since for any fixed 2, each entry of ][
is an independent random variable distributed ac-
cording to (0, 2) and hence
Ee
16 =||*]
=||=1|²
Generalization Bound: Now, using Theorem for the above choices Pe and P Pwjemu Tw (according to the scheme [I, Cw, 1)) gives
2 ($,
gen (,, A) SKs
(S.A)
+ W.w.,.ss.
A(W,
n
2 dlog
Cu tv)
+e -221011-) +0
Eg,
vd
(6)
2d 1E s.e
All ($, 0)
+V
0.21d(1-023
log
+ Va
8d(cw v)2 log
Ou +
+ -.21d((--2)
where (a) is achieved using equation 27 and equation 47
(b) by Jensen inequality and due the concavity
of the function Vz. and (c) derived using equation 37
The proof is completed by letting
d = Vn, 1.1, == 0.5.
E.5
Proof of Lemma 4
Note that
Ry, Uiitoom (B(()) [[Vr,a]] vEx (nioo(((()))) [|x1]]
where X
(X1 (X....., X.)
(nlform(Ba())) Hence, is sufficient show that
r 4+2
Ex=uUnloe((BB(11)
[| VFI( 2
40

---

First, we compute the marginal distribution of X1. Note that
(x,(=1) = Volume(Ba(1)) 02 V1
dxg ... daa
21
Volume (Ba-1 1 (VI- 2²
Volume(Bx(1)
A+2
d= (1 - -x1) 1_1
/T
Now, we have
E Ex~unntoo(Ba((11)
[Xi]]]
= =Ex [X1]]
2r
21 (1 - -xa) - dxi
V
d+11
2
===0
r' (#422
(a)
u) 2 du
V (411)
r' (d422)
Beta (1, (d 1)/2)
VRI (#+1
(412)
T(I) (22)
RTl (d+1)
r (
2
r (+2
/ 2
where (a) achieved by letting u 2 and in (b), Beta(..)) is the Beta function.
G Proofs of Section 5 and Appendix C:
Memorization
this section, we provide the proofs of Section Appendix Recall that for given Kg, the adversary outputs its guess of K2 as K, Q(W, Zi,k, n). Throughout the proofs and for better readability, we sometimes denote K; by K; 'in' and K; = 0 by K; = 'not in', referring to the semantic meaning that the given Zr,K, part of the training dataset or not.
G.1 Proof of Theorem 5
We prove each part separately. As stated the beginning Appendix G throughout the proofs and for better readability, sometimes denote K; 1 by K; 'in' and K; by K₃ = 'not in' referring to the semantic meaning that the given K,,k, is part of the training dataset or not.
G.1.1 i.
We prove the result by contradiction. Suppose that there exists an adversary for the algorithm A that is E-sound and certifies recall of samples with probability q, where & < q and m M(n). As before. we denote the output of the learning algorithm by (s.).. = W.
Recall that S = (Z1,,, 22.4...... Un,J.) is training dataset S, and Š S5 the test dataset St,-
Define J. E {0, 1} follows:
0, if Q( 14) = 'in' and Q(W, 7,,,/4) = "nol in', J,
if RQ Zi,, 'not in' and Q(W, Zi,1, ()) 'in', Uz, otherwise,
where U, ~ Bern(1/2) a binary uniform random variable, independent of other random variables.
Recall that given A, E-sound adversary means that,
P (3i c [n]: Q(W, 2,, 11) = 'in') < E
41

---

and an adversary certifying recall of samples means that,
Σ IC
(Q(,, 3.) 'in'} 2 2 q.
Since assumed m Qn)), there exists ei (0, and no N such that, for all no. m a.n The second condition then yields,
Σ 1QQ(, 2.),,,1) = 'in') cin 29. cc/M)
Define the Hamming distance dæ: {0, 13 x (0, 13"h - [n]] between binary vectors J and J as
dи
[J.)) Σ 1( J.}.
iEin]
Next, use Fano's incquality with approximate recovery denote
59
Theorem 2]. Let L (1 _] and
Pe. a P
dH (J.J) > nt),
NJ A Σ 1 (in S nt)
[C(0,1]
Note that Nj is the same for all j E (0.1)". Indeed, du (i.j) = du (i @ a.J @ a). where @ de- notes the modulo two summation, for any E {0, , and Ej a dd (i @ a.j@ s nt
Ip 1 du (i.j O a) & n Hence, Nj = Njea for any a, and the maximum over of Ng is equal to N
With these notations, have
onn) @ [[(]:
[[(JWI$.KK
([J:W.
(4) (J]:J|
21(J:
2 (1 Pe,) log
2"
log(2)
Ni.
n (1 P.,) ht) (1 - Pe.)) log(es) log(2),
where (a) follows by the assumption of the theorem, (6) results from K is independent of (W. S, J). (c)
results from I(J; JJW. S, K) = since J is a function of (W, S, K), (d) results from I(J; W, W.J[S. JJS.K] K)
JJS. K) + I(J; W Š K) 2 I(J: i K) (by the positivity of mutual information), (e) is due to the identities below,
I(J (J = H(J) - HJJ K) 2 H(J H(J = I(J;J),
(f) results from applying Fano's inequality with approximate recovery [59 Theorem 2], and (g) is de- rived using the claim, proved later below, that N1, < (22 for some constant E R, and for sufficiently large.
1/2. Hence, since hz(x)) is continuous function of [0, (t) converges the constant 1 h4 (L_0//2 0. Hence, if we show that for sufficiently large n, - Pe, > O, we obtain contradiction. Since the left-hand side of order o(n), which is greater than the right-hand side, which is I(n), and the proof is complete.
Note that 1 (1 4) 1/2 and
xc, 1-0/2 /2
42

---

Hence, it remains to show for sufficiently large, Claim i) Ni,, S co22hestt for some constant C3 E R+, and Claim ii) Pe. <
Proof of Claim i)
We have
N1,
Σ
1(d (j. 1,.) S nt)
[0.1)
72
(6)
52n
(0) 2n has (int+)//n))
4m(nt/n' + 1/n')(1 nt/n' 1/ne'
(d) 3 c2222hs(t)
(49)
where n' = 2 [ and c3 E R4. (a) results from 2 n, (b) follows from applying 72 Proposition 5.18 (n' is even and nt S n'/ /2 1). (c) is derived using the relation
mholi/m)
m
m
I mhuli/m)
m
8j(m - j)
j
2
j)
which valid for any m E N and j S m (see
77
Exercise 5.8.a)), and (d) holds for sufficiently
large n, using n < n < nn+1. 1.
Proof Claim ii) Define the following events: & & { E [m]] Q(W, 1., 12) = 'in'.. & 2
[ie( H{Q(W, Z). 'in'} < <an Then, we have
Pe. P
du J,J) > nt
du
JJ.J)
> nt, Eÿ + +F E2)
1
Σ
1 UU: # 1 :1) 'not in') nt, E + &
(c(n]
Σ
P
Σ
(04 J.} (2(W, (t) 'not 'n' > nt,
re][n(1- -e]l]
Σ
(Q(W, = 'not = E9. in' &P(E
< Σ
P
Σ
IQU # (Q (w,, 'not > nt,
re([n(1-cx])
iElm
'not in') 1 LQ( in =r) =r)
+ PP
= Σ
P
Σ
1 (U: J.) [Q(W, Zi,,, not > nt Σ
(Q(W, Zi)., 'not in') =r
re][n(1 aill
[[(m]
'See for reformulation.
43

---

P
Σ
2... -not in') =
iE/ni
+ P (E1,82)
Σ
P
Σ
1 # J.) 2.,,, = 'not in') > nt
Σ sE[n]
(QQ(, Zi,J, 14) = 'not in') =
rEint,(a(l-c))
iEin]
P
Σ
1 (Q(W, Z.),,.)) 'not in')'n =r =rr
iE|n|
+ PP (2),
Σ rE|nl, [E|nt,[x[1-0]]]]
2r( 1)²² P
Σ
1 (Q(W, 'not in') -r +P(EL,82)
|E(M]
e -2 4 -4) + &2)
<
max
- [x(_cx(]-
9 2[n(1 [1=(1-c)](
[ 1)²² (Ei,
(f) -2[n(I-aa) (mi })²² (EiE ((2)))
Se
<c (c= কলকनতाي ))² + q.
and we justify the main steps hereafter:
(a) holds since under the event Ef, we have that Vi E [n), J,, =in'} } and also whenever i) both Q(W, Zy, μ1) = 'not in' and Q(W, Zr. H)) 'not in', J, is chosen as U/ and hence the Hamming difference of the i'th coordinate is (U: # J:). and ii) when Q(W, 2 11) 'not in' and Q(W, Zi.... p) 'in', J, is chosen as and hence the Hamming difference of the i'th coordinate is O.
(b) holds since under the event Eg, we have that Exe [o) 1(2(, Z) = 'not (on) < n111 c1),
(c) holds since for nt, the probability is zero,
(d) holds by Hoeffding's ss inequality for the independent uniform random variables 1(U, * Ji} and since > n11 c1 /2 2 2 r/2 for sufficiently large,
(e) holds for large enough since,
2r mzl 1)²²
2r nt
1
2
log
min ( mn]-)
r
2
1 2
2nd r
min
E|1, [m:1-a))
nt
2
1
2nd
sE(1,
min
[n[l e1ll
x
α
2
+ x
2nf
min
zE[1.
[
4
nt
- [n( - ci)
2nt
[n[1 c1)]
4nf
nt
1
- 2[2nn(1 - ci)]
nn(1 e1)
2
where (+) is derived since i) for sufficiently large,
[n(1 a()
[n[] e
which is less than 2 for
ntt
[1
large, and ii) since (1 1 + :) is decreasing in the range (0,
(f) results from P (Ei, E2) < (Ei) + +P (82).
44

---

-[n(L-e1]] (=(-))
Since for sufficiently large n, e small. hence, if E < then Pe. < 1. This completes the proof of Claim ii), and hence of Part i).
(which converges to -0-01) gets sufficiently
G.1.2 Part ii.
Similarly to Part i) (Appendix G.I.1 an adversary for A such that
we will prove the result by contradiction: assume that there exists
((3 E [n]: Q(W, 2.) 'in') S.
and
P
Σ
(.,,,),,.,,)))1111 = =in'" an a.
iein
This also gives,
IP
Σ 1[Q 'not in'} 2 n(1 - a) [E(m]
-1-9.
(50)
In our proof, we allow the adversary to be stochastic. We denote expectations and probabilities with respect the adversary's randomness (which is independent of all other random variables) by Eoli and Pell, where needed. The main part of the proof relies on the following lemma, which we state below but prove later (in Appendix (G.)) for better readability.
Lemma 5.
The following holds.
E e
Σ |c|n]
(1 {o(W, Za,je, 11) = 'not in'} - (2(W, 14) = 'not in'))
= o(n)
By Lemma have
E E. 2
Σ I [QW,, 11) not in')
cc(m]
=o(n) + E E.
Σ
1{Q(W, Z),,, 'not in'}
[E(M]]
(2) <d(m) + n(1 q) + n11 aag
=o(n) + n(1 - aq))
where (a) holds using (50) and Exc(o 1fo(W, (1) = 'not in') < n.
Hence, using Markov's 's inequality,
{ (1) = 'not in') > ml) <
o(n) + n(1 aq)
P
Σ
ml
|E|m
or equivalently,
Σ 1 (@(W, Zo,Je, p)) 'in'} mmm
2 o(n) + n1(1 - oq)
P
m
iE/m]
Hence, for any
m' d(n) + n2( aq)
n(aq d' o(1))
g' E (0,
1-
of
have
Σ
(4) 'in'} m' 2d'
45

---

Hence, by varying o' over the interval (0, aq), the ratio m' /n changes asymptotically from 0 to ag. In other words, n sufficiently large, then for any
6E (0, m' = ( (179=e- )" n o(n) = 52(n).
we have
IP 1 (2(W, -nnn m²) 2 (a c)g Σ <C(n]
This completes the proof of Part it).
G.2 Proof of Theoree
To prove Theorem we show that for any learning algorithm A: 2 + R,, the projected-quantized algorithm, defined
A (S.) A eλ(e@ A(S.)) (AS.()((S.)) OW,
satisfies equation and
(MI(H,AA(SA.) S Ee (M,I
o(n2,
(51)
for any distribution μs. Having shown this, applying Theorem D completes the proof.
Fix any arbitrary distribution μ.. Consider the construction of [L,d, Cw. v), described in Appendix F.1 is shown in equation 26 that
CMI Id
which, together with the data-processing inequality, yield
Cw +
log
(52)
Furthermore, similar to equation 36 where it shown that
Epsn. w Pa Pajew gen(S.. W) gen )nne
(
2 1/4
0.21 22
1 d
c
nn
it can be shown that
EPs., w Pe P Tw
gen(S Sn, W) gen(S SennSn.e11)]
x Vn
( 1+
d
2
0.21 9.21 dec 113
(53)
Plugging the choices in equation
500r log(n), Cw 1.1, 0.4,
52 and equation 53 result equation
51 and equation g which completes the proof.
G.3 Proof Lemma
If m = 0, then consider an adversary that always outputs Q(W, 2, = 0, for any Z E 2.
In the following, assume that nmm * 0. Let V {0, 1} be binary random variable, independent of all other random variables, such that P(V = 0) = a. For example, if there exists a set B S W such that P(W B) a, then the adversary
set V 1 (W & B).
Consider an adversary that first picks a random V. V = 0. then for any 2, it declares Q(W, Z,u)
0. Otherwise (i.e., V 1), it declares Q(W, 1, 0 with probability Tn and Q(W, Z, = 1 with probability - ra. independently of (W, 2, p))
If V = 0, the adversary never recalls samples with any positive probability
P
Σ <C|D]
Q(W, 2..1. 2.1,
m =
Σ ic[m]
Q(W, Z., 2 m. V=
(1 (1
Σ
Q(W, Zr,1, mlV
iE(x]
46

---

Moreover,
( [n]: Q(W, k,,, PP ( [m] 2(W: 2,0011 1, =1)
IP Ii [m] 2(W, 74,0,14 = -V
Using the above two relations, this adversary f-sound and recalls m samples with probability g if, restricting to V = 1, the adversary is (1-a) -sound and recalls m samples with probability (1-a)- For the adversary to be (I-a) sounnd given 1, we should have (vi E [n]. Q(W, Zio. ()) = 0) 2 a) Hence, this adversary is {-sound and only
therefore,
{ Tn (1 a)
Next, when V = 1, to find the probability of recalling m nm' samples with probability (1-a)- note that the probability of Q(W, Z4,1,/) (4) I is equal to (1 Tn)) We consider two cases:
rr =0, [ME| QWW Z, 2 m|V 1 1. ii. If m rn. using Hoefiding's inequality, we have
P
Σ
Q(W, 2,,, MV 21 2n(m''
iE(M)
Considering these two cases separately,
g i. We should find a value of such that (1-a) I and 0 2 1/1 (1-u).
Both conditions are
satisfied for 1 if 4.
ii. It is sufficient to find a value for ra such that m' < (1 - (1-rn), 2 V 1 Vi-m-aj
- and 1
e 2n(mm (ammmm+ra-00 tra 11² 2 (1-a) If, 1 m
V
Zn
1
log
I-
(T-a)
> 0, then let
1 mmmmm
log
2n
It satisfies the first condition and the recall condition. Lastly, the soundness condition is satisfied if for sufficiently large n, we have
E
m < I.
+
log
II a)
2m
(1-0)
n
G.4 Proof of Theorem
We prove the theorem and the comment after it, separately.
the first case and to prove Theorem 8 we show that for every r < there exists a projection matrix θ
R Dxd with d in 222211, $7, Markov Kernel P Weeeew and compression algorithm Ab. 2" Rd
defined as Ab.n (S.) Ā(e A(S.)) = W, such that
E EP w Pwreew
gen, W) gen(Sn, [w]]]= (n-))
and
AM,,,, o(n).
47

---

Having shown this, then applying Theorem 5 completes the proof.
In the second case, show that for every d = [rr (og(n)] a Markov Kernel WieTw and a compression algorithm AB, - - IR defined as
there exist projection matrix θ RDd with
(S.) _ A(e* A(S.)) = W, such that
gen(Snn W) gen(Sn, (un]s,,;,v))] = =0
E.... PwieT
and
CMI(u, Ab,.) = o(n).
Having shown this, again applying Theorem completes the proof.
Hence, remains show the existence of such projection matrices E R Pxd Markov Kernels Pwieew and compression algorithms A 2" + Rd. for each of the above cases.
G.4.1 Case i.
Consider the construction of [L[d, Gw, v), described in Appendix
F.1
It is shown in equation 26 that
CMI (S. =Sd Cw
Hence, for any fixed e
CMI CMI log
Cw + 2
Now, let
AW, eW; = gen(Sn. W) gen( Sn, WW)
We show that for any letting
Cw 1.1, , 0.4, 2r-1
n
results in
e
a Ee
Bw,wss
E
A(W, ww; S.)
(54)
n2"
Having shown this, it's easy to see that there exists a θ for which simultaneously
Ew.wss.
((W.OW::...) =
n
and
CMI (14, A) = o(n).
this matrix E R Dxd and the Markov Kereel PwieTw induced by that. Choosing the overall algorithms Ag,n : 2 Rd completes the proof.
Hence, remains show that equation holds. By equation 28 we have
A(W, ; -WW, 2) (W, e Z),
where 2 A Ezzz [Z]
1 - Z, Recall that W = U + Vu, where Ev, [V.] 0. Hence,
Ee |
A(W, ew, S.)
-Ee E Ew.s.
(W. 2) + (U, T ])]]
(W, 2) (U, 2
<Eo.w W.S.,
2) ||-(w, (w. (U (U, 2
SEs., w Eg
Combining above equation with equation 44 for ((2) 7 gives
Es | w.s..
ew, (W;)
0.21d(1 221² + Es. [1|2]]] (12)
Next, know by equation 35 that B[| 2
E||| E|||
Vn' Henee,
Ee Ew,.s,
<e -.21 + 0
1
w.s.
dn
The proof is completed by letting
d 1= 2r-1 Cu 1.1, == 0.4.
48

---

G.4.2 Case ii.
Consider the construction of [L,d, Cw, v), described in Appendix
F.I
It is shown in equation 26 that
CMI =<d
Cw
Hence, for any fixed θ
CMI A) log
Cw + V
(55)
1
Furthermore, it shown in equation 36 that
Ep w Pa PaPwie We w gen(Sn, W) gen(Sn. own
(1 1
2 d
0.21 -2
n/
Hence, there exists at least one θ for which
Ess., W P WiotT gen(Snn W) gW) )wne
<
2 Vn
1 +
2
1/4
0.21 d(c
-12 1)²
(56)
Choose this matrix @ Dxd and the Markov Kernel Pwierw induced by that. Call the overall algorithms as Ag,n 2" + Rd, with the choices
= 500r log(n), Cw 1.1, == 0.4.
Plugging these constants in equation 55 and equation colooommmtscooomstss the proof.
G.5 Proof of Theorem
proof the comment after the theorem, i.e., to show equation 14 instead of equation 13 then follows similarly to the below proof, in similar manner shown the Case part of the proof of Theorem
first provide proof Theorem
To prove Theorem 9 we follow the Case i part of the proof of Theorem 8 with slight modification: is replaced by Z, which results convergence rates roughly v larger than the current ones. the sake of completeness, provide the proof.
Let
AC(W, θA) = R(W)-R(Oti))
Following similarly to the Case part of the proof of Theorem it is sufficient to show that for any < 1/2, letting
n= en 1.1,
, 0.4,
results in
e Ee
Ew w AC(W
0
(57)
Hence, remains to show that equation 57 holds. We have
AC(W,WW)
-EEzyu (W, 2) [2)
-ZE~ (W,2) + (W.eTT eT [2]]
(W, WW,Ezap [2]) (W, e T (2]).
Denote A Eznn [Z]. Hence, since W- = U + Vv. where Ey, [V>] 0, we have
Ee E..w [AC[W.WW)]]] -Ee |B (W. 2) + (U, TU)
<Eo.w (W. (U, (U.e Tz
Combining the above equation with equation 44 and by replacing (02) by gives
Ee
(L((W)W)) se 0.21d(c 112 + E Ew w
1 /d
The proof is completed by letting
=
n
Cu = 111, 0.4.
49

---

G.6 Proof of Lemma
Consider the the [L,d, Curs v) transformation described in Appendix F.1 with some d E N+, Cu E (1./5/4), and (0, 1]. Recall that W = U Vu, where Vu be random variable that takes value uniformly over Ba (1) and
@Twu w. if I w|ll S Cw:
Oa:
otherwise.
Let & be the event that ||e| (iTTwi
Ca and denote by E the complementary event of E. We have w/]
E
[
(a)
Ee
E
[1V].11]
[Eine]]
d Ev,
[|V.1P]
D
Ee
|
(4)
E
00 wo
1 {EE}
Dv²
d
=Ee
00
w
Ee
00 T w
2
1 [(8
D
d
Dv2
Ee
00
E
90
Ee [1 (23)1/2
d
Ee
00
Ee
o w
1/2
e 0.1d(e 112
D
d
D 1
||=||
DD
d 3)(D d 5) 2)
|| u.1dde2
Dv?
d
d3
d
where
(a) follows by the triangle incquality,
follows by noting that each element of θ is i.i.d. with distribution (00 1/d),
(c) holds since V, E Ba (V),
(d) is derived by the definition of U and E
(c) follows using Sauwhy-Schwarz inequality,
(f) is derived in equation 32
and (g) followed by following relations
D + d+1
Ea
00
m
=
d
||m11?
10e T w
(D+d+b 3) 3) d 5) 2) ||
Ee
d3
shown below.
Proof of norm two. Note that Ee ||eeT T w/ scales with [/w]] Hence, it suffices to assume that ||
Next, first we show that Ee | w|ll is the same for any w with ||||| = 1.
For any i E D there exists an orthonormal matrix Q Dx such QQ Ip and Que = e1 e [1, 0,0, 0, ... _ This matrix be constructed letting the first row and choosing the other
50

---

rows orthogonal to w Next, by letting O' = Qe,, we can write
@0
=w To
=c 00'Que
=ci e'e""
e'e'Ta a
The result follows by noting that || rotationally invariant.
6
[|
|100 ea
=ll]].
since distribution θ
Hence, it is sufficient to compute E |le0 e1 e
Denote the elements of θ by Oug where i e [D].
j C [d]. Then, simple algebra gives
E
0
ea
=
Σ
01,50
01,0011
We know that for 0 (O, 1/d).
E [ odd m E
[ d'
0
3
d2
Then, it suffices to consider terms in the expansions that are non-zero, i.e. the terms where only even norms of each random variable appear. We consider all such cases:
1. i + 1: D choices
j=: d choices and and the expectation of each term equals 1 1.1. j = 3/:4
d2
2. i = 1: 1 choice
2.1. j = j d choices and and the expectation of each term equals 3 T 2.2. j # jf: d(d 1) choices and and the expectation of each equals
Summing all terms and factorizing properly gives
E
00
T
e1
=E
Σ
Σ
01
[E[D] E
D
d
Proof of norm four. Note that Ee |all ui|"
scales with ||w||] Hence, it suffices to assume that [| 1. Next, similar to the proof of norm two, it can be shown that Ee ||00TTm is the same for any
with ||w||| = 1. Hence, is sufficient to compute [100 e [1"] Denote the elements O by 0z.j
where [D].j [d]. Then, simple algebra gives
E ee T ei 1|]=E =E
Σ
Σ
0z
01 01 I1.1
LLE'D indh J'El
We know that for 0 ~ NN 1/d),
E. T0 = 0 for odd
E
R
00
3
E
06
15
E
[
105
d'
J
g
dt
Then, suffices to consider terms in expansions that are non-zero, the terms where only even norms of each random variable appear. We consider all such cases:
51

---

i D choices
1.1. j2 = 12: choices, and the expectation of cach term equals de
9
1.2. Two of (ji, j2, J1. (22) are the same, and two others well, with different value: 3d 3d(d-1) choices, and the expectation each term equals
Hence, the sum of the expectation of the terms for this case equals:
3d (D - 1)(d 2).
2. i, and # fl: (D- 1)(1-) -
2) choices
2.1. = J f4: choices, and the expectation of each term equals zd-
2.2. = j2 and different from j2: d(d 1) choices and the expectation of each term equals प..
Hence, the sum of the expectation of the terms for this case equals:
d (D () 2) + 2).
3. = 1 and i' * or and * 2(D - 1) choices
3.1. f1 =2
12: choices. and the expectation of each term equals 28.
3.2. f1 = j2 and different from j jb: d(d 1) choices and the expectation of cach term equals di
3.3. different from j j/2 f2: d(d- 1) choices and the expectation of each term equals 4
gr.
3.4. jz different from jí = 1/2 = jı: d(d 1) choices and the expectation of each term equals
3.5. f1 * j2 and both different from jí f2: d(d () - 2) choices and the expectation of each term equals
Hence, the sum of the expectation of the terms for this case equals:
2d 3 1)(15 + 9(d 1) + (d l) - 2) 2d () ()
4. 1 = 1' = 1: choice
4.1. j1 = j2 - = jı: choices, and the expectation of each term equals 105 "= 4.2. Exactly three of the indices among (j1,j2,J11.55) are the same: 4d 1) choices and the expectation each term equals 15
4.3. Two (21, f2. j/) are the same, and two others as well, with different value: 3d(d-1) choices, and the expectation of each term equals $
4.4. There exactly two same indices among (i.j2.Hi. 6d(d - 1)(d 2) choices and the expectation of each term equals +.
4.5. All indices among (j,,j2,J' .J2) are different: d(d - 1)(d - 2) 3) choices and the expectation each term equals dt-
Hence, the sum of the expectation of the terms for this case equals:
d (105 + 60(d - 1) 27 1) + 18(d 1) - d (d (d + 4) 6).
Finally, summing all terms and factorizing properly gives
E 00 ei 1'] =
Σ
Σ
0 Or.
01 01. 01.3%
i.F'(D]) indt
(1) + d ()) d (d+
d
52

---

G.7
Proof of Lemma
To prove this lemma, we show the below stronger result:
1 (2(W, Z,,js, 'in'} 1 (2(,, (1,, 'in') ]| = d(n),
xc
which results also
E,
Σ
(1 (2W, Ze, p)) 'not in'} 1 (2(W, Z.... 'not in'3) =(n).
jEIm
For a given (W, Zi,j), denote
Pe (Q(W, Zz.j (4) 'in) = E [1 {Q(W, 14) = p
(W, Zz,z)
where the probability and expectation with respect to Q refer to the stochasticity of the adversary. Note that (W, Lx,)) ) measurable function of (W, Zz
For r E {0, . 2n 1}, denote binary representation as r = (by,1. br,n). where br,, E {0, 1}. Now, consider 2" auxiliary estimators, indexed by E {0, 1,..., 2 - 1} and defined follows. The estimator r. for the i-th sample, by having access to (W, Z,,u. Z,,1) estimates J. as
j. 3 0, with probability 1+(-1) 2, (-1) (W.2.))
with probability 1-(-1)) + 1-1 pW.2..))
Note that each of these estimators makes its estimations only by having access to (W, Zi,0; Z,,1). Define the Hamming distance dæ: : {0, 13" x {0, 13"
[n]] between binary vectors J and å
dæ JJ.J = Σ [1}
igin]
We now compute the expectation of du (J, for the r-th estimator, i.e., B.,,S. de (J, (J,J)] Note that due to the symmetry of S. we can only consider the case where = (1, 1, 1,..,, 1) == 1n.
E E (dr (J, = =Ew.s. (n J1] 3)]
E E B -M-
der (1,
m
(- 1) (W, ( (-1)0mip (W, Zr.1)
Σ
Bw
1) 1 E (p (W, (1,1
2
kE[m)
n
br. 2 Pp (W, Zi.;;) - Zi..).
2
vE|m)
n
Σ
(-1)
E W W, 100 (Q( Z,.,; ()) = 'in'}
2
ig|m]
1 (9(W, 14) 'in'}]
Then, there exists estimator r", for which
Ewa.. (dr(JJ.))
n 1 Σ
Bws 1.0 1 (Q(W, 11) = 'in') 1 (o(W, Zi.J.
'in'
2
xE(x]
Now, suppose by contradiction that
Σ
Bw.s.
1 [Q(W, Zz,ry 'in'} (Q(W, Z....)) -in')
sE[n]
53

---

is not o(n).. This means that there exists some by E R+ and sequence {at such that lim oo limiting n to this subsequence, we have
Σ
S. a (Q(W, Za,j;, p)) 'in'}
() - nb
EE mg
Without loss of generality, we can assume that b1 E (0, 1/4). Then, for the estimator r",
E...JJ.J du (J. Ji] - n(1 - 2b1)
2
Next, Fano's inequality with approximate recovery
59
Theorem
Let
(1-b,)n
and
denote
Pe. AP (d (J.J) > nt).
Nj Σ 1f lddu(i.) I ml)
je(o.1}
is easy to not that Nj is the same for all j E {0, 13". Hence, the maximum over of N3 is equal to Ni.. With these notations, we have
o(m)
IJ; W|S)
(J: W. J(J
2 [J;J;
2 (1 Pa.) log
2"
log(2)
N1.
@ 1n (1 (1-ho(t)) (1 11--Pe Pe.) log(3) -log())
where (a) is by construction of W and as shown in the proof of Theorem (b) is derived since J is a
function of (W, S). (c) is derived due to positivity of the mutual information, (al) is derived due the
below relations
[[] = H(J) - (JJJ S) 2 H(J) (J]jj) = (JJ:)),
(e) is derived using (59 Theorem 21, and (f) is derived using the claim, proved later below, that N1. S (g2 for some constant R2 and for sufficiently large.
Note that
oc, ht) converges to the constant 1-hs ( 0. Hence, if we show that for sufficiently large 1 - Pe. > 1 - b2, for some constant b2 E (0. 1). the contradiction achieved. Since the left-hand side is of order o(n), which is greater than the right-hand side, which is ((2), and the proof is complete.
(1- (1-b))² 1/2 and
Hence, it remains to show for n sufficiently larg N1. S c22mho(l) for some constant c E R, and ii)
Pe, < b2. for some constant b2 E (0, 1).
Proof of Claim i) This is shown equation 49
Proof of Claim ii) Using Markov's inequality, we have
Pe, Ar (du (J.J) > n²)
E Ew, (J.
nl
(1 2b1)
2t
1 - 2b
< 1 by + 1/n
54

---

1 1 01 + 1/n
<b2
for some constant b2 E (1/2, 1) and n sufficiently large (or sufficiently large).
This completes the proof of the lemma.
H Proofs of Appendix D: Random subspace training algorithms
H.1 Proof Lemma
Part i. For a = 0,
(x.p(x)
2m
which is a standard Gaussian distribution. Hence, hgga, (+)) = log(v2Tre) and f(a,p) = 0.
Part ii The relation f(a p) f(-a,p) is trivial since by the symmetry of the distribution ga.p. To show the increasing behavior with respect to a, consider I a' < a and some E [0,1]. We show f(a', p) f(a, For a 0, let
Xi = Yi+ Ja, X2 -1
1 Yi J.
a
where Y1 ~ (N(0,) is independent of J Bern(p). Then, it is easy verify that
1(X2; I(X1; f(.
(58)
Now 2 (())² and define
X= X2
Yy (Yi Y2) + a
(59)
where Y2 N (0, of) is independent of other random variables. Note that Y2 A a(()++%) is indepen- dent of and distributed according to (0, 1). Hence, we can write
1 Ya a
Xa
(60)
Now, we have
f(.
1(X2. J)
I(Xs:J)
(g) f(a'.p) .p..
where (a) follows from equation 58 (b) from equation 59 and the strong data processing incquality, and (c) from equation 60 This completes the proof of the strictly increasing behavior with respect to a the range oo).
Part iii. Denote (z) = 1 e and Q2(x)= = V2n
Note that ga = (x) + Iog Now, considering
V2n
(x)) Hence, (g)) pEq, [log(ga.(<z)) the limit to infinity, we have
lim (x)a,(())) pÊE, (log(pQ(<))) - (1-p) p) lim EQ, (1{(--))((a 40000
plog(p) (1 (1)-p)log(11 1 log(2) (p) + 2 (2gee))))
pEQ, [lg((Q( (1-p) lim Eq, [lo((Q(z)))
where (a) is deduced by noting that both Q1 and Q2 are Gaussian distributions with variance hence, their differential entropy is equal to 3 log(2.r)).
55

---

This concludes that limo- (a, p) (p(p).
Part iv. f(a. p) f(a, p) trivial since by the symmetry of the distribution Da.p-
To show the strictly increasing hehavior with respect to p. consider 0 S p1 < p2 S 1/2. Let
X1 Y + Jaa
where Y (0) is independent of J1 Bem(p1). Then, due to Part
1(x1;J1) = pl) h(ga.p(z)) - log( 2
(61)
Moreover, note that
h(X1) hg (z)) h(go,1-p1 (x)).
(62)
Let Z BBrr(()) be independent of other random variables for some a E (0, 1) that will be determined
later. Let
X₂ 2 Y + Va,
where V = J1 ZI. Note that V Bern(pqq + (1 p1)(1 q)) is independent of Y. Now, on the one hand, we have
VX = h(Y) = (I))
(63)
On the other hand.
(a) > 1())lZ)
MXx)
(X2l2 = 0)g (x 9)
=h +|Jila) hY + +|11 [|a) 4)
+ Jía) (1 (1-q)
2 (()g, h (z))
[h(gam
_
where (a) is derived by strong data processing inequality and since pr [0. 1/2) and q E (0, 1). (b) derived for J' ~ Bern(1 - p1) independent of Y, and steps (c), (d), (e) are derived using equation 62
Hence, combining equation 61
equation 63
and equation
have
((a
(1)
V)
=f (a, (1 p1) -))-
The proof completes by find a E [0, 1] such that pig (1 p1) (1)1-p1)(1100
= To show that such cxist, first denote Cy (9) == Piq + (1 p1)(1 q). Now, note that ep. (1) = pı pa ep, cp, (0) P1 > 2
Hence, there exists a E (0, 1) such that ep(a") This completes the proof of this part.
H.2
Proof of Theorem 10
Recall that
V, (fr,1 ..... 1.,)
is the set of sample indices chosen time E [T], chosen independently of any other random variables. Hence,
g Ev [ge A(o))]
where A is the algorithm (d) where the batch indices V (Vi,... Vi) are used.
56

---

The proof consists of bounding each of the conditional mutual information terms
CMIV A. (S, w') & SS.J... (A (S,, +); Ja),
i [n],
and then using the bound 15 of Corollary 2 with AV A and e = O.
It is sufficient then to show that for fixed V and every fixed E [n]. we have that
S
Σ
[5
Th bor
Ac,i. Pt..s
(64)
1: iEV,
where
A _ || w e (9W; 1, 7,,,, Vall (OW; 1, :1
Pt, _ F J; 0/$, V, W {W",, W; r diniitttiiii E.))).
For a fixed E [n]. if {t: i E }i} is an empty set, then the final model is independent of Jr and hence CMI _, (S, W') = 0, which completes the proof. Now, assume that this set is not empty. For case of notation, suppose that
(t: E Vt) (t1 (tI....,t. t...
where tt < t2 <
<tM= S.
Then, for fixed V.
C W*) Il 1. (A (Ss, JI)
- -..J_. e.V (W/;; J:)
S.J... (W -
-1 W W WI W -1; J4)
S. (W W 1: 1 W W 11--- W -1)
M][M]
S.J_,, (W J. 11, W m W Wm---11." Wi, W(,-1)
M]IM
where (a) holds since by the data processing inequality e..J....V V S 9.._....V (W?yr J.) 1: J.) the
(WF; - W 1-..... W/, W
and V (W i J.) < (,.. .WW, W W non-negativity of the mutual information, (b) is derived using the chain rule for the mutual information and
by using the convention that when I, the conditioning part {W% W W -1. W/, 1/,-1
empty set, and (c) is derived since | ... (W2 Jsl, W W - W7. W W = 0.
W/ Consider a fixed value of (W/ -1. W/ m- WY
1: W W and let
S. W 1. W - W W 1: WV W 15. F
Note that
Ptm. P J;
J W (W", W-- 1:r tm i E Vz})
=P (J, = 0 Fm.
Hence, is sufficient to show that
Fm FW.. (W! 51) S
Mm
Atmods Pemis)
(65)
bat
Recall that
W/ Proj { (W:,, 1 nmm V w R(V OW?.. 1) + oe oem Etm
where R(V.... W) Evev. 8 (Zv,J,r W). Denote
R (V W)
Σ ((or,,y.W)
57

---

Furthermore, denote
W W Tit.. V R(V... + Etm Etm
o1 =W Tm V R- oW: Nm V wl (Zi,Je OWW + ol Elm
where the last line holds since by assumption C Vem Using the data processing incquality, have that
mm (Wi,) Ji) S Fm (Wimi di).
Hence, is sufficient to show that
Fm Wi) SS
apm bors..
Dtmats Plmnit)
(66)
Note that
Fm (Wr,; = 1m (We... /otm: = 5m "(W /0mm)) Fm orm (1).
(67)
To compute each of the terms in right-side of equation 67 distributions of Wim.
first we derive the marginal and conditional
dtm.
Given Fm and given Ji O,
Wem
W/ -1
Ihe ot
V.,/ R-i(RV. OW! OW!--) Ttt V (Zi., O00,,, OW bore
Etm
Otm.
Hence, given Fm and given Jj
Wen. is distributed
osm
Wem Po 2 N (Ho,Ja),
(68)
Ttm
where
1
Wim--
V R R- OW
V ( OW!...
1i0
Ot.
bot
Similarly, given Fm and given Ji = 1, 1 We.. is distributed as
dem
Wem.
p 2 N CENNwu Ia),
(69)
Ftm
where
1 W/ -1
Mm V R
R_ (Vi OW -1)
9im Varl
(Ze, (Zi,1 OW!
Ot.
Ttm
bot
Lastly, since P (J; = Fm
Pen.ii then given Fm, Win is distributed as
1 Wim
P 2 pe io + (1 Ptm..) :) A
Ttm
=Pnm,iN iN (mn Id) + (1 Pem.i) II1,
Now, we compute each of the two terms of h Fm (We.e///r (otm)))) and Fm (Wem /otnn//s)) (J:):
The term Fm (W.../ /o...) equals the differential entropy ((P). Since the differential entropy is in- variant under the shift and since also Gaussian distributions and P are invariant under rotation, h( ()) is equal to the entropy of the distribution Q, defined as
Q Pt... N (0a, Ia) + (1 - Pt.m..) N (ad. Ia).
where
9ml bot
p. O,.. 0) Rd
ad
58

---

and
bat
| woll
V Worl
V.rl -1, Zz,,,)
tm.d.
Note that ||aد|| ||l Furthermore, can write
poll-
Q = 2=Q1@Q20 Qa.
(70)
where
Hem Aemids ))
Q1 Pt N (0, -m -bm, W
botem
and for r E f2,3,....d d}.
Q. = N (0.1).
Hence,
h "W: (Wen/W//r /0mm. =h(P)
=h(Q)
Σ I(²+)
re(d)
h(Q1) (d log( 2Te)
(Ma (x)) + (d - 1) log( v 2Te)
Me
Almir Pimii + d log( (oog(v22 22T)),
(71)
bote..
where (a) is derived by equation 70 (b) holds since the distributions Q2...., Qa are scalar standard
Gaussian distributions, (c) is derived for a1
99mm
Dem. and by the definition of (-) in 19 and
bo
(d) by the definition of f(a, p) in 18
compute 5m (We.../r /o... Js),, note that for each value J;, due to equation 68 and equation 69 the We,, multivariate Gaussian distribution with covariance Ig. Hence,
conditional distribution of drim
h Fm (We /o... (J.) =d log( 2tre).
(72)
Combining equation and equation
72 gives equation which completes the proof.
H.3 Proof of Theorem 13
Recall that
W = Proj Wh- V. R(V, 015t
where W) A I l (Zi,,, W).
In the proof, to define the lossy compression algorithm Pwiwe,,, ,,,s of Corollary 2 we introduce auxiliary optimization iterations
{wi} (e(T) as follows. Let Wo W/, and for E [T], let
W. Proj W/ V R(,,, ow, 1) + deet + net)
(73)
where st ~ NNs,, Ia) is an additional noise, independent of all other random variables.
In the following Lemma, proved in Appendix H.4 show that, this choice of Pwiw'ee.s e.s,v sutisfies the distortion term equation 16
gS, (WS) gen (W)) Sc.
Ep sav P Wring.
for
2v22 1)/2)
a T-t
T(d/2)
CE
59

---

Lemma 6. The following inequalities holds:
We w/| <
Σ re(t]
a
_ Vr |
and
2V28T((d+ 1)/2)
EPs Pugiison Pwg. s...v
gen(S, @w?)
gen(S, (en(S.WW))
O T- Vt. (E[T]
T(d/2)
Hence, it is sufficient to show that
Epg Payys
gSn OWr)
CV2
S...
Σ L:
A I
bVoo v
iE|n]
Note that the iterations defined in equation 73 are equivalent in distribution to the following iterations:
We =
R OW, + ÖggE
where E, ~ (0,, La) is independent of all other random variables and
Vo +
Similar to the proof of Theorem 10 and by using Corollary 2 is sufficient to show that for fixed V and every fixed [n.] have that
[100 (oo
[s
Sesi. Prrs)) )
C.
Σ
Ar, Ben
1: 1VV
where
CMI AMIV
Wr) 21 (iW.:./WWWW Je)s
Â Vwrk (OW,-1, Vuil (1W)-1
PL, - IP
J; = 0 S, θ, V. Wi-1).
A
II gr.
re(++::T]: igV.
For fixed i E [n). if (t: e V/J} is empty set, then the final model is independent of Jr and hence C (S, Wr) 0, which completes the proof. Now, assume that this set is not empty. For case of notation, suppose that
(t: E V2) = (t.....,tas
where S t1 < 12
<
tm T.
We show by induction on E [M] that, we have
(S, <
Atr. Pr Begi
f
The Dec de bor,
(74)
k5mm
where åe,t and pr., are defined as above and
AlAs
II gr:
rE((+1:01: igV,
with the convention that At's for t' tt
60

---

Once this claim is shown, then we have
T
S. (WWr.
II
S. (Wiscisi)
dr
T
Σ KSM
Abal 18
B A I
(Mh bōen
The Seent
T=(M++
(6)
The Senids Senn))Dant)) )
Ate, Den
bōte
R
where
(a) is achieved by repeated using [74 Lemma 4].
( is derived using equation 74
and (c) holds by definitions of A A and A
Hence, it remains to show that equation 74 holds by induction.
Consider the base of the induction m Note that A 1. Hence, the result follows using the
proof of Theorem more precisely using equation 64 with W - We, De,s + Âe.s. Pt,s + pr,s, and
at - öt.
Now, suppose that the result holds for m = N S M Le..
CMI C. Win)
Σ
N A
B Prn [s
The bār,
Amnii:eens ]:
(75)
rE[N]
where
AN
II +litdd igV,
We show that also holds for N+15 M.
We have
S. (Wi
S ..V
(WIXEL) Wix
S.V. enns J Wen 1) + ....
CEVV(W,, (WeNes 1;
ToNLL S SENTI PeNeLi)) )
+ VVWe..n
bōenen
(b)
MNN+1 AenIIdPrrNnd
< Epinaad
bōeNi1
-N=I-1
II
S.J..... (Weyi.Ji
gr
r=N++1
Epiniid
TeNos DeN bōewss
ANol II Gr
Σ
Atr, Brod
[
Me- bōr,
Denis Der.s ]
r=NN+1
rEIN] [
(
Ep....
The hōr.
Sendi Blooos) ))
where
(a) is derived using the proof of Theorem more precisely using equation 65 with W
W Wine Alms + ÂiN=siis Pimii -> Pl Fia + 6ix.1. and by considering
Fm + V.J. J.J_,. Wix..
61

---

(b) is derived by repeated using of [74] Lemma 4].
holds by the assumption of the induction 75
and (d) by definition of A and A
t.
This completes the proof of the theorem.
H.4 Proof of Lemma
To prove the result, we show first what
We
wil S Σ
D' ur |
(76)
rE|(
using induction over E [7]. Then, using the Lipschitrness property of the loss function, we have that
Prg ww gen(S, @W;) - gen(S,
<29E
Σ
ur
||E!||
LEIT
2v22 + 1)/2)
Σ
T
Mr:
((d/2)
rC[T]
where (a) obtained using the fact that if 3 ~ -N(0, Ia). then ||3]] has a chi-distribution, whose mean is equal to 2 ((d+1)/))
T(d/2)
For t 1,
W3
w1 (0) S
W/o m R + t1s )16t) (Wo m R +1e))
=nn -
where (a) is derived since for any w(, w² E Rdd Proj [w1} - Proj { [wb}] contraction properly of the projection. This shows the base of the induction.
< |w] w/ll. by the
Suppose that equation holds for f'. Now, we show that it also holds for 1' + 1.
Wr41 - W2 W //|
(wr (We-no4iVe
nu V R(Ve+1, θW:) +04114411 + vV4161111)
(W/- nu+1 V R (WMe +
-| (wr We41V Vw ((1HH, (W% - n R(Ve (MMe
2y 165+1
-
(W'- (WW--me -1-1- Well-nn+iwwriV......v (-me
| ||
We Wx
+ + ||
1' - ur ||oil| + vor+1 ||6b
re(e]]
Σ re[U+1]
(1'11)-r ||+l1|
where (a) is derived using the triangle incquality, (b) using the contractility assumption, and (c) using the assumption of the induction. This completes the proof of the induction and the proof of the lemma.
62


Reviews:
[{"review_id": "0ezUerz8uM", "reviewer": "Reviewer_RmaZ", "summary": "This paper studies generalization bounds in stochastic convex optimization (SCO) using information-theoretic measures. While it is known that existing quantities like mutual information (MI) and conditional mutual information (CMI) do not guarantee optimal generalization, this paper proposes a new variant of CMI that achieves the optimal convergence rate. The key idea is to perform dimension reduction via a stochastic projection, such that the low-dimensional compressed model retains similar generalization guarantees to the high-dimensional model.\n\nAs an application, the paper examines the problem of memorization, defined in terms of membership inference or tracing attacks. Recent work (Attias et al., 2024) has shown that for any accurate, sample-efficient, overparameterized model in SCO, there exist distributions where an adversary can trace a constant fraction of the training set. The new bound presented in this paper appears to mitigate, to some extent, the memorization effect.\n\nWhile this result does not contradict existing impossibility results (and the paper does not claim otherwise), it would be helpful if the authors clarified how their results should be interpreted in light of the related literature. Concrete discussion and comparison would improve the paper’s positioning and help avoid potential misunderstandings.\n\nIf these points are clarified and properly discussed, I would reconsider revising my score.", "questions": "Questions for the Authors:\n\nWhat is the exact formal claim made in the paper? In particular, what are the precise order of quantifiers?\n\nHow should we reconcile your results with Attias et al. (2024), which claim:\nFor any learner, there exists a distribution such that there exists an attacker that can trace samples?\n\nDoes the success of your approach rely on randomness in the algorithm that is unknown to the adversary?\n\nWouldn't it be more accurate to say that the adversary traces the data (rather than \"memorizes\")? The learner memorizes, the adversary performs a tracing attack. Clarifying this terminology may help.\n\nHow is your paper related to \"In Defense of Uniform Convergence: Generalization via Derandomization with an Application to Interpolating Predictors\" (ICML 2020)? \nThe proposal in your paper reminds me of the idea of understanding generalization through a surrogate algorithm. In your case, the surrogate operates on the projected data. One could also consider a surrogate that works conditional on the projection, which would align more directly with the surrogate-via-conditioning approach advocated in that work.\n\nMinor: The results at Attias et al. hold true for $d>n^2\\log(n)$ and not $n^4$, but I assume it doesn’t make a difference.", "limitations": "See the above.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\nThe use of random projection to compress the model  based on training data drawn from a distribution is interesting. It shows that under these conditions, information-theoretic methods can achieve optimal convergence rates and mitigate memorization. Overall, the paper is well written, aside from a crucial point of interpretation discussed below.\n\nWeaknesses:\n\nPositioning the result:\n\nIn Attias et al. (2024), the order of quantifiers is: for any accurate, sample-efficient, overparameterized model in SCO, there exist distributions and adversaries such that a fraction of the training data can be traced (i.e., the model memorizes that data).\n\nIn contrast, the present paper claims that for any algorithm A that memorizes, there exists another algorithm A' (the compressed model) that does not memorize and achieves comparable generalization error. However, this appears to hold only for the specific distribution used to construct A', and does not rule out the possibility that a different distribution D' could be adversarially constructed for A'.\n\nIn other words, Attias et al. make a universal claim over learning algorithms, while this paper chooses a favorable algorithm tailored to a given distribution (using information from the distribution to perform compression). This effectively reverses the order of quantifiers, which avoids contradiction but results in a fundamentally different (and weaker) claim. This distinction should be discussed explicitly.\n\nAnother potential explanation, which I suspect is correct, is that the construction of the compressed model involves internal randomness that is unknown to the adversary. If so, the result may hold for randomized algorithms in a way that is compatible with prior impossibility results. Again, this is a subtle but essential point that should be addressed in the paper.\n\nThis issue is especially relevant given the abstract's phrasing:\n\n\"We show that for every learning algorithm and every data distribution, there exists an algorithm that does not memorize and which yields comparable generalization error.\"\n\nWhile this statement is technically accurate, the difference in the game being played compared to prior work is non-obvious and potentially misleading. The main text (e.g., line 352) does soften the claim slightly:\n\n\"... allow to (partly) address this memorization issue, in a sense that will become clearer in the sequel.\"\n\nThis is more precise, but the relationship to prior results is still unclear. A detailed discussion of the interpretation of quantifiers (and perhaps the role of algorithmic randomness) would greatly strengthen the paper.\n\nA similar concern arises in Section 4, which states that the proposed approach \"resolves recently raised limitations of classic CMI bounds.\" While the method does provide a resolution in a certain sense, the conditions under which the bounds are derived are different. The phrase “stochastic projection along with our lossy compression resolves those issues…” seems insufficient. The dependence on the data distribution appears critical and should be made explicit.\n\nAdditional comment:\nThe current construction is existential: it shows that a compressed model with good generalization exists, but it does not provide an explicit or practical method to construct such a model.", "was_revised": true, "final_justification": "POST REBUTTAL:\n\nI believe the ideas in this paper are fundamental and could inspire future work on the role of compression in mitigating privacy issues, particularly in the overparameterized regime. The paper is also clearly written, though the comparison to prior work should be improved—it remains somewhat elusive in the broader context.\nTherefore, I will raise my score to 6 (strong accept).\n\nI encourage the authors to further clarify the presentation, especially regarding how and why the results do not contradict previous findings, as discussed in detail in the response. Clarifying this point would make the contribution more visible and valuable for future research.\nPlease also update the text to reflect that $D$ can grow as $n^2\\log(n)$, rather than $n^4\\log(n)$, since this strengthens the result. It would also be helpful to mention the exact rate at which $D$, should grow to enable memorization in the non-compressible model.\n\nAs additional suggestions, you could expand on the implications for differential privacy and sample compression schemes.\nAnother potentially interesting direction might be to frame your “random” version of the theorem in a game-theoretic language. In this view, the learner could be seen as the first player in a game, selecting a randomized strategy (i.e., the projection matrix) to share with the second player (the adversary)—without revealing the actual realization. Even under this partial information, the learner can still achieve their goal, highlighting the strength of randomization over determinism.", "rebuttal": "We thank the reviewer for the positive feedback and relevant suggestions. As requested, we clarify our contributions and how we think should be positioned with respect to prior work.\n\nFor convenience, this is a summary of our formal claim and how it reconcilies with the impossibility results of Attias et al. (2024). Details will follow.\n\nOur proof of Theorem 7 actually allows two forms for the statement of the result: one that is explicit (the current one), and one that is implicit and can easily be implied by the very same proof. The two statements differ among them through the degree of algorithm randomness that is shared with the adversary and the order of quantifiers.\n* The current statement of Theorem 7 holds for $\\Theta$ being deterministic and shared with the adversary. It asserts that for any learning algorithm $\\mathcal{A}(S)=W$ and data distribution $\\mu$, there exists a suitable projected-quantized model $\\hat{\\mathcal{A}}(S,\\Theta)=\\Theta \\hat{W}$ for which no adversary would be able to trace the data. As correctly observed by the Reviewer, this statement indeed does not preclude the existence of data distributions and adversaries which would be able to trace that data from the output of the new algorithm $\\hat{\\mathcal{A}}(S,\\Theta)=\\Theta \\hat{W}$. Note, however, that the impossibility result of Attias et al. does *not* apply to the new algorithm $\\hat{\\mathcal{A}}(S,\\Theta)$ (see below); and, so, while our result of Theorem 7 in its current form does not rule out the existence of such distributions and adversaries for the new algorithm $\\hat{\\mathcal{A}}(S,\\Theta)$, that of Attias et al. does not guarantee that existence either. \n* Easily implied by the very same proof, a second form of Theorem 7 holds for $\\Theta$ being random and shared with the adversary (not deterministic as for the current statement!); and its statement is exactly that of the current one but with an added extra expectation over the projection matrix $\\Theta$ in the LHS of the inequality (6) -- See the section **Randomized projections and quantization** below).   This alternate form of statement of Theorem 7 asserts that if for a given $W$ a random $\\Theta$ is chosen and **revealed to the adversary**, then the projected-quantized model which uses that $\\Theta$ guarantees that: (i) for **any data distribution**, **no adversary** can trace the data; and (ii) on average over $\\Theta$, the corresponding generalization error is comparable to that of the original model $W$. This means that the order of quantifiers here is the same as for the impossibility result of Attias et al. (2024). \n\nWe hasten to mention that  none of these two forms of statement contradicts the impossibility result of Attias et al. (2024). This is because the result of Attias et al. does *not* apply to our projected-quantized algorithm $\\hat{\\mathcal{A}}(S,\\Theta)$. In particular, athough equally universal the seemingly contracting above alternate statement of Theorem 7 does actually *not* contradict the impossiblity result of Attias et al. (2024). More precisely, their main assumption on the boundednes of model's norm (used in the proof of their Theorem 4.1, e.g., right before equation (12) in the PMLR version of their paper) would require that $\\mathbb{E}\\left[\\|\\Theta \\Theta^\\top W\\|^2\\right]=\\frac{D+d+1}{d}\\|W\\|^2 \\leq 1$, which cannot be statisfied with a dimension $D$ that grows with $n$ as $O(n^4 \\log n)$. The same argument holds for the current statement of Theorem 7.\n\nIf the reviewer agrees with, we will keep the statement of Theorem 7 as is but add in the revised paper a discussion on the order of quantifiers and relation to Attias et al., as well as how a slightly modified form of the statement can be inferred from the very same proof but with a result that holds with the same universality as Attias et al. (2024) and, finally, how/why the result of Attias et al. (2024) applies to none of the two versions of statement.\n\n**On the formal claim, order of quantifiers, and disclosure of the randomness of the algorithm:** Thank you for taking the time to carefully read our paper and write thorough comments. Regarding the randomness, in addition to the standard randomness already present in the process of learning from samples, our method introduces two further sources of randomness: the stochastic projection matrix $\\Theta$ and the quantization noise (the random variable $V_{\\nu}$, see l.1076). Depending on whether these sources are fixed and shared with the decoder or not, Theorem 7 can be stated in slightly different ways, resulting in distinct levels of generality:\n\n- **Partially deterministic (deterministic projection and random quantization):** Theorem 7, as stated now, assumes a fixed projection matrix $\\Theta$ that is known to the adversary, in addition to a random (quantization noise) $V_{\\nu}$ which is unknown to the adversary. The randomness on $V_{\\nu}$ is used merely to properly quantize the projected hypothesis space, as is common in rate-distortion theory literature. Alternatively, one could use a \"fixed\" quantization technique similar to $\\epsilon$-net covering in order to map the projected models to the closest points on the $\\epsilon$-net mesh. However, there would still exists some level of randomness that is unknown to the adversary (related to how such a mapping is performed as the adversary only observes the centroid points on the $\\epsilon$-net). We note that even with common learning algorithms (i.e., in the absence of any stochastic projection and/or lossy compression, such as using standard mini-batch SGD), there are sources of randomness (related, e.g. to the choices of mini-batch size, initialization, and other choices) that are unknown to the adversary.\n\n  For this setting, we show that for any learning algorithm $\\mathcal{A}(S)=W$ and data distribution $\\mu$, there exists a suitable projected-quantized model $\\hat{\\mathcal{A}}(S,\\Theta)=\\Theta \\hat{W}$ for which no adversary can trace the data. Such statement indeed does not preclude the existence of data distributions and adversaries which could trace some amount of the data by directly observing the output of the new algorithm $\\hat{\\mathcal{A}}(S,\\Theta)=\\Theta \\hat{W}$. However, as we argue (see the argument in the above summary in the beginning of this response) the impossibility result of Attias et al. does *not* apply to this new algorithm $\\hat{\\mathcal{A}}(S,\\Theta)$.\n  \n\n\n- **Randomized projections and quantization:** In the actual proof of Theorem 7, we begin by establishing a version of the inequality (6) that holds in-expectation over $\\Theta$. Namely, the same inequality (6) but with an extra expectation over $\\Theta$ in the LHS of the inequality (and, actually, this is the exact argument that we then use to infer the existence of at (least) one value of $\\Theta$ for which the inequality holds without the expectation).\n\nAs a result, Theorem 7 also holds if $\\Theta$ is randomly generated and revealed to the adversary (provided that one adds the mentioned extra expectation over $\\Theta$ in the LHS of (6)). \nFor this setting (i.e., for a given $W$, a random $\\Theta$ chosen and **revealed to the adversary**) we get that the projected-quantized model which uses that $\\Theta$ guarantees that: (i) for **any data distribution**, **no adversary** can trace the data; and (ii) on average over $\\Theta$, the corresponding generalization error is comparable to that of the original model $W$.\n\n  This new statement makes the claim more general and somewhat similar to that of Attias et al. in its universality (which it does not contradict, as explained above), but at the expense of more randomness in designing the learning algorithm.\n\nWe will add these discussions to avoid any confusion. \n\n**On the terminology usage \"tracing vs. memorizing the data:\"**  Indeed; it would be better to refer to the adversary as being able to \"trace or not trace\" the data instead of it memorizing or not that data. We will revise the document using this terminology, which is better. \n\n**On the relation to the prior art ICML 2020 paper \"In Defense of Uniform Convergence: Generalization via Derandomization with an Application to Interpolating Predictors\":** Thank you for pointing out to us the connection with this work, which we were not aware of. In that work, the generalization error of an algorithm is studied indirectly using a \"surrogate algorithm\" and by controlling the distortions induced for the population and empirical risks, in a way that is essentially similar to lossy compression in rate-distortion theory. Note that although there is indeed a high level connection, in our case: (i) the surrogate or lossy algorithm is achieved through suitable stochastic projection (onto a proper smaller dimension space) followed by quantization, not just lossy compression, (ii) the quantization is a very careful one, chosen in a manner that the  generalization error of the surrogate algorithm has comparable generalization error with the original algorithm, and (iii) we accomodate the CMI framework to the used stochastic projection and lossy compression. Nontheless it is indeed useful to the reader to reference this paper, which we will do; and discuss relationship to our work.\n\n**On the order of dimension:** In the latest version of the PMLR paper by Attias et al. (2024), the condition is written as $n^4\\log(n)$. However, as the reviewer mentioned, this ordering does not affect our results.\n\n**Regarding the practical method for constructing the model:** The reviewer is right. However, it should be noted that similar high-probability bounds also hold for the used Johnson-Lindenstrauss projection. This means that if we take a random matrix $\\Theta$ whose entries are chosen i.i.d. from the distribution $\\mathcal{N}(0,1/d)$ then, with high probability, the new algorithm will have comprable generalization error to that of the original algorithm."}, {"review_id": "GcJnRcSHL1", "reviewer": "Reviewer_6JF3", "summary": "This paper proposes new generalization error bound for learning algorithm.\nIt is based on Conditional Mutual Information (CMI) that are made tighter by the joint use of stochastic projection (of model parameters) and the concept of lossy compression.\nThe bound is shown to be non-vacuous in specific problem instances for which MI and CMI bound were vacuous.\nThe paper also investigates the use of this new bound to discuss memorization (and, in appendix, bounds for SG(L)D).", "questions": "To what extent can the bounds be evaluated (e.g., plotted) and used to design new algorithms?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The proposed compressed-projected-CMI approach is, to my knowledge, novel.\nIt provides non-vacuous bound for cases identified as pathological for previous MI-based bounding approaches, advancing the current knowledge on theoretical results.\nThe paper also reads well and the results seem sound.\nIllustrations could have been helpful to help understanding the main concepts (MI, CMI, J, projection and Θ, lossy compression).\n\nRemarks\n\n- the paper might have been cut, there is no conclusion\n\nLocal comments\n\n- l22: \"intrinsic-dimension-\" -> \"intrinsic-dimension\"\n- l53: \"_also_ used in [22], [45]\", [22] is already mentioned just before\n- l83: \"A: Z -> W\" -> \"A: Z^n -> W\"\n- l96: \"j=1,2\" -> \"j=0,1\"", "was_revised": true, "final_justification": "This paper proposes a novel way to derive tight generalization bounds.\nProvided improvements to the exposition are made as discussed with the reviewers, it will be a very strong paper.", "rebuttal": "Thank you for your feedback and positive evaluation: we appreciate you find our approach novel and sound. We have corrected the identified typos. \n\n> \"Illustrations could have been helpful to help understanding the main concepts (MI, CMI, J, projection and Θ, lossy compression).\"\n\nWe agree that illustrations could help clarify these concepts, and observe that such visual aids are generally lacking in the existing literature. If the paper is accepted we will add a diagram that depicts pictorially our approach, i.e., stochastic projection onto a smaller dimension space followed by lossy compression that preserves the generalization; and, on top of all the CMI framework.  \n\n> \"there is no conclusion\"\n\nWe will add the following paragraph as a conclusion section at the end of our paper. \n\n*\"In this work, we revisit recent limitations identified in conditional mutual information-based generalization bounds. By incorporating stochastic projections and lossy compression mechanisms into the CMI framework, we derive bounds that remain informative in stochastic convex optimization, thereby offering a new perspective on the results in [42,43]. Our approach also provides a constructive resolution to the memorization phenomenon described in [43], by showing that for any algorithm and data distribution, one can construct an alternative model that does not trace training data while achieving comparable generalization.*\n\n***Limitations and open questions.** Like prior work on information-theoretic bounds, our analysis applies to stochastic convex optimization. A natural, open question is whether and how these results can be extended to more general learning settings. Another key direction is to translate our theoretical findings into actionable design principles for learning algorithms with controlled generalization and compressibility.\"*\n\n> \"To what extent can the bounds be evaluated (e.g., plotted) and used to design new algorithms?\"\n\nPlease note that our CMI-based generalization bounds are primarily intended as diagnostic tools. A direct major utility of them is to uncover which properties of learning algorithms lead to generalization. But they can of course also be used in the construction of suitable regularizes for new algorithms that are generalization-aware (similar to in [45]). On this latter aspect, we mention that some estimation strategies have been proposed in prior art that can be applied within our framework. For example, the CMI term can be upper-bounded by the KL divergence between the conditional distribution of the parameters given the data and a prior [38] or, for countable hypothesis spaces, by a deterministic (but potentially loose) quantity [§4.1, 10] (see our Section D.2)."}, {"review_id": "pQVzxO3VA7", "reviewer": "Reviewer_KsyD", "summary": "This paper presents a new type of conditional mutual information-based (CMI-based) generalization error bound based on passing a learned, randomized (even conditional on the data) hypothesis $W \\\\in \\\\mathbb{R}^D$ through a low-dimensional projection (via a linear mapping $\\Theta^T$ from $\\\\mathbb{R}^D$ to $\\\\mathbb{R}^d$, passing the result through a possibly randomized procedure $\\\\tilde{\\\\mathcal{A}}$ which again yields a parameter in $\\\\mathbb{R}^d$, and then projecting back to $\\\\mathbb{R}^D$ via the linear mapping $\\\\Theta$. The authors refer to their procedure as \"quantization\". The first main result shows a generalization error bound for a quantized hypothesis which has on its RHS the disintegrated CMI of the parameter produced (prior to projecting back to $\\\\mathbb{R}^D$) with a sequence of binary indices (indicating which elements from a double sample of size $2n$ were included in the training set of size $n$), all conditional on the realization of the double sample and the realization of $\\\\Theta$ (which itself can be random). Importantly, the quantized hypothesis has the property that it upper bounds the generalization error of the original hypothesis up to an additive $\\\\varepsilon$, allowing us (up to $\\\\varepsilon$) extend the generalization error bound for the quantized hypothesis to a generalization error bound for the original hypothesis.\n\nSeveral counter-examples from recent prior works have shown apparently strong limitations of CMI-based generalization error bounds, essentially showing that in high-dimensional settings ($D$ of order $\\\\Omega(n^4)$ or larger) that are potentially of interest, previous CMI-based generalization bounds become useless. For these settings, which include convex Lipschitz bounded stochastic convex optimization (SCO) problems and strongly convex Lipschitz SCO problems, the authors show that their new bounds provide meaningful generalization error guarantees. The authors also give results for a rather general, potentially non-convex setting that they call \"generalized linear stochastic optimization problems\". Finally, they give results related to memorization, showing that discretization can fight memorization.", "questions": "1. In lines 234–235, I wish for more explanation for the claim that the authors dimension reduction technique being lossy implies that they additionally need lossy compression of the algorithm to get the desired result. Can you explain more here? (just a few sentences should be fine; don't go overdo it!)\n\n2. Does my interpretation of the results of Section 5 (Memorization) match up with your own, that is, (see $\\\\textcolor{blue}{\\\\bigstar}$ from Strengths and Weaknesses), memorization is not necessary for generalization?\n\n3. On Line 275: \"unlike the CMI bound of [11]\" should be \"unlike the MI bound if [11]\"?\n\n4. In Section 5, in Theorem 7, in point **ii)**, I was unsure of what algorithm (original vs discretized) the authors had in mind when they wrote \"an adversary which $(m, q, \\\\xi)$-memorizes the data\". Which is it, original or discretized?", "limitations": "I think it's fine. This work is mostly about circumventing limitations, so it would be a bit much to heavily emphasize limitations of the authors' circumventing of limitations.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "## Pros\n\nOverall, the paper is written very clearly until just before Section 5 (Memorization). Given all of the complexity of what the authors are doing (with many variables, stochastic kernels, etc.), the authors did a great job in making the mathematical presentation understandable. Also, the English descriptions to give interpretation to the various results helped a lot.\n\nI really like the idea of this work. It is quite natural to consider using some type of lossy, noisy model compression in order to get much-improved generalization error bounds, but this of course can only be useful if the compression is able to faithfully describe the original model of interest. In this case, the authors measure this \"faithfulness\" according to difference in generalization error. They succeeded in using a standard idea of linearly mapping to a low-dimensional space, along with some additional ingredients, to get a CMI-based generalization error bound that applies to the original hypothesis (not just the compressed model). This is nice. Also, the authors noticed that some previous negative results for CMI-based generalization error bounds seem to heavily rely on having dimension of order $n^4$ or larger, which suggests trying to \"take care of the dimension\" via a low-dimensional mapping.\n\nAt first, one might say that the impact of this work is narrow due to its focus (in Section 4) of circumventing limitations of CMI bounds, limitations that were shown for high-dimensional settings. However, these limitations can be viewed as a sign of a problem with the bounds as used thus far, and the authors \"knocking out\" these limitations is a sign of a better path, specifically, a better way to witness the power of CMI bounds.\n\nTo be honest, I did read all of Section 4, and it was clear to me. The discussion from the authors was good. I don't really have any major comments here. One quibble (which I keep here rather than under \"Cons\" since it's minor) is that in lines 234–235, I wish for more explanation for the claim that the authors dimension reduction technique being lossy implies that they additionally need lossy compression of the algorithm to get the desired result. I'll repeat this as a question in the Questions section.\n\nI appreciate the authors mentioning technical challenges in the main text and hinting at proof techniques. I'm guessing this paper would have worked better as a COLT paper, where the authors could take the space (in the main text) to explain more about how they specifically addresses technical issues (like getting Theorem 4, which sounds very interesting, but due to time I could not look at the appendix to see how the authors pulled off this result).\n\nThe results on memorization seem interesting. I did not have as good of a grasp (but still a reasonably ok grasp) on this section and felt the paper already was strong enough without this section, so I place somewhat less weight on this section in my review. Regarding the results on memorization, if I understand correctly, we can view Theorems 6 and 7 as being a critique on using memorization as a perspective on generalization. This is because an original algorithm might memorize (in some meaningful way, i.e, $m = \\Omega(n)$ and suitably small $\\xi$ and suitably large $q$), whereas a discretized algorithm can fail to memorize; the latter then can be shown to have good generalization properties, and those properties transfer to the original algorithm. Hence,  $\\\\textcolor{blue}{\\\\bigstar}$ memorization is not necessary for generalization.\n\n\n## Cons\n\nI have to say that Section 5, Memorization, is very interesting. However, packing it all into 2 pages, including the sophisticated Recall Game, giving an appreciation for what a suitable benchmark performance level should be, etc. just feels like too much. As a result, this section suffers. For example, in the paragraph immediately after Lemma 1, there is a confusing sentence regarding \"every one of the following requirements taking separately\". I interpret the authors as saying that for any one of the requirements, there exists an adversary that satisfies the requirement (given the authors' emphasis on \"separately\"), but I am still not sure and this could have been presented better. Assuming my interpretation is correct, then point **i)** is trivial since an adversary that always outputs $0$ is $0$-sound, and point **ii)** is trivial since an adversary that always outputs $1$ will recall $m = n$ samples with probability $q = 1$. And then points **iii)** looks the same as condition **i)** from the statement of Lemma 1. I guess the only thing worth spending space on is clarifying the interpretation of **iv)**.\n\nAlso in Section 5, in Theorem 7, in point **ii)**, I was unsure of what algorithm (original vs discretized) the authors had in mind when they wrote \"an adversary which $(m, q, \\\\xi)$-memorizes the data\".\n\n\n\n## Minor comments\n\nOn line 96, $j = 1, 2$ should be changed to $j = 0, 1$\n\nIn Theorem 1, it may be helpful to explicitly clarify that $W \\\\mid \\\\mathbf{\\\\tilde{S}}$ means that $W$ is trained on the entire double sample $\\\\mathbf{\\\\tilde{S}}$ as this is the only time in the paper (as far as I can tell) that you do this. Other places all train on $n$-samples rather than a $2n$-sample.\n\nIn the statement of Theorem 1, first math display, the notation $\\\\mathcal{A}^{(d)}$ was never defined. I infer that it is the algorithm's hypothesis obtained via \"quantization\" (stochastic projection and lossy compression).\n\nLine 275: \"unlike the CMI bound of [11]\" should be \"unlike the MI bound if [11]\"? (I didn't think [11] considers CMI bounds as those were unveiled in a concurrent work by different authors)", "was_revised": true, "final_justification": "I am satisfied with the authors' responses to me. Initially, I had some concerns due to points raised by Reviewer RmaZ regarding order of quantifiers, etc. I can see that this reviewer is satisfied with the authors' response and is in fact more positive on this work now. That is good enough for me (I initially did not have these concerns); I appreciate the nuance here (sorry for the vagueness of this statement).  This is a solid paper which I would like to see accepted.", "rebuttal": "Thank you for your careful reading and positive rating. We are grateful for your detailed comments in the 'Pros' section, and your appreciation of our results and discussion. \n\n> \"Section 5, Memorization, is very interesting. However, packing it all into 2 pages ... just feels like too much.\"\n\nWe acknowledge that Section 5 is dense, and we have revised it to improve readability. Based on your comment, we made the discussion after Lemma 1 more concise and to the point (see details below). Additionally, we have shortened Section 4.4 and move part of its content to the appendix. This allows us to add more background on the recall game. We hope these changes improve clarity, and we would be happy to receive any further suggestions you may have on this section. \n\n> \"after Lemma 1, there is a confusing sentence\"\n \nThe reviewer's interpretation is correct, and we agree that sentence could be much clearer. We also agree that the first three cases are trivial. These were included for two reasons: to provide simple examples of the recall game that help readers build intuition; to emphasize that considering the soundness or recall criterion alone is not sufficient. For instance, it is possible to achieve either $\\xi = 0$ or $q = 1$, or both small $\\xi$ and large $q$ when $m=o(n)$. Therefore, an adversary is considered good if it achieves a small $\\xi$ or large $q$ simultaneously, with a non-negligible value of $m$. \n\nRegarding  (iii), stating $\\xi \\geq q$ is \"achievable\" is highlighted because Theorems 6 and 7 show that when $m$ is not $o(n)$ and $\\mathsf{CMI}(\\mu,{\\mathcal{A}_n}) = o(n)$, no adversary can outperform a \"dummy\" adversary.\n\nBased on your feedback, we will thus rephrase lines 333-339 as follows: \"In particular, Lemma 1 shows that even a dummy adversary can  $(m,q,\\xi)$-trace the data in several cases: when $\\xi$ is small, when $q$ is large, when $\\xi \\geq q$, or when $\\xi$ is small $q$ is large, provided that $m=o(n)$ and there exists a subset $\\mathcal{B}\\subseteq \\mathcal{W}$ such that $\\mathbb{P}\\left(W \\in \\mathcal{B}\\right)=1-\\xi$. Hence, $(m,q,\\xi)$-memorization does not always translate ... \"\n\n**Minor comments:** Thank you for your thorough comments: we have corrected the typos in l.96 and 275, and we provide further clarifications on your other points below.\n\n> \"In Theorem 1, it may be helpful to explicitly clarify that $W | \\tilde{\\mathbf{S}}$ means that $W$ is trained on the entire double sample $\\tilde{\\mathbf{S}}$\"\n\nThis notation actually refers to a random variable drawn from the conditional distribution $P_{W | \\tilde{\\mathbf{S}}} = \\mathbb{E}_{P_{\\mathbf{J}}}[P_{W |\\tilde{\\mathbf{S}}_\\mathbf{J}}]$ (as in l.1055). Therefore, $W$ is in fact trained on $n$ samples (not $2n$). We thank you for pointing out this ambiguity, and will clarify it in the statement of Theorem 1.\n\n> \"In the statement of Theorem 1, first math display, the notation $\\mathcal{A}^{(d)}$ was never defined.\"\n\nWhile your interpretation of $\\mathcal{A}^{(d)}$ is correct (see the definition in Section B, l.941), it should not appear in Theorem 1: the correct notation here is $\\mathcal{A}$. We have now fixed it. We emphasize that this typo does not affect our results and conclusions.\n\n**Questions:**\n\n1. Thank you for pointing this out, we realize that our writing was ambiguous. There are two sources of distortion in our framework: \n(i) the (stochastic) projection from a high- to low-dimensional space, which is inherently lossy, \n(ii) a second, intentional lossy compression step applied *after* projection. \n\n   The reason for step (ii) is that, in order to control the distortion introduced by step (i) (projection), we follow a standard approach inspired by lossy source coding. This helps us obtain quantized representations that are easier to analyze and leads to tighter bounds. This procedure is analogous to $\\epsilon$-net covering.\n\n   We will revise l.234-235 as follows: *\"Since this dimension reduction technique is lossy, controlling the induced distortion is essential. To do so, we introduce an additional lossy compression step by adding independent noise in the lower-dimensional space. This approach is inspired by lossy source coding and allows us to obtain tighter bounds on the quantized, projected model.\"*\n\n2. Your interpretation aligns with ours. Our results show that an adversary's ability to memorize or trace training data from the learning model does not necessarily imply poor generalization: one can construct a quantized, projected representation of the model with similar generalization error that does not memorize the data.\n\n3. Indeed, we have fixed the typo, thank you!\n \n4. Thank you for your careful reading: we meant the discretized model, so $W$ should be replaced by $\\Theta \\hat{W}$ in Theorem 7(ii). We have corrected this typo."}, {"review_id": "phroSR7Crd", "reviewer": "Reviewer_9s6T", "summary": "This paper presents tighter conditional mutual information (CMI) bounds by using random projection and lossy compression. The motivation is to address known limitations of previous CMI-based generalization bounds in certain stochastic convex optimization (SCO) problems. Specifically, previous CMI bounds fail to explain the learnability of some SCO settings because the CMI term scales explicitly with the dimension $D$ of the hypothesis space, while the actual generalization error in these problems can be dimension-independent. As a result, in overparameterized regimes (e.g., $D>n$), such CMI bounds do not vanish as the sample size n increases.\n\nTo overcome this issue, the authors propose compressing the hypothesis through random projection and lossy encoding. This leads to new generalization bounds where the error is upper bounded by the CMI of the compressed model, plus an additional term quantifying the generalization gap between the compressed and original models. Although the CMI term still depends on the compressed dimension $d$, this dimension corresponds to a subspace of the original hypothesis space and can be chosen arbitrarily, e.g., $d=1,\\Theta(\\sqrt{n}), n^{1-r}$, to ensure that the bound vanishes with n. Consequently, the proposed CMI bounds successfully capture the learnability of SCO problems that elude explanation under standard CMI analysis.\n\nMoreover, the authors apply their bounds to the memorization game and demonstrate that the compressed models achieve strong generalization without exhibiting memorization.", "questions": "1. While I generally enjoyed reading this paper and believe it deserves acceptance, I do have some concerns regarding the claim about the \"inherent limitation\" of the CMI framework. Specifically, is it possible to directly bound the generalization error of $\\mathcal{P}_{cvx}^{(D)}$ without relying on the CMI framework? My concern is that bounding the $\\epsilon$ term in your result seems to require a level of effort comparable to directly bounding the generalization error itself. If this is indeed the case, then although the dimensional dependence of the CMI term is now controllable via compression, the practical utility of your CMI bound remains unclear without an explicit control over $\\epsilon$, which again seems to require similar efforts on bounding the generalization gap. In this sense, is it really accurate to claim (as in Line 54) that \"the aforementioned limitations are not inherent to the CMI framework\"?\n\nPut differently, while this work successfully mitigates the dimensional dependency of the CMI term, the framework still relies on the additional control of the generalization gap between the compressed and uncompressed models. Since this requires nontrivial analysis, one might argue that the fundamental limitation of CMI, as a generalization measure, still persists, albeit in a more manageable form.\n\n2. Regarding Theorem 4, would it be possible to provide the order-wise behavior of the actual generalization error in a concrete example? This would help clarify whether the $\\mathcal{O}(1/n^{1/4})$  bound is sufficiently tight and informative as a generalization measure in practice.\n\n3. Please clarify how Theorem 7 supports the claim that the auxiliary model $\\Theta\\hat{W}$ is not vulnerable to memorization. In particular, part (ii) of the theorem seems unrelated to the auxiliary model, and it is unclear how the conclusion follows from the stated result.", "limitations": "Yes, the authors mention certain limitations in the checklist. I would like to raise an additional point: the proposed CMI bounds are primarily designed for parameterized models. In contrast to works such as [2–4], the framework does not naturally extend to non-parameterized models, which may be considered a potential limitation.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The main strength of this paper is straightforward: the proposed CMI bounds successfully address the counterexamples raised in previous works on SCO, where earlier CMI-based generalization bounds fail to vanish.\n\n2. The paper provides an insightful result that, for a learning algorithm using compression, memorization might not be necessary to achieve strong generalization performance. \n\n**Weaknesses:**\n\n1. Regarding Theorem 7, it is unclear why the auxiliary (compressed) model is considered not vulnerable to memorization.  In particular, part (ii) of the theorem appears unrelated to the auxiliary model $\\Theta\\hat{W}$.\n\n2. The following are not significant weaknesses but rather suggestions for improvement:\n\nThe clarity of some claims, particularly in the introduction, could be improved. For example, the first listed contribution states: \"we use them to establish a new CMI-based bound that is generally tighter than existing ones.\" However, \"existing ones\" are not specified, and Section 3 does not formally justify the claim that the proposed bounds are generally tighter than all previous CMI variants before discussing the counterexamples. Notably, several other CMI-based bounds, such as chained CMI bounds [1], evaluation-based bounds [2–4], are not shown to fail on the counterexamples from Attias et al. (2024) and Livni (2023). While Theorem 1 is clearly tighter than classic hypothesis-based CMI bounds, and while techniques from [1–4] may be extendable to Theorem 1, the introduction should clarify its scope to avoid overstating generality.\n\n[1] Hafez-Kolahi, Hassan, et al. \"Conditioning and processing: Techniques to improve information-theoretic generalization bounds.\"NeurIPS 2020.\n\n[2] Harutyunyan, Hrayr, et al. \"Information-theoretic generalization bounds for black-box learning algorithms.\" NeurIPS 2021.\n\n[3] Hellström, Fredrik, and Giuseppe Durisi. \"A new family of generalization bounds using samplewise evaluated CMI.\" NeurIPS 2022.\n\n[4] Wang, Ziqiao, and Yongyi Mao. \"Tighter information-theoretic generalization bounds from supersamples.\" ICML 2023.\n\nIn addition, below are some additional relevant references:\n\nThe use of (input-output) mutual information to evaluate memorization has been studied from a different angle in:\n\n[5] Brown, Gavin, et al. \"When is memorization of irrelevant training data necessary for high-accuracy learning?.\" STOC 2021.\n\nThe idea of applying model compression to obtain improved information-theoretic generalization bounds has also been explored in:\n\n[6] Bu, Yuheng, et al. \"Information-theoretic understanding of population risk improvement with model compression.\" AAAI 2020.\n\nTighter variants of CMI bound in the context of some CLB problems are also studied in:\n\n[7] Wang, Ziqiao, and Yongyi Mao. \"Sample-conditioned hypothesis stability sharpens information-theoretic generalization bounds.\" NeurIPS 2023.", "was_revised": true, "final_justification": "I recommend accepting this paper without reservation.", "rebuttal": "We thank the reviewer for the positive rating and feedback. We are glad that they enjoyed reading the paper and answer their questions below. \n\n**Question 1.** This is a good and valid point: one could indeed question whether the fact that our approach yields bounds with the desired behavior truly implies that the limitations are not inherent to the CMI framework, especially given the technical work required to make CMI successful, as the reviewer noted.\n\nNonetheless, we would like to maintain this claim for two main reasons:\n* First, while the machinary of suitable stochastic projection and lossy compression is indeed essential (notably, the way we control simultaneously the projection dimension and incurred distortion in the generalization error of the projected-quantized surrogate model), our final bounds are still within the CMI framework (not from another one).\n* Second, although seemingly so, the core analysis is not excessively more complex. In particular, when controlling the distortion $\\epsilon$ induced by the compression, we do not need to account for the statistical dependencies between the original model $W$ and the data $S$, which simplifies the bounding steps. We elaborate on this point below. \n\nThe main difficulty in bounding the generalization error of stochastic learning algorithms is essentially due to the dependence of $W$ on $S$. Otherwise, bounding the generalization error would reduce to a classical concentration problem, e.g., for a fixed model. A common approach to overcome this difficulty is the change-of-measure trick, which comes at the expense of, e.g., a KL-divergence term. MI and CMI bounds fall into this category of approaches.\n\nOur general framework consists of two main steps: i) we apply projection-quantization to the original model and study the induced distortion, then ii) we study the generalization error of the projected-quantized model.\n\n*Step i:* We consider the expected difference of the generalization errors for $W$ and $\\Theta \\hat{W}$. Since we construct $\\hat{W}$ suitably from $\\Theta^\\top W$, **we do not need to account for the dependence between $W$ and $S$** at this stage. Instead, the analysis involves developing expected concentration bounds by taking expectations over three sources of randomness: **the projection matrix** ($\\Theta$), **quantization noise** ($V_{\\nu}$, see l. 1076), and the **empirical deviation of the distribution of $S$ from $\\mu$**. As shown in the proofs, the analysis of the distortion term often **reduces to classical concentration problems with well-known (near)-tight bounds**.\n\n*Step ii:* We then consider the joint distribution of $(S,\\Theta \\hat{W})$, and leverage CMI to establish generalization bounds. Projection-quantization reduces the dependence between the model and training data.\n\nIn short, our approach decomposes the generalization error into two components, where the first can often be bounded near-optimally using classical concentration techniques.\n\nThat said, we agree with the reviewer that the statement that our claim \"the aforementioned limitations are not inherent to the CMI framework\" may be questioned by readers, so we will add this discussion to clarify this point accordingly. \n\n\n**Question 2.** Theorem 4 is primarily given to show that there are no counterexamples to our extended CMI bound of Theorem 1, not even within the broader class of generalized linear stochastic optimization. Regarding the order of the bound in Theorem 4, we acknowledge that it is likely suboptimal and conjecture that a refined analysis could achieve a rate of $\\sqrt{\\log(n)/n}$. The intuition is as follows.\n\nAs stated in our response to Question 1, analyzing the distortion requires bounding some expectations over the randomness on the projection-quantization and the dataset. However, the current distortion analysis in the proof of Theorem 4 only averages over the projection-quantization randomness and considers the worst-case scenario among all data samples. We think that a more refined analysis, which incorporates a concentration bound related to the deviation of empirical distribution of $S$ from $\\mu$, could lead to a better rate. We will include this discussion in the paper.\n\n**Question 3.** This is actually a typo: $W$ should read $\\Theta \\hat{W}$. Thank you for pointing it out. \n\n**On the extension to other variants of CMI:** Thank you for these suggestions and for pointing us these additional references. We agree that the wording in our introduction lacks precision, and we understand it may overstate the scope of our results. As you correctly note, our intention was to emphasize that Theorem 1 improves upon standard CMI bounds. We did not mean to imply that it dominates all the proposed variants, especially since, to the best of our knowledge, those approaches have not been explicitly shown to fail on the counterexamples of Attias et al. (2024) and Livni (2023). \n\nWe will thus revise the introduction accordingly. More precisely, we will clearly state that our bound improves on standard hypothesis-based CMI bounds in a provable sense; acknowledge that other CMI variants, such as those you referred in [1–4] are not directly addressed in our paper. \n\n**Limitations:** Indeed, the CMI framework applies to parameterized models. We will add this potential limitation in the checklist."}, {"review_id": "A3JsrS1Odn", "reviewer": "Reviewer_UwxD", "summary": "This paper aims at improving the well-established conditional mutual information (CMI) generalization bounds. The main idea is to apply the CMI bounds to a compressed parameter that has been obtained via stochastic projection. In this context, the obtained generalization bounds is the sum of two terms: (1) a loss compression constant, measuring how the generalization errors of the compressed and uncompressed learned parameters differ, and (2) a CMI bound on a lower-dimensional space, on which the parameter has been projected. In order to show that this strategy yields tighter generalization bounds, the authors apply it to several counter-examples of the classical CMI bounds, that have been recently proposed by Livni (2023) and Attias et al. (2024). In these classes of simple optimization problems, the authors obtain better convergence and sample complexity, hence, beating the proposed counter-examples. The last part of the paper is dedicated to the application of lossy compression and stochastic projection to the problem of memorization, ie, the ability of an adversary to guess which data points have been used in training. For one of the problem classes studied above, it is shown that these techniques allow to construct algorithms that are robust to memorization and, yet, have similar generalization error as their uncompressed counterpart.", "questions": "- In most of the counter-examples, the constructed data distribution seems to depend on $n$, which seems restrictive compared to the practice. Are there counter-examples for which it is not the case and where you new bound are tighter? In particular, an example in the style of Section 4.1 would be more convincing with data distributions that do not depend on $n$. \n- In section 5, you find alternate learning algorithms with comparable generalization error but which do not memorize the dataset. Is it also possible to show the same alternate algorithm have similar empirical risk, ie, do they have similar overall performance (population risk)? Indeed, this is waht practitioners really care about.\n- Is it possible to demonstrate that the new bounds are tightest on a more complex problem class than the ones that are studied in the main text? The same quesion holds for memorization in Section 5.", "limitations": "The limitations could be discussed more precisely. For instance, adding a conclusion paragraph to summarize the limitations of the work would be helpful.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n- The proposed approach is very general. While stochastic projection has already been used in mutual information bounds, the authors successfully apply it the CMI framework and combine it with lossy compression.\n- The new framework addresses the counter-examples of the CMI bounds found in earlier studies. Therefore, the proposed bounds are arguable tighter.\n- In addition to providing tighter generalization bounds, the same techniques (stochastic projection and lossy compression) can be used to address the vulnerability to memorization, at least in simple examples.\n- The literature review in the introduction is quite complete.\n\n\n**Weaknesses:**\n\n- Despite addressing several known counter examples, the interest of the new bounds is only assessed on very simple settings (linear, quandratic). \n- In the abstract, applications to randomsubspace algorithms, SGD and SGLD are mentioned but these are not discussed in the main text.\n- The main paper ends abruptly, in particular there is no conclusion to discuss the potential limitations and future works.\n\n**Other remarks**\n\n- I think some notations have not been introduced, for instance: $M_1(Z)$. Also $A^{(d)}$ has not been defined in theorem 1, is it a typo?\n- When the data distribution $\\mu$ depends on $n$, maybe it should be denoted $\\mu_n$, to make it explicit.", "was_revised": true, "final_justification": "During the rebuttal, most of the points raised in the review were addressed by the authors. In particular there were discussions about the counter-examples involving data distributions that depend on the sample size. I understand that this is something that has been previously introduced in the literature and it is not the aim of this paper to address this particular point.\n\nI still have a positive opinion on the paper and I will keep my score.", "rebuttal": "Thank you for your comments and positive rating.\n\n**Weaknesses**\n\n> \"Despite addressing several known counter examples, the interest of the new bounds is only assessed on very simple settings (linear, quandratic).\"\n\nWe appreciate the opportunity to clarify the motivation and contribution of our paper. Our work focuses on stochastic convex optimization (SCO), a commonly used framework in theoretical machine learning, in particular for rigorously analyzing generalization in overparameterized models. SCO encompasses classical algorithms such as (stochastic) gradient descent, and is not limited to linear or quadratic losses.\n\nFollowing [42, 43], we considered linear/quadratic losses in order to derive fully explicit and tight bounds. These setups are simple yet nontrivial, and allow for rigorous derivations that reveal concrete insights into generalization, compressibility, and memorization. This strategy allows us to precisely characterize certain phenomena and illustrate our main theorems, which are of the form: *there exists an instance in the class of SCO such that the generalization bound exhibits a specific behavior.* These examples should therefore be considered as concrete instances where our analysis and discussion apply, rather than as restrictions of the general SCO framework. \n\nThat said, linear losses are not the only ones we considered: in Section 4.4, we go beyond them by analyzing generalized linear models, which form a larger, nonlinear class. Given that computations and proofs are already nontrivial in the setings we cover, exploring richer nonlinear instances remains an interesting yet challenging research direction.\n\n> \"In the abstract, applications to random subspace algorithms, SGD and SGLD are mentioned but these are not discussed in the main text.\"\n\nThank you for pointing this out. We will remove the last sentence of the abstract to clarify the main text's content, but we will still refer to these applications at the end of our introduction.\n\n> \"The main paper ends abruptly\" \n\nWe will add the following paragraph as a conclusion section at the end of our paper. \n\n*\"In this work, we revisit recent limitations identified in conditional mutual information-based generalization bounds. By incorporating stochastic projections and lossy compression mechanisms into the CMI framework, we derive bounds that remain informative in stochastic convex optimization, thereby offering a new perspective on the results in [42,43]. Our approach also provides a constructive resolution to the memorization phenomenon described in [43], by showing that for any algorithm and data distribution, one can construct an alternative model that does not trace training data while achieving comparable generalization.*\n\n***Limitations and open questions.** Like prior work on information-theoretic bounds, our analysis applies to stochastic convex optimization. A natural, open question is whether and how these results can be extended to more general learning settings. Another key direction is to translate our theoretical findings into actionable design principles for learning algorithms with controlled generalization and compressibility.\"*\n\n**Other remarks**\n\n> \"I think some notations have not been introduced, for instance: $M_1(Z)$.\" \n\nThank you for noting this: $M_1(Z)$ denotes the set of probability measures on $Z$. We will precise it in Definition 3.\n\n> \"Also $A^{(d)}$ has not been defined in theorem 1, is it a typo?\" \n\nThis is indeed a typo: the correct notation is $\\mathcal{A}$.\n\n> \"When the data distribution $\\mu$ depends on $n$, maybe it should be denoted $\\mu_n$\" \n\nFor readability, we chose to omit this dependence in the notation. We acknowledge this may cause some confusion and will thus clarify this choice at the beginning of Section 3.\n\n**Questions**\n\n> the constructed data distribution seems to depend on $n$, which seems restrictive\n\nWe agree that this is a relevant question, and note that this restriction is not specific to our work. To the best of our knowledge, there is no counter-example in the literature where the data distribution and dimensionality do not depend on $n$. This dependence seems crucial in existing approaches, including in Attias et al. (2024), where counter-examples involve (C\\)MI terms that grow with $D$. Intuitively, the higher $D$, the more likely one finds a coordinate that makes the training and test data distinguishable. Therefore, to obtain bounds that shrinks with $n$ increasing, it is typically necessary for $D$ to grow faster than $n$.\n\n> Is it also possible to show the same alternate algorithm have similar empirical risk\n\nWe can indeed provide additional guarantees on the population risk of the projected-quantized model in Theorem 7. Based on your feedback, we were able to show that for any $r< 1/2$, there exists an auxiliary model $\\Theta \\hat{W}$ that cannot trace data and such that \n$$|\\mathbb{E}\\_{P_{S_n,W}P_{\\hat{W} | \\Theta^T W}}[\\mathcal{L}(W) - \\mathcal{L}(\\Theta \\hat{W})] | \\leq \\mathcal{O}(n^{-r}),$$\nwhich is achieved with $d=n^{2r}$. \n\nAlternatively, for any $r\\in[R]$, we can guarantee the existence of an auxiliary model $\\Theta \\hat{W}$ that cannot trace data and satisfies\n$$\\mathbb{E}\\_{P_{S_n,W}P_{\\hat{W} | \\Theta^T W}}[\\mathcal{L}(W) - \\mathcal{L}(\\Theta \\hat{W})] \\leq \\mathcal{O}(n^{-r}),$$\nachieved for $d=r\\log(n)$. \n\nThe proof closely follows that of Theorem 7, with a slight modification: $\\bar{Z}$ is replaced by $Z$, which results in convergence rates roughly $\\sqrt{n}$ larger than the current ones. For example, in the first case, this strategy yields\n$$\\mathbb{E}\\_{\\Theta}\\big[\\big|\\mathbb{E}\\_{\\hat{W}, W, S_n}[\\mathcal{L}(W)-\\mathcal{L}(\\Theta \\hat{W})] \\big|\\big] \\leq e^{-0.21 d(1-c_w^2)^2} + \\mathcal{O}(d^{-1/2}),$$\nwhich is in $\\mathcal{O}(n^{-r})$ for $d=n^{2r}$. Furthermore, since $r<1/2$,\n$$\\mathsf{CMI}^{\\Theta}({\\mu},\\hat{\\mathcal{A}}) \\leq d \\log\\left(\\frac{c_w+\\nu}{\\nu}\\right) = o(n)$$\nwhich completes the proof.\n\nWe thank the reviewer for raising this interesting question, which has helped us extending our results. We will incorporate the above discussion in the paper.\n\n> \"Is it possible to demonstrate that the new bounds are tightest on a more complex problem class?\"\n\nThis is a natural and interesting question. Currently, we have not formally established that our bounds are tightest for more complex problem classes beyond those studied in the main text, and we view this as a direction for future work.\n\nThat said, despite its simple characterization, we emphasize that stochastic convex optimization already captures relevant aspects for overparameterized models. It also enables nontrivial analytical derivations and encompasses standard algorithms in modern ML (e.g., stochastic gradient descent and accelerated variants). These explain its popularity in theoretical ML research. We refer to [42, 43] for detailed explanations and references.\n\nRegarding memorization (Section 5), we also focused on SCO to allow clear theoretical analysis and to align our setting with that of [43], since our primary goal was to demonstrate the value of incorporating compression in their analysis. Extending both analyses ([43] and ours) to more complex function classes, such as non-convex losses or deep networks, would indeed be a valuable extension."}]

Author rebuttal:

Meta-review: This paper establishes new algorithm-dependent generalization bounds for stochastic convex optimization, based on a variant of conditional mutual information (CMI) involving stochastic projections.  The new bounds are applicable to natural scenarios where previous CMI bounds are known to be inapplicable.  They further use these bounds to explore issues concerning avoiding the need for "data memorization" for certain learning problems, contrasting with recent work on the subject.

It is now well-understood that techniques for algorithm-dependent analysis are necessary for understanding generalization in overparameterized regimes.  CMI is a natural framework for approaching such algorithm-dependent analysis.  However, previous attempts to use CMI to understand generalization yielded negative results in high-dimensional problems.  This new definition breaks through such limitations, showing this variant of CMI can establish generalization guarantees for stochastic convex optimization in such scenarios, thus demonstrating this as a promising technique for algorithm-dependent analysis.

Reviewers all agree that the results are novel and important, shedding light on topics currently of high interest to the community.  

Reviewers praise the clarity of writing in the paper, with only a few spots as exceptions.

The discussion between authors and reviewers (RmaZ) was enlightening, concerning why the new results on avoiding data memorization do not contradict prior works showing necessity of data memorization, and the authors have indicated they will expand upon this explanation in the final version of the paper.
Decision: Accept (oral)