PaperlayerView exact revision on arXiv

Source-linked AI summary

Even Sharper Bounds for Transductive Learning and Its Applications

Yingzhen Yang

arXiv:2609.28459v2cs.LGcs.ITmath.ITmath.STstat.TH

TL;DR

Transductive local-complexity bounds have lacked the inductive fixed-point and confidence structure without either split-size restrictions or an extra logarithmic confidence factor. The paper introduces STLC, using Bernstein-type concentration and localization, and obtains generic bounds plus realizable-VC and kernel-learning applications.

  • Problem

    Earlier transductive local-complexity results either impose an imbalance condition or include an additional logarithmic confidence factor.

    Source: §I · p. 1

  • Method

    STLC combines Bernstein-type concentration for the test–train supremum with peeling and a surrogate localization functional.

    Source: B. Main Results · p. 3, §VI · p. 6

  • Results

    For realizable binary classes with u ≥ m ≥ d(VC), the excess-risk bound is O{d(VC) log(me/d(VC))/m}, and the kernel bound is spectrum-adaptive without earlier imbalance prefactors.

    Source: §I · p. 1, §VI · p. 6

  • Takeaways & Limitations

    The generic confidence term has order x/Nu,m without an imbalance condition, and the realizable VC rate is within a logarithmic factor of the transductive minimax lower bound when m ≥ 9.

    Source: §I · p. 1, B. Main Results · p. 3

    Extending the analysis beyond bounded function classes remains an open direction.

    Source: Appendix E · p. 26

Abstract

from arXiv · show

We introduce Sharper Transductive Local Complexity (STLC), a localized complexity method for transductive learning under uniform sampling without replacement. The construction starts from a Bernstein-type concentration inequality for the supremum of the test--train empirical process. Its proof uses the modified log-Sobolev inequality for the swap walk and a two-parameter entropy closure. A peeling argument with a surrogate localization functional then gives excess-risk bounds with the same fixed-point and confidence terms as the classical inductive local Rademacher-complexity bounds, without the additional logarithmic confidence factor in earlier transductive results. For realizable learning over a binary class of VC dimension $\dVC$, with training size $m$, test size $u$, and $u\ge m\ge\dVC$, STLC yields $\cO\{\dVC\log(me/\dVC)/m\}$. This matches the standard inductive rate and, when $m\ge9$, is within a logarithmic factor of the transductive minimax lower bound of order $\dVC/m$. For transductive kernel learning, STLC gives a spectrum-adaptive excess-risk bound without the multiplicative imbalance factors appearing in the earlier local-complexity bound.

I. INTRODUCTION

Transductive learning evaluates predictions on the complement of a uniformly sampled training subset from a fixed full sample. This paper develops local-complexity bounds for that setting without requiring a particular balance between training and test sizes.

I. INTRODUCTION

  • The central question is whether sampling without replacement admits inductive-style fixed-point and confidence terms without restrictions on the relative training and test sizes.Source: §I · p. 1
  • Earlier transductive bounds either require strongly imbalanced set sizes or incur an additional logarithmic confidence factor, which the generic result removes.The new confidence term is proportional to x/min{u,m}.Source: §I · p. 1

III. SUMMARY OF MAIN RESULTS

  • For realizable binary classes, the bound is O{d(VC) log(me/d(VC))/m}; for transductive kernel learning, it is spectrum-dependent without earlier imbalance factors.The VC bound is within a logarithmic factor of the minimax lower bound when m ≥ 9.Source: §I · p. 1

II. PROBLEM SETUP OF TRANSDUCTIVE LEARNING

  • A uniformly sampled training subset is labeled, and predictions are evaluated on the complementary test subset of the fixed full sample.The split is sampled without replacement.Source: §I · p. 1, §II · p. 2

A. Basic Definitions

The paper defines the transductive quantities and complexity tools used in its bounds, then combines a swap-walk concentration result with localization and peeling. The resulting bounds include a realizable VC rate and apply without an imbalance condition.

A. Basic Definitions

  • The test–train process compares test and training averages, while exchanging the two sets gives the reverse process.Source: A. Basic Definitions · p. 2
  • A sub-root function has a unique positive fixed point, which serves as the localization threshold in the subsequent bounds.The function is nonnegative and nondecreasing, and its ratio to the square root of its argument is nonincreasing.Source: A. Basic Definitions · p. 3

B. Main Results

  • The main results proceed from swap-walk concentration to a uniform local-complexity bound and then to empirical-risk bounds, with confidence term x/Nu,m and no imbalance condition.Source: B. Main Results · p. 3
  • For realizable binary classes with u ≥ m ≥ d(VC), the VC specialization gives O{d(VC) log(me/d(VC))/m}.Source: B. Main Results · p. 3

A. Concentration Inequality for the Test-Train Process

B. Sharper Transductive Local-Complexity Bound

