High-probability zeroth-order online convex optimisation beyond Euclidean geometry

기술 요약: 유클리드 기하학을 넘어선 고확률 영차 온라인 볼록 최적화

문제 설정
본 연구는 학습자가 기울기가 아닌 함수 값 평가에만 접근할 수 있는 영차 (zeroth-order) 설정에서의 온라인 볼록 최적화 (OCO) 문제를 다룹니다. 구체적인 설정은 분포 $\mu$ 에서 추출된 일련의 무작위 리프시츠 (Lipschitz) 손실 함수 $f_t$ 를 포함합니다. 실현된 $f_t$ 가 볼록일 필요는 없으나, 그 평균 함수 $F_\mu(x) = \mathbb{E}_{f \sim \mu}[f(x)]$ 는 볼록하다고 가정합니다. 학습자는 컴팩트하고 볼록한 집합 $\Theta \subset \mathbb{R}^d$ 위에서 작동하며, 다음 의사-후회 (pseudo-regret) 를 최소화하는 것을 목표로 합니다:
$$R_n^\mu = \sup_{u \in \Theta} \sum_{t=1}^n \left( F_\mu(x_t) - F_\mu(u) \right)$$
피드백 모델은 학습자가 매 라운드 두 점 $x_t \pm h_t \zeta_t$ 에서 함수를 쿼리할 수 있게 허용하며, 여기서 방향 $\zeta_t$ 는 $\ell_r$-볼의 경계에서 원뿔 측도 (cone measure) 에 따라 샘플링됩니다. 손실 함수는 $\ell_q$ 노름에 대해 $L$-리프시츠라고 가정하며, 알고리즘은 Follow-The-Regularised-Leader (FTRL) 프레임워크 내에서 $\ell_p$-강볼록 정규화자를 사용합니다.

방법론
본 논문은 무작위화된 두 점 유한 차분 기울기 추정기를 활용하는 적응형, 언제든 가능한 (anytime) 알고리즘 (SOLO FTRL) 을 제안합니다. 방법론적 혁신의 핵심은 기하학적 일반화와 확률론적 분석에 있습니다:

1. 일반화된 기울기 추정: 기울기 추정기는 $\ell_r$ 볼의 경계에서 원뿔 측도로 샘플링된 방향 ($\zeta \sim \partial B_d^r$) 을 사용하여 구성됩니다. 추정기는 다음과 같이 정의됩니다:
   $$g_t = \frac{d}{2h_t} \left( f_t(x_t + h_t \zeta_t) - f_t(x_t - h_t \zeta_t) \right) n_r(\zeta_t)$$
   여기서 $n_r(\zeta)$ 는 $\zeta$ 에서의 $\ell_r$ 구의 단위 법선 벡터입니다. 이는 고전적인 구형 추정기 ($r=2$) 를 일반화하며 $\ell_1$ 또는 $\ell_\infty$ 샘플링 기하학을 허용합니다.

2. 모멘트 분석과 집중: 이전 연구들이 주로 이차 모멘트를 사용하는 기대값 내 (in-expectation) 경계에 의존한 것과 달리, 본 분석은 쌍대 노름 $\ell_{p^*}$ 에서 기울기 추정기에 대한 모든 모멘트 경계 (all-moment bounds) 를 확립합니다. 쌍대 노름 제곱 오차의 시퀀스가 순차적 베르슈타인 모멘트 조건 (SBM) 을 만족함을 증명함으로써, 저자들은 시간 균일 고확률 집중 부등식을 유도합니다. 이는 $\ell_r$ 구 위의 리프시츠 함수에 대한 측도 집중 결과를 사용하여 기울기 추정기의 꼬리 행동을 제어하는 과정을 포함합니다.

3. 적응형 알고리즘: 알고리즘은 완전히 데이터 주도적이며, 시간 범위 $n$ 이나 모멘트 분석에서 유도된 최악의 경우 상수에 대한 지식이 필요하지 않습니다. 이는 기하학 매개변수 ($p, r$), 정규화자, 그리고 정의역 크기의 상한만 지정하면 됩니다.

