One-sentence Summary

This work establishes a precise tradeoff between excess error and conditional mutual information in stochastic convex optimization, proving CMI lower bounds of $\Omega ( 1 / \varepsilon ^ { 2 } )$Ω(1/ε2) for $L ^ { 2 }$L2 Lipschitz-bounded settings and $\Omega ( 1 / \varepsilon )$Ω(1/ε) for strongly convex settings, and demonstrates that memorization is inherent by constructing an adversary capable of identifying a significant fraction of training samples.

Key Contributions

• Memorization is defined as the information a learner reveals about its training samples and is measured by conditional mutual information, yielding lower bounds of Ω(1/ε^2) in the L2 Lipschitz bounded setting and Ω(1/ε) under strong convexity for any learner with excess error ε.
• An adversary is constructed for specific stochastic convex optimization instances that accurately identifies a significant fraction of the training samples, showing that memorization is essential for learning these problems.
• Corollaries prove that sample compression schemes achieving sample complexity Θ(1/ε^2) for Lipschitz bounded losses or Θ(1/ε) for strongly convex losses require size Ω(n) when the dimension is at least Ω(n^4 log n), implying limitations of generalization bounds based on CMI and sample incompressibility in stochastic convex optimization.

Introduction

The paper revisits how much a learner must know about its training data in order to generalize. In machine learning, stochastic convex optimization (SCO) provides a tractable model for modern gradient-based training, especially because first-order algorithms can often generalize well even when the parameter dimension is large. This makes SCO a natural testbed for the tension between ideal learning, which extracts structure without memorizing noise, and deep models, which can achieve high accuracy while retaining training examples. Earlier information-theoretic explanations mainly used input-output mutual information, but that measure conflates the number of memorized points with the entropy stored in each point and is known to scale badly with dimension. Building on conditional mutual information, the authors prove tight CMI-accuracy tradeoffs for ε-learners in SCO, showing that sample-efficient learning requires CMI on the order of the optimal sample size. They also show that this information can be interpreted as memorization, since an adversary can identify a constant fraction of training examples, and they derive consequences for generalization bounds and the impossibility of constant-size sample compression.

Method

The analysis is organized as an information-theoretic pipeline for characterizing what an accurate $\varepsilon$ε-learner must reveal about its training sample. Rather than studying a concrete neural architecture or training loop, the method treats a learning algorithm $\mathcal{A}_n$An​ as a randomized channel that maps a training set $S_n$Sn​ to an estimator $\widehat{\theta}=\mathcal{A}_n(S_n)$θ=An​(Sn​), and then asks how many bits of sample information must leak through this channel whenever the learner achieves a target accuracy. The resulting framework connects excess risk, sample complexity, conditional mutual information, and algorithmic information usage under stochastic convex optimization problems.

At the center of the framework is the excess error decomposition for a stochastic convex optimization problem $(\Theta,\mathcal{Z},f)$(Θ,Z,f). For a data distribution $\mathcal{D}$D, define the population and empirical objectives

$$\mathrm{F}_{\mathcal{D}}(\theta)=\mathbb{E}_{Z\sim\mathcal{D}}[f(\theta,Z)], \qquad \widehat{\mathrm{F}}_{S_n}(\theta)=\frac{1}{n}\sum_{i=1}^n f(\theta,Z_i).$$FD​(θ)=EZ∼D​[f(θ,Z)],FSn​​(θ)=n1​i=1∑n​f(θ,Zi​).

A standard way to control the expected excess population error is to split it into a generalization term and an optimization term:

$$\mathbb{E}\left[\mathrm{F}_{\mathcal{D}}(\mathcal{A}_n(S_n))\right] - \min_{\theta\in\Theta}\mathrm{F}_{\mathcal{D}}(\theta) \le \operatorname{EGE}_{\mathcal{D}}(\mathcal{A}_n) + \mathbb{E}\left[ \widehat{\mathrm{F}}_{S_n}(\mathcal{A}_n(S_n)) - \min_{\theta\in\Theta}\widehat{\mathrm{F}}_{S_n}(\theta) \right].$$E[FD​(An​(Sn​))]−θ∈Θmin​FD​(θ)≤EGED​(An​)+E[FSn​​(An​(Sn​))−θ∈Θmin​FSn​​(θ)].

