근접 경사법

최적설계 수치해석 통계 마지막 수정: 2026-08-05 04:41:16

1. 개요[편집]

근접 경사법 Proximal Gradient Method
다른 이름	전진-후진 분할(forward–backward splitting), ISTA
대상 문제	min f(x) + g(x), f는 매끄럽고 g는 볼록·비매끄러움
스텝 크기	η ≤ 1/L (L은 ∇f의 립시츠 상수)
수렴률	O(1/k), 가속하면 O(1/k²)
대표 응용	LASSO, 압축센싱 복원, 전변분 잡음제거

근접 경사법은 목적함수가 “미분 가능한 매끄러운 부분 + 미분 불가능하지만 근접 연산자를 닫힌 형태로 계산할 수 있는 볼록 부분”으로 쪼개지는 복합 최적화 문제

\min_{x \in \mathbb{R}^n} \; F(x) = f(x) + g(x)

를, 매끄러운 항에는 경사 스텝을 밟고 비매끄러운 항에는 근접(proximal) 스텝을 밟는 방식으로 푸는 1차 최적화 알고리즘이다. 여기서 $f$ 는 볼록이며 그래디언트가 $L$ -립시츠 연속이고, $g$ 는 볼록·닫힌·진(proper)이지만 미분 가능성은 요구하지 않는다.

왜 필요하냐면, 현대 역문제와 통계 학습의 목적함수가 죄다 이 꼴이기 때문이다. 데이터 적합항은 매끄러운데( $\|Ax-b\|^2$ ) 정규화항은 미분이 안 된다( $\|x\|_1$ , 전변분, 인디케이터 함수). 경사하강법은 $\|x\|_1$ 의 원점에서 그냥 멈춰 서고, 열헝겊 같은 하위경사법(subgradient)은 $O(1/\sqrt{k})$ 로 기어간다. 근접 경사법은 비매끄러운 부분을 경사가 아니라 근접 연산자로 다뤄서, 비매끄러운 문제인데도 매끄러운 문제와 같은 $O(1/k)$ 를 회복한다.¹

2. 근접 연산자[편집]

핵심 도구는 근접 연산자다.

\mathrm{prox}_{\lambda g}(v) = \arg\min_{x} \left\{ g(x) + \frac{1}{2\lambda}\|x - v\|_2^2 \right\}

” $v$ 근처에 머물되 $g$ 를 줄이는 타협점.” $g$ 가 볼록·닫힌·진이면 괄호 안이 강볼록이라 최솟값이 유일하게 존재하므로, 이 연산자는 잘 정의된 단일값 사상이다. 대표적인 닫힌 형태들:

$g(x) = \|x\|_1$ → 연성 임계화(soft-thresholding). 성분별로 $\mathrm{sign}(v_i)\max(|v_i| - \lambda,\,0)$ . 작은 값은 정확히 0으로 눌리고 큰 값은 $\lambda$ 만큼 원점 쪽으로 당겨진다. ℓ1 정규화가 희소해를 만드는 이유가 이 한 줄에 다 들어 있다.
$g = \iota_C$ (집합 $C$ 의 인디케이터, 안이면 0 밖이면 $+\infty$ ) → $C$ 위로의 사영. 이 경우 근접 경사법은 그대로 투영 경사법이 된다. 즉 제약 최적화의 투영법이 근접법의 특수 사례다.
$g(X) = \|X\|_*$ (핵 노름) → 특이값에 연성 임계화를 적용하는 특이값 임계화. 특이값 분해 한 번이 곧 prox 한 번이다.
$g(x) = \frac{1}{2}\|x\|_2^2$ → 단순 축소 $v/(1+\lambda)$ . 리지 정규화가 왜 희소해를 못 만드는지도 여기서 보인다 — 절대 0이 되지 않는다.

근접 연산자는 **모로 포락**과도 직결된다. $M_{\lambda g}(v) = \min_x \{g(x) + \frac{1}{2\lambda}\|x-v\|^2\}$ 로 정의하면 $M_{\lambda g}$ 는 $C^1$ 이고 그래디언트가 $1/\lambda$ -립시츠이며

\mathrm{prox}_{\lambda g}(v) = v - \lambda \nabla M_{\lambda g}(v)

