Even Sharper Bounds for Transductive Learning and Its Applications¶
Conference: NeurIPS2026
arXiv: 2609.28459
Paper: https://arxiv.org/abs/2609.28459
Area: Learning Theory
Keywords: transductive learning, local complexity, sampling without replacement, modified log-Sobolev inequality, kernel learning
Version Read: arXiv v2, 2026-09-24; theoretical paper
TL;DR¶
The paper proves Bernstein-type supremum concentration through a two-parameter entropy closure for the swap walk, then uses local complexity to analyze transductive empirical risk minimization, removing both earlier sample-imbalance restrictions and an extra logarithmic confidence factor under bounded-loss and appropriate localization conditions, with applications to realizable VC classification and the empirical kernel spectrum.
Background & Motivation¶
Transductive learning does not draw a training sample and then confront independent new test data: the learner already observes all features in a fixed finite collection, receives labels for a randomly selected subset, and predicts the remaining points. Training and test indices are complementary, so their empirical averages are dependent. In inductive learning, local Rademacher complexity exploits the smaller fluctuations of low-risk functions to improve global bounds into a local fixed point plus a confidence term; importing an independent-sampling proof does not automatically produce an equally clean transductive guarantee.
The paper targets two distinct limitations of earlier transductive local-complexity analyses. Reference [6] already obtains fixed points plus \(x/\min\{u,m\}\), but requires \(u\gg m^{2}\) or \(m\gg u^{2}\); reference [7] removes this imbalance condition but retains \(\log_{2}(4\min\{u,m\}/\delta)\) multiplying the confidence term. Rather than introducing a new predictor, the paper improves concentration over the random split so that localization no longer incurs this extra factor for arbitrary relative sample sizes.
Core Idea: jointly track the test–train supremum and a squared-function auxiliary process on size-preserving swap geometry, handle random variance through a two-parameter entropy closure, and convert this into ERM excess test-risk bounds through one concentration event, geometric peeling, and surrogate localization.
Method¶
Overall Architecture¶
Sharper Transductive Local Complexity (STLC) is a proof chain, not a network architecture. It establishes swap concentration, a localized inequality for a gauge-rescaled class, and a two-fixed-point ERM comparison, before making the fixed points explicit through VC dimension or the empirical kernel spectrum. A diagram of proof sections would not represent a model pipeline and is therefore omitted.
The full labeled sample \(((\mathbf{x}_{i},y_{i}))_{i=1}^{n}\) is fixed, with \(n=m+u\). The learner observes all features and the labels indexed by the training set \(\bar Z\); \(\bar Z\) is a uniformly sampled set of \(m\) indices without replacement, and the test set \(Z\) is its complement. Feature values may repeat because sampling is over indices, not distinct feature values. The principal probabilities and expectations throughout the paper concern this split, not a newly generated i.i.d. sample.
Write \(\mathcal L_n(h)\), \(\mathcal L_m(h)\), and \(\mathcal L_u(h)\) for the averages of a function \(h\) over the full sample, training set, and test set, respectively; \(T_n(h)=\mathcal L_n(h^2)\) is its full-sample second moment, and \(N_{u,m}=\min\{u,m\}\geq2\). The concentration target is
Local complexity measures the expected one-sided supremum of subset averages relative to full-sample averages within a low-second-moment class. Specifically, write \(\mathfrak R_p^\eta(\mathcal A)=\mathbb E\sup_{h\in\mathcal A}\eta\{\mathcal L_p(h)-\mathcal L_n(h)\}\), where \(p\in\{u,m\}\) and \(\eta\in\{+1,-1\}\). This is not the complexity of a protocol in which the without-replacement split has been replaced by independent training and test samples.
The training ERM \(\widehat f_m\) minimizes training loss; the test oracle \(\widehat f_u\) minimizes test loss and is only an inaccessible comparator. The paper's excess risk is \(\mathcal E(\widehat f_m)=\mathcal L_u(\ell_{\widehat f_m})-\mathcal L_u(\ell_{\widehat f_u})\), not a risk difference over an unknown population distribution. The generic theorem requires a full-sample minimizer to exist and both empirical minima to be attained for every split; measurable selections among nonunique minimizers are allowed.
Key Designs¶
1. Swap concentration and two-parameter entropy closure: retain random variance in the joint analysis
On the space of all subsets of size \(u\), each step exchanges one test index with one training index, producing a swap walk on the Johnson graph. Its stationary distribution is exactly the uniform split distribution, and the modified log-Sobolev inequality connects the entropy of an exponential function to its one-step swap Dirichlet energy. Appendix C.1 also checks the normalization between the cited lazy down–up walk and the paper's non-lazy swap walk; constants cannot simply be reused after discarding self-loops.
The difficulty is that a supremum is not the linear average of a fixed function. At each subset, the author selects an approximately maximizing function and compares the neighboring subset using the same function, controlling the oriented variance that counts only decreasing swaps. Sending the approximation error to zero removes any need for the supremum over the class to be attained. When \(|h(i)|\leq H_0\) and \(T_n(h)\leq r\), this variance is controlled jointly by the deterministic radius and the auxiliary process \(Q(Z)=\sup_{h\in\mathcal H}\{\mathcal L_u(h^2)-T_n(h)\}\). Although \(Q\) can be negative pointwise, \(Q\geq-r\), so the relevant variance upper bounds remain nonnegative.
Applying the same swap estimate to the auxiliary process yields a self-bounding relation. The author centers the main and auxiliary processes separately and constructs their two-parameter log-moment generating function; the auxiliary mean under exponential tilting becomes a partial derivative of this function rather than being crudely replaced by its maximum possible value. The modified log-Sobolev inequality then produces a first-order differential inequality, integrated along a controlled backward characteristic before applying Chernoff's method. This is the mechanism behind removing the extra logarithmic confidence factor, rather than deleting a logarithm from the final expression.
The full concentration statement in Theorem IV.1 is that, for every \(x>0\), with split probability at least \(1-\exp(-x)\),
Here \(\mathcal H^2=\{h^2:h\in\mathcal H\}\), and \(\mathfrak R_{N_{u,m}}^+\) selects the positive complexity for the smaller side. The proof first handles \(u\leq m\) and treats the other case through complementation and sign reversal; this explains the smaller sample size without imposing extreme imbalance. The squared-class complexity remains present, so this is not a classical single-function Bernstein bound involving variance alone.
2. Gauge rescaling and geometric peeling: avoid paying confidence separately for every radius
Low-risk and high-risk functions cannot share one refined second-moment radius. Theorem IV.2 permits any deterministic surrogate functional \(\tilde T_n(h)\geq T_n(h)\) and requires a sub-root majorant to control the positive and negative local complexities on both sides of the split, as well as squared-class complexities under the same localization constraint. A sub-root function is nonnegative and nondecreasing, with \(\psi(r)/\sqrt r\) nonincreasing; its positive fixed point satisfies \(\psi(r_{u,m})=r_{u,m}\).
For each function, the proof selects the smallest geometric shell radius \(w(h)\) that is no smaller than its surrogate radius, then rescales the function to \(rh/w(h)\). Every function in the rescaled class has second moment at most \(r\), so the concentration inequality is applied only once to this class. The expected complexities are then controlled by peeling according to \(w(h)\), rather than establishing a separate high-probability event for every shell and taking a confidence union bound.
Appendix C-C uses shell ratio \(\lambda=4\) and the sub-root property to bound the geometric sums for the linear and squared classes by \(2\psi(r)\) and \(8\psi(r)/7\), respectively. The fixed point converts \(\psi(r)\) into \(\sqrt{rr_{u,m}}\); calibrating \(r\) absorbs the square-root deviation into the surrogate-radius and fixed-point terms. Deterministic inverse rescaling finally yields, simultaneously for every function,
This event has probability at least \(1-\exp(-x)\). The constants are \(d_0=4+4c_0/7\), \(c_1=8K_0d_0^2\), and \(c_2=1752K_0+32H_0+\sqrt{219}\). These constants are not small: the principal improvement concerns dependence structure and rates, rather than numerically tight small-sample certificates.
3. Surrogate localization and two-fixed-point ERM comparison: control the difference between two random minimizers
The generic result assumes \(0\leq\ell_f(i)\leq L_0\) on the full sample. Let \(f_n^*\) be a full-sample risk minimizer and \(g_f=\ell_f-\ell_{f_n^*}\). Besides existence of this minimizer, the empirical Bernstein condition \(T_n(g_f)\leq B\mathcal L_n(g_f)\) must hold for every \(f\). Its right-hand side is the nonnegative full-sample excess mean, not a variance condition over an unknown data distribution.
This condition controls excess losses around \(f_n^*\), whereas the final comparison involves \(\widehat f_m\) and \(\widehat f_u\), both dependent on the random split. The author therefore defines, for an arbitrary loss difference \(h\),
A loss difference may have multiple representations; taking the infimum makes localization depend only on the function \(h\). Since the square of a difference is at most twice the sum of the two squares, every representation supplies a second-moment upper bound, and taking their infimum preserves \(T_n(h)\leq\tilde T_n(h)\). Attainment of this infimum is unnecessary.
The first fixed point \(r_{u,m}\) controls the paired loss-difference class under surrogate localization; the second, \(r^*\), controls the excess-loss class around \(f_n^*\) localized by \(B\mathcal L_n(g_f)\). Appendix C.8 applies the localized inequality in both split orientations, and C.10 uses empirical optimality and an absorbable coefficient to bound the full-sample excess losses of both random minimizers. Finally, the uniform event is applied to their loss difference. Training ERM optimality makes the training-risk difference nonpositive, allowing the preceding two bounds to control the surrogate radius.
Consequently, Theorem IV.4 gives, for every \(x>0\), with split probability at least \(1-3\exp(-x)\),
Here \(H_0=L_0\), and \(c_\Delta\) depends only on \(B,L_0\). The three failure terms come from a union bound over the final localization event and the two full-sample comparison events. For example, \(x=\log(3/\delta)\) gives failure probability at most \(\delta\), without the additional multiplier \(\log_2(4N_{u,m}/\delta)\) in the earlier result. Existence of the fixed points and their majorization of local complexities still require justification; this is not an unconditional fast rate for every bounded learning problem.
4. VC and kernel-spectrum specialization: turn abstract fixed points into interpretable complexity
In realizable binary classification, one function matches every label in the full sample, and squared loss for binary predictions is the error indicator. Thus \(h^2=h\) and \(T_n(h)=\mathcal L_n(h)\), the squared class coincides with the original class, and training ERM loss is zero. Appendix C-E uses a relative VC deviation bound to transfer full-sample localization to empirical \(L_2\) localization on an auxiliary with-replacement sample, then applies contraction and Dudley's entropy integral to the good and bad events.
Auxiliary with-replacement sampling is only a tool for upper-bounding complexity: it samples the uniform distribution on the fixed index set and does not change the actual training protocol. VC entropy gives a sub-root majorant of the form \(C\sqrt{a_mr}+Ca_m\), where \(a_m=d^{\mathrm{(VC)}}\log(me/d^{\mathrm{(VC)}})/m\), with a fixed point of order \(a_m\). Theorem IV.2 with \(K_0=2\) absorbs half of the full-sample error into the test error and yields V.1, without the three events needed for the generic ERM comparison.
For kernel learning, the prediction class is a radius-\(\mu\) ball in the RKHS subspace spanned by all full-sample features. Let \(\widehat\lambda_1\geq\cdots\geq\widehat\lambda_n\geq0\) be the eigenvalues of the full Gram matrix \(\mathbf K/n\), not a training submatrix. Besides bounded loss and minimizer existence, the result requires an \(L\)-Lipschitz loss and the prediction-localization condition
Lipschitz continuity converts prediction second moments into loss second moments, so the generic Bernstein condition holds with \(B_K=\max\{1,L^2B'\}\). However, Lipschitz continuity alone does not imply the prediction-localization condition; V.2 cannot be claimed for every kernel and every bounded loss.
Appendix C.11 splits the empirical covariance eigenbasis after direction \(Q\): the spectral head is controlled by the local empirical second moment, contributing \(\sqrt{rQ/p}\), while the spectral tail is controlled by the RKHS norm, contributing \(\mu\sqrt{\sum_{q>Q}\widehat\lambda_q/p}\), for \(p\in\{u,m\}\). In C-F, prediction localization converts the surrogate loss radius into a prediction radius, contraction controls losses and their square class, and fixed-point inequalities are solved. Both fixed points are controlled by the spectral expression, and the constructed second fixed point satisfies \(r_{u,m}\leq r^*\leq2r_{u,m}\).
Finally, define
Theorem V.2 gives \(\mathcal E(\widehat f_m)\leq c_5\{\min_Qr(u,m,Q)+x/N_{u,m}\}\) with probability at least \(1-3\exp(-x)\), where \(c_5\) depends only on \(K_0,B',L_0,L,\mu\). The head–tail trade-off reflects effective complexity rather than a new hyperparameter that must be optimized during training. A singular Gram matrix permits multiple coefficient representations of the same function; the proof divides only along positive-eigenvalue directions and treats the zero-spectrum case separately.
Key Experimental Results¶
The source contains no empirical experiments; the following compares theoretical results and assumptions.
Main Results¶
“Main Results” here refers to the principal theorems, not dataset accuracy, runtime, or numerical ablations.
| Result | Guarantee | Split probability | Required scope |
|---|---|---|---|
| IV.4: generic ERM | \(c_1r_{u,m}+4Bc_\Delta r^*/K_0+c_3x/N_{u,m}\) | \(1-3\exp(-x)\) | \(u,m\geq2\); bounded loss, minimizer existence, empirical Bernstein condition, and local-complexity majorants for two classes |
| V.1: realizable VC classification | \(c_0''d^{\mathrm{(VC)}}\log(me/d^{\mathrm{(VC)}})/m+c_1'x/m\) | \(1-\exp(-x)\) | Binary functions and labels; full-sample realizability; \(u\geq m\geq d^{\mathrm{(VC)}}\geq2\) |
| Lower-bound comparison for V.1 | Expected minimax lower bound \((d^{\mathrm{(VC)}}-1)/(16m)\) | An expectation lower bound, not the same high-probability statement | The comparison additionally requires \(m\geq9\); a logarithmic gap remains in the upper bound |
| V.2: transductive kernel learning | \(c_5\{\min_Qr(u,m,Q)+x/N_{u,m}\}\) | \(1-3\exp(-x)\) | RKHS ball, bounded loss, Lipschitz continuity, and prediction localization; constants depend on \(K_0,B',L_0,L,\mu\) |
Ablation Study¶
There are no empirical ablations; the roles of assumptions and proof mechanisms are compared instead. These are not measurements obtained by removing modules.
| Condition or mechanism | Role in the proof | Boundary that must not be crossed |
|---|---|---|
| Fixed full sample and uniform index splitting without replacement | Matches the swap walk's stationary distribution to the learning protocol | Not a guarantee for distribution shift or arbitrary label selection |
| \(T_n(h)\leq B\mathcal L_n(h)\) | Converts risk radii around the full-sample minimizer into second-moment radii | Bounded loss alone does not imply the generic fast rate |
| Two-parameter entropy closure | Jointly handles the supremum and squared-function auxiliary process | The improvement is not a direct application of a single-function tail bound |
| One concentration event plus rescaled-class peeling | Sums geometric shells at the expected-complexity level | Does not introduce an additional shellwise confidence logarithm |
| Realizable binary loss | \(h^2=h\) and training error is \(0\), permitting a single-event proof | V.1 does not directly cover nonrealizable classification |
| Kernel prediction localization and Lipschitz continuity | Connects loss localization to the empirical spectral head–tail bound | An unconditional fast-rate claim for every kernel is invalid |
Key Findings¶
- The generic result only requires \(u,m\geq2\) for sample sizes, without an imbalance growth condition; the VC application separately requires \(u\geq m\geq d^{\mathrm{(VC)}}\geq2\). These restrictions must not be conflated.
- The VC upper bound has the standard inductive local-complexity rate form but remains a logarithmic factor above the cited expected minimax lower bound; the paper does not remove \(\log(me/d^{\mathrm{(VC)}})\).
- The kernel result removes the \(n/u\) and \(n/m\) multipliers on fixed points in an earlier bound, not all fixed points or all sample-size dependence.
- Appendix D-B sets \(Q=0\) to obtain \(\min_Qr(u,m,Q)\leq\sqrt{\operatorname{tr}(\mathbf K/n)}(u^{-1/2}+m^{-1/2})\). If the empirical spectrum changes with the full sample, removal of prefactors alone does not establish a universal asymptotic advantage.
Highlights & Insights¶
- The most reusable contribution is the treatment of random variance: a squared-function supremum need not first become a separate bad event and can instead enter the entropy analysis jointly with the target supremum. This improves the confidence cost, not the expressive power of the function class.
- One concentration event for the rescaled class separates probability control from geometric peeling: peeling sums expected complexities, while confidence is paid on the uniform event alone. This is better suited to sharp confidence dependence than giving every radius its own high-probability statement.
- The surrogate functional bridges a condition centered on a fixed minimizer and a comparison between two random minimizers. Taking an infimum over representations also illustrates that localization can be an analytical quantity rather than a training quantity directly computable by the learner.
Limitations & Future Work¶
- The results concern a random split of a fixed full sample. Sharing the fixed-point structure of inductive bounds does not establish the same generalization guarantee for future points from an unknown population distribution.
- The generic theorem relies on boundedness, an empirical Bernstein condition, attained minima, and effective local-complexity majorants. Appendix E identifies extension beyond bounded classes as open; heavy-tailed losses are not covered directly.
- The VC application concerns realizable binary classification and retains a logarithmic gap relative to the expected minimax lower bound. Neither nonrealizability nor removal of this rate logarithm is resolved by the current theorem.
- The kernel application requires additional prediction localization. Although all features determine the kernel spectrum, checking that condition involves full labels and the minimizer; it is not an unconditional certificate verifiable without labels.
- Concentration and peeling constants are large, and the paper presents no algorithm implementation or empirical comparison. Whether finite-sample numerical bounds improve requires separately comparing constants, spectra, and valid assumptions.
Related Work & Insights¶
- vs Bartlett–Bousquet–Mendelson [5]: The paper inherits sub-root fixed points and local Rademacher analysis, but its probability space is a without-replacement split of a fixed collection. The shared feature is bound structure, not the risk object of independent sampling.
- vs Yang [6]: The earlier result already has a similar fixed-point and confidence form but requires \(u\gg m^2\) or \(m\gg u^2\); swap concentration and two-parameter closure remove this relative-size restriction.
- vs Yang [7]: The earlier analysis allows general relative sizes but multiplies the confidence term by \(\log_2(4N_{u,m}/\delta)\); this paper obtains \(x/N_{u,m}\) directly. Comparisons still need matched total failure probabilities.
- vs Tolstikhin–Blanchard–Kloft [10]: The earlier kernel bound in Appendix D.1 contains \((n/u)r_m^*+(n/m)r_u^*+x(1/m+1/u)\); the new spectral bound lacks the imbalance multipliers on the first two terms. The earlier normalization and respective assumptions still need to be matched.
- vs Tolstikhin–Lopez-Paz [9]: Their lower bound locates the minimax difficulty of realizable classification. Expectation lower bounds and high-probability upper bounds are different statements, making “near-optimal up to a logarithmic factor” appropriate rather than exact minimax optimality.
Rating¶
- Novelty: 4/5. Two-parameter entropy closure and uniform rescaling with peeling provide a specific confidence improvement over earlier transductive bounds.
- Experimental Thoroughness: Not applicable. This is a theoretical paper without empirical experiments; theorems and appendix proofs cover the generic, VC, and kernel applications.
- Writing Quality: 4/5. Main-text roadmaps correspond clearly to complete proofs; the local text contains duplicated mathematical extraction artifacts, so formulas must be read through the intact LaTeX fragments.
- Value: 4/5. A cleaner local-complexity tool for general relative training and test sizes, although strong assumptions and large constants limit direct numerical use.