For convex $L$L-Lipschitz losses over a parameter space of diameter bounded by $R$R, the conditional mutual information based generalization bound controls the generalization term by

$$\operatorname{EGE}_{\mathcal{D}}(\mathcal{A}_n) \le LR\sqrt{\frac{8\,\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n)}{n}}.$$EGED​(An​)≤LRn8CMID​(An​)​​.

This gives the information-dependent excess error control

$$\mathbb{E}\left[\mathrm{F}_{\mathcal{D}}(\mathcal{A}_n(S_n))\right] - \min_{\theta\in\Theta}\mathrm{F}_{\mathcal{D}}(\theta) \le LR\sqrt{\frac{8\,\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n)}{n}} + \mathbb{E}\left[ \widehat{\mathrm{F}}_{S_n}(\mathcal{A}_n(S_n)) - \min_{\theta\in\Theta}\widehat{\mathrm{F}}_{S_n}(\theta) \right].$$E[FD​(An​(Sn​))]−θ∈Θmin​FD​(θ)≤LRn8CMID​(An​)​​+E[FSn​​(An​(Sn​))−θ∈Θmin​FSn​​(θ)].

The first analytical module checks whether this decomposition is sharp for optimal learners. The optimal sample complexity for learning convex Lipschitz losses at accuracy $\varepsilon$ε is on the order of

$$\Theta\left(\left(\frac{LR}{\varepsilon}\right)^2\right).$$Θ((εLR​)2).

The framework then constructs distributions under which every learner with near-optimal sample complexity has large conditional mutual information. In the normalized case $L=R=1$L=R=1, the conditional mutual information of any $\varepsilon$ε-learner scales as

$$\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n) = \Omega\left(\frac{1}{\varepsilon^2}\right).$$CMID​(An​)=Ω(ε21​).

After restoring the dependence on $L$L and $R$R, this implies that the conditional mutual information term must be large enough that

$$LR\sqrt{\frac{\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n)}{n}} = \Theta(LR),$$LRnCMID​(An​)​​=Θ(LR),

even though the learner may achieve excess error at most $\varepsilon$ε. Thus, for such problems, the conditional mutual information based generalization bound cannot certify the optimal excess risk of every optimal-sample-complexity learner. The limitation is not tied to one specific algorithm; it is universal across algorithms whose sample complexity matches the statistical minimum.

The lower-bound construction is built in stages. The first stage constructs a hard convex Lipschitz problem. In the simplified normalized case, one sets

$$\mathcal{Z}=\left\{\pm \frac{1}{\sqrt d}\right\}^d, \qquad \Theta=B_d(1), \qquad f(\theta,z)=-\langle\theta,z\rangle.$$Z={±d​1​}d,Θ=Bd​(1),f(θ,z)=−⟨θ,z⟩.

This loss is convex and $1$1-Lipschitz. Its population optimum is determined by the distributional mean

$$\mu=\mathbb{E}_{Z\sim\mathcal{D}}[Z].$$μ=EZ∼D​[Z].

The second stage proves that any accurate learner must produce an output that is strongly aligned with $\mu$μ. More concretely, for every accurate learner and suitable distribution, one can establish correlations of the form

$$\|\mu\|-\varepsilon \le \mathbb{E}\left[\langle \widehat{\theta},\mu\rangle\right], \qquad \widehat{\theta}=\mathcal{A}_n(S_n).$$∥μ∥−ε≤E[⟨θ,μ⟩],θ=An​(Sn​).

This says that a learner that predicts well on average must implicitly encode information about the mean of the unknown data distribution. Since the learner only observes finite samples, the framework then converts this mean-correlation into correlation with individual training samples. A weighted coordinate correlation expression of the form