가 성립한다. 즉 prox 스텝은 ” $g$ 를 매끄럽게 뭉갠 함수 위에서의 정확한 경사 스텝”이다. 비매끄러움을 없앤 게 아니라 매끄러운 대리함수로 갈아 끼운 것.

3. ISTA — 알고리즘[편집]

반복은 놀랄 만큼 단순하다.

x^{k+1} = \mathrm{prox}_{\eta g}\!\left(x^{k} - \eta \nabla f(x^{k})\right)

경사 스텝(전진, forward) 한 번 + 근접 스텝(후진, backward) 한 번. 그래서 이 알고리즘의 다른 이름이 전진-후진 분할이며, 큰 틀에서는 연산자 분리 기법의 한 가족이다. $g$ 가 ℓ1일 때 이 반복이 그 유명한 ISTA(Iterative Shrinkage-Thresholding Algorithm)다 — 경사 한 번, 임계화 한 번, 반복. 코드로 다섯 줄.

이 반복이 왜 옳은가는 고정점을 보면 안다. $x^\ast = \mathrm{prox}_{\eta g}(x^\ast - \eta\nabla f(x^\ast))$ 는 근접 연산자의 최적성 조건을 풀면

0 \in \nabla f(x^\ast) + \partial g(x^\ast)

와 동치이며, 이것이 복합 볼록 문제의 1차 최적성 조건 그 자체다. 즉 알고리즘의 고정점 집합 = 최적해 집합.

또 다른 해석: $f$ 를 $x^k$ 에서 2차 상계로 근사하고( $\nabla^2 f \preceq LI$ ) $g$ 는 그대로 둔 대리 문제

x^{k+1} = \arg\min_x \left\{ f(x^k) + \nabla f(x^k)^\top (x - x^k) + \frac{1}{2\eta}\|x-x^k\|^2 + g(x) \right\}

를 정확히 푼 결과가 위 반복이다. 매 스텝에서 상계를 최소화하므로 $\eta \le 1/L$ 이면 목적함수가 단조 감소한다(majorize-minimize).

4. 스텝 크기와 수렴률[편집]

$\eta \le 1/L$ 이면 $F(x^k) - F^\ast \le \frac{\|x^0 - x^\ast\|^2}{2\eta k} = O(1/k)$ .
$f$ 가 추가로 $\mu$ -강볼록이면 선형 수렴( $O(\rho^k)$ )으로 승급한다. 조건수 $L/\mu$ 가 그대로 수렴 속도를 지배하는 것은 경사하강법과 같다.
$L$ 을 모르면 백트래킹을 쓴다. $f(x^+) \le f(x^k) + \nabla f(x^k)^\top(x^+ - x^k) + \frac{1}{2\eta}\|x^+-x^k\|^2$ 를 만족할 때까지 $\eta \leftarrow \beta\eta$ 로 줄이는 방식. 매끄러운 문제의 라인서치와 목적은 같지만, 검사하는 부등식이 아르미호 조건이 아니라 위의 2차 상계라는 점이 다르다.

$O(1/k)$ 는 사실 답답하다. 여기에 네스테로프 가속을 얹은 것이 FISTA다.

y^{k} = x^{k} + \frac{t_{k}-1}{t_{k+1}}\left(x^{k}-x^{k-1}\right), \qquad t_{k+1} = \frac{1+\sqrt{1+4t_k^2}}{2}

로 외삽점 $y^k$ 를 만들고 거기서 근접 경사 스텝을 밟으면 $F(x^k)-F^\ast = O(1/k^2)$ 로 올라간다. 스텝당 비용은 사실상 동일한데 수렴률만 한 차수 오르니 안 쓸 이유가 없다 — 다만 FISTA는 단조 감소가 아니다. 목적함수가 중간에 출렁이는 걸 보고 버그라고 판단해 롤백하는 게 이 알고리즘의 통과의례.² 단조성이 꼭 필요하면 MFISTA처럼 두 후보 중 나은 쪽을 고르는 변형을 쓴다.

5. 친척들과의 관계[편집]

상황	알고리즘	비고
g가 없음	경사하강법	prox가 항등사상
g가 인디케이터	투영 경사법	prox가 사영
f가 없음	근접점법	안정적이지만 스텝마다 부분문제
f, g 둘 다 비매끄러움	더글러스-래치포드	양쪽 다 prox로
선형 결합 제약	교대방향 승수법	쌍대 문제의 더글러스-래치포드
g가 여러 개	조건부 경사, 프라이멀-듀얼	prox가 안 풀릴 때

