arXiv:2609.28459v1 cs.LG

트랜스덕티브 학습을 위한 더욱 엄밀한 경계와 그 응용

Even Sharper Bounds for Transductive Learning and Its Applications

Yingzhen Yang

제출 2026-09-24

한국어 초록

복원 없는 균등 샘플링 하에서의 트랜스덕티브 학습(transductive learning)을 위한 국소화 복잡도 기법인 Sharper Transductive Local Complexity(STLC)를 제안한다. 이 구성은 테스트-학습 경험적 과정(test--train empirical process)의 상한(supremum)에 대한 Bernstein 유형의 집중 부등식(concentration inequality)에서 출발한다. 이 부등식의 증명에는 스왑 워크(swap walk)에 대한 수정된 log-Sobolev 부등식과 두 매개변수 엔트로피 폐쇄(two-parameter entropy closure)가 사용된다. 이어서 대리 국소화 범함수(surrogate localization functional)를 이용한 필링(peeling) 논증을 적용하면, 기존 트랜스덕티브 결과에 존재하던 추가적인 로그 신뢰도 인자 없이도, 고전적인 귀납적 국소 Rademacher 복잡도 경계와 동일한 고정점 항 및 신뢰도 항을 갖는 초과 위험(excess-risk) 경계를 얻을 수 있다. VC 차원이 $\dVC$인 이진 클래스에 대한 실현 가능(realizable) 학습에서, 학습 크기가 $m$, 테스트 크기가 $u$이며 $u\ge m\ge\dVC$일 때, STLC는 $\cO\{\dVC\log(me/\dVC)/m\}$을 도출한다. 이는 표준적인 귀납적 수렴률과 일치하며, $m\ge9$일 때 $\dVC/m$ 차수의 트랜스덕티브 미니맥스 하한과 로그 인자 이내로 일치한다. 트랜스덕티브 커널(kernel) 학습에 대해서는, STLC가 기존 국소 복잡도 경계에 나타나던 곱셈 형태의 불균형 인자 없이 스펙트럼 적응형(spectrum-adaptive) 초과 위험 경계를 제공한다.

원문 초록

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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2609.28459v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.07513v2cs.LG공통 태그 Learning Theory, Transductive Learning

데이터 증강 그래프 정규화를 통한 준지도 학습의 빠른 수렴률

Fast Rates for Semi-Supervised Learning via Data-Augmentation Graph Regularization

자기지도 학습(self-supervised learning)은 전체 레이블의 일부만으로 지도 학습 수준의 정확도를 달성하지만, 이를 뒷받침하는 레이블 샘플 효율성에 대한 이론적 설명은 부족했다. 본 연구에서 이를 제공한다. 데이터 증강은 비레이블 데이터에 유사도 그래프(similarity graph)를 형성하며, 따라서 해당 그래프에서의 하위(downstream) 학습은 그래프 라플라시안 정규화(graph-Laplacian-regularized) 학습이다. Johnson and Zhang (JMLR 2007)의 leave-one-out 안정성(leave-one-out stability) 기법을 증강 그래프에 적용하여, 한계 기반 분석(정확한 커널, 일반화 가능한 특징)의 비현실적 가정 없이, 지도 학습의 $O(1/\sqrt{n_L})$ 대신 레이블 수 $n_L$에 대해 $O(1/n_L)$의 빠른 transductive 수렴률을 증명한다. 이 경계는 증강 품질을 명시적으로 드러낸다. 기대 오차는 최대 $C/n_L + R_{\mathrm{DA}}(y)$이며, 여기서 데이터 증강 정렬 오류 $R_{\mathrm{DA}}(y)$는 레이블 경계를 가로지르는 증강의 graph-cut mass에 비례하므로, 좋은 증강을 사용하면 적은 레이블로 충분하다. 분석은 표준 목적 함수의 projector, negative-sample, orthogonality 오버헤드를 제거한 간소화된 손실을 사용하지만, Zhai et al.이 연구한 증강-커널 고유공간(augmentation-kernel eigenspace)에서 무한 데이터 한계(infinite-data limit)에 있는 top-$K$ 이상적 특징(ideal features)을 여전히 복원한다. 이 경계는 증강 품질을 통해 정확도-레이블 수 곡선에 대한 기제적 설명을 제공하며, 상수가 알려진 통제 모델(controlled model)에서 이를 검증한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.