$$\mathbb{E}\left[ \sum_{i=1}^n\sum_{k=1}^d \frac{144\varepsilon^2-d(\mu^{(k)})^2}{1-d(\mu^{(k)})^2} \, \widehat{\theta}^{(k)} \left(Z_i^{(k)}-\mu^{(k)}\right) \right] \ge 2\varepsilon-4\delta$$E[i=1∑n​k=1∑d​1−d(μ(k))2144ε2−d(μ(k))2​θ(k)(Zi(k)​−μ(k))]≥2ε−4δ

is used to quantify how the learned parameter tracks sample fluctuations around the mean. Equivalently, one can aggregate these coordinates through a diagonal weighting matrix $A$A and define sample-wise statistics

$$T_{0,i}=\langle \widehat{\theta},A(Z_{0,i}-\mu)\rangle, \qquad T_{1,i}=\langle \widehat{\theta},A(Z_{1,i}-\mu)\rangle.$$T0,i​=⟨θ,A(Z0,i​−μ)⟩,T1,i​=⟨θ,A(Z1,i​−μ)⟩.

The conditional mutual information construction introduces two possible realizations $Z_{0,i}$Z0,i​ and $Z_{1,i}$Z1,i​ for each sample coordinate, together with a hidden bit $U_i$Ui​ indicating which realization is used in the actual training set. The learner’s output and these statistics are then examined through the lens of $U_i$Ui​.

The key information-counting idea is to identify coordinates where the two possible realizations straddle a carefully chosen threshold. With

$$\tau=\Theta\left(\frac{\varepsilon}{n}\right),$$τ=Θ(nε​),

define

$$\mathcal{I} = \left\{ i: \max\{T_{0,i},T_{1,i}\}>\tau \ \text{and}\ \min\{T_{0,i},T_{1,i}\}<\tau \right\}.$$I={i:max{T0,i​,T1,i​}>τ and min{T0,i​,T1,i​}<τ}.

For coordinates in $\mathcal{I}$I, the learner’s statistic is sensitive to which realization was present, so these coordinates tend to reveal the hidden bits $U_i$Ui​. The high-dimensional parameter $d\ge \Omega(n^4\log n)$d≥Ω(n4logn) ensures that the statistic corresponding to the unused realization is small with high probability, while the aggregate correlation with the actual samples remains large. The cardinality of $\mathcal{I}$I is then related to a ratio of sums:

$$|\mathcal{I}| = \Omega\left( \frac{\left(\sum_{i=1}^n T_{U_i,i}\right)^2} {\sum_{i=1}^n T_{U_i,i}^2} \right).$$∣I∣=Ω(∑i=1n​TUi​,i2​(∑i=1n​TUi​,i​)2​).

Using the lower bound on the aggregate correlation and an upper bound on the squared aggregate, one obtains

$$\mathbb{E}|\mathcal{I}| = \Omega\left(\frac{1}{\varepsilon^2}\right),$$E∣I∣=Ω(ε21​),

which translates into

$$\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n) = \Omega\left(\frac{1}{\varepsilon^2}\right)$$CMID​(An​)=Ω(ε21​)

for the normalized convex Lipschitz instance. After rescaling, this yields the corresponding lower bound for general $L$L and $R$R.

The next module extends the argument from proper learners, whose outputs lie in $B_d(1)$Bd​(1), to improper learners, whose outputs may lie anywhere in $\mathbb{R}^d$Rd. This is done by replacing the original constrained loss with an extension to the full space:

$$\widetilde{f}(\theta,z) = \inf_{w\in B_d(1)} \left\{ f(w,z)+\|\theta-w\| \right\}.$$f​(θ,z)=w∈Bd​(1)inf​{f(w,z)+∥θ−w∥}.

For the linear loss $f(\theta,z)=-\langle\theta,z\rangle$f(θ,z)=−⟨θ,z⟩, this modified loss remains convex and $1$1-Lipschitz. The analysis then projects any improper learner’s output back onto $B_d(1)$Bd​(1):

$$\Pi(\widehat{\theta}) = \Pi(\mathcal{A}_n(S_n)),$$Π(θ)=Π(An​(Sn​)),

