Information Theoretic Lower Bounds for Information Theoretic Upper Bounds
Authors: Roi Livni
Venue: NeurIPS 2023 poster (2023)
Keywords: Learning Theory
TL;DR: Every learner in stochastic convex optimization must carry dimension dependent bits of information over the data set

Abstract: We examine the relationship between the mutual information between the output model and the empirical sample and the algorithm's generalization in the context of stochastic convex optimization. Despite increasing interest in information-theoretic generalization bounds, it is uncertain if these bounds can provide insight into the exceptional performance of various learning algorithms. Our study of stochastic convex optimization reveals that, for true risk minimization, dimension-dependent mutual information is necessary. This indicates that existing information-theoretic generalization bounds fall short in capturing the generalization capabilities of algorithms like SGD and regularized ERM, which have dimension-independent sample complexity.

Information Theoretic Lower Bounds for Information Theoretic Upper Bounds
Roi Livni
Department Electrical Engineering Tel Aviv University rl rlivni@tauex. tau.ac... ac.
Abstract
We examine the relationship between the mutual information between the output model and the empirical sample and the generalization of the algorithm in the context of stochastic convex optimization. Despite increasing interest information- theoretic generalization bounds, it uncertain if these bounds can provide insight into the exceptional performance of various learning algorithms. Our study of stochastic convex optimization reveals that, for true risk minimization, dimension- dependent mutual information is necessary. This indicates that existing information- theoretic generalization bounds fall short in capturing the generalization capabilities of algorithms like SGD and regularized ERM, which have ciinension-independdee sample complexity.
Introduction
One of the crucial challenges facing contemporary generalization theory is to understand and explain the behavior of overparameterized models. These models have a large number of parameters compared to the available training examples. But nonetheless, they tend to perform well on unseen test data. The significance of this issue has become that many state-of-the-ar Icarning algorithms are highly overparameterized Neyshabur et al. [2014), Zhang et al. [2021]. The classical generalization bounds, which are well designed to describe the learning behavior of underparameterized models, seem to fail to explain these algorithms.
pronounced in recent years, it has become evident
Understanding the success of overparameterized models seems challenging. Partly, due to the counter-intuitive nature the process. Common wisdom suggests that, inorder to learn, one has to have certain good bias of the problem at hand, and that in learning we need to restrict ourselves to a class of models that cannot overfit the data. This intuition has been justified by classical learning models such as PAC learning Valiant (984) well regression Alon et al. (1997). In these classical models, can be even demonstrated Vapnik and Chervonenkis [2015]. Blumer et al. 1989) that learning requires more examples than the capacity of the class of model to be learnt, and that avoiding interpolation is necessary for generalization. These results, though, are obtained in distribution-ine cerrbuttooninddeenddenl setups where assumes worst-cast distributions over the data.
For this reason, researchers have been searching for new, refined models, as well as improved generalization bounds that incorporate distributional as well as algorithmic assumptions. A promising approach, this direction, tries connect the generalization performance to the amount of information the learner holds regarding the data Russo and Zou (2019] Xu and Raginsky (2017), |Bassily et al. [2018). For example, Xu and Raginsky [017]] demonstrated an upper bound on the generalization gap which informally states:
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

