Slater 조건이 없는 제약 조건이 있는 온라인 볼록 최적화 (Constrained Online Convex Optimization)
요약
Slater 조건과 같은 정규성 가정 없이도 작동하는 제약 조건이 있는 온라인 볼록 최적화(COCO) 프레임워크를 제안합니다. 적응형 정규화 항을 통합한 anytime primal-dual 방식을 통해 확률적 및 적대적 제약 조건 환경에서 안정적인 성능을 보장합니다.
핵심 포인트
- Slater 조건 없이도 작동하는 anytime primal-dual 프레임워크 제안
- 적응형 정규화 항을 통해 dual 업데이트 과정의 안정성 확보
- 확률적 제약 조건에서 O(√T)의 기대 후회 달성
- 강볼록 손실 환경에서 후회 경계치를 O(log T)로 개선
- 적대적 제약 조건에 대한 하드 제약 조건 위반 보장 제공
우리는 적대적 손실 (adversarial losses)과 확률적 또는 적대적 제약 조건 (stochastic or adversarial constraints)이 있는 제약 조건이 있는 온라인 볼록 최적화 (constrained online convex optimization)를 연구합니다. 확률적 제약 조건의 경우, 거의 최적에 가까운 후회 (regret) 및 제약 조건 위반 (constraint violation) 경계치를 달성하는 기존 알고리즘들은 일반적으로 Slater 조건 (Slater's condition)과 같은 정규성 가정 (regularity assumptions)에 의존하는 반면, 적대적 제약 조건 알고리즘들은 다소 제한적인 라운드별 실행 가능한 비교 대상 (round-wise feasible comparator)을 사용함으로써 이러한 가정을 피합니다. 우리는 dual 업데이트에 적응형 정규화 항 (adaptive regularizer)을 통합하는 anytime primal-dual 프레임워크를 통해 이 간극을 메웁니다. 이 정규화 항은 Slater 조건에 의해 유도되는 음의 드리프트 (negative drift)에 의존하지 않고 dual 과정을 안정화합니다. 확률적 제약 조건과 볼록 손실 (convex losses)에 대해, 우리의 알고리즘은 $O(\sqrt{T})$의 기대 후회 (expected regret)와 $O(\sqrt{T}\log T)$의 기대 누적 제약 조건 위반 (expected cumulative constraint violation)을 달성합니다. 나아가, 우리의 알고리즘이 후회와 제약 조건 위반에 대해 동일한 차수의 고확률 경계치 (high-probability bounds)도 허용함을 보여줍니다. 강볼록 손실 (strongly convex losses)의 경우, 후회 경계치는 $O(\log T)$로 개선되며 위반 경계치 또한 동일한 차수를 가집니다. 약간의 수정을 통해, 이 프레임워크는 적대적 제약 조건에도 적용될 수 있으며 하드 제약 조건 위반 (hard constraint violation)에 대한 보장을 제공합니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.LG의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기