zero order optimization

zero order optimization과 관련된 내용들

zero-order optimization

Zeroth-order optimization는 objective function의 gradient 정보를 이용하지 않는 최적화 방법이다. 따라서 해당 방법론은 gradient를 계산할 수 없는 경우 유용하다.

zero-order information을 통해 gradient estimator를 구축하고 true first-order gradient를 gradient estimator로 대체하는 것이 목적이다.

딥러닝에서 gradient에 대한 정보 없이 input과 output 정보만 이용할 수 있는 black-box attack에 대해 vulnerable features를 찾기 위해 사용될 수 있다.

https://stanford.edu/~rezab/dao/notes/L08/cme323_lec8.pdf

L-Smooth

Definition. 미분 가능한 함수 $\mathbb{R}^n \rightarrow \mathbb{R}$ 가 모든 $x, y \in \mathbb{R}^n$에 대해 L-smooth 하다고 하면, 다음이 성립한다.

• gradient가 임의적이고 매우 빠르게 변한다면 과거 step의 gradient 정보는 쓸모없으므로 L-Smoothness 를 통해 gradient가 매우 빠르게 변하지 않음을 보장받을 수 있고 함축적으로, gradient의 반대 방향으로 이동했을 때 function value가 감소할 것임을 예상할 수 있다.

$\mu$-strongly convex

Definition. A function $f: \mathbb{R}^n \to \mathbb{R}$ is said to be $\mu$-strongly convex for $\mu \geq$ 0 if for all $x, y \in \mathbb{R}^n$ and t $\in$ [0, 1] we have that
$f(ty + (1 - t)x) \leq tf(y) + (1 - t)f(x) - \frac{\mu}{2}t(1 - t)\| x - y \|_2^2$

$\mu$ = 0 일 때는 convex한 경우에 해당한다.

A Tutorial on Zero-Order Optimization

2-point gradient estimator

papers
DeepZero: Scaling Up Zeroth-Order Optimization for Deep Model Training, 2024 ICLR

contents
https://cci.drexel.edu/bigdata/bigdata2018/files/Tutorial4.pdf