비쌍대 리프시츠 볼록 최적화의 안정적인 이동성 연구

본 연구는 $\ell_p$-볼에서의 $G$-Lipschitz 볼록 함수 최적화를 위한 효율적인 알고리즘을 다룹니다. 특히 매개변수 조건($p<q$) 하에서, 이들은 $T$번의 오라클 쿼리 후 $\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)_{+}})$라는 에러를 얻어내며, 이는 (MBG+26)의 거의 최적 비율을 효율적으로 실현합니다. 구체적인 예시로, 유클리드 리프시츠성(Euclidean Lipschitzness)이 $\ell_1$-볼에 적용될 경우 $p=1, q=2$일 때 오차율은 $\widetilde{O}(GR/T)$가 됩니다.

제안된 해결책의 핵심은 볼록 리프시츠 최적화 문제를 '진화하는 번들(evolving bundle)의 준수 레벨 집합에서의 추격 중첩 볼록 집합 문제'로 환원시키는 것입니다. 이 알고리즘은 각 쿼리마다 함수 값이 낮은 지점을 찾거나, 현재 번들의 준수 레벨에 깊은 절단면을 생성하여 이를 따라가는 방식으로 작동합니다. 선택자(selector)의 안정성과 깊은 절단면에 의한 강제 이동 사이의 이분법적 관계가 알고리즘의 반복 횟수를 거의 최적으로 제한합니다.

또한, $R B_{p}^{d}$의 중첩 부분집합에 대해 새로운 개념인 '안정 중심(stable center)'을 도입했습니다. 이 안정 중심의 이동은 $\widetilde{O}_{p,q}(RT^{1-1/p+(1/q-1/2)_{+}})$로 제한되며, 이는 고차원에서도 거의 최적임을 입증합니다. 제안된 선택자의 몬테카를로 평균값은 높은 확률로 근사 최적 비율을 달성하며, 실제 산술 모델에서 다항 시간으로 구현 가능함을 보여줍니다.