Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

기술적 요약: 꼬리가 두꺼운 노이즈가 있는 0 차 비볼록 비매끄러운 최적화

문제 공식화
본 논문은 제약이 없는 확률적 최적화 문제를 다룹니다:
$$\min_{x \in \mathbb{R}^d} f(x) = \mathbb{E}_{\xi \sim P}[F(x; \xi)]$$
여기서 목적 함수 $f$는 비볼록이고 비매끄러우나, 리프시츠 연속입니다. 설정은 0 차이므로, 알고리즘은 기울기에 접근할 수 없고 대신 노이즈가 포함된 함수 평가값 $F(x; \xi)$에만 접근할 수 있습니다.

이전 연구와의 중요한 차이는 노이즈 가정입니다. 많은 기존 분석이 유계 분산 가정 (2 차 모멘트) 에 의존하는 반면, 본 논문은 꼬리가 두꺼운 노이즈 가정 하에 작동합니다. 구체적으로, 확률적 구성 요소 함수의 리프시츠 상수 $L(\xi)$는 유계 $p$ 차 모멘트 조건을 만족합니다:
$$\mathbb{E}[L(\xi)^p] \leq L^p$$
여기서 $p \in (1, 2]$입니다. $p < 2$일 때 분산은 무계일 수 있으며, 이는 심층 신경망 학습 및 강화 학습과 같은 실제 기계 학습 응용에서 흔히 관찰되는 꼬리가 두꺼운 분포 (예: Lévy $\alpha$-stable) 를 특징짓습니다.

방법론: ZOCOON 알고리즘
저자들은 0 차 클리핑 온라인-비볼록 (ZOCOON) 알고리즘을 제안합니다. 이 방법은 세 가지 핵심 구성 요소를 통합합니다:

1. 온라인-비볼록 변환 프레임워크: Cutkosky 등 [9]이 확립하고 Kornowski 와 Shamir [25]가 확장한 프레임워크에 기반하여, 알고리즘은 온라인 학습 문제를 비볼록 최적화 솔버로 변환합니다. 이는 고정점을 찾기 위해 라운드에 걸쳐 업데이트 시퀀스를 실행하는 것을 포함합니다.
2. 이점 확률적 기울기 추정기: 기울기를 사용할 수 없으므로, 알고리즘은 매끄러운 대리 함수 $f_{\delta'}(x)$에 기반한 0 차 추정기를 사용합니다. 단위 구 위의 점 $x$와 무작위 방향 $w$에 대해 추정기는 다음과 같습니다:
   $$\hat{g}(x; w, \xi) = \frac{d}{2\delta'} (F(x + \delta'w; \xi) - F(x - \delta'w; \xi))w$$
   이는 매끄러운 함수의 기울기에 대한 불편 추정을 제공합니다.
3. 기울기 클리핑: 꼬리가 두꺼운 노이즈의 영향을 완화하기 위해, 알고리즘은 기울기 추정기에 클리핑 연산자를 통합합니다. 업데이트 단계는 $\hat{g}_{clipped} = \text{clip}(\hat{g}, \tau)$를 사용하며, 여기서 $\tau$는 임계값 매개변수입니다. 이는 크고 노이즈가 많은 기울기가 최적화 과정을 불안정하게 만드는 것을 방지합니다.

알고리즘은 재시작을 동반한 에포크 단위로 작동하며, 수렴 보장을 위해 평균화된 반복점 집합에서 균일하게 무작위로 선택된 점을 출력합니다.

주요 기여 및 이론적 결과
본 논문은 Goldstein $\delta$-부분미분을 통해 정의된 비매끄러운 함수에 대한 정제된 근사 정지성 개념인 $(\delta, \epsilon)$-Goldstein 정지점을 찾는 것에 대한 이론적 보장을 확립합니다.

• 수렴 복잡도: ZOCOON 알고리즘은 다음과 같은 확률적 0 차 오라클 복잡도로 $(\delta, \epsilon)$-Goldstein 정지점을 달성합니다:
  $$O\left( d^{\frac{p}{2(p-1)}} \delta^{-1} \epsilon^{-\frac{2p-1}{p-1}} \right)$$
  이 결과는 기대값과 높은 확률로 모두 성립합니다.
• 차원 의존성: 차원 $d$에 대한 의존성은 볼록 비매끄러운 설정에서의 확률적 0 차 최적화에 대한 가장 잘 알려진 결과와 일치합니다.
• 정확도 의존성: 정확도 매개변수 $\delta$ 및 $\epsilon$에 대한 의존성은 꼬리가 두꺼운 노이즈 하의 비볼록 비매끄러운 문제에 대한 가장 잘 알려진 확률적 1 차 알고리즘과 일치합니다.
• 매끄러운 확장: 결과는 자연스럽게 매끄러운 설정으로 확장됩니다. $\delta = \epsilon/H$ (여기서 $H$는 매끄러움 상수) 로 설정함으로써, 이 방법은 매끄러운 비볼록 최적화에 대한 최적의 확률적 1 차 방법과 복잡도가 일치하는 $\epsilon$-정지점을 달성합니다.

실험적 검증
실제 데이터셋 (a9a, covtype, w8a) 을 사용하여 인위적으로 추가된 꼬리가 두꺼운 노이즈 (파레토 분포) 가 있는 비볼록 패널티 SVM 문제에 대해 수치 실험이 수행되었습니다.

• 베이스라인: ZOCOON 은 GFM [26], GFM+ [5], ZOO2N [25] 과 비교되었습니다.
• 결과: ZOCOON 과 ZOO2N 은 GFM 과 GFM+ 보다 훨씬 빠르게 수렴했습니다. ZOCOON 은 대부분의 데이터셋에서 ZOO2N 보다 더 안정적인 성능을 보여주었으며, 이는 꼬리가 두꺼운 노이즈를 처리하는 클리핑 메커니즘의 유효성을 입증했습니다.

의의 및 주장
본 논문은 문헌의 중요한 공백을 메운다고 주장합니다: 실제에서 꼬리가 두꺼운 노이즈가 만연함에도 불구하고, 기존 비볼록 비매끄러운 최적화를 위한 0 차 방법은 유계 분산 가정이나 볼록 설정으로 제한되었습니다.

• 유일한 사례: ZOCOON 은 꼬리가 두꺼운 노이즈 하의 비볼록 비매끄러운 최적화를 위한 최초의 효율적인 확률적 0 차 알고리즘으로 제시됩니다.
• 최적성: 저자들은 $L$, $\delta$, $\epsilon$에 대한 의존성이 이 문제 클래스에 대해 최근 확립된 하한선과 일치한다고 지적하며, 이 방법이 정확도 매개변수와 관련하여 거의 최적임을 시사합니다.
• 강건성: 이 연구는 1 차 방법에서 일반적인 기술인 기울기 클리핑이 차원 의존적 복잡도를 희생하지 않고 무계 분산을 처리하기 위해 0 차 프레임워크에 성공적으로 적응될 수 있음을 보여줍니다.

본 논문은 차원 의존성이 최적인지, 그리고 프레임워크가 제약 최적화 문제로 확장될 수 있는지와 같은 열린 질문들을 인정하며 결론을 맺습니다.