The sharper transductive local-complexity bound localizes function classes using a surrogate for the full-sample second moment. Its proof combines concentration with peeling around a sub-root fixed point.

B. Sharper Transductive Local-Complexity Bound

  • The bound uses a surrogate localization functional that upper-bounds the full-sample second moment of each function.Source: B. Sharper Transductive… · p. 4
  • A sub-root function with positive fixed point ru,m controls the localized classes at radii r ≥ ru,m.Source: B. Sharper Transductive… · p. 4
  • The proof rescales functions into a localized class, applies concentration, peels into geometric shells, and sums their complexities using the sub-root property.A deterministic rescaling inequality then returns the bound to the original functions.Source: B. Sharper Transductive… · p. 4

C. Sharp Excess Risk Bounds using STLC for Generic Transductive Learning

The generic STLC excess-risk result bounds empirical risk minimization under bounded losses and an empirical Bernstein condition. Its proof transfers full-sample controls to the test risk through a surrogate radius.

C. Sharp Excess Risk Bounds using STLC for Generic Transductive Learning

  • The result studies transductive excess risk relative to a test-risk oracle and applies to any measurable empirical-minimizer selection when the minima are attained.An ε-optimal oracle gives a risk quantity within ε of the infimum when the test minimum is not attained.Source: C. Sharp Excess Risk Bounds using STLC… · p. 4
  • The main assumption supplies a full-sample risk minimizer and controls each excess-loss second moment by its nonnegative full-sample mean.Source: C. Sharp Excess Risk Bounds using STLC… · p. 4
  • For bounded squared loss with a convex evaluation-vector set, the empirical Bernstein condition holds with B = 4L0.Source: C. Sharp Excess Risk Bounds using STLC… · p. 4
  • With probability at least 1 − 3 exp(−x), the generic bound has the inductive fixed-point and confidence structure, up to constants multiplying ru,m and r∗.The proof controls full-sample excess losses in both split directions before using empirical optimality to relate test and training risk.Source: C. Sharp Excess Risk Bounds using STLC… · p. 5

V. APPLICATIONS

The applications apply the generic STLC bounds to realizable binary classification and transductive kernel learning. In the realizable setting, one predictor agrees with every full-sample label.

V. APPLICATIONS

  • STLC is applied to realizable binary classification and transductive kernel learning.The realizable setting assumes a predictor agrees with every full-sample label.Source: §V · p. 5
  • The realizable application uses a predictor that agrees with every full-sample label.Source: §V · p. 5
  • Detailed proofs of the applications are deferred to Appendix C.Source: §V · p. 5

A. Transductive Learning Over Binary-Valued Function Classes

The applications specialize STLC to realizable binary classification and transductive kernel learning. The binary-class result assumes full-sample realizability, while the kernel result bounds fixed points using the empirical kernel spectrum.

A. Transductive Learning Over Binary-Valued Function Classes

  • The realizable VC result assumes a binary class with 2 ≤ d(VC) < ∞, u ≥ m ≥ d(VC), and a predictor fitting every full-sample label.The bound applies to any empirical minimizer of training loss.Source: A. Transductive Learning Over… · p. 5
  • The proof roadmap localizes empirical L2 error using a VC relative-deviation inequality, then bounds localized Rademacher processes with symmetrization, contraction, and Dudley’s entropy integral.The resulting sub-root majorant has a fixed point of order d(VC) log(me/d(VC))/m.Source: A. Transductive Learning Over… · p. 5
  • The realizable rate matches the corresponding inductive local-complexity rate and, for m ≥ 9, is within a logarithmic factor of the expected minimax lower bound.Source: A. Transductive Learning Over… · p. 5

1) Background in RKHS and Kernel Learning:

  • The kernel prediction class is a radius-µ ball in the finite-sample span of kernel sections, and positive definiteness permits positive semidefinite Gram matrices.When the Gram matrix is singular, different coefficient vectors may represent the same RKHS element.Source: 1) Background in RKHS and Kernel… · p. 6

2) Results:

  • The kernel result assumes bounded losses, minimizer existence, and Lipschitz and prediction-localization conditions.The Lipschitz condition also yields the stated loss Bernstein condition under the accompanying assumptions.Source: 2) Results · p. 6
  • Theorem V.2 states that a positive constant c5, depending only on K0, B′, L0, L, and µ, applies for every x > 0 with probability at least 1 − 3 exp(−x) over Z.The theorem assumes a positive definite kernel, Assumptions 1(1) and 2, and 0 ≤ ℓf(i) ≤ L0 for every f ∈ F and i ∈ [n], with L0 > 0.Source: 2) Results · p. 6
  • The kernel proof splits the eigen-expansion at Q, combines a head term with a spectral-tail term, and minimizes the resulting fixed-point bounds over Q.Lipschitz contraction transfers the prediction-process bound to loss differences.Source: 2) Results · p. 6