핵심 판정 기준은 하나다. $g$ 의 prox를 싸게 계산할 수 있는가. ℓ1이나 상자 제약처럼 성분별로 분해되면 $O(n)$ 이라 사실상 공짜지만, 전변분처럼 이웃 픽셀이 얽히면 prox 자체가 또 하나의 최적화 문제라 내부 반복이 필요하다. 이 경우 근접 경사법을 고집하는 대신 프라이멀-듀얼 계열로 넘어가는 게 낫다.

6. 응용[편집]

LASSO / 희소 회귀. $\frac{1}{2}\|Ax-b\|^2 + \lambda\|x\|_1$ . ISTA/FISTA의 원조 무대. 활성집합법이나 내점법이 정확해를 주지만, $A$ 가 명시적으로 안 만들어지고 행렬-벡터 곱만 가능한 대규모 문제에서는 1차법이 유일한 선택지다.
압축센싱 복원. 측정 연산자가 FFT나 비균일 푸리에 변환인 MRI 재구성에서, 스텝마다 필요한 건 $A^\top(Ax-b)$ 뿐이라 궁합이 좋다.
전변분 잡음제거. 영상 복원의 표준. prox가 닫힌 형태가 아니어서 샹볼의 쌍대 알고리즘을 내부에 끼우거나 프라이멀-듀얼로 바꾼다.
딕셔너리 학습. 희소 코딩 단계가 정확히 LASSO라, 교대 최소화의 절반을 ISTA/FISTA가 담당한다.
저계수 행렬 완성. 핵 노름 prox = 특이값 임계화. 축소차수모델 계열에서 결측 데이터를 메울 때 쓴다.
비볼록 확장. $g = \|x\|_0$ 의 prox는 경성 임계화(작은 성분을 그냥 자름)이며, 이 반복이 IHT다. 볼록성이 없어 전역해 보장은 사라지지만 실무에서는 잘 돈다.

7. 실무 메모[편집]

정지 조건은 목적함수 변화가 아니라 근접 잔차 $\|x^{k+1}-x^k\|/\eta$ 로 잡는 게 정직하다. 이 양이 0이면 최적성 조건이 정확히 만족된다.
$\lambda$ 를 크게 잡고 시작해 점점 줄이는 연속화(warm start)를 쓰면 정규화 경로 전체를 훨씬 싸게 얻는다. 앞 해를 다음 문제의 초기값으로 넘기는 것만으로 반복 수가 몇 배 줄어든다.
조건수가 나쁘면 FISTA도 느리다. 대각 전처리나 가변 계량 근접법(prox를 헤세 계량에서 정의)으로 넘어가는 게 다음 카드지만, 계량이 바뀌면 대부분의 prox 닫힌 형태가 깨진다는 대가가 있다.³

8. 관련 문서[편집]

정확히는 “매끄러운 문제와 같은 차수”다. 하위경사법의 $O(1/\sqrt{k})$ 는 일반 비매끄러운 볼록 함수에 대한 정보이론적 하한이라 못 이긴다. 근접 경사법이 그 하한을 피해 가는 건 $g$ 의 구조를 prox로 정확히 알고 있다는 추가 정보를 썼기 때문이다. 공짜 점심은 여기서도 없다. ↩
FISTA의 목적함수 곡선을 처음 보면 “발산하나?” 싶은 출렁임이 초반 수십 회 나온다. 정상이다. 진짜 발산은 $\eta > 1/L$ 일 때 나오며, 그건 출렁이는 게 아니라 그냥 지수적으로 터진다. 둘은 로그 스케일로 보면 확실히 구분된다. ↩
이 지점에서 “그냥 뉴턴법 쓰면 안 되나요”라는 질문이 나오는데, 비매끄러운 항이 있는 순간 헤세 행렬이 존재하지 않는다. 준뉴턴 근접법(예: 근접 L-BFGS)이 있긴 하지만, 부분문제가 더 이상 닫힌 형태가 아니라서 매 스텝 안에 또 반복 루프가 생긴다. 세상에 공짜는 없고, 특히 최적화에는 더 없다. ↩