Proximal Operator는 왜 경사하강법의 일반화인가

비매끄러운 손실함수를 다루는 proximal operator의 정의부터 ISTA/FISTA의 수렴률 차이, ADMM의 분산 학습 적용까지, 현대 최적화의 핵심 구조를 추적한다.

L1 정규화는 왜 희소 해를 만드는가? FISTA는 ISTA보다 왜 두 배 빠른가? 분산 학습에서 각 클라이언트가 데이터를 공유하지 않으면서도 전역 최적해에 수렴할 수 있는 이유는 무엇인가? 이 질문들은 모두 하나의 개념으로 이어진다 — proximal operator.

경사하강법이 실패하는 곳

경사하강법은 미분 가능한 함수를 전제한다. 그런데 현실 ML의 손실함수는 자주 미분 불가능하다. L1 정규화 $\lambda\|x\|_1$ 는 원점에서 미분이 없고, indicator 함수는 아예 값이 $+\infty$ 로 점프한다.

이 상황에서 proximal operator는 “ $f$ 를 최소화하되, 현재 점 $v$ 에서 너무 멀리 가지 않는다” 는 타협 문제의 해다.

\text{prox}_f(v) = \arg\min_x \left( f(x) + \frac{1}{2}\|x - v\|^2 \right)

첫 번째 항은 목적, 두 번째 항은 관성이다. $f = 0$ 이면 $\text{prox}_f(v) = v$ (아무것도 하지 않는다). $f = I_C$ (집합 $C$ 의 indicator)이면 $\text{prox}_f(v) = \text{proj}_C(v)$ (가장 가까운 경계로 당긴다). 이 두 극단 사이에 모든 정규화가 놓인다.

명제 1 · Proximal은 Implicit Gradient Step이다

$f$ 의 Moreau envelope $M_\eta f(x) = \min_y \left( f(y) + \frac{1}{2\eta}\|x-y\|^2 \right)$ 에 대해,

\nabla M_\eta f(x) = \frac{1}{\eta}(x - \text{prox}_{\eta f}(x))

이고, gradient step은 정확히 proximal step과 일치한다.

x - \eta \nabla M_\eta f(x) = \text{prox}_{\eta f}(x)

▷ 증명

최적성 조건 $0 \in \partial f(y^*) + \frac{1}{\eta}(y^* - x)$ 에서 $y^* = \text{prox}_{\eta f}(x)$ 이므로, $\frac{1}{\eta}(x - y^*) \in \partial f(y^*)$ . Envelope theorem을 적용하면 $\nabla M_\eta f(x) = \frac{1}{\eta}(x - y^*)$ . 대입하면 $x - \eta \nabla M_\eta f(x) = x - (x - y^*) = y^* = \text{prox}_{\eta f}(x)$ . ∎

∎

proximal operator가 경사하강법의 일반화인 이유가 여기 있다. $f$ 가 smooth이면 prox는 gradient step과 같고, $f$ 가 non-smooth이면 prox가 gradient를 대신한다.

닫힌 형태가 존재하는 핵심 연산자들

proximal 기반 알고리즘의 실용성은 **닫힌 형태(closed-form)**의 존재에 달린다. 다행히 ML에서 자주 나오는 함수들은 모두 명시적으로 계산된다.

Soft-thresholding ( $f = \lambda\|\cdot\|_1$ ):

[\text{prox}_{\lambda\|\cdot\|_1}(v)]_i = \text{sign}(v_i)\max(|v_i| - \lambda, 0)

최적성 조건 $0 \in \lambda\partial|x^*| + (x^* - v)$ 를 세 경우로 나눠 풀면 직접 유도된다. $|v_i| \leq \lambda$ 이면 0, 그보다 크면 $\lambda$ 만큼 줄인다. 이것이 L1 정규화가 희소 해를 만드는 메커니즘의 전부다 — 작은 계수는 정확히 0으로, 큰 계수는 조금 줄인다.

L2 ball projection ( $f = I_{\|x\|_2 \leq r}$ ):

\text{prox}_f(v) = \begin{cases} v & \|v\| \leq r \\ rv/\|v\| & \|v\| > r \end{cases}

Nuclear norm ( $f = \lambda\|\cdot\|_*$ ): SVD $V = U\text{diag}(\sigma)V^T$ 에서 각 특이값에 soft-thresholding 적용.

\text{prox}_{\lambda\|\cdot\|_*}(V) = U\,\text{diag}(S_\lambda(\sigma))\,V^T

이 패턴은 일관된다 — “작은 것은 버리고, 큰 것은 조금 줄인다.” 차이는 좌표(L1), 그룹(Group Lasso), 특이값(Nuclear norm) 중 어디서 이 연산을 수행하느냐다.

ISTA에서 FISTA로: O(1/k)에서 O(1/k²)

대부분의 ML 문제는 smooth + non-smooth 구조를 가진다.

\min_x \underbrace{f(x)}_{\text{smooth}} + \underbrace{g(x)}_{\text{non-smooth}}