VI. CONCLUSION

The paper introduces Sharper Transductive Local Complexity for uniform sampling without replacement, using a Bernstein-type concentration inequality for the test–train supremum. Its applications give a near-optimal realizable VC bound and a spectrum-adaptive kernel bound without earlier imbalance prefactors.

VI. CONCLUSION

  • STLC uses a Bernstein-type concentration inequality for the test–train supremum under uniform sampling without replacement.Source: §VI · p. 6
  • Peeling with a surrogate localization functional yields generic bounded-loss excess-risk bounds with a sharp confidence term.Source: §VI · p. 6
  • The applications provide a near-optimal realizable VC bound and a spectrum-adaptive kernel-learning bound without earlier imbalance prefactors.Source: §VI · p. 6

APPENDIX A MATHEMATICAL TOOLS

The appendices collect empirical-process tools and compare centered-supremum concentration under sampling without replacement with earlier guarantees. The new bound avoids their split-imbalance restrictions and yields convergence as the smaller split grows.

APPENDIX A MATHEMATICAL TOOLS

  • The mathematical tools include contraction and entropy bounds, a VC-class concentration inequality, and comparisons between transductive and with-replacement complexities.The VC proof bounds its fixed point using the Sauer entropy estimate.Source: Appendix A · pp. 7–8

APPENDIX B CONCENTRATION OF CENTERED SUPREMA UNDER SAMPLING WITHOUT REPLACEMENT

  • The appendix derives simultaneous centered one-sided process bounds by applying the test–train concentration result to H and −H and combining their tails.Centering each function by its full-sample mean leaves the empirical processes invariant, allowing a centered-class formulation.Source: Appendix B · p. 8, A. A centered formulation · p. 9

B. Comparison with earlier bounds

  • For fixed confidence and bounded class parameters, the Rademacher-complexity comparison yields convergence whenever min{u, m} grows, regardless of the relative split sizes.The argument uses the with-replacement complexity comparison and contraction inequality.Source: B. Comparison with earlier bounds · p. 9
  • The new centered-supremum bound needs neither an imbalance condition nor an auxiliary failure parameter and controls both one-sided suprema simultaneously.Earlier guarantees have complementary regime dependence and do not give a vanishing bound at the critical scale u ≍ √n without additional information.Source: B. Comparison with earlier bounds · p. 9

A. Background in Modified Log-Sobolev Inequality

The proof uses the swap walk on uniformly sampled subsets to establish concentration for the test–train supremum. Oriented swap-variance bounds and a two-parameter log-MGF closure lead to the stated tail bound.

A. Background in Modified Log-Sobolev Inequality

  • The uniform distribution on u-subsets is analyzed through a reversible swap walk whose modified log-Sobolev constant is at least 1/u.The proof relates this walk to a down–up walk on the bases of a uniform matroid.Source: A. Background in Modified Log-Sobolev… · p. 10

B. Proof of Theorem IV.1 and Corollary B.1

  • Oriented swap variances for the supremum and its squared-class auxiliary process are bounded using nearly maximizing functions and second-moment control.An ε-maximizer argument removes the need for the supremum to be attained.Source: B. Proof of Theorem IV.1 and Corollary… · pp. 11–12
  • The proof closes the mixed supremum and auxiliary-process terms with a two-parameter log-MGF argument along a backward characteristic curve.The closure controls the log-MGF before Chernoff optimization produces the tail bound.Source: B. Proof of Theorem IV.1 and Corollary… · pp. 12–13
  • The concentration proof centers both processes, applies the modified log-Sobolev inequality and oriented-variance bounds, then optimizes the resulting Chernoff bound.When u exceeds m, complementation and sign reversal reduce the argument to the smaller split.Source: B. Proof of Theorem IV.1 and Corollary… · pp. 13–14

C. Proofs of Theorem IV.2

The proof of Theorem IV.2 localizes the class through a gauge rescaling, applies concentration on geometric shells, and uses the sub-root fixed point to absorb the localization term.

C. Proofs of Theorem IV.2

  • Gauge rescaling constructs a localized class whose second-moment radius meets the hypotheses of the concentration theorem.The proof then applies concentration to the rescaled class.Source: C. Proofs of Theorem IV.2 · pp. 14–15
  • Peeling the rescaled class and its square class into geometric shells lets the proof sum shell complexities using the sub-root property.The shell bounds apply to both sample orientations and both one-sided processes.Source: C. Proofs of Theorem IV.2 · p. 15
  • Choosing the localization radius makes the square-root term absorbable, yielding a bound with fixed-point and confidence terms.The proof uses the sub-root fixed point and a deterministic localization lemma to complete the bound.Source: C. Proofs of Theorem IV.2 · pp. 15–16

