Blackwell 접근 가능성(Approachability)과 경사 평형(Gradient Equilibrium)의 동등성

경사 평형 (Gradient Equilibrium, GEQ)은 오프라인 최적화(offline optimization)의 1차 정지성(first-order stationarity)을 일반화하고 온라인 정형 예측 (online conformal prediction)과 같은 문제들을 추상화하는 최근 도입된 온라인 최적화 프레임워크입니다. GEQ는 기존의 온라인 학습 프레임워크, 즉 후회 최소화 (regret minimization)와 흥미로운 유사성을 가지고 있지만, 이전 연구들은 GEQ 오차와 후회(regret)가 비교할 수 없는 목적임을 보여주었으며, 이로 인해 GEQ가 더 넓은 온라인 학습 지형에서 어떻게 자리 잡는지에 대한 정확한 이해가 미결 과제로 남아 있었습니다. 본 연구에서 우리는 알고리즘적 관점에서 GEQ가 Blackwell 접근 가능성 (Blackwell approachability)과 동등함을 보여줍니다. 즉, Blackwell 접근 가능성 문제는 블랙박스 GEQ 오라클 (black-box GEQ oracle)에 대한 질의를 사용하여 오라클의 오차율에 있어 점근적 손실 없이 항상 해결될 수 있으며, 그 역도 성립합니다. 접근 가능성, 후회 최소화, 그리고 교정 (calibration) 사이의 알려진 동등성과 결합하여, 이러한 결과들은 GEQ 또한 이 프레임워크들과 동등함을 시사합니다. 우리의 환원 (reduction) 방식은 효율적이며, 낙관주의 (optimism) 및 강력한 적응성 (strong adaptivity)과 같은 정교한 보장 사항들을 후회 최소화에서 GEQ로 전달하는 데 사용될 수 있습니다. 이 과정에서 우리는 또한 GEQ를 위한 필요충분조건을 식별하고, 제약 없는 결정 집합과 제약된 결정 집합을 가진 서로 다른 GEQ 개념들 사이의 환원을 확립합니다.