arXiv:2605.06710v2 cs.IT

학습과 추정의 정보 이론적 한계

Information-theoretic Limits of Learning and Estimation

Abbas El Gamal, Maxim Raginsky

제출 2026-11-17

한국어 초록

정보 이론은 계산 능력과 무관하게 어떠한 학습 또는 추정 알고리즘이 달성할 수 있는 것과 없는 것에 대한 근본적 한계를 확립하는 데 중심적인 역할을 한다. 이 초안은 이러한 연결에 대한 입문을 제공한다. 먼저 집중 부등식과 함께 거리 공간에서의 덮개(covering)와 패킹(packing)의 개념, 그리고 이와 관련된 거리 엔트로피 개념을 소개한다. 이러한 도구는 본 분석에 필수적이다. 이어서 학습 이론적 프레임워크를 소개하고, 거리 엔트로피, Rademacher 복잡도, VC 차원, 그리고 상호 정보량과 상대 엔트로피로 표현되는 일반화 오차의 상한을 유도한다. 마지막으로 미니맥스 추정 프레임워크를 논의하고, Fano 부등식을 이용하여 상대 엔트로피와 덮개 및 패킹 수로 표현되는 미니맥스 위험의 하한을 확립한다. 본 원고의 상당히 개정 및 보강된 버전은 Cover와 Thomas의 Elements of Information Theory 제3판의 두 개 장으로 수록될 예정이다. 문의는 abbas@ee.stanford.edu로 연락하기 바란다.

원문 초록

Information theory plays a central role in establishing fundamental limits on what any learning or estimation algorithm can -- and cannot -- achieve, regardless of computational power. This draft provides an introduction to these connections. We begin by introducing concentration inequalities along with the notions of covering and packing in metric spaces, and the associated concept of metric entropy. These tools are essential for our analysis. We then introduce the learning-theoretic framework and derive upper bounds on generalization error in terms of metric entropy, Rademacher complexity, and the VC dimension, as well as mutual information and relative entropy. Finally we discuss the minimax estimation framework and establish lower bounds on minimax risk using Fano's inequality, yielding bounds in terms of relative entropy and covering and packing numbers. A significantly revised and augmented version of this manuscript will appear as two chapters in the forthcoming third edition of Cover and Thomas's Elements of Information Theory. For questions, please contact abbas@ee.stanford.edu.

제출 이력

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

  1. arXiv:2605.06710v2제출 시각 미확인

함께 살펴볼 논문

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

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

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