무거운 꼬리 확률 분포 노이즈 환경에서의 온라인 볼록 최적화 문제에 대한 매개변수-자유 동적 후회 최소화

Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise

본 연구는 비정상적인 환경에서, 특정 $p$ 값 ($1 < p ext{≤} 2$)에 대해 유한한 $p$차 중심 모멘트만을 갖는 확률적 기울기 오라클을 사용하는 온라인 볼록 최적화 (OCO) 문제를 다룬다. 정적 후회(static regret)는 잘 알려져 있지만, 모든 경우에 적용 가능한 동적 후회를 매개변수 없이 달성하는 것은 여전히 해결해야 할 과제이다. 본 연구에서는 재시작 AdaGrad 전문가를 기하학적인 블록 길이 풀과 결합하고, 메타-손실에 대한 모멘트 조건을 요구하지 않는 경로 기반 메타 알고리즘인 extbf{AdaGrad-Hedge}를 활용하는 매개변수-자유 알고리즘인 extbf{HT-PAder}를 제안한다. 영역의 지름 $D$, Lipschitz 상수 $G$, 노이즈 수준 $σ$, 그리고 비교 경로 길이 $P_T$에 대해, HT-PAder는 다음과 같은 예상되는 동적 후회 값을 달성한다: [ widetilde O extbackslashleft( GD extsqrt{T(1+P_T/D)} + σD T^{1/p}(1+P_T/D)^{(p-1)/p} ight) brack. 본 알고리즘은 이러한 문제 파라미터에 대한 사전 지식을 필요로 하지 않는다. 특히 유한 분산 ($p=2$)의 특별한 경우에서도, HT-PAder는 최초의 매개변수-자유 미니막스 동적 후회 보증을 제공한다. 또한, 본 연구에서는 경로 길이 지수의 최적성을 입증하는 상호 보완적인 하한(lower bound)을 증명하였다.

We study online convex optimization (OCO) in non-stationary environments under heavy-tailed noise, where the stochastic gradient oracle admits only a finite $p$-th central moment for some $p \in (1, 2]$. While static regret is well-understood, achieving universal dynamic regret in a parameter-free manner remains an open challenge. We resolve this by proposing \textbf{HT-PAder}, a parameter-free algorithm combining restarted AdaGrad experts over a geometric pool of block lengths with a pathwise meta-algorithm, \textbf{AdaGrad-Hedge}, which requires no moment conditions on meta-losses. For a domain of diameter $D$, Lipschitz constant $G$, noise level $σ$, and comparator path length $P_T$, HT-PAder achieves an expected universal dynamic regret of \[ \widetilde O\left( GD\sqrt{T(1+P_T/D)} + σD T^{1/p}(1+P_T/D)^{(p-1)/p} \right). \] The algorithm does not require prior knowledge of any of these problem parameters. Even in the special case of finite variance ($p=2$), HT-PAder provides the first parameter-free minimax universal dynamic regret guarantee. We also prove a matching lower bound, establishing the optimality of the path-length exponent.