where $\Pi$Π denotes projection onto the unit ball. Projection does not increase conditional mutual information because of the data processing inequality. Moreover, if the improper learner is accurate for the extended problem, then the projected learner is accurate for the original constrained problem. Therefore, the improper case reduces to the proper case, and the same conditional mutual information lower bound follows.

The framework also includes matching upper bounds, which show that the lower bounds are not artifacts of the particular hard instances. For convex Lipschitz losses, there exists a proper $\varepsilon$ε-learner with sample complexity

$$N(\varepsilon,\delta) = \frac{128(LR)^2}{\varepsilon^2}\log\left(\frac{2}{\delta}\right),$$N(ε,δ)=ε2128(LR)2​log(δ2​),

such that, whenever $n\ge N(\varepsilon,\delta)$n≥N(ε,δ), the learner satisfies

$$\mathrm{F}_{\mathcal{D}}(\mathcal{A}_n(S_n)) - \min_{\theta\in\Theta}\mathrm{F}_{\mathcal{D}}(\theta) \le \varepsilon$$FD​(An​(Sn​))−θ∈Θmin​FD​(θ)≤ε

with probability at least $1-\delta$1−δ, and its information complexity obeys

$$\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n) \le \frac{128(LR)^2}{\varepsilon^2}\log\left(\frac{2}{\delta}\right).$$CMID​(An​)≤ε2128(LR)2​log(δ2​).

This matching construction places an upper envelope on the amount of sample information required by optimal learners. It shows that, for this class, the conditional mutual information required for learning and the sample complexity needed for accuracy scale in a compatible $\varepsilon^{-2}$ε−2 manner.

A parallel pipeline handles strongly convex losses. The hard problem is defined by

$$\Theta=\mathbb{R}^d, \qquad \mathcal{Z}=\left\{\pm \frac{1}{\sqrt d}\right\}^d, \qquad f(\theta,z)=-\langle\theta,z\rangle+\frac{1}{2}\|\theta\|^2.$$Θ=Rd,Z={±d​1​}d,f(θ,z)=−⟨θ,z⟩+21​∥θ∥2.

The population optimum is again the mean $\mu=\mathbb{E}_{\mathcal{D}}[Z]$μ=ED​[Z], and for any output $\widehat{\theta}$θ the excess population risk reduces to a squared Euclidean distance:

$$\mathrm{F}_{\mathcal{D}}(\widehat{\theta}) - \min_{\theta\in\mathbb{R}^d}\mathrm{F}_{\mathcal{D}}(\theta) = \frac{1}{2}\|\widehat{\theta}-\mu\|^2.$$FD​(θ)−θ∈Rdmin​FD​(θ)=21​∥θ−μ∥2.

Because the data mean lies inside $B_d(1)$Bd​(1), any output can be projected onto $B_d(1)$Bd​(1) without increasing excess risk. Projection also does not increase conditional mutual information, so the analysis can focus on learners whose outputs lie inside the unit ball.

For such learners, accuracy implies not only alignment with $\mu$μ, but also closeness to $\mu$μ:

$$\|\widehat{\theta}-\mu\|^2\le 2\varepsilon$$∥θ−μ∥2≤2ε

with high probability. A fingerprinting-style lemma then guarantees the existence of a distribution for which the learner’s output correlates with the sample fluctuations:

$$\mathbb{E}\left[ \sum_{i=1}^n \langle \widehat{\theta}-\mu, Z_i-\mu\rangle \right] \ge \frac{1}{3}-2\varepsilon-3\delta.$$E[i=1∑n​⟨θ−μ,Zi​−μ⟩]≥31​−2ε−3δ.

The conditional mutual information construction uses the statistics

$$T_{0,i}=\langle \widehat{\theta}-\mu, Z_{0,i}-\mu\rangle, \qquad T_{1,i}=\langle \widehat{\theta}-\mu, Z_{1,i}-\mu\rangle.$$T0,i​=⟨θ−μ,Z0,i​−μ⟩,T1,i​=⟨θ−μ,Z1,i​−μ⟩.

A boundary set is again defined using a threshold $\tau=\Theta(1/n)$τ=Θ(1/n):

