앵커링된 낙관적 방법(Anchored Optimistic Method)을 통한 가속화 및 안정적인 수렴

우리는 min-max 최적화(optimization)에서 발생하는 단조 변분 부등식(monotone variational inequalities)을 해결하기 위한 1차 방법론(first-order methods)을 연구합니다. extragradient 방법과 같은 고전적인 접근 방식은 반복(iteration)당 두 번의 그래디언트(gradient) 쿼리에 의존하며, 이는 온라인(online) 및 확률적(stochastic) 환경에서의 분석과 적용 가능성을 제한합니다. 우리는 Halpern 반복(Halpern iteration)에서 영감을 얻은 앵커링 항(anchoring term)과 이중 시간 척도 낙관적 업데이트(two-time-scale optimistic updates)를 결합한 앵커링된 일반화된 낙관적 방법론(Generalized Optimistic Methods with Anchoring, GOMA) 제품군을 제안합니다. 결정론적(deterministic) 환경에서 GOMA는 단조 Lipschitz 연산자(monotone Lipschitz operators)에 대해 그래디언트 노름의 제곱(squared gradient norm)에 대한 최적의 가속화된 마지막 반복(last-iterate) 속도인 $O(1/k^2)$를 달성합니다. 무제한 분산(unbounded variance)을 가진 확률적(stochastic) 환경에서, GOMA의 단순화된 단일 호출(single-call) 변형은 그래디언트 노름의 제곱에 대해 $O(1/\sqrt{k})$의 마지막 반복 수렴 속도를 달성합니다. 우리가 알고 있는 바로는, 이는 분산 감소(variance reduction)나 배치 크기 증가(growing batches) 없이 제약이 없는 환경에서 확률적 단조 Lipschitz 변분 부등식에 대해 이러한 보장을 제공하는 최초의 사례입니다.