ERM 오라클을 활용한 표본 최적 다중 그룹 학습
Sample-Optimal Multi-Group Learning with an ERM Oracle
한국어 초록
다중 그룹 학습(multi-group learning)에서는 단일 예측기가 풍부하며 잠재적으로 무한하고 중첩될 수 있는 하위 집단 모음의 모든 그룹에 대해 해당 클래스 내 최적의 가설만큼 우수한 성능을 보여야 합니다. 최적의 표본 복잡도(sample complexity)를 갖는 기존 알고리즘들은 그룹과 가설의 모든 쌍을 추적하는데, 이는 관심 대상인 대규모 클래스에서는 불가능하며, 알려진 오라클 기반 알고리즘들은 더 열등한 수렴 속도를 갖습니다. 본 연구에서는 경험적 위험 최소화(ERM) 오라클을 통해서만 클래스에 접근하는 학습자가 최적의 수렴 속도를 달성할 수 있는지 질문을 던집니다. 본 논문에서는 그룹과 가설 쌍에 대한 가중치 적용 ERM 오라클을 다항 횟수만큼 호출하고 $\tilde{O}((d_G+d_H)/\varepsilon^2)$개의 표본을 사용하는 알고리즘을 제시합니다. 여기서 $d_G$와 $d_H$는 그룹 및 가설 클래스의 VC 차원이며, $\varepsilon$은 확률로 가중치가 부여된 모든 그룹에서의 초과 위험(excess risk)을 제한합니다. 또한 무제한의 계산 능력을 가진 모든 학습자에 대해서도 일치하는 하한인 $\Omega((d_G+d_H)/\varepsilon^2)$개의 표본을 보여줌으로써, 오라클 효율성을 위해 추가적인 표본이 소모되지 않음을 입증합니다. 아울러 모든 입력이 최대 $k$개의 그룹에 속하고 이러한 그룹들을 나열할 수 있는 자연스러운 특수 경우도 고려합니다. 이 경우 가설 클래스에 대한 ERM 오라클만으로 충분하며, 애그노스틱(agnostic) 설정에서는 $\tilde{O}((d_H+\log k)/\varepsilon^2)$개의 표본이, 모든 그룹에 대해 해당 그룹에서 올바른 가설이 존재하는 경우에는 $\tilde{O}((d_H+\log k)/\varepsilon)$개의 표본이 필요합니다.
원문 초록
In multi-group learning, a single predictor must perform nearly as well as the best hypothesis in a class on every group in a rich, possibly infinite and overlapping, collection of subpopulations. The known algorithms with the optimal sample complexity keep track of every pair of a group and a hypothesis, which is impossible for the large classes of interest, and the known oracle-based algorithms have a worse rate. We ask whether the optimal rate can be attained by a learner that accesses the classes only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses $\tilde{O}((d_G+d_H)/\varepsilon^2)$ samples and polynomially many calls to a weighted ERM oracle over pairs of a group and a hypothesis, where $d_G$ and $d_H$ are the VC dimensions of the group and hypothesis classes and $\varepsilon$ bounds the excess risk on every group, weighted by its probability. We also show a matching lower bound of $Ω((d_G+d_H)/\varepsilon^2)$ samples for every learner even with unlimited computation, so oracle efficiency costs no additional samples. We also consider a natural special case in which every input belongs to at most $k$ groups and these groups can be listed. In this case, an ERM oracle for the hypothesis class alone suffices, with $\tilde{O}((d_H+\log k)/\varepsilon^2)$ samples in the agnostic setting and $\tilde{O}((d_H+\log k)/\varepsilon)$ samples when every group has a hypothesis that is correct on it.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
보손 가우시안 상태는 언제 고전적으로 학습할 수 있는가?
When are bosonic Gaussian states classical to learn?
물리학의 근본적인 질문 중 하나는 양자계에서 고전적 거동이 언제 나타나는가이다. 보손 가우시안 상태(bosonic Gaussian state)는 빛의 고전적 장(field) 거동과 본질적인 양자적 성질을 모두 포착하므로, 이러한 양자-고전 경계를 탐구하기에 자연스러운 환경을 제공한다. 본 연구에서는 학습 이론의 관점에서 이 문제를 다루며 다음과 같이 묻는다. 보손 가우시안 상태는 언제 고전적으로 학습할 수 있는가? 즉, n-모드 보손 가우시안 상태를 고전적인 2n변량 가우시안 분포를 학습할 때 필요한 만큼 적은 샘플과 그만큼 단순한 연산으로 학습할 수 있는 조건은 (있다면) 무엇인가? 우리는 상태의 열적 요동(thermal fluctuation)에 의해 결정되는 학습 가능성의 매끄러운 크로스오버를 규명한다. - 차가운 가우시안 상태는 학습 측면에서 비고전적이다. 공분산 행렬이 $\Sigma\le(\frac12+O(\frac1n))I$를 만족하여 진공 공분산에 가까운 경우, 단일 복사본(single-copy, 즉 얽힘이 없는) 측정 하의 토모그래피(tomography)는 근본적으로 $\Omega(n^3)$개의 복사본을 필요로 하며, 이는 고전적 가우시안 분포를 학습하는 샘플 복잡도 $\Theta(n^2)$를 엄밀하게 초과한다. 우리는 소수 복사본에 대한 얽힘 측정이 허용되더라도 이러한 어려움이 지속됨을 보인다. - 따뜻한 가우시안 상태는 학습 측면에서 고전적이다. 열적 요동이 진공 잡음을 초과하여 임의의 매개변수 $\nu>0$에 대해 $\Sigma\ge(\frac12+\nu)I$로 나타내지는 경우, 단일 복사본 토모그래피에는 $N=\Theta\left(n^2\min(n,1+\nu^{-1})\right)$개의 복사본이 필요함을 증명한다. 이 한계는 타이트(tight)하며, 단순하고 비적응적(non-adaptive)이며 얽힘이 없는 헤테로다인(heterodyne) 측정으로 달성된다. 특히 $\nu=\Omega(1)$인 경우 샘플 복잡도는 $\Theta(n^2)$로 줄어들어 고전적인 경우와 일치한다. 우리의 결과는 보손 가우시안 상태의 학습 가능성에서 나타나는 양자-고전 크로스오버를 엄밀하게 규명하고, 근본 물리학과 통계적 학습 이론 사이의 새로운 연결고리를 드러내며, 실제 센싱 실험에도 시사점을 가진다.
VC 학습의 최적 정보 복잡도
The optimal information complexity of VC learning
Steinke와 Zakynthinou(2020)는 알고리즘 의존적 정보이론적 양에 기반하여 학습 알고리즘의 정보 복잡도를 분석하는 조건부 상호정보량(CMI) 프레임워크를 도입했습니다. 본 연구에서는 이러한 양 중 하나인 평가된 조건부 상호정보량(eCMI)을 연구합니다. CMI를 통한 알고리즘 의존적 분석으로부터 VC 클래스에 대한 최적의 PAC 보장을 복원할 수 있는지는 흥미로운 질문이었습니다. 본 논문에서는 개념 클래스의 VC 차원이 d일 때, 실현 가능(realizable)한 경우에서 eCMI가 O(d) 차수인 학습 알고리즘을 구축함으로써 이러한 보장을 복원할 수 있음을 보입니다. 구체적으로 본 알고리즘은 최적의 기댓값 일반화 보장을 갖는 5개 기반 학습기의 무작위화된 다수결(Majority-of-5) 방식입니다.
Decomposing Yes-No Bias in LLM Moral Judgment: Stance, Position, Word, and Verdict
영향력 있는 다원주의적 정렬 연구를 위한 로드맵
A Roadmap to Impactful Pluralistic Alignment Research
공정한 자기지도 학습을 위한 편향 없는 Open World 정규화
Unbiased Open World Regularization for Fair Self-Supervised Learning
텍스트-이미지 생성에서 대표 다양성을 위한 다축 Max@K 강화학습
Multi-Axis Max@K Reinforcement Learning for Representative Diversity in Text-to-Image Generation
토론
이 논문과 연결된 포럼 글이 아직 없습니다.