arXiv:2610.13442v1 stat.ML

압축을 통한 학습: 위험 추정치가 큰 수의 법칙 수렴 속도를 달성하다

Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate

Simone Garatti, Marco C. Campi

제출 2026-10-09

한국어 초록

압축 스키마(compression schemes)는 학습 알고리즘에 대한 데이터 의존적 위험 상한(risk bound)을 유도하기 위한 일반적인 프레임워크를 제공합니다. 선호 압축(preferent compression) 기반 학습 규칙의 경우, 기존 연구 결과들은 복원된 가설이 부적절한 학습(training) 예제들이 더해진 압축 집합의 크기로 정의되는 샘플 의존적 복잡도 $\boldsymbol{k}$를 바탕으로 위험의 상한을 설정합니다. 그러나 이러한 결과들은 $\boldsymbol{k}/N$ 위에 $O(\sqrt{\ln N/N})$ 차수의 마진(margin)을 유발합니다. 본 논문에서는 이 로그 팩터가 본질적인 것이 아님을 규명합니다. 우리는 모든 고정된 신뢰 수준 $1-δ$에 대해, 위험이 적어도 $1-δ$의 확률로 모든 가능한 $\boldsymbol{k}$ 값에 걸쳐 균일하게 다음과 같이 제한됨을 증명합니다: $$ \frac{\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right) $$ 따라서 선호 압축 기반 학습 알고리즘의 위험 추정치는 고정된 사건 확률의 경험적 추정치와 동일한 큰 수의 법칙 수렴 속도를 달성합니다. 또한 우리는 주요 항인 $\boldsymbol{k}/N$이 필수적임을 보이고, 이것과 경험적 위험(empirical risk) 간의 관계를 조사합니다. 특히, 경험적 위험이 $O(1/\sqrt{N})$ 수렴(convergence) 속도를 유지하는 체계뿐만 아니라, 복잡도 기반 추정기가 $O(1/\sqrt{N})$ 속도를 보존하는 반면 경험적 위험은 더 느리게 수렴하거나 일치성(consistency)을 잃는 체계를 규명합니다.

원문 초록

Compression schemes provide a general framework for deriving data-dependent risk bounds for learning algorithms. For learning rules based on preferent compression, existing results upper-bound the risk in terms of a sample-dependent complexity $\boldsymbol{k}$, defined as the cardinality of the compression augmented by the training examples on which the reconstructed hypothesis is inappropriate. These results, however, yield a margin of order $O(\sqrt{\ln N/N})$ above $\boldsymbol{k}/N$. In this paper, we establish that the logarithmic factor is not intrinsic. We prove that, for every fixed confidence level $1-δ$, the risk is bounded with probability at least $1-δ$ by $$ \frac{\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right), $$ uniformly over all possible values of $\boldsymbol{k}$. Thus, risk estimates for learning algorithms based on preferent compression attain the same law-of-large-numbers rate as the empirical estimate of the probability of a fixed event. We also show that the leading term $\boldsymbol{k}/N$ is necessary and investigate its relation to the empirical risk. In particular, we identify regimes in which the empirical risk retains the $O(1/\sqrt{N})$ convergence rate, as well as regimes in which it converges more slowly or ceases to be consistent, while the complexity-based estimator preserves the $O(1/\sqrt{N})$ rate.

제출 이력

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

  1. arXiv:2610.13442v1

함께 살펴볼 논문

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

arXiv:2303.08777v3stat.ML공통 태그 Generalization Bounds, statistical learning theory

분포 무관 편차 경계와 교차 검증 위험 추정을 통한 모델 선택 학습에서 도메인 지식의 역할

Distribution-free Deviation Bounds and The Role of Domain Knowledge in Learning via Model Selection with Cross-validation Risk Estimation

교차 검증(cross-validation)은 통계학과 머신러닝에서 위험 추정 및 모델 선택에 가장 널리 사용되는 도구 중 하나이지만, 학습 절차에 내재될 때의 이론적 특성은 아직 충분히 이해되지 않고 있다. 본 논문은 고전적 통계 학습 이론 내에서 교차 검증 위험 추정을 활용한 모델 선택을 통한 학습을 위한 일반적이고 분포 무관한 프레임워크를 개발한다. 우리는 전체 학습 파이프라인에 대해 VC 차원 기반의 편차 경계를 확립하며, 유계 및 비유계 손실 함수 모두에 대한 상세한 증명을 제공한다. 후자는 기존 결과의 새로운 확장을 필요로 한다. 분석의 핵심은 후보 모델 집합의 구조가 일반화에 어떻게 영향을 미치는가이다. 이를 위해 우리는 모델 복잡도의 증가를 반영하는 포함 구조를 갖춘 부분 순서가 부여된 후보 모델 집합으로서 학습 공간(Learning Spaces)을 도입한다. 우리는 학습 공간이 도메인 지식으로부터 어떻게 구성될 수 있는지를 보이고, 그러한 구조적 정보가 일반화를 어떻게 향상시키는지를 분석한다. 이 프레임워크는 고차원 선형 회귀에서의 사례 연구 및 시뮬레이션 연구를 통해 예시되며, 두 개의 서로 다른 학습 공간에서의 모델 선택을 통한 학습을 사전 지식과 실제 목표 간의 정합도가 다양한 시나리오에서 일반 최소제곱법, LASSO, 릿지 회귀(ridge regression)와 비교한다. 결과는 학습 공간이 목표에 잘 적응되어 있고 효율적인 탐색 알고리즘이 사용될 경우, 모델 선택을 통한 학습이 표준 방법을 수 배 이상 능가할 수 있음을 보여준다. 이론적 통찰과 구체적 예시를 통해, 우리는 교차 검증을 활용한 모델 선택의 성능을 향상시키기 위해 도메인 지식에 기반한 후보 모델 집합 선택에 대한 지침을 제공한다.

토론

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