Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)

기술 요약: OGD+Projection 알고리즘의 누적 제약 조건 위반에 대한 하한선

문제 정의
본 논문은 제약된 온라인 볼록 최적화(Constrained Online Convex Optimization, COCO) 문제를 다룹로다. 이 설정에서 온라인 학습자는 $T$ 라운드 동안 동작합니다. 각 라운드 $dt$에서 학습자는 볼록 가용 집합$X \subset \mathbb{R}^d$에서 행동$x_t$를 선택합니다. 그 후 적대적 생성자(adversary)는 볼록 손실 함수 $f_t$와 볼록 제약 함수 $g_t$를 공개합니다. 학습자는 손실 $f_t(x_t)$를 입게 되며, $g_t(x_t) > 0$인 경우 제약 위반을 입습니다. 학습자의 목표는 정적 벤치마크 $x^\star$(모든 미래 함수를 알고 있으며 가용한 행동을 선택함, 즉 모든 $t$에 대해 $g_t(x^\star) \le 0$)와 비교하여 두 가지 지표를 동시에 최소화하는 것입니다:

1. 정적 후회(Static Regret): 학습자의 누적 손실과 벤치마크 간의 차이.
2. 누적 제약 위반(Cumulative Constraint Violation, CCV): 양의 제약 위반 부분의 합, $\sum_{t=1}^T \max(g_t(x_t), 0)$.

본 논문은 특히 OGD+Projection 알고리즘(Vaze와 Sinha, 2025가 제안)에 초점을 맞춥니다. 이 알고리즘은 온라인 경사 하강법(OGD) 단계를 수행한 후, 그때까지 공개된 모든 제약 집합의 교집합으로 투영(projection)을 수행합니다. 이 알고리즘에 대한 상한선(upper bounds)은 알려져 있으나, CCV에 관한 하한선(lower bound) 성능은 아직 확립되지 않았습니다.

방법론 및 구성
하한선을 도출하기 위해, 저자들은 COCO 문제의 특정 "어려운(hard)" 인스스턴스를 구성합니다. 이 구성은 $d$차원 공간에서의 점들과 제약 조건들의 기하학적 배치를 기반으로 합니다.

1. 벡터 구성 (정리 2): 증립의 핵심은 단위 구 $S^d$ 위의 순서가 있는 단위 벡터 집합 $U_d(\rho)$를 구성하는 것입니다. 이 벡터들은 다음 두 가지 속성을 만족하도록 설계되었습니다:

   • 분리(Separation): 임의의 서로 다른 두 벡터는 $\rho$ 이상의 각도 거리로 분리됩니다.
   • 국소 연결성(Local Connectivity): 순서가 있는 시퀀스의 연속적인 벡터들은 $A_d \rho$ 이하의 각도 거리로 분리됩니다.
   • 기수(Cardinality): 이러한 벡터들의 개수는 $\Omega(\rho^{-(d-1)})$로 스케일링됩니다.
     이 구성은 구형 캡(spherical caps)과 경도/위도 순회를 활용하여 순서 및 분리 속성이 유지되도록 하는 $d$차원에 대한 귀납적 과정을 통해 달성됩니다.

2. 제약 조건 및 행동 궤적:

   • 행동 공간 $X$는 볼 $B(0, D)$로 정의됩니다.
   • 시간 지평 $T$는 각각 수축하는 반지름을 가진 동심 구 $C_m$에 대응하는 $M = T^{1/d}$개의 "레이어(layers)"로 나뉩니다.
   • 각 레이어 $m$ 내에서, 알고리즘은 위에서 구성한 단위 벡터들을 스케일링하여 얻은 일련의 점들 $z^{(m)}_i$를 통과하도록 강제됩니다.
   • 제약 설계: 각 점 $z^{(m)}_i$에 대해, $z^{(m)}_i$의 투영 지점에서의 다음 작은 구 $C_{m+1}$에 접하는 하프스페이스(half-space)인 새로운 제약 조건이 도입됩니다. 이 제약 조건은 $z^{(m)}_i$를 중심으로 하는 구형 캡을 효과적으로 "잘라냅니다(cut off)".
   • 가용성 로직: 각도 분리 $\rho$와 신중하게 선택된 절단 각도 덕분에, $z^{(m)}_i$와 관련된 제약 조건은 현재 레이어의 후보 집합에서 오직 해당 점만을 제거하며, 나머지 점들은 모두 가용 상태로 남겨둡니다. 그러나 점 $z^{(m)}_i$ 자체는 제약이 공개된 직후에 불가용(infeasible) 상태가 됩니다.

