자기 수축 (Self-Contraction)을 통한 제약 조건이 있는 온라인 볼록 최적화 (COCO)의 개선된 보장

우리는 적대적으로 선택된 제약 조건이 있는 제약 조건이 있는 온라인 볼록 최적화 (Constrained Online Convex Optimization, COCO)를 고려합니다. 각 라운드에서 학습자는 해당 라운드의 손실 함수 (loss function)와 제약 조건 함수 (constraint function)를 관찰하기 전에 행동을 선택합니다. 목표는 모든 제약 조건을 만족하는 최적의 지점에 대해 작은 정적 후회 (static regret)를 달성하는 동시에, 누적 제약 조건 위반 ($\mathsf{CCV}$)을 제어하는 것입니다. 강볼록 (strongly convex) 손실의 경우, 최신 알고리즘들은 $O(\log T)$의 후회와 $O(\sqrt{T \log T})$의 $\mathsf{CCV}$를 달성합니다. 볼록 (convex) 손실에 대한 기존의 최적 경계는 $O(\sqrt{T})$의 후회와 $O(\sqrt{T} \log T)$의 $\mathsf{CCV}$입니다. 본 논문에서 우리는 강볼록 손실에 대해 $O(\log T)$의 후회와 $O(\log T)$의 $\mathsf{CCV}$를 동시에 달성하는 간단한 투영 기반 (projection-based) 알고리즘을 제시하며, 이는 $\mathsf{CCV}$ 측면에서 지수적인 개선을 가져옵니다. 볼록 손실의 경우, 우리의 알고리즘은 최적의 $O(\sqrt{T})$ 후회를 유지하면서 $\mathsf{CCV}$를 $O(\sqrt{T})$로 개선합니다. 우리의 개선의 핵심은 최근의 자기 수축 곡선 (self-contracted curves)에 대한 기하학적 결과이며, 이는 독립적인 관심사가 될 수 있습니다.