M(ws. S) [S]
generalization gap(ws)= = 0
Namely, given an empirical sample S. and an output model ws, the difference between its empirical error and true error can be upper bounded by ((ws. the mutual information between these two random variables. Notice that Eq. ①T) does not depend any trait of the class of feasible models to be considered. In particular, does not depend, apriori, on number of "free parameters", or complexity measure such as VC dimension, the dimension of ws. and not even some prior distribution. However, it remains a question whether this method and technique can be useful in analysing state-of-the- art learning algorithms. While there has been lot of work trying to establish the success of learning algorithms in various setups Neu et al.) [021] Xu and Raginsky] [2017]. J |u et al.] 22000), /Aminian et al. [2021] Pensia et al. (0188) many of the established bounds are opaque, and often there is no comprehensive end-to-end analysis that effectively illustrates how generalization is to be bounded by Eq. (7) and simultaneously obtaín good empirical performance. In fact, there is also evidence Carlini et al. [202T], Feldman [020] that memorizing data is required, in some regimes, for effective learning. Towards better understanding, we will focus, in this work, on the setup of Stochastic Convex Optimization Shalev-Shward et al.) [2009] (SCO), and provide accompanying lower bounds to Eq. TT that will describe how much mutual information necessary for learning.
study for overparametrizationn SCO is very clean and simple setup where learner observes noisy instances of (Lipschitz) convex functions, defined in R and is required to minimize their expectation. On the one hand, it provides simple, amenable to rigorous analysis, definitions of learnability and learning. On the other hand, this model is the cradle of prototypical algorithms such as Gradient Descent (GD) and Stochastic Gradient Descent (SGD), well as accelerated methods, which are the workhorse behind state-of-the -ohe-----hhhtrr art optimization methods.
SCO
Moreover, SCO is an ideal model for understanding overparameterization It is known Feldman (0066) that in this setup, (2d) examples are needed in order to avoid overfitting. In fact, even concrete algorithms such GD and regularized-GD may overfit unless they observe dimension- -eppenee sample size Amir et al. [2021a]b]. In other words, the capacity of the model and its ability to overfit does indeed scale with the dimension. Nevertheless, it is also known that some algorithms do learn with far fewer examples. For example SGD et al. [2016). Regularized- -RMM RRMSShlle-SSwartt et al. 2009 Bousquet and Elisseefi [2002] and a stable variant of GD BBssily et al. [2020] all learn with O(1/E") examples, a dimension independent magnitude. To put it differently, learning in SCO is not just a question of finding the empirical risk minimizer, but also a question of how what algorithm was used, and learning is not demonstrated by naive uniform convergence bounds that scale with the number of parameters in the model.
Therefore, SCO is a natural candidate to study how information theoretic bounds play a role in learning. We might even hope that these bounds shed light why some algorithms succeed to learn while others fail. Existing algorithms don't avoid memorizing the data, but it is unclear if holding information on the data is necessary. So we start here with the simplest question:
What is the smallest amount of mutual information required for learning in SCO?
Our main result shows that, in contrast with the cinnensioonindependded learnability results in this setup, the information between the model and the sample has to be dimenssion-dependent. As such, the complexity of the class appears implicitly in Eq. ( As a result, carrying ((d) bits of information over the sample is necessary for learning at optimal rates, and Eq. (I) doesn't yield the optimal generalization performance of algorithms such as Regularized ERM, SGD and stable-GD.
1.1 Related Work
Information-theone generalization bounds have a long history of study in ML theory McAllester
[198 1999], [angford and Shawe-Tayaee Taylor [202]. Generalization bounds that directly relate to the information between output and input of the learner initiated the works of Xf and Raginsky 2017] Bassily et al. [2088] Russo and Zou (2019) [Bassily et al. [2018) demonstrated limitations for such generalization bounds, for proper ERM learners, and and Moran 2020) showed that any learner (proper or not), that learns the class of thresholds must leak unbounded amount of information. In

---

this work we focus on stochastic optimization and on learning Lipschitz functions. In the setup of SCO the above is not true, and one can construct learners that leak (dd) bits of information (see Proposition D. But we would like to know whether informationnthhoree uniform convergence bounds (dimension dependent) or capture the minmax learning rates (dimension independent).
bounds behave like the
Several lines of works applied the analysis of Xu and Raginsky [0017] to provide algorithmic-
dependent analysis in the context of stochastic optimization. Pensia et al. [2018] and followup
improvements [Rodriguez Galigu et al. [202T]. Negrea et al. [2019] Haghifam et al. 2020 provided
information theoretic generalization bounds for Stochastic Gradient Langevine Dynamics (SGLD)
and Neu et al.) (202T) extends the idea to analyze vanilla SGD,
SGD., [Aminian et al. (202T) also provides full
characterization of the closely related, Gibbs Algorithm and shows that the information can inverseley scale with the sample bounds. The bounds in these works are implicitly dimension independent which may seem contradictory to the result established here. Importantly, the above bounds may depend on papee-pprameters such as noise in SGLD and temparature in Gibbs algorithm, and these hyperparameters may affect the optimization performance of the algorithms. The bounds obtain are applicable only to algorithms with non-trivial true risk, which depends on hyperparameter choice, and as such there is no real contradiction. Taken together, the noise, for example, in SGLD needs to scale with the dimension in order to obtain non-trive non-trivial cntormmiiionthhorttii bounds, but that will lead to large empirical error. Similarly, if the temperature in the Gibbs algorithm doesn't scale with the dimension, one can potentially achieve small empirical error but at the expanse of high information.
Most similar to our work, recently, Haghifam et al. [022] provided the first set of limitations to information theoretic generalization bounds. They focus on the Gradient Descent method and perturbed variants of it, and provide limitations to both MI bounds as well as conditional mutual information (CMI) bounds Steinke and Ullman (2015) and their individual sample variants Bu et al. 22200). Negrea Negreaa et al. [2199), Haghifam et al. 2020), Zhou et al. [0022). In contrast, we focus on the mutual information bound (as well as its individual sample version of Bu et al. (020 ) but we
provide bounds that are irrespective of the algorithm.
The key idea behind our lower bound proof builds on privacy attacks developed in the differntial privacy literature Bun et al. (2014). Kamath et al.] [2019), SSteinke and Ullman [2013). In the context of classification, lower and upper bounds techniques Alon et al.) [1997], |Bnn et al. (2020) were successfully imported to obtain analogous information-theored Pradeep et al. (2022). In optimization, though, bounds behave slightly different and therefore, bounds from classification cannot be directly imported to the context of optimization.
bounds Livni and Moran [2020).
2 Setup and Main Results
We begin by describing the classical setup of Stochastic Convex Optimization (SCO), following Shalev-Shwartz al. (2009]. In this model, we assume domain 2, a parameter space W S Rd and a function f(, 2). termed loss function. The function f satisfies that for every 20 E 2, the function f(w, zo) function over the parameter
convex and L-Lipschitz.
For concreteness, we treat as a constant, L. = 0(1), and we concentrate on the case where W the unit ball. Namely:
W = (w : ||w|| s 1).
As we mostly care about lower bounds, these won't affect the generality of our results. Given distribution D, the expected loss of a parameter w is given by
(D(w)= = E (f( z-D
The excess true risk of w, with respect to distribution D. denoted as:
An(w) = (n (ww"), where, (D ;= min [f(w,))]
WcW2-DD
We also denote the excess empirical risk, given sample S = (Z)...., 2m))
As(w)= 1 m m
1 m
f(w zi)
min
f f(w 2i).
wEW m
3

---

Leranbility We will focus here on the setup of learning in expectation. In particular, a learning algorithm is defined as an algorithm that receives sample (Zi..... ................................ 2m) and outputs parameter w's We will normally supress the dependence of the parameter w in A and simply write ws- The algorithm A is said to learn with sample complexity m(e) it has the following property: For every 0, if S is sample drawn i.i.d from some unknown distribution D, and [S] m(E) then:
E >
IF [Wp(w
S-Dm
closely related setup requires that the learner succeeds with high probability. Standard tools such as Markov's inequality and boosting the confidence Schapire [1990] demonstrate that the two definitions are essentially equivalent in our model.
Information Theory We next overview basic concepts in information theory as well as known generalization bounds that are obtained via such information-thcorede quantities. We will consider here the case of discrete random variables. We elaborate more on this at the end of this section, and how our results extend to algorithms with continuous output. Therefore, throughout, we assume discrete space of possible outcomes as well as a distribution over Ω. Recall that a random variable X that takes values in X is said to be distributed according to P if P(x = X) P(x) for every x E X. Similarly two random variables X and that take values X and respectively have joint distribution P if
P(x = xx=xxy=WP = p(x,y).
For given y E y, the conditional distribution Pxly is defined to be P (x ly Y) = Σ, P(x.y)* and
P(x,))
the marginal distribution Px X - [0, is given by Px(x) -,, P(x, y). If Pi and P2 are two distributions defined on discrete set X then the KL divergence is defined to be:
DEL (PillP2)
Σ X
Pi(x)
log Pi(x)
P2(x)
Given a joint distribution P that takes values in X y the mutual information between random variable X and Y is given by
I(X:Y) =
Dxzz (Pxiv|IPx)]
We now provide exact statement of Eq. (1)
Theorem (Xu and Raginsky [2017]). Suppose f(w, 2) is a bounded by loss function. And let A be an algorithm that given a sample S = (2I...., 2m) drawn i..d from a distribution D outputs Ws- Then
1 m
m f(w, zi)
21(ws. S) m
LD(ws) EF
Remark on Continuous Algorithms As stated, we focus here on the case of algorithms whose output is discrete, and we also assume that the sample is drawn from discrete set. Regarding the sample, since we care about lower bounds and our constructions assume discrete set, there is no loss of generality here. Regarding the algorithm's 'i output, in the setup of SCO there is also no loss of generality assuming the output is discrete. Indeed, we can show that if there exists continuous algorithm with sample complexity mo(e), and bounded mutual information over the sample, then there exists also a discrete algorithm with sample complexity m()) = mn(0 (x)) with even less mutual information.
To see that notice that, since we care about minimizing a Lipschitz loss function, given any accuracy we can take any finite e-approximation subset of the unit ball and simply project our output to this set. Namely, given output ws, where m()), we output Ws, the nearest neighbour in the e-approximation sub set. Because L.p is 0(1) Lipschitz, we have that
(w LD(W*) I s (W LD(W3)) (LD(WW)) LD(w") O(e).
hence up to constant factor the algorithm has the same learning guarantees. On the other hand, due to data processing inequality:
I(W5, S I(w5, S).

---

2.1
Main Result
Eq. 2 provides a bound over the difference between the expected loss of the output parameter and the empirical loss. Without further constraints, it is not hard to construct an algorithm that carries little information on the sample. But, obtain a bound over the excess risk of the parameter ws. one is required not only to obtain a generalization error gap but also to non-trivially bound the empirical risk. The following result shows that requiring both has its limits:
Theorem 1. For every 0 E < 1/54 and algorithm A, with sample complexity m(E), there exists a distribution D over a space Z, and loss function f. L-Lipschitz and convex in w, such that, if |S] Z m(E) then:
I(ws; S) 2
Σ
m
1(ws, z1) = E0 ())
d
Theorem 1 accompanies the upper bound provided in Eq. and shows that, while the generalization gap is bounded by the mutual information, the mutual information inversely scales with the optimality of the true risk. Taken together, for any algorithm with non-trivial learning guarantees, there is at least one scenario where it must carry a ciiiennsion-deeendee
amount of information on the sample or require a large sample. Indeed, either me) 22( Ed/=s), (and then, trivially, the sample complexity of the algorithm scales with the dimension) or, via Eq. (3), we obtain dimension dependent mutual information, and in turn, Eq. is non-vacuous only if the sample is larger than the dimension.
The first inequality is standard and follows from standard chain rule argument (see e.g. [Bu et al. 2020, proposition 2)). The second inequality lower bounds the information with the individual samples. Recently, [u et al. [2020] obtained refined bound that improves over Xu and Raginsky [2017) by bounding the generalization with the information between the individual samples and output. Theorem 1 together with subadditivity of the square function, shows that the individual sample bound of Bu et al. 20200 can also become dimension dependent.
Discussion
Our main result shows necessary condition the mutual information between the model and empirical sample. Theorem [shows that for any algorithm with non-trivial learning guarantees, there is at least scenario where it must carry dimension-dependen amount of information the sample or require a large sample. A natural question, then, is whether natural structural assumptions may circumvent the lower bound and allow to still maintain meaningful information theoretic bounds in slightly different setups. To initiate a discussion on this we begin by looking deeper into the concrete construction at hand in Theorem [ that the construction we provided for Theorem Iaremm]reiia relies on a distribution D that is always supported on functions of the form:
We notice (see Section and the supplementary material)
f(w, 2) ||w =11 ||w|| 2w
Z (-1/V,
The constant has no effect over the optimization, nor on the optimal solution, therefore we can treat equivalent to the following function
f = || -w.
The distribution over the element z is also quite straightforward and involves only bias sampling of the coordinates. The function f. then, is arguably the simplest non-linear convex function that one can think of and as we further discuss it holds most if not all of the niceties a function can hold that allow fast optimization it is strongly convex, smooth, and in fact enjoys generalization bounds that can even be derived using standard uniform convergence tools. Indeed for any choice Ws
1
Σ f(ws. zi) = E sup S-Dm wI|sl
E S-
(D(ws)
E [w z]] 2-D
E=
001/mm
Where the last inequality follows from a standard Rademacher bound over the complexity of linear classifiers (see Shalev-Shhaee Shwartz and Ben- Ben-David (2014). In other words, while under further structural
5

---

assumptions one might hope to obtain meaningful information theoretic bounds, it should be noted that such structural assumptions must exclude a highly simplistic class of functions that are in fact extremely easy to learn and even enjoy dimension independent uniform convergence bounds.
We now discuss further the niceties of this function class and the implications refined prrriimiidisttibuiiiaa-ppppppeed
generalization bound via the information--heoortie bounds. We begin by analyzing algorithms that achieve the minimax rate.
Algorithmi--dependent generalization bounds As discussed, is known that SGD Hazan et al. (2016), regularized-ERMM (Shalev-Shwartz al. [2099] [oosqqet and Elisseeff (2002). as well as
stabilized versions of Gradient Descent [Bassily et al. 2020] have the following minmax rate for
learning O11)-Lipscthiz convex functions over ((1) bbounded domain:
E (Ws) = (11/mm).
Plugging the above Eq. (3) we obtain that any such algorithm must earry at least (2(d/m m/2mmmmm))) bits of information. which entails an information theoretic bound in Eq. ( of O (d/mm/4) This exceeds the true excess risk of such algorithms when d >> and becomes vacuous bound when we don't assume the sample scales with the dimension (even though the algorithm perfectly learns this setup). Now, do not need Theorem[] obtain generalization gaps over these concrete algorithms, as a more direct approach would do. But, one might hope that by analyzing noisy versions these algorithms, some other forms of information regulationnegulllaizatiion generalization of these algorithms. But, our lower bound applies to any algorithm with meaningful Information-theoreee generalization bound. In particular, adding noise, for example, either makes the algorithm diverge or the noise is too small to delete enough information.
could obtain some insight on the
generalization bounds Next, would like to discuss the implications to distributional ussumptions. The above discussion shows that any trait of an algorithm that makes it optimal is not captured by the amount of information it holds on the data (in the setup of SCO). Distinct from SCO, in practice, many of the underlying problems can be cast into binary classification where it is known Blumer et al. [1989] that without further distributional assumptions learnability cannot be separated from uniform convergence as in SCO.
Distributional-deeenne
An interesting question, then, is if information theoretic generalization bounds can be used to obtain distribution-dependenn bounds.
The function f(w, z) in Eq. (4) is known to be strongly-convex for every Recall that function f is
called 1 -strongly convex if - is convex. It is known Shalev-Shwartz.. et al. 2209 that any ERM over strongly convex will achieve suboptimality:
[[Ap(ws)] 0(1m).
Moreover, the above result can be even strengthened to any approximate empirical risk minimizer, that is minimizer with additive 0 (1/m²²) error over the empirical risk Shalev-Shwartz al. [2009]. Amir et al. (2021b). But even further, for the particular structure of f. which regularized linear objective, by SSidhhaaan al. 2008 Thm I] we have:
ElAp(ws)] s Ó(E[As(ws) 1/m).
Together with Theorem I we obtain the following algorithmic-indeendde result: Theorem 2. There exists a family of distributions D such that for any algorithum A and m > 3, there exists distribution D E D such that if (s(ws) 1/54 and |S] > then
1(ws. S) = m6 (E(As(ws)] 1)5
but for any algorithm A and distribution D D: E[Ap(ws)] = Ô (E[As(ws)] 1/m).
In other words, even without algorithmic assumptions, we can construct a class of distributions which make the problem easy learn, but the information bounds are still dimension dependent. In

---

particular, for any algorithm such that As(ws) = (11/m) we will have that the bound in Eq. (2 is order of:
[[Ap(ws)] Ō (vd/m).
(5)
Comparison to uniform convergence bounds: Notice that Eq. (5) is the standard generalization
bound that can be obtained for any ERM algorithm in the setting of stochastic convex optimization.
In detail, through a standard covering number argument (Shalev-Shward et al., 2009 thm 5) it is
known that, when f is 1- I-Lipschitz (not necessarily convex even):
1 m
m
sup E we W S
(w)
f(w2z)
S O(vd/m).
In other words, the bound we obtain in Eq. (5) can be obtained for any algorithm, with minimal assumptions, irrespective of the mutual information between output and sample. We remark, though, that, through similar covering argument, one can show that indeed there are algorithms where one can recover the above bound via information-theoree
reasoning.
Proposition 1. Given a I-Lipschitz funcction f. there exists an algorithm A that given impul sample outputs parameters ws E W: such that
1
2()s,z) S min
f(w",
(6)
w
and
1(w5.5) mog
In particular,
LD(ws) lD( = Ō(vd/m).
Sketch. The result follows a simple covering argument. In particular, it is known that there exists finite subset W c W of size [W] 0 vmm such that for every E W there is w W such that
||w - W|l v vd/m (e.g. Wu (2017)) Now. we consider an ERM that is restricted to the set W. By Lipschitness we have that Eq. (6) holds. The information is bounded by the entropy of the algorithm and we have that
S) S H(Ws) log [ O(d logm).
The genearlization gap can be bounded via Eq. (2) (or standard union bound).
CMI-bounds Similarly to our setting, also in the setting of PAC learning, Livni and Moran 2020
Bassily al. (018 provided limitations to information theoretic generalization bounds. Specifically, they showed that such bounds become vacous in the task of learning thresholds, and the information between output and sample may be unbounded. To resolve this issue, which happens because of the numerical precision required by a thresholds learner, Steinke and Zakynthinou (200) introduced generalization bounds that depend on conditional mutual information (CMI). They provided CMI bounds that can be derived from VC bounds, compression bounds etc... which a nutshell means that they are powerful enough to achieve tight learning rates for VC classes such as thresholds. However, the issue in SCO is not comparable. As we show in Proposition [ already the classical information-theoretie bounds are powerful enough to demonstrate generalization bounds that can be derived via union bound or uniform convergence. In PAC learning, these bounds are also tight, but in SCO such bounds are dimension-dee -dpendden...eeeee... In that sense, there no analog result to the limitation of learning thresholds. Partly because there is no need for infinite precision in SCO. In SCO, though, we require separation from uniform convergence bounds, or even more strongly from dimension dependent bounds. While Haghifam et al. (2000) does demonstrate certain algorithmic-dependen limitations for GD and perturbed GD algorithms, one might hope that, similar to PAC learning, here too CMI-bounds might be able to capture optimal Himension-indeeenee
rates for some algorithms.
More formally, given a distribution D over 2, we consider process where we draw i.i.d two random samples Z = S x S2, where S = :zf...................... ....zm)) m] ~ D and S2 = [z]...., 2 } ~ D Then we define a sample S by randomly picking z zi w.p. 1/2 and z = 2/ w.p. 1/2 (independently from
7

---

....... 2f-1, 2itl...... ..... 2m). Then, Steinke and Zakynthinou (2020) showed that, similarly to Eq. 17 the generalization of an algorithm can be bounded in terms of
generalization(A) (A) = = (VCMIm(A) (A)/m)
CMI = (ws, (Z).
Recall that, given random variable Z, the conditional mutual information between r.v. X and r.v. Y defined as:
1 (x; (2) =E 2 |
One can show that CM) = (m). The simplest way to achieve a dimension independent generalization bound would be subsample. If algorithm A observes sample of size and subsamples f(m) samples, then we trivially obtain the generalization gap: O(1/ of Taking Eq. 7 into consideration by subsampling O(ym) examples, Eq. (7) will lead dimension independent generalization bound of O /m). So it is possible to obtain dimension independent bounds through the CMI framework, nevertheless is stll not clear we can beat the above, nonoptimal and naive subsampling bound
Open Problem. Is there an algorithm A in the SCO setup that can achieve
CMI (A) = o( 0(vm).
as well
=
Technical overview
We next outline the key technical tools and ideas that Icad to the proof of Theorem I A full proof of Theorem iis provided in the supplementary material. As discussed draw our idea from the privacy literature Steinke and Ullman 2013). Kamath et al. 2019), Bun et al. (2014) and build on fingerprinting Lemmas Boneh and Shaw 11998 Tardos [2008 to construct "information attacks". We employ simplified and well-tailore version of the fingerprinting Lemma, due to Kamath et al. (019). construct a lower bound the correlation between the output and the data. From that point our proof differ from standard privacy attacks.
Given the above correlation bound, we now want to lower bound the mutual information between the two correlated random variables (i.c. the output of the algorithm and the empirical mean). Surprisingly, we could not find in the literature between two correlated random variables. The next Lemma provides such a lower bound and as such may be of independent interest.. We next depict these two technical Lemmas that need for our proof the fingerprinting Lemma due to Kamath et al. (2099 and a lower bound on the mutual information between two correlated random variables.
existing lower bound on the mutual information
For describing the fingerprinting Lemma, let us denote by U[-1/3, 1/3] the uniform distribution over the interval [-1/3, 1/3], and given p [-1/3, 1/3], we denote by 71mm (m) random process where we draw m i.i.d random variables Zi..... .. 7m where Z E (+1) and E[Z] = p:
Lemma 1 (Fingerprinting Lemma Kamath et al. 2019)). )). For every f {+1] [-3. 31 we
have:
I 9p2 P-U1-1331133 2im Um)PP) 9- (f(Z)m) - P) _
m
E
(4 P) (f(Z).)) - p)² 2 27
1=1
The above theorem shows that if a random variable f(Z).m) uses the sample to non-trivially estimate the random variable P, then the output must correlate with the empirical mean. Notice that, in particular, it means that f(Zz:m) is not independent of Ztm and certain information exists. Our next Lemma quantifies this statement and, as far the author knows, novel. The proof is provided the supplementary material
8

---

Lemma 2. Let X and Y be two random variables such that X is bounded by 1, E(X) and
E(Y?) [X then:
B
vI(X,))
2v2
The proof of Lemma is provided in the supplementary material
With Lemmas] and at hand, the proof idea is quite straightforward. For every e (-1/Vd, define the following loss function:
f(w,2)= (w(() -())) -1w- -
(8)
For every distribution D. one can show that the minimizer w* = arg min (w)) provided by
E[z]. By standard decomposition can show:
(p(ws)= (nww)) = |lls + (w* - =) - w*11 1|2 1|w*~
- =11
E [llws w=11 [|2 2(ws w*) (w* - 2) ||W -2l1 1| -- =|l²]
= E [llws ==1 + 2E [(ws - w-) (E[z] 2)
= E [lws 1
(9)
Now, for simplicity of this overview only consider the case that A(ws) 22(1 constant, for example we may assume that A (Ws) < 1/54 and let us show that for every coordinate, r, the mutual information between (t) and 2,( is order of f2(1m²².. Then by standard chain rule, and proper derivations the end result can be obtained.
l) is some non-trivial
Indeed, one can observe that if Awws) 1/54, and since w* P()))) s 1/54. In turn, can use Lemma 1 and show that in expectation over P we also have:
[[=] = P we have that E( (IV
r)] =2(1)
(Vaws(1- -P) p)
2(1).
We now use Lemma 2 and convexity, lower bound the individual sume of the mutual information, Σ (ww (f); (f) P). By standard technique we conclude that there exists P for which the mutual information bounded.
The above outline does not provide bound that scales with the accuracy of A(ws), and we need to be more careful in our analysis for the full derivation. The detailed proof is provided in the supplementary material.
The author would like to thank the anonymous reviewers that suggested to incorporate the lower bound for the individual mutual information term. This turned out simplify some of the proofs. The author would like to thank Shay Moran, and the research was funded in part by the ERC grant opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. The author is a recipient of Google research scholar award and would like acknowledge his thanks.
Ackgnoweledgments
10139692), as well as an ISF Grant (2188) 20). Views and
References
D. Aldous. Random walks on finite groups and rapidly mixing markov chains. In Séminaire de Probabilités XVII 1981/82, pages 247.297. Springer, 1983.
N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the ACM (JACM), (A(4):615-631, 1997.
G. Aminian, Y. Bu, L. Toni, M. Rodrigues, and G. Wornell. An exact characterization of the generalization error for the gibbs algorithm. Advances Neural Information Processing Systems, 34:8106-88 81 18, 2021.

---

I. Amir, Y. Carmon, T. Koren, and R. Livni. Never go full batch (in stochastic convex optimization). Advances in Neural Information Processing Systems, 34:25033-25043. 2021a.
I. Amir, Koren, and R. Livni. Sgd generalizes better than gd (and regularization doesn't help). In Conference Learning Theory, pages 63-92. PMLR, 2021b.
R. Bassily, S. Moran, I. Nachum, J. Shafer, and A. Yehudayoff. Learners that use little information. In Algorithmic Learning Theory, pages 25-55, PMLR, 2018.
R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33:4381-4391 2020.
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), 36(4):929- 99529999999999999 1989.
D. Boneh and J. Shaw. Collusion-secure fingerprinting for digital data. IEEE Transactions Information Theory, 44(5):1877-1055, 1998.
O. Bousquet and A. Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526 526, 2002.
Y. Bu, S. Zou, and V. V. Veeravalli. Tightening mutual information-based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 1(I):121-130 2020.
M. Bun, J. Ullman, and S. Vadhan. Fingerprinting codes and the price of approximate differential privacy. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 1-10, 2014.
M. Bun, R. Livni, and S. Moran. An equivalence between private classification and online prediction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages IEEE, 2020.
N. Carlini, F. Tramer, E. Wallace, M. Jagielski, A. Herbert-Voss, K. Lee, A. Roberts, T. Brown, D. Song, U. Erlingsson, et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pages 2633-2650, 2021.
J. Duchi. Lecture notes for statistics 311/elcctrical engineering 377. URL: https://stanfrrd. (abulllas//stas33leLeeeeeeeessss
notes. pdf. Last visited on, 2:23, 2016.
V. Feldman. Generalization of erm in stochastic convex optimization: The dimension strikes back.
Advances in Neural Information Processing Systems, 29, 2016.
V. Feldman. Does learning require memorization? short tale about long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 954-959 2020.
M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application noisy, iterative algorithms. Advances in Neural Information Processing Systems, 33:9925-9935,, 2020.
M. Haghifam, B. Rodriguez-Gälvez. R. Thobaben, M. Skoglund, D. M. Roy, and G. K. Dziugaite. Limitations of ceormationnthhoreee generalization bounds for gradient descent methods in stochastic convex optimization. arXiv preprint arXiv:2212.13556, 2022.
E. Hazan et al. Introduction to online convex optimization. Foundations and Trends& in Optimization, 135-4): 2016.
G. Kamath, Li, V. Singhal, and Ullman. Privately learning high-dimensional distributions. In Conference on Learning Theory, pages 1853-1902. PMLR, 2019.
J. Langford and J. Shawe-Taylor. Pac-bayes & margins. Advances in neural information processing systems, 15, 2002.
R. Livni and S. Moran. A limitation of the pac-bayes framework. Advances in Neural Information Processing Systems, 33:20543-20553, 2020.
10

---

D. A. McAllester. Some pac-bayesian theorems. In Proceedings of the eleventh annual conference on Computational learning theory. pages 230-234, 1998.
D. A. McAllester. Pac-bayesian model averaging. Proceedings of the twelfth annual conference on Computational learning theory, pages 164-170, 1999.
Negrea, M. Haghifam, G. Dziugaite, A. Khisti, and D. M. Roy. thfooeiiion-hhoortticc generalization bounds for sgld via data-dependent estimates. Advances in Neural Information Processing Systems, 32, 2019.
theoretic
G. Neu, G. K. Dziugaite, M. Haghifam, and D. M. Roy. Information-thheortiic generalization bounds for stochastic gradient descent. In Conference on Learning Theory, pages 3526-3545, PMLR, 2021.
B. Neyshabur, R. Tomioka, and N. Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. arXiv preprint arXiv: 1412.6614, 2014.
R. Paley and A. Zygmund. A note on analytic functions in the unit circle. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 28, pages 266-277 272. Cambridge University Press, 1932.
A. Pensia, V. Jog, and P.-.. Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 546-550. IEEE, 2018.
A. Pradeep, I. Nachum, and M. Gastpar. Finite littlestone dimension implies finite information complexity. In 2022 IEEE International Symposium on Information (1ST)) IEEE, 2022.
(ISIT), pages 3055-3060.
B. Rodrfguez-GGälvez, G. Bassi, R. Thobaben, and M. Skoglund. On random subset generalization error bounds and the stochastic gradient langevin dynamics algorithm. In 2020 IEEE Information Theory Workshop (ITW), pages 1-5. IEEE, 2021.
D. Russo and J. Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions Information Theory, 66(1):302-33) 2019.
R. Schapire. The strength of weak learnability. Machine learning, 1(2):197-227, 1990.
Shalev-Shwartz and Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Stochastic convex optimization. In COLT, volume 2, page 5, 2009.
K. Sridharan, S. neural information processing systems, 21, 2008.
and N. Srebro. Fast rates for regularized objectives. Advances in
T. Steinke and J. Ullman. Interactive fingerprinting codes and the hardness of preventing false discovery. In Conference on learning theory, pages 1588-1628. PMLR, 2015.
T. Steinke and L. Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference Learning Thheory, pages 3437-3452. PMLR, 2020.
G. Tardos. Optimal probabilistic fingerprint codes. Journal of the ACM (JACM), 55(2):1 2008.
L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134 1142, 1984.
V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity, pages 11 11-30. Springer, 2015.
Y. Wu. Lecture notes on informatiin-theoretic methods for high-dimensional statistics. Lecture Notes for ECE598YW (UIUC), 16, 2017.
A. Xu and Raginsky. eeformation-theoreee analysis of generalization capability of learning algorithms. Advances in Neural Information Processing Systems, 30, 2017.
11

---

C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
R. Zhou, C. Tian, and T. Liu, Individually conditional individual mutual information bound on generalization error. IEEE Transactions Information Theory, 68(3)3334--3316 2022.
12


Reviews:
[{"review_id": "hO1ykcNz0E", "reviewer": "Reviewer_VAde", "summary": "The paper shows that there exist stochastic convex optimization problems, which are easy to learn but for which the mutual information based generalization bound of [Xu-Raginsky, 2017] scales at least linearly in the dimension of the parameter space. ", "questions": "NONE", "limitations": "NONE", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper presents the limitation of mutual information based generalization bound of [Xu-Raginsky 2017] in capturing dimension dependency. The work improves on the previous results of [Haghifam et al 2022] in this respect, in which the lower bound scales logarithmically with dimension and is restricted to gradient descent. \n\nI did not carefully check all proofs but they look fine.The results of this paper are original. This work is among the very few that point to the limitations of information-theoretic upper bounds for generalization errors of learning algorithms. Such results are important for the learning theory community to developed improved information-theoretic tools that overcome such limitations.  \n\nThe paper is also very well written. The presentation is clear to this reviewer. The presented results are very well positioned in the related literature. ", "weaknesses": "NONE", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much!"}, {"review_id": "bRqRuB0y6c", "reviewer": "Reviewer_z3UU", "summary": "This work considers the setting of stochastic convex optimization in $\\mathbb{R}^d$ with learning algorithms that achieve less than $\\epsilon$ expected excess risk when at least $m(\\epsilon)$ examples are given. The main result of this work (Theorem 1) states that such algorithms have $\\tilde{\\Omega}\\left(\\frac{d}{\\epsilon^5 m(\\epsilon)^5}\\right)$ amount of Shannon mutual information between the input and the output (i.e., $I(w_S; S)$ with $w_S$ being the output on input sample $S$). The significance of this lower bound is that there is a linear dependence on dimension $d$, which renders the bound of Xu and Raginsky [2017] dimension-dependent in case $m(\\epsilon)=o(d^{1/5})$. For example, if one considers minimax optimal learning algorithms (that have $\\frac{1}{\\epsilon}$ or $\\frac{1}{\\epsilon^2}$ sample complexity depending on assumptions about the loss function), the generalization gap bounds with input-output mutual information become dimension dependent and can be vacuous when $d \\gg m$.", "questions": "- Please use `\\citep` or `\\citet` (depending on whether authors are a part of the sentence or not) rather than `\\cite`. \n- Lines 74-78: Need to be rewritten to improve clarity.\n- Line 116: Calling $\\Delta_S(w)$ \"empirical risk\" is confusing. It is better to call it \"excess empirical risk\".\n- Line 116: \"With the optimality\" -> \"with the suboptimality\".\n- Line 117: Typo in \"Leranbility\".\n- Lines 117-118: As I understand from the expectation in between lines 121-122, only deterministic algorithms are considered. Does the main result of Theorem 1 extend to stochastic algorithms?\n- Just below line 187: it should be $\\le$ in the first equation line.\n- Appendix A. Proof of Theorem 1, first paragraph: It should be $z \\in \\\\{-1/\\sqrt{d}, 1/\\sqrt{d}\\\\}$. Also, in \"each coordinate z(t) is chosen uniformly\" the word \"uniformly\" should be removed or replaced by \"independently\".\n- Lines 200-201: It is clear what is the main message here, but the information-theoretic bound applies to the generalization gap and should not be directly compared with the suboptimality rate.\n- In equation between lines 212 and 213, it should be $d^{1/7}$.\n- The CMI bound in eq. (7) instead of $I(w_S; S | Z)$ it should be $I(w_S; J | Z)$ where $J$ denotes the selection variables. Note that $I(w_S; J | Z)  = I(w_S; S | Z) + I(w_S; J | Z, S)$ and the last term is not always zero (e.g., when $\\mathcal{Z}$ is a finite domain with small size).\n- Line 282: It should be $O(\\sqrt{f(m)/m})$. \n- Lines 280-286: Subsampling will result in dimension-independent *generalization gap* bounds, but one might not be able to convert that into an excess risk bound.\n- In a few places throughout the paper we see \"true risk\", does it refer to the excess risk (suboptimality) or the expected loss?\n- In the equation below line 315, there should be parentheses for the logarithm to indicate that the $\\frac{c^2}{\\beta^2}$ part is inside the logarithm.", "limitations": "See weakness #3.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "**Strength #1: Significance.** Recently information-theoretic generalization bounds have gained a lot of attention, partly because they are algorithm and distribution-dependent and some variants of them are nonvacuous in practical setting for deep learning. Understanding limitations of information-theoretic generalization bounds is thus important and relevant for the NeurIPS community. The lower bound derived in this work is a good contribution to the list of already known limitations.\n\n**Strength #2: Originality.** To my best knowledge the derived lower bound is novel. The related work is cited adequately.", "weaknesses": "**Weakness #1: Soundness.** I couldn't verify some parts of the proof of Theorem 1. Some clarifications are needed.\n- In the line after equation (17), \"Next, for fixed $p$ we define two random variables\": Is $p$ a vector here or a constant? Should it be $\\frac{1-9p(t)^2}{9-9p(t)^2}$ instead?\n- In the line after equation (18), \"Applying Lemma 1, ...\": It was hard for me to follow the proof. I suggest to clearly write what $f$ is, verify that $f$ has the signature $f: \\\\{-1,1\\\\}^m \\rightarrow [-1/3, +1/3]$ as required by Lemma 1, and clearly write what $X_i$ of Lemma 1 are in your construction. As I understand $X_i$ of Lemma 1 correspond to $\\sqrt{d} z_i(t)$, but in that case $\\hat{p}(t)$ is not a function of $\\\\{\\sqrt{d}z_i(t)\\\\}_{i=1}^m$.\n- In the line after equation (20), \"Write $Z = \\mathbb{E}_{S\\sim D^m(p)}\\left[ X_p(t) Y_p(t)\\right]$\": I suggest to use another letter instead of $Z$, which is already used to denote the input. Additionally, in order to apply Paley-Zygmund inequality, $Z$ needs to be positive. I think this should be verified. As I understand, the algorithm can be such that it fails to be positively correlated with the mean for some choices of $p$. For those choices of $p$, $Z$ can be zero or negative.\n- I could verify the proof after equation (21).\n\n**Weakness #2: Clarity & Presentation [minor].** The paper would benefit a lot from improvements in terms of clarity and presentation. It was hard for me to read and understand the details, as there were many small mistakes, some parts of derivations were not detailed enough, and some parts of the main text made sense only after reading the later parts of the paper. Please see more detailed comments and suggestions below.\n\n**Weakness #3: Limitations [minor].** Deriving a lower-bound for the input-output mutual information is does not have strong implications about the line of information-theoretic generalization bounds.\n\nIt is well-known that information-theoretic generalization bounds that depend on input-output mutual information have many limitations. For example, they can be infinite for well-generalizing continuous learning algorithms. For this reason many techniques of improving such bounds were proposed.\n1. Bu et al. [1] derived an improved expected generalization gap bound that depends on $\\sum_i I(w_S; Z_i)$ rather than $I(w_S, S)$ with $S=(Z_1,\\ldots,Z_m)$ being the sample.\n2. As discussed in the paper, there are conditional mutual information bounds that are dimension independent. These CMI bounds of Steinke and Zakynthinou have been improved a lot subsequently: (a) deriving sample wise bounds $\\sum_i I(w_S; J_i | \\tilde{Z})$ (where $J$ is the train-test split variable and $\\tilde{Z} \\in \\mathcal{Z}^{n\\times 2}$ is the supersample) [2], (b) conditioning on individual pair of supersample examples: $\\sum_i I(w_S; J_i | \\tilde{Z}_i)$ [3]; (c) measuring information in function space [4]; and (d) leave-one-out bounds [5].\nTo my understanding, the result of this paper does not extend to these stronger bounds.\n\n\nFinal note: the main determinant of the score assigned below is the weakness #1. I am willing to increase the score if the concerns are properly addressed.\n\n\n**References**\n\n[1] Y. Bu, S. Zou, and V. V. Veeravalli. Tightening mutual information-based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 2020.\n\n[2] M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. NeurIPS 2020.\n\n[3] H. Harutyunyan, M. Raginsky, GV. Steeg, and A. Galstyan. Information-theoretic generalization bounds for black-box learning algorithms. NeurIPS 2021.\n\n[4] B. Rodríguez-Gálvez, G. Bassi, R. Thobaben, and M. Skoglund. On random subset generalization error bounds and the stochastic gradient Langevin dynamics algorithm. IEEE ITW 2021.\n\n[5] M. Haghifam, S. Moran, DM. Roy, and GK. Dziugiate. Understanding generalization via leave-one-out conditional mutual information. IEEE ISIT 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback and comments. The proofs are correct, but certain typos have been identified by the reviewer, and indeed, a certain assertion was neglected that could clarify things (see below).If further clarifications are in order, those can be delivered..\n\n> In the line after equation (17), \"Next, for fixed p   we define two random variables\": Is  a vector here or a constant? \n\nThanks!, you are right and it is a typo. It should be p(t) instead of p.\n\n> In the line after equation (18), \"Applying Lemma 1, ...\": It was hard for me to follow the proof. I suggest to clearly write what\n\nThanks for pointing out the need for further elaboration here. What is missing is the statement that without loss of generality we can assume that $|w(t)| <= 1/(3\\sqrt{d})$. Indeed, concatenating w(t) will only diminish the loss and will not add information.This will also mean that f is bounded as required.\n\nNext, as you correctly point out, to apply fingerprinting, f is $\\hat{p}(t)$. f is a function of $z_i(t)$’s as $w_S$ is a function of $z_i(t)$, all other r.v.s are independent of $p(t)$ hence the fingerprinting Lemma can be readily applied. This part indeed can benefit from a more detailed derivation but it is well justified \n\n\n> in order to apply Paley-Zygmund inequality,  Z  needs to be positive. I think this should be verified.\n\nThanks for this remark. Paley-Zygmund is indeed generally formulated so that $Z$ has to be positive. However, it is true that one can apply the inequality to any random variable with positive expectation (i.e. $E[Z]>0$) which follows from  eq. 19.\n\nThe proof is so straightforward that it can be verified here: Indeed, the standard derivation begins with the equality:\n$Z = Z\\cdot 1_{Z\\le \\theta E[Z]} + Z\\cdot 1_{Z> \\theta [Z]}$, hence $E[Z] \\le \\theta E[Z] + E[ Z\\cdot 1_{Z> \\theta [Z]}]$.\n\nThis step ofcourse doesn’t require positivity. Next, we apply C.S which also doesn’t require positivity:\n $E[ Z\\cdot 1_{Z> \\theta [Z]}] \\le \\sqrt{E[Z^2] P(Z> \\theta E[Z])}.$\n\nRearranging we obtain \n\n$$(1-\\theta) E[Z]) \\le  \\sqrt{E[Z^2] P(Z> \\theta E[Z])}.$$\n\nNow taking the square of both sides (which now requires $(1-\\theta) E[Z]\\ge 0$) we obtain the inequality.\n\nThis remark will be added to the manuscript, to make it clear for everyone that Paley-Zygmund can be applied here.\n\n> I could verify the proof after equation (21).\n\nWhile there are a few tedious lines after eq.21 they are all being justified. Perhaps if the reviewer can point out the difficulty here, that could be gladly clarified. \n\n> It is well-known that information-theoretic generalization bounds that depend on input-output mutual information have many limitations. For example, they can be infinite for well-generalizing continuous learning algorithms.\n\nThis is true, but this deficiency is not due to the input-output mutual information, one can artificially encode any information in the model. For example, think of a perfectly well-generalizing algorithm where the model includes storage of all the data that was used in training, such an algorithm will hold information even on the individual samples. The point in this paper is to develop a technique that shows that **every** algorithm must hold information.\n\n > Bu et al. [1] derived an improved expected generalization gap bound \n\nFirst, thanks for the reference! The bound in Bu et al indeed requires discussion and that will be added. Similarly, a dimension dependent lower bound can be derived to the form of Bu et al. Since this was asked by several reviewers, a proof sketch will be added in a separate official comment. A full derivation can also be provided upon request.\n\nRegarding further questions, the reviews does identify certain typos and places where clarification is in order, these will be addressed in the paper and Thanks for pointing these out. if some further clarifications are in order, those will gladly be provided."}, {"review_id": "ZZSq6p5ZAn", "reviewer": "Reviewer_UMeF", "summary": "This paper challenges the tightness of some information-theoretic upper bounds on the generalization error in the stochastic convex optimization (SCO) setting (i.e. convex, Lipschitz, bounded loss on a bounded domain). More precisely, it challenges the bound from Xu and Raginksy that (vaguely) states that the generalization error is bounded from above by a function of the mutual information between the dataset and the output of the learning algorithm. With this purpose, the authors derive lower bounds on the mutual information that grows with the dimension of the input space. This, in turn, shows that there is a distribution over an input space such that the mutual information is arbitrarily large. Therefore the mutual information-based bounds are vacuous for that distribution.\n\nThese lower bounds are obtained by means of three essential tricks:\n1) Noting that one may only study discrete algorithms and discrete distributions over the inputs. The fact of considering discrete distributions over the input comes naturally from the fact that they are looking for lower bounds. Then, restricting to discrete algorithms is possible since (i) the loss is Lipschitz and the generalization error of a discretization of the parameters can at most incur into a constant multiplicative penalty and since (ii) the mutual information will only be smaller by the data processing inequality.\n2) Employing a fingerprinting lemma from Kamath et al. (2019). For random variables $(X\\_i)\\_{i=1}^m \\in \\lbrace -1, 1 \\rbrace$ such that $\\mathbb{E}[X\\_i]=p$. This lemma essentially states that the MSE of an estimator of $p$ decreases the more correlated the error of the estimator is with the error of the empirical mean. That is, a good estimator of $p$ is highly correlated with the empirical mean.\n3) Noting that if two random variables $X$ and $Y$ are correlated with $\\mathbb{E}[XY] = \\beta$, then the mutual information $I(X;Y)$ is grows as $\\Omega(\\beta^4)$.\n\nOverly simplifying, this way, they construct an example where the loss function is $f(w,z) = \\lVert w - z \\rVert^2$. Then, by the fingerprinting lemma, any algorithm that attains a good error is necessarily correlated with the empirical mean. Therefore, the mutual information between the output of the algorithm and the empirical mean is bounded from below. Finally, by the data processing inequality, the mutual information between the output of the algorithm and the dataset is also bounded from below. The use of the chain rule makes sure that this scales with the dimension of the input.", "questions": "- Why is there a vector $p$ such that for $d / (10^6 m \\epsilon)$ of the coordinates (22) holds? Why is it not possible that less cordinates have that value be much larger than 1/108?\n- Why can you employ the data processing inequality after (24)? X\\_p(t) depends both on $Z\\_i$ and $W\\_S$, and $Y\\_p(t)$ depends on $W\\_S$?\n- Could the techniques from this paper be employed to also find lower bounds on stronger information-theoretic bounds on the generalization such as the individual MI from Bu, Zhou, and Veeravalli (2020)?\n\n**References**\n\nY.Bu, S. Zhou, and V. V. Veeravalli. \"Tightening Mutual Information-Based Bounds on Generalization Error\". Journal on Selected Areas in Information Theory. 2020. ", "limitations": "Some limitations are touched on in the comparison of the results with uniform convergence bounds in lines 239-256. However, there is not a large discussion of the limitations of the paper. For instance, what happens if an algorithm chooses another loss function? or, could one just consider a stronger information-theoretic notion such as the individual MI and then achieve bounds with a good rate?\n\nMaybe the space from lines 333 onwards could be used to reflect more on these issues in the Discussion section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The problem studied is interesting. While Bassily et al. (2019) presented some lower bounds of the mutual information for learning thresholds and Haghifam et al. (2022) showed lower bounds of the mutual information, conditional mutual information, and its variants for gradient descent (GD) in the SCO setting, studying general lower bounds for any algorithms in this setting is important. \n\nAs mentioned in the summary, the realization of being able to only consider discrete algorithms and the usage of the fingerprinting lemma to find lower bounds on the mutual information of algorithms in the SCO setting is original and interesting. Moreover, formalizing the expected result that correlated random variables have large mutual information is valuable in its own right.", "weaknesses": "- The authors sometimes fail to position the related literature correctly. \n  - They only glass over Haghifam et al. (2022) in Section 1.1 and they say that the paper finds lower bounds on the mutual information (MI) and the conditional mutual information (CMI) of GD and a variant of GD with a perturbation on the final iterate. They also find lower bounds for the individual sample versions of the MI and CMI as well as the evaluated CMI for the GD algorithm.  Moreover, they mention that the bounds have a logarithmic dependence on the dimension. This is not accurate, while the dependence is logarithmic for the perturbed version of GD, for vanilla GD the bounds grow with the square root of the dimension. \n  - In line 257 it seems they forgot to cite Bassiliy et al. (2018). In the same sub-subsection (CMI-bounds) it seems that they also forgot to mention the existing lower bounds from Haghifam et al. (2022).\n  - Also in the CMI-bounds sub-subsection they describe wrong the CMI. The CMI is not $I(w\\_S;S|Z)$, it is $I(w\\_S; U|Z)$, where $U$ is a sequence of Bernoulli random variables whose realization is used to select between $z\\_i^0$ and $z\\_i^1$ to generate the dataset $S$.\n\n- The paper is not very clear. \n  - Most of the citations in the paper are not in the correct format (that is, they are not within brackets in the \\citep style of natbib, but directly written in the \\citet style of natbib), difficulting readability. \n  - Sometimes the sentences are a little overstated: e.g. in line 174 they say \"Theorem 1 shows that any algorithm with non-trivial learning guarantees must carry a dimension-dependent amount of information on the sample or require a large sample\". This is not completely accurate. To be precise, for every algorithm $A$, there is a distribution $D$ over a space $\\mathcal{Z}$ and a convex, Lipschitz function $f$ such that if the algorithm achieves a non-trivial learning guarantee, then it must carry a dimension-dependent amount of information on the sample or require a large sample.\n  - The sub-subsection CMI-bounds seems a little disconnected. The whole paper focuses on finding lower bounds of the mutual information, showing limitations to these bounds. Haghifam et al. (2022) show that at least for GD one can have a population risk of $O(1/\\sqrt{m})$ while having a CMI of $\\Omega(m)$, which would go in the direction of obtaining lower bounds. Moreover, it is not clear why $O(1/\\sqrt{m})$ is chosen for the population risk and $o(\\sqrt{m})$ is chosen for the CMI. The subsampling statement above seems to try to clarify this, but why would not one choose to subsample $O(m^{1/4})$ or $O(\\log m)$? There seems to be no justification.\n  - Lemma 3 is used without any proof in the Appendix of the supplementary material, which is in the template of the submission to another conference whose main text differs in some places from the main text submitted.\n  - The final part of the paper (from line 333 on) seems disconnected from the rest of the text. \n\nSmall mistakes:\n-  In 237-238 it states that \"for any algorithm such that $\\Delta\\_S(w\\_S) = O(1/m)$ we will have that the bound in Eq. (2) is order of $\\mathbb{E}[\\Delta\\_D (w\\_S)] = \\tilde{O}(\\sqrt{d/m})$. This is not correct, the bound is of that order, but not $\\mathbb{E}[\\Delta\\_D (w\\_S)] $.\n- In Appendix A, it should be $\\lbrace -1 / \\sqrt{d}, 1 / \\sqrt{d} \\rbrace$, right?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThanks for the review. Hopefully, the rebuttal will help the reviewer be convinced that there is no reason for providing such a low score. Especially given that the reviewer identifies strengths (important problem and interesting techniques) and that the weaknesses can be easily addressed and require some small formatting changes, adding further elaborations, as well as a few citations.\n\nBelow is an address to what seem like the most emergent issues, further elaboration can be provided if needed.\n\n> They only glass over Haghifam et al. (2022) in Section 1.1\n\nThe paragraph will be changed to clarify that they can achieve bounds to other variants. The final sentence will be clarified: that the logarithmic bound applies to the perturbed version.\n\n> In line 257 it seems they forgot to cite Bassiliy et al. (2018) …. it seems that they also forgot to mention the existing lower bounds from Haghifam et al. (2022).\n\nA discussion on the work of Bassiley et al, in the context of CMI,  will be added here, and also the work of Haghifam et al will be reiterated.\n\n> Also in the CMI-bounds sub-subsection they describe wrong the CMI. \n\nThanks for the clarification, this detail can be fixed. This is an inaccuracy in the discussion part, it is self-contained and has little to no effect on the rest of the paper (which does not deal with the CMI bound)\n\n> Sometimes the sentences are a little overstated: e.g. in line 174 they say \"Theorem 1 shows that any algorithm with non-trivial learning guarantees must carry a dimension-dependent amount of information on the sample or require a large sample\". \n\nThis sentence appears in the discussion section, after stating the exact statement, and after establishing the paper's distribution-independent setup (a standard arrangement) in previous sections. In this context, which is distribution independent, there's no overstatement. The sentence, though, can be rephrased as: \"any algorithm with distribution-independent nontrivial guarantees...\"\n\n>Lemma 3 is used without any proof in the Appendix of the supplementary material, which is in the template of the submission to another conference whose main text differs in some places from the main text submitted.\n\nThanks for this input, there was indeed a mistake in the main text version that was attached to the appendix, apologies for the inconvenience and confusion. This will be fixed ofcourse, and the proof of Lemma 3 will be added to the appendix. For now, the proof does appear in the current reviewed manuscript exactly under the statement of Lemma 3 in the supplementary. \n\n\n\nQuestions:\n\n>Why is there a vector p such that for  (d/106m\\epsilon^2)  of the coordinates (22) holds? Why is it not possible that less cordinates have that value be much larger than 1/108?\n\nNotice that in (22) we take expectation only over the sample, i.e. one should think of (22) as an event that depends on the realization of (p,t). Thus, if for every p, (22) holds for less than (d/106m\\epsilon^2) of coordinates, then for every p, the probability of (22) to hold, conditioned on p and w.r.t t,  is less than (1/106m\\epsilon^2). Then, the probability (w.r.t p and t) of (22) to hold is less than (1/106m\\epsilon^2) which is a contradiction.\n\n>Why can you employ the data processing inequality after (24)?\n\nNotice that X_p(t) doesn’t depend on w_s as you write. (It depends on the variance of w_S but that is not a random variable but a fixed number determined by p and t)\n\n>Could the techniques from this paper be employed to also find lower bounds on stronger information-theoretic bounds\n\nYes, thank you very much for this question and for pointing out the bound of Bu et al. Because this was inquired by several reviewers, I will add an additional official comment that discusses this (and a full derivation can be added upon request).\n"}, {"review_id": "uTG4gsBStt", "reviewer": "Reviewer_dYAB", "summary": "This paper provides a lower bound on the mutual information between the output weights and the input training data in the context of stochastic convex optimization to examine the tightness of the mutual information-based generalization bound. It is shown in the paper that mutual information grows with the dimension of the parameter, which implies that existing information-theoretic generalization bounds fall short in capturing the generalization capabilities of SGD and regularized ERM, which have dimension-independent sample complexity.", "questions": "1.\tLine 212, to my understanding it should be d^{1/7}/m^{6/7}. Please double-check.\n2.\tLine 280, it is said that CMI_m(A)=O(m). Can you provide a reference or insights into why it is the case?\n3.\tLine 20 “inorder” should be “in order”.\n4.\tThe term suboptimality is often referred to as excess risk in literature.", "limitations": "No potential negative societal impact was observed.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "It is important to consider the lower bound (converse) result to understand the fundamental limits of information-theoretic analysis in characterizing the generalization of learning algorithms. To my understanding, pessimistic analysis can be more insightful than some ad-hoc method for tightening existing bounds.", "weaknesses": "1.\tIt is hard for me to understand why Theorem 1 holds for any learning algorithm. Let us take the Gibbs algorithm considered in Section 4.3 of (Xu and Raginsky [2017]) and further investigated in the following paper as an example.\n\nAminian, Gholamali, Yuheng Bu, Laura Toni, Miguel Rodrigues, and Gregory Wornell. \"An exact characterization of the generalization error for the Gibbs algorithm.\" Advances in Neural Information Processing Systems 34 (2021): 8106-8118.\n\nThe above reference provides an exact characterization of generalization error using information measures. It has been shown in their proof of Theorem 2 that the mutual information $I(S;W_S)$ can be upper bound by $O(1/n)$, which is independent of d. Thus, it is hard for me to digest the result presented in Theorem 1.\n\n2.\tThis paper mainly criticizes the tightness of the MI bound in (Xu and Raginsky [2017]) and the CMI bound in (Steinke and Zakynthinou [2020]). However, these issues are well-known in the literature. For example, MI can be infinite for deterministic learning algorithms. There are results tightening these results by considering the MI (or CMI) between W and each individual sample $Z_i$ (see below). Is there a way to show that these bounds also suffered from the same issue described in the paper?\n \nBu, Yuheng, Shaofeng Zou, and Venugopal V. Veeravalli. \"Tightening mutual information-based bounds on generalization error.\" IEEE Journal on Selected Areas in Information Theory 1, no. 1 (2020): 121-130.\n \nZhou, Ruida, Chao Tian, and Tie Liu. \"Individually conditional individual mutual information bound on generalization error.\" IEEE Transactions on Information Theory 68, no. 5 (2022): 3304-3316.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your detailed review. It seems the main weakness pointed out is an alleged contradiction between the result and existing upper bounds. There is no such contradiction and hopefully below it will be clarified, please do ask for further clarifications if this is not the case or if other issues were found to be emergent and are not resolved.\n\n> It is hard for me to understand why Theorem 1 holds for any learning algorithm. Let us take the Gibbs algorithm considered in Section 4.3 of (Xu and Raginsky [2017]) and further investigated in the following paper as an example.\n\nThere is no contradiction between the result in this paper and the analysis of the Gibbs algorithm. Notice that the bound on the information scales with the temperature hyper-parameter (\\alpha). In more detail, if the temperature is very low then the Gibbs algorithm behaves like an ERM algorithm and has no generalization guarantees. At the other extreme, if the temperature is very high the algorithm behaves close to purely random and one can achieve a non trivial generalization error/ MI bound, but in this extreme there will be a trivial train error - and as a result, trivial test error.. \n\nNotice that theorem 1 applies only to an algorithm with non-trivial **test error**. So there’s no contradiction and the conclusion is that, to obtain non trivial train error, the temperature must scale with the dimension. Notice also that it is trivial to obtain small MI-bounds to algorithms with trivial test error (e.g. random guessing) so the assumption of small test error is in fact necessary here.\n\n> However, these issues are well-known in the literature. For example, MI can be infinite for deterministic learning algorithms. There are results tightening these results by considering the MI (or CMI) between W and each individual sample  Z_i (see below). Is there a way to show that these bounds also suffered from the same issue described in the paper?\n\nThanks for the reference. First the issue shown in this paper is not that there are algorithms that carry information but that it is necessary to carry information for learning. The paper does not rule out the possibility of exploiting MI-type bounds in general, but to simply observe that some excess information is necessary.\n\nRegarding the specific variation proposed in Bu et al. Thanks for the reference. The argument depicted here can be easily applied to their setup. As this was asked by several reviewers I will provide a proof sketch in a separate official comment (a full derivation can also be provided upon request)\n\n\n>It is said that CMI_m(A)=O(m). Can you provide a reference or insights into why it is the case?\n\n.Given Z the entropy of S is merely the chosen example (i.e. z_i^1 or z_i^0), this is a r.v.with  2^m possible configurations hence entropy at most m.\n"}]

Author rebuttal:
Thank you very much for the thoughtful reviews.

Several reviewers pointed out to the work of Bu et al. and asked it the techniques can also be applied to this individual sample bound, here I am providing a proof sketch explaining why the technique easily applies. I will only show dependence on the dimension and not on the accuracy (similar to the technical overview in the main text) to avoid complications. Of course, a full derivation as is done in the paper can also be provided. But the argument here already shows that measuring the mutual information with the individual samples will not lead to dimension-free bounds (and that the proof is almost identical).


The main observation is that applying Lemma 2 we have that:

$$ \sum_{i=1}^m \sqrt{I(w_S(t),z_i(t))} = \sum_{i=1}^m \sqrt{I(\sqrt{d} w_S(t)-P(t),\sqrt{d} z_i(t)-P(t))} \ge \sum_{i=1}^m \Omega (E[(\sqrt{d} w_S(t)-P(t)) \cdot (\sqrt{d} z_i(t)-P(t))]^2)$$
and by convexity:
$$ \sum_{i=1}^m \Omega (E[(\sqrt{d} w_S(t)-P(t)) \cdot (\sqrt{d} z_i(t)-P(t))]^2) \ge m \Omega (E[(\sqrt{d} w_S(t)-P(t)) \cdot (\frac{1}{m}\sum_{i=1}^m  \sqrt{d} z_i(t)-P(t))]^2)$$

From here the derivation is the same where we use the fingerprinting Lemma to show that

$$ E[(\sqrt{d} w_S(t)-P(t)) \cdot (\frac{1}{m}\sum_{i=1}^m  \sqrt{d} z_i(t)-P(t))] = \Omega (1) $$ and we conclude that

$$ \frac{1}{m}\sum_{i=1}^m \sqrt{I(w_S(t),z_i(t))}  = \Omega (1) $$
for each single coordinate. By proper derivation we can show that the information accumulated in all coordinates scale with the dimension.

Meta-review: All reviewers agree to accept this paper. The paper is theoretically sound and sufficiently novel to grant acceptance to this conference.

For a camera-ready version, please take into the account the comments from all reviewers regarding typos and clarifications. In particular, please include:
- a discussion about additional results related to Bu et al.
- a proper discussion of Haghifam et al.
- some discussion about Gibbs algorithm
Decision: Accept (poster)