3. 비용 함수 설계:

   • 손실 함수는 OGD+Projection 알고리즘이 미리 정의된 궤적 $z_1, z_2, \dots, z_P$를 따르도록 유도하도록 설계되었습니다.
   • 각 단계의 시작 시(새로운 제약이 공개될 때), 알고리즘은 투영 거리(projection distance)로 인해 위반을 입습니다.
   • 이후 단계 동안, 손실 함수는 선형이며 알고리즘을 투영된 점에서 다음 타겟 점으로 다시 이동시키도록 방향이 설정되어, 알고리즘이 의도된 경로를 유지하도록 보장합니다.

주요 결과
본 논문은 OGD+Projection 알고리즘의 CCV에 대한 첫 번째 하한선을 확립합니다.

• 정리 1: 지름 $2D$와 리프시츠 상수 $G$를 갖는 COCO 인스턴스가 존재하여, OGD+Projection 알고리즘의 CCV는 $\Omega(T^{\frac{d-1}{2d}})$입니다.
• 도출: 총 CCV는 "단계 헤드(phase heads)"(새로운 제약이 도입되는 시점)에서 발생하는 위반의 합입니다. 이러한 단계는 $P \approx T^{\frac{d+1}{2d}}$개 존재합니다. 각 단계 헤드에서 알고리즘은 $T^{-1/d}$ 차수의 위반을 입습니다. 이를 곱하면 다음과 같습니다:
  $$\text{CCV} \approx T^{\frac{d+1}{2d}} \times T^{-\frac{1}{d}} = T^{\frac{d-1}{2d}}$$
• 차원 의존성: 결과는 하한선이 차원 $d$에 의존함을 강조합니다. $d=2$인 경우, 하한선은 $\Omega(T^{1/3})$이며, 이는 $d=2$에 대한 알려진 상한선(Balasundaram 등, 2026)과 일치합니다. 일반적인 $d$에 대해, 하한선은 $\Omega(T^{\frac{d-1}{2d}})$입니다.

의의 및 주장
저자들은 이 연구가 OGD+Projection 알고리즘의 CCV에 대한 최초의 하한선 결과임을 주장합니다. 이 결과의 주요 의의는 OGD+Projection 알고리즘에 대한 기존의 상한선 분석이 근본적으로 느슨하지 않음을 보여준다는 데 있습니다.

구체적으로, 본 논문은 OGD+Projection 알고리즘이 $d=2$에서 $O(T^{1/3})$의 CCV를 달성하고 보편적으로 $O(\sqrt{T})$를 달성하지만, 도출된 하한선 $\Omega(T^{\frac{d-1}{2d}})$은 알고리즘의 성능이 차원 $d$에 대해 타이트(tight)함을 보여준다고 명시합니다. $d=2$의 경우, 하한선 $\Omega(T^{1/3})$은 상한선과 일치하여 해당 차원에 대한 최적성을 확인해 줍니다. 더 높은 차원의 경우, 하한선 $\Omega(T^{\frac{d-1}{2d}})$와 보편적인 $O(\sqrt{T})$ 상한선 사이의 간극은, 알고리즘이 견고하긴 하지만 특정 기하학적 제약 구조가 위반율을 차원에 따라 스케일링하도록 강제할 수 있음을 시사합니다.

본 논문은 새로운 알고리즘이나 응용 분야를 제안하는 것이 아니라, 제약된 온라인 최적화 분야에서 현재의 최첨단(state-of-the-art) 방식인 OGD+Projection 접근법의 이론적 한계를 규명하는 역할을 합니다.