확률적 최적화에서 PGD와 Mirror Descent를 선택하는 법

비평활 항과 제약이 있는 확률적 갱신

대규모 데이터에서는 전체 손실을 매번 계산하기보다 샘플이나 미니배치로 얻은 추정량으로 파라미터를 반복 갱신한다. 확률적 최적화는 이 과정을 위한 프레임워크이며, 목적함수는 보통 (f(x) = E_\xi[F(x; \xi)]) 또는 (f(x) = (1/n)\sum F_i(x)) 형태로 둔다.

일반적인 SGD는 손실의 기울기를 따라 이동하는 데 적합하지만, L1 정규화처럼 미분하기 어려운 항이나 단체(simplex) 같은 도메인 제약까지 자연스럽게 반영하기는 어렵다. 이때 Proximal Gradient Descent(PGD)와 Mirror Descent(MD)가 문제의 구조를 갱신 과정에 포함시키는 선택지가 된다.

PGD는 합성 최적화 (f(x) = g(x) + h(x))를 전제로 한다. (g)는 미분 가능하고 L-리프시츠 그라디언트를 가지며, (h)는 프로시말 연산자를 계산할 수 있는 비매끄러운 항이다. 확률적 그라디언트 (\nabla g_t)를 사용하면 갱신은 다음과 같이 쓴다.

[ x_{t+1} = prox_{\eta_t h}(x_t - \eta_t \nabla g_t) ]

여기서 prox는 비평활 정규화 또는 제약을 반영하는 연산이다.

MD는 미러 맵 (\psi)가 정의하는 브레그먼 발산 (D_\psi)을 기준으로 이동한다. 원공간의 제약과 기하를 듀얼공간의 경사 스텝으로 옮긴 뒤, 미러 역상으로 복원하는 방식이다.

[ z_{t+1} = \nabla\psi(x_t) - \eta_t g_t,\qquad x_{t+1} = (\nabla\psi)^{-1}(z_{t+1}) ]

도메인 투영을 함께 둘 수도 있으며, 확률적 설정의 (g_t)는 미니배치 추정량이다. 유클리드 기하 (\psi(x)=1/2||x||^2)에서는 PGD를 MD의 특수한 경우로 볼 수 있다. 반대로 엔트로피를 (\psi)로 택하면 MD는 단체 제약을 자연스럽게 만족하는 지수 가중(Exponentiated Gradient) 갱신이 된다.

목적함수 구조가 알고리즘 선택을 결정한다

PGD는 매끄러운 항 (g)와 비매끄러운 항 (h)를 분리할 수 있을 때 잘 맞는다. 확률적 경사 스텝 뒤에 prox 연산을 적용하므로, 소프트 임계값화처럼 폐형으로 계산되는 연산이 있으면 구현도 단순하다.

MD에서는 가중 노름, 엔트로피처럼 문제의 기하를 표현하는 미러 맵이 핵심이다. 양의 직교좌표, 단체, PSD 등 어떤 도메인을 다루는지 먼저 명확해야 한다. 듀얼공간에서 이동한 뒤 미러 역상으로 되돌리므로, 정규화나 투영 비용을 낮출 수 있는 경우가 있다.

프로시말 연산자로는 L1의 소프트 스레숄딩, TV의 근사 연산, 핵노름의 SVT, 박스 제약의 클리핑을 사용할 수 있다. 미러 맵은 유클리드 기하 외에도 단체에 맞는 음의 엔트로피, 양의 영역을 위한 로지스틱 배리어, 로가민 등을 후보로 둔다.

일반 볼록 문제에서 확률적 그라디언트를 사용하면 (\eta_t \propto 1/\sqrt{t}) 설정으로 기대 최적성격차 (O(1/\sqrt{t})) 수렴을 기대할 수 있다. 강볼록성과 적절한 지표가 갖춰지면 (O(1/t)) 수렴도 가능하다. 비볼록 문제는 정지점으로의 수렴 보장 수준에서 분석해야 한다.