$$\mathcal{I} = \left\{ i: \max\{T_{0,i},T_{1,i}\}>\tau \ \text{and}\ \min\{T_{0,i},T_{1,i}\}<\tau \right\}.$$I={i:max{T0,i​,T1,i​}>τ and min{T0,i​,T1,i​}<τ}.

The same information-counting logic applies. The cardinality of $\mathcal{I}$I is lower bounded by a ratio of aggregate correlation terms:

$$|\mathcal{I}| = \Omega\left( \frac{\left(\sum_{i=1}^n T_{U_i,i}\right)^2} {\sum_{i=1}^n T_{U_i,i}^2} \right).$$∣I∣=Ω(∑i=1n​TUi​,i2​(∑i=1n​TUi​,i​)2​).

In the strongly convex case, the numerator is bounded below by a constant under the construction, while the denominator scales like $O(\varepsilon)$O(ε). This yields

$$\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n) = \Omega\left(\frac{1}{\varepsilon}\right).$$CMID​(An​)=Ω(ε1​).

A matching upper bound for strongly convex Lipschitz losses shows that there exists a learner with sample complexity depending on $L^2/(\lambda\varepsilon)$L2/(λε), where $\lambda$λ denotes the strong convexity parameter, such that

$$\mathbb{E}[\mathrm{F}_{\mathcal{D}}(\mathcal{A}_n(S_n))] - \min_{\theta\in\Theta}\mathrm{F}_{\mathcal{D}}(\theta) \le \varepsilon,$$E[FD​(An​(Sn​))]−θ∈Θmin​FD​(θ)≤ε,

and

$$\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n) \le O\left(\frac{L^2}{\lambda\varepsilon}\right).$$CMID​(An​)≤O(λεL2​).

Thus the strongly convex pipeline produces a tighter $\varepsilon^{-1}$ε−1 dependence rather than the $\varepsilon^{-2}$ε−2 dependence of the convex Lipschitz case.

The framework also considers a refined information measure called individual sample conditional mutual information, defined by

$$\mathrm{ISCMI}_{\mathcal{D}}(\mathcal{A}_n) = \sum_{i=1}^n I\left( \mathcal{A}_n(S); U_i \mid Z_{0,i},Z_{1,i} \right).$$ISCMID​(An​)=i=1∑n​I(An​(S);Ui​∣Z0,i​,Z1,i​).

This quantity is designed to avoid the conditioning structure of standard conditional mutual information, which can be large even for some natural deterministic learners. It is always bounded above by standard conditional mutual information:

$$\mathrm{ISCMI}_{\mathcal{D}}(\mathcal{A}_n) \le \mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n).$$ISCMID​(An​)≤CMID​(An​).

The lower-bound construction therefore checks whether the previously derived tradeoffs depend only on the more demanding conditioning used by standard conditional mutual information. The result is negative: the same $\Omega(1/\varepsilon^2)$Ω(1/ε2) lower bound for convex Lipschitz learning and the same $\Omega(1/\varepsilon)$Ω(1/ε) lower bound for strongly convex learning persist for individual sample conditional mutual information. In other words, the necessity of sample information revealed by accurate learners is robust to this refinement.

Overall, the methodological structure is a sequence of reduction steps: first connect excess risk to information leakage, then build hard geometric problem instances, then prove that accurate learners must correlate with distributional mean and individual samples, then convert correlation into hidden-bit recovery, and finally match the lower bounds with explicitly constructed learners. The resulting framework characterizes not only whether a generalization bound is mathematically valid, but also whether that bound can tightly track the information that optimal learners are forced to expose during training.

Experiment

The evaluation studies the relationship between mutual information and accuracy in stochastic convex optimization by considering Lipschitz convex and strongly convex objectives in high-dimensional settings. The results establish information lower bounds for ε-learners and show that these bounds are tight through matching upper bounds obtained via subsampling and stability-based learning. A recall-based memorization game further validates that the information captured by a learner can be exploited by an adversary to identify actual training examples, connecting large CMI to concrete memorization behavior.