커널 밴딧에서 알고리즘 복잡도와 미니맥스 복잡도의 차이를 규명

한줄 요약

GP-UCB와 DEC 방법을 통합하는 MAIR 프레임워크를 제안하고, 커널 밴딧에서 알고리즘 복잡도가 미니맥스 복잡도보다 더 유용할 수 있음을 증명했다.

풀어야 하는 문제

기존의 GP-UCB와 DEC 방법은 서로 다른 이론적 배경을 가지고 있어 통합된 이해가 부족했다. 특히, 알고리즘 복잡도와 클래스 전체 미니맥스 복잡도 간의 관계와 차이를 명확히 규명할 필요가 있었다.

접근 방법

MAIR 프레임워크를 도입하여 GP-UCB의 알고리즘적 사전분포와 MAMS의 미니맥스 접근법을 통합했다. 이종 양의 정부호 알고리즘 사전분포를 사용하여 두 방법을 일반화하고, 두 장점을 결합한 보호된 마스터 알고리즘을 제안했다. 또한, 커널 밴딧 설정에서 알고리즘 복잡도가 과대모수화된 모델에서 더 유용함을 보이는 구체적인 구성을 제공했다.

결과·기여

알고리즘 정보와 클래스 전체 미니맥스 계수가 다른 질문에 답하며, 커널 밴딧에서 그 차이가 수학적으로 명확히 드러남을 보였다. 이는 밴딧 이론에서 알고리즘 복잡도와 미니맥스 복잡도의 관계에 대한 새로운 통찰을 제공한다.