갱신 경로와 장애 처리

⤢✕

관점	PGD	MD
성능	비평활 정규화 처리에 효율적이며 prox가 폐형이면 고속 처리 가능	도메인 구조를 활용하면 실질 수렴이 빠르고 확률 분포·단체 제약에 강점
확장성	대규모·분산 미니배치에 적합하고 통신량 최소화가 쉬움	좌표 분해·온라인 학습에 강하며 대규모 범주 확률 모델에 유리
수렴	볼록 설정에서 표준 보장을 제공하며 비볼록은 정지점 수렴 수준	브레그먼 기하 기반의 이론적 보장이 있으나 적절한 (\psi) 선택에 의존
안정성	prox가 노이즈와 정칙화의 균형을 돕지만 스텝이 과대하면 진동 가능	지수·엔트로피 맵은 희소 확률의 수치 안정성을 돕지만 언더플로우에 주의 필요
운영	다양한 정규화를 즉시 적용하고 자동 미분과 결합하기 쉬움	제약을 자동으로 만족시키고 투영 비용을 줄일 수 있으나 미러 맵 튜닝이 필요

정규화와 도메인에 따른 적용 장면

L1-정규화 로지스틱 회귀에서는 PGD의 소프트 스레숄딩으로 희소성을 즉시 유도할 수 있다. 대규모 클릭로그나 텍스트 특성에서는 수백만 차원까지 확장 운용할 수 있다.

이미지 복원과 복구에서는 (g)를 데이터 적합 항으로, (h)를 총변분(TV)으로 둔다. prox-TV 근사나 FISTA 가속을 결합하면 고해상도 이미지의 실시간 처리가 가능하다.

추천과 랭킹의 행렬완성에서는 관측이 희소한 행렬을 저랭크로 복원하기 위해 PGD의 SVT(singular value thresholding)를 사용할 수 있다. 대규모 행렬에서는 부분 SVD 근사와 분산 처리를 결합한다.

확률 분포 학습이나 온라인 광고 입찰처럼 단체 제약이 있는 문제는 엔트로피 미러 맵을 둔 MD가 적합하다. 지수 가중 업데이트는 확률 벡터를 자동으로 정규화하며, 라벨 스무딩과 멀티암드 밴딧의 가중 갱신 같은 온라인 설정에도 사용할 수 있다.

L1 정규화 로지스틱 회귀의 확률적 PGD

다음 예시는 Python 3.10+, NumPy 1.26+ 환경을 전제로 하며, 재현을 위해 난수 시드를 지정하는 방식을 사용한다.

import numpy as np

rng = np.random.default_rng(42)
n, d = 20000, 1000
X = rng.normal(size=(n, d)).astype(np.float32)
w_true = rng.normal(size=d)
w_true[rng.choice(d, size=d-50, replace=False)] = 0.0  # 희소 진실
y = (rng.random(n) < 1/(1+np.exp(-X @ w_true))).astype(np.float32)  # Bernoulli

def soft_threshold(v, lam):
    return np.sign(v) * np.maximum(np.abs(v) - lam, 0.0)

def logistic_grad(w, Xb, yb, reg_l2=0.0):
    z = Xb @ w
    p = 1.0 / (1.0 + np.exp(-np.clip(z, -20, 20)))
    grad = Xb.T @ (p - yb) / Xb.shape[0]
    if reg_l2 > 0:
        grad += reg_l2 * w
    return grad

# 하이퍼파라미터
epochs = 3
batch = 512
eta0 = 0.5
lam_l1 = 1e-3