D. Proof of Theorem IV.4

Theorem IV.4 applies the uniform STLC bound to empirical risk minimization using a surrogate localization functional and full-sample excess-loss controls. The realizable VC application reduces squared loss to an indicator class and solves the resulting localized fixed point.

D. Proof of Theorem IV.4

  • Theorem IV.4 combines the uniform STLC event with full-sample excess-loss controls to bound ERM excess risk.The proof uses a surrogate functional that majorizes the excess-loss class's second moments.Source: D. Proof of Theorem IV.4 · pp. 17–18

E. Proof of Theorem V.1

  • The VC proof transfers full-sample localization to with-replacement empirical L2 localization using a relative VC bound.Contraction and entropy integration then control the localized complexity.Source: E. Proof of Theorem V.1 · pp. 18–19
  • In the realizable VC case, squared loss becomes an indicator loss, so the loss class is indicator-valued and its empirical second moment equals its mean.This permits Theorem IV.2 to be applied with H0 = 1 and the empirical mean as the localization functional.Source: E. Proof of Theorem V.1 · p. 18
  • Solving the sub-root fixed point gives a VC-scale bound proportional to d(VC) log(me/d(VC))/m under u ≥ m ≥ d(VC).The proof uses that p ↦ log(pe/d(VC))/p is nonincreasing for p ≥ d(VC), and then applies Theorem IV.2.Source: E. Proof of Theorem V.1 · p. 21

F. Proof of Theorem V.2: STLC-Based Excess Risk Bound for Transductive Kernel Learning

The kernel proof uses an empirical-covariance spectral estimate to control localized complexities, then compares fixed points and applies the generic STLC theorem to bound excess risk.

F. Proof of Theorem V.2: STLC-Based Excess Risk Bound for Transductive Kernel Learning

  • The spectral estimate expands functions in the empirical covariance eigenbasis and splits the Rademacher sum into leading and tail coordinates, controlled by empirical L2 and RKHS radii.The empirical covariance operator has ordered nonnegative eigenvalues, with exactly rank(K_n) of them positive.Source: F. Proof of Theorem V.2: STLC-Based… · pp. 21–22
  • A corollary gives a uniform localized-complexity bound with fixed-point and confidence terms for every h in the loss-difference class.Its probability is at least 1 − exp(−x), and the bound includes the surrogate functional ˜T_n(h).Source: F. Proof of Theorem V.2: STLC-Based… · p. 23
  • Localized loss differences are majorized using contraction and the class’s symmetry and convexity, producing sub-root functions for the two sample sizes.The proof also establishes existence of the empirical minimizers and handles zero-loss or singleton-class cases separately.Source: F. Proof of Theorem V.2: STLC-Based… · pp. 24–25
  • The positive fixed point is bounded by a minimum over spectral cutoffs Q, with constants depending on kernel and loss parameters.The proof compares the excess-loss fixed point with the localized fixed point and bounds it by twice the latter.Source: F. Proof of Theorem V.2: STLC-Based… · p. 25
  • The proof applies the generic STLC theorem after verifying its hypotheses, yielding the stated high-probability result for the kernel setting.The supplied passage gives probability at least 1 − 3 exp(−x), but omits the bound’s displayed right-hand side.Source: F. Proof of Theorem V.2: STLC-Based… · pp. 24–25

APPENDIX D MORE DETAILED COMPARISONS TO EXISTING WORKS

The comparisons report a sharper confidence term for realizable binary classes and kernel learning, and a kernel bound without earlier imbalance prefactors. The discussion also states the bounded-function scope and identifies extension beyond it as open.

A. More Detailed Comparison for Transductive Learning Over Binary-Valued Function Classes

  • Theorem V.1 removes the log2(4m/δ) factor from the confidence term in [7, Theorem 6.1] while retaining the stated realizable VC rate.The comparison assumes u ≥ m, so N_{u,m} = m.Source: A. More Detailed Comparison for… · p. 25

B. More Detailed Comparisons for Transductive Kernel Learning

  • At the displayed-bound level, (V.2) lacks the n/u and n/m prefactors in [10], but this algebra alone gives no universal asymptotic conclusion.The empirical spectrum may change with the full sample.Source: B. More Detailed Comparisons for… · p. 26
  • Theorem V.2 removes the log2(4 min {u, m}/δ) factor from the compared kernel bound, while the earlier [6] result requires an imbalanced regime.The stated imbalanced regimes are u ≫ m² or m ≫ u².Source: B. More Detailed Comparisons for… · p. 26

APPENDIX E MORE DISCUSSIONS

  • The present results require no relation between m and u and give a nearly minimax-optimal realizable VC bound for m ≥ 9; extending beyond bounded function classes remains open.The discussion also identifies a spectrum-dependent kernel bound.Source: Appendix E · p. 26
Loading 2609.28459v2…