최소-최적 표본 복잡도를 달성하는 결정론적 다중 교정 알고리즘

한줄 요약

최소-최적 표본 복잡도를 달성하는 결정론적 다중 교정 알고리즘을 제시하고, 결과 구별 불가능성 및 전방 예측기로 확장한다.

풀어야 하는 문제

다중 교정은 예측의 신뢰성을 위한 기본 속성이지만, 기존의 최소-최적 표본 복잡도를 달성하는 예측기는 모두 무작위화된 것이었다. 결정론적 예측기는 표본 복잡도가 훨씬 나빴으며, 무작위화가 필요한지 여부는 공개 문제였다.

접근 방법

저자들은 최소-최적 표본 복잡도 O~(ε^{-3})을 달성하는 결정론적 다중 교정 알고리즘을 설계했다. 이를 유한 또는 유한하게 덮힌 테스트 모음에 대한 결과 구별 불가능성으로 일반화하고, 결정론적 전방 예측기와 전방 예측기로 확장했다.

결과·기여

결정론적 예측기로도 최적 표본 복잡도가 가능함을 증명하여 공개 문제를 해결했다. 또한 결정론적 전방 예측기와 전방 예측기의 최적 표본 복잡도를 달성하여 [OKK25]와 [BHHLZ25]의 문제를 해결했다.