w = np.zeros(d, dtype=np.float32)
for t in range(1, epochs * (n // batch) + 1):
    idx = rng.integers(0, n, size=batch)
    Xb, yb = X[idx], y[idx]
    g = logistic_grad(w, Xb, yb)
    eta = eta0 / np.sqrt(t)  # 감쇠 스케줄
    y_tmp = w - eta * g
    w = soft_threshold(y_tmp, eta * lam_l1)  # prox-L1

# 간단 평가
z = X @ w
p = 1.0 / (1.0 + np.exp(-np.clip(z, -20, 20)))
logloss = -np.mean(y*np.log(p+1e-12) + (1-y)*np.log(1-p+1e-12))
sparsity = np.mean(np.isclose(w, 0.0))
print(f"logloss={logloss:.4f}, sparsity={sparsity:.2%}")

입력 스케일링을 맞추고, 필요한 경우 그라디언트 클리핑을 적용하며, NaN/Inf를 감시해야 한다.

엔트로피 미러 맵으로 단체를 유지하는 방법

음의 엔트로피 (\psi(x)=\sum x_i \log x_i)를 선택하면 갱신식은 지수 가중과 정규화 형태로 단순화된다.

import numpy as np

rng = np.random.default_rng(0)
d = 500  # 카테고리 수
T = 2000
eta0 = 0.5

# 초기 확률벡터 (단체)
x = np.ones(d) / d

def grad_loss(x, reward):
    # 예: -reward^T x 최소화 = reward에 대한 선형손실, grad = -reward
    return -reward

for t in range(1, T+1):
    # 스트리밍 보상(또는 손실) 관측
    reward = rng.random(d)
    g = grad_loss(x, reward)
    eta = eta0 / np.sqrt(t)

    # Exponentiated Gradient (Mirror Descent with entropy)
    # 수치 안정성: 이동 평균 감산으로 언더/오버플로우 방지
    u = np.log(np.clip(x, 1e-32, 1.0)) - eta * g
    u -= u.max()
    x = np.exp(u)
    x /= x.sum()

print(f"min/max prob: {x.min():.3e}/{x.max():.3e}, sum={x.sum():.4f}")

로그 도메인에서 연산해 언더플로우를 피하고, 최소 확률 바닥값을 적용해야 한다.

분산 실행과 수치 안정성의 트레이드오프

스텝사이즈는 감쇠형 (\eta_t = \eta_0/\sqrt{t})를 기본으로 둘 수 있고, 강볼록 문제에서는 (\eta_t = \eta_0/t)도 고려할 수 있다. 실무에서는 워밍업과 감쇠를 조합하는 방식이 권장된다. 백트래킹은 확률적 잡음 때문에 불안정할 수 있으므로 미니배치 평균화와 함께 사용해야 한다.

두 방식 모두 데이터 병렬 미니배치에 적합하다. 통신 주기와 그라디언트 압축을 조절하면 네트워크 병목을 완화할 수 있다. 비동기 갱신은 스케일 이점을 주지만, 지연(staleness)이 수렴률을 떨어뜨릴 수 있다.

SVRG/SAGA 같은 분산 감소 기법은 추정량 분산을 줄일 수 있으나 추가 메모리와 패스 비용이 따른다. 모멘텀과 AdaGrad/Adam은 MD 해석과 연결되며, 좌표별 스케일링으로 수렴을 가속할 수 있다.

복잡한 정규화나 제약에서 prox가 폐형이면 PGD는 구현하기 쉽다. 그렇지 않으면 내적 반복 비용이 커진다. MD는 도메인 구조가 분명할수록 투영 비용을 줄일 수 있지만, 미러 맵을 고르고 튜닝하는 부담이 남는다.

볼록 문제에서는 (O(1/\sqrt{t})) 또는 (O(1/t)) 수렴률을 확보할 수 있고, 대규모 데이터에서는 에폭당 시간 대비 성능이 우수하다. L1-정규화 PGD는 파라미터를 80% 이상 희소화한 사례가 빈번하며, 예측 지표를 유지하면서 추론 비용을 줄일 수 있다. 희소성과 제약 일관성은 모델 해석성을 높이고, 자연스러운 정규화와 투영은 운영 안정성을 돕는다. 도메인 기하를 반영하면 하이퍼파라미터 민감도를 완화하고 수치 안정성도 높일 수 있다.