예: $f(x) = \frac{1}{2}\|Ax - b\|^2$ (Lasso의 데이터 항), $g(x) = \lambda\|x\|_1$ .

**ISTA(Iterative Shrinkage-Thresholding Algorithm)**는 이 구조를 활용한다. $f$ 는 gradient step, $g$ 는 proximal step으로 분리해 처리한다.

x_{k+1} = \text{prox}_{\eta g}(x_k - \eta \nabla f(x_k))

수렴률은 $O(1/k)$ 다. step size $\eta \leq 1/L$ (L = Lipschitz 상수)이 필요하고, 이보다 크면 descent를 보장할 수 없다.

FISTA는 Nesterov 모멘텀을 추가한다.

y_k = x_k + \frac{t_k - 1}{t_{k+1}}(x_k - x_{k-1}), \quad x_{k+1} = \text{prox}_{\eta g}(y_k - \eta \nabla f(y_k))

여기서 $t_{k+1} = \frac{1 + \sqrt{1 + 4t_k^2}}{2}$ . 이 수열은 점근적으로 $t_k \sim k/2$ 로 성장하며, potential function 분석에 의해 수렴률이 $O(1/k^2)$ 로 개선된다.

✎ 트레이드오프

ISTA와 FISTA는 모두 step size $\eta \leq 1/L$ 이 필요하다. $L = \|A\|_2^2$ 를 모르면 over-estimate해야 하고, 이는 수렴을 느리게 만든다. 또한 $f$ 가 strongly convex이면 ISTA도 linear rate를 달성하므로 FISTA의 이점이 줄어든다. non-convex 문제에서는 두 알고리즘 모두 stationary point만 보장한다.

Lasso 실험(n=100, p=200, true sparsity=5)에서 ISTA는 약 156회, FISTA는 약 82회 만에 수렴한다. log-log 플롯에서 기울기가 ISTA는 -1, FISTA는 -2로 수렴률 차이가 명확히 드러난다.

ADMM과 Operator Splitting: 분리가 핵심이다

ISTA/FISTA는 $f + g$ 구조를 다룬다. 그러나 현실에는 더 복잡한 구조가 있다 — 데이터가 여러 노드에 분산되어 있거나, 목적함수가 $f(x) + g(Kx)$ 형태로 선형 연산자를 포함하는 경우.

**ADMM(Alternating Direction Method of Multipliers)**은 분리 가능한 구조를 명시적으로 활용한다.

\min_{x,z} f(x) + g(z) \quad \text{s.t.} \quad Ax + Bz = c

Augmented Lagrangian $L_\rho(x,z,y) = f(x) + g(z) + y^T(Ax+Bz-c) + \frac{\rho}{2}\|Ax+Bz-c\|^2$ 를 x, z, y에 대해 교대로 최소화한다. x-step과 z-step이 독립적이므로, 각 클라이언트가 자신의 데이터만으로 x-step을 수행하고 중앙 서버가 z와 dual variable y를 관리하는 federated 구조가 자연스럽게 나온다.

Douglas-Rachford는 $f + g$ 형태에서 두 proximal을 교대로 적용한다.

x_{k+1}^{(1)} = \text{prox}_{\gamma f}(z_k), \quad x_{k+1}^{(2)} = \text{prox}_{\gamma g}(2x_{k+1}^{(1)} - z_k), \quad z_{k+1} = z_k + (x_{k+1}^{(2)} - x_{k+1}^{(1)})

Chambolle-Pock은 $f(x) + g(Kx)$ 구조를 primal-dual 관점으로 분해한다. dual step으로 $g^*$ 의 prox를, primal step으로 $f$ 의 prox를 교대 적용한다. 수렴 조건은 $\tau\sigma\|K\|^2 < 1$ 이고, total variation denoising의 표준 알고리즘이다.

정리

Proximal operator는 “f 최소화 + v에 가까이 유지”의 타협이며, gradient step을 미분 불가능 함수로 일반화한다.
Soft-thresholding, L2 ball projection, nuclear norm prox는 각각 L1 희소성, 제약 최적화, 저랭크 행렬의 닫힌 형태 해다.
FISTA는 Nesterov 모멘텀으로 ISTA의 $O(1/k)$ 를 $O(1/k^2)$ 로 개선한다. 차이는 gradient를 “현재 점”이 아닌 “미래 위치 추정”에서 계산하는 것이다.
ADMM은 분리 가능 구조를 분산 계산으로 자연스럽게 매핑한다. 각 노드가 local 문제를 풀고, dual variable 교환으로 전역 일관성을 달성한다.
세 알고리즘(ISTA/FISTA, ADMM, Chambolle-Pock) 모두 수렴률은 $O(1/k)$ 또는 $O(1/k^2)$ 이며, 공통 가정은 볼록성이다.

proximal 계산이 닫힌 형태로 존재하는 함수들만 모아도, 현대 ML의 정규화와 제약 최적화 대부분을 커버한다. 구조를 아는 것이 알고리즘 선택의 전부다.

REF

Beck, A. and Teboulle, M. · 2009 · A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems · SIAM Journal on Imaging Sciences