주요 기여

1. 통합된 고확률 경계: 본 논문은 모든 기하학 조합 $p, q, r \in [1, \infty]$ 에 대한 영차 OCO 에 대한 최초의 통합된 고확률 후회 경계를 제공합니다. 이러한 경계는 볼록한 평균을 가진 무작위 리프시츠 손실에 대해 성립하며, 기존의 기대값 내 보장을 시간 균일 고확률 진술로 강화합니다.
2. 기울기 추정기 모멘트 경계: 저자들은 쌍대 노름 $\ell_{p^*}$ 에서 $\ell_r$-무작위화된 두 점 기울기 추정기에 대한 새로운 모멘트 경계를 증명합니다. 이러한 결과는 샘플링 기하학 ($r$) 과 리프시츠 노름 ($q$) 에 대한 의존성을 추적하며, 누적 쌍대 노름 제곱이 서브가우시안 (subgamma) 과정처럼 행동함을 확립합니다.
3. 알고리즘 독립 하한: 본 논문은 동일한 문제 클래스에 대한 상수 확률 하한을 확립합니다. 이러한 경계는 이전의 기대값 내 결과 (특히 $p=q=1$ 인 경우 $\sqrt{\log d}$ 인자를 제거하여) 를 개선하며, 단일 구성으로 $p, q \in [1, \infty]$ 의 전체 범위를 포괄합니다.
4. $q > 2$ 에 대한 간극의 식별: 분석은 $q > 2$ 일 때 상한과 하한 사이의 불일치를 드러냅니다. 저자들은 이것이 증명의 산물이 아니라, 이 영역에서 표준 무작위화된 두 점 기울기 추정기가 고 $q$ 리프시츠 함수에 내재된 희소성을 활용하지 못하기 때문에 발생하는 본질적인 비최적성을 나타낸다고 주장합니다.

주요 결과
주요 이론적 결과 (정리 2.3) 는 확률 $1-\delta$ 이상으로 후회가 다음을 만족함을 명시합니다:
$$R_n^\mu \leq 22R\sqrt{\nu_r} \left( \sqrt{n \Lambda_n^*(\delta)} + 11 d^{\gamma_r} \log(32n/\delta)^{3/2} \right)$$
여기서 $\nu_r$ 은 $L, d, p, q, r$ 에 의존하는 대리 분산이며, $\gamma_r = (1/p - 1/r)_+$ 입니다. $\sqrt{\log \log n}$ 항은 경계의 언제든 가능한 (anytime) 성질에서 비롯됩니다.

하한 (정리 2.4) 은 임의의 두 점 알고리즘에 대해, 후회가 상수 확률로 적어도 $d^{(1/2 + 1/q - 1/p)_+} LR\sqrt{n}$ 순서인 문제 인스턴스가 존재함을 보여줍니다.

의의와 주장
본 논문은 유클리드 설정 ($p=q=r=2$) 을 넘어선 영차 온라인 볼록 최적화에 대한 최초의 통합적 처리를 제공한다고 주장합니다. 기대값 내 분석에서 고확률 분석으로 이동함으로써, 결과는 적응형 및 언제든 가능한 설정에 적합한 더 강력하고 시간 균일한 보장을 제공합니다.

이 연구는 현재 방법론의 특정 한계를 강조합니다: $q > 2$ 인 경우, 표준 무작위화된 기울기 추정기는 이론적 하한에 비해 비최적으로 보입니다. 저자들은 이 간극이 $q > 2$ 영역에서 "어려운" 인스턴스의 희소성을 활용하는 메커니즘이 추정기에 결여되어 있기 때문에 발생하며, 하한 구성이 명시적으로 이러한 속성을 활용한다는 점을 지적합니다. 이 발견은 이 영역에서의 향후 개선이 기존 유한 차분 방법의 정제된 분석이 아니라 근본적으로 다른 추정기 구조를 필요로 할 수 있음을 시사합니다.