시뮬레이터를 이용한 학습: 계산적으로 제한된 환경에서의 후회 없음

일반화에 필요한 최소한의 가정을 이해하는 것이 학습 이론의 근본적인 질문입니다. 불행하게도, 대부분의 결과는 데이터 생성 과정의 독립성(또는 그 대리 지표)에 크게 의존하며, 강하게 종속된 데이터에 대한 결과는 훨씬 더 제한적입니다. 이 격차를 해소하기 위해, 우리는 학습자가 데이터를 생성하는 분포를 근사하는 시뮬레이터에 접근할 수 있는 '시뮬레이트 가능한 과정(simulatable processes)'의 프레임워크를 도입합니다 (이 분포는 임의로 복잡하고 종속적인 과정일 수 있습니다). 놀랍게도, 이러한 시뮬레이터에 접근할 수 있다는 사실만으로, 우리는 독립적인 데이터가 있는 고전적 설정과 동일한 학습 보장(learning guarantees)을 회복할 수 있음을 보여줍니다. 즉, VC 차원(VC dimension)에 의존하는 오차 경계입니다. 나아가, 우리는 이 프레임워크를 사용하여 조건부 샘플링(conditional sampling)의 힘을 연구하고 이 설정에서 엄격한 통계적 및 계산적 이점을 보여줍니다. 우리 프레임워크의 하이라이트로, 우리는 주어진 VC 클래스를 모든 유한 다항 시간 내에 샘플링 가능한 모든 과정 하에서 동시에 학습하는 단일 알고리즘을 제시하며, 이때 후회(regret)는 과정의 시간 제한된 Kolmogorov 복잡도에 의해 제어됩니다. 이는 고전적인 PAC 모델에 상당한 개념적 확장을 제공합니다.