좌표 하강법

1. 개요[편집]

좌표 하강법 Coordinate Descent
다른 이름	좌표하강, 블록 좌표 하강(BCD), 비선형 가우스-자이델
갱신	한 좌표만 남기고 전부 고정한 뒤 그 좌표를 정확히 최소화
수렴 조건	매끄러운 볼록 + 분리가능한 비매끄러움 (Tseng 2001)
고장 사례	비분리 비매끄러움(융합 벌점), 매끄러워도 비볼록이면 순환(Powell 1973)
대표 구현	glmnet — 라쏘·엘라스틱 넷 정규화 경로
친척	가우스-자이델, SMO, 교대최소제곱(ALS)

좌표 하강법은 다변수 최적화 문제를 좌표 하나짜리 부분문제들로 쪼개, 나머지 변수를 전부 고정한 채 한 좌표만 정확히 최소화하는 갱신을 돌아가며 반복하는 방법이다.

$$x_j^{k+1} = \arg\min_{t\in\mathbb{R}}\; f\bigl(x_1^{k+1},\dots,x_{j-1}^{k+1},\,t,\,x_{j+1}^{k},\dots,x_n^{k}\bigr)$$

아이디어 자체는 최적화에서 가장 오래되고 가장 순진한 축에 속한다. 그래디언트도, 헤세 행렬도, 라인서치도 필요 없고 한 변수 문제만 풀 줄 알면 된다. 그래서 20세기 내내 “이론적으로 위험하고 실전에서도 느린 방법” 취급을 받았다. 그러다 2007년 전후로 라쏘 계열의 $\ell_1$ 정규화 문제에서 좌표 하강이 내점법과 최소각 회귀를 압도한다는 것이 드러나면서 지위가 뒤집혔다.¹ 오늘날 “변수 십만 개짜리 희소 회귀를 노트북에서 몇 초 만에 푼다”는 이야기는 대부분 좌표 하강 이야기다.

핵심 질문은 하나다. 한 좌표씩만 움직여서 언제 최적점에 도달하는가. 답이 “항상”이 아니라는 것이 이 문서의 대부분이다.

2. 좌표 하나만 움직여도 되는 경우[편집]

$f$ 가 연속 미분가능하고 볼록이며, 각 좌표방향 부분문제의 최소점이 유일하면 순환 좌표 하강의 모든 극한점은 최소점이다. 증명의 뼈대는 단순하다 — 좌표별로 더 내려갈 곳이 없다는 것은 $\partial f/\partial x_j = 0$ 이 모든 $j$ 에 대해 성립한다는 뜻이고, 매끄러운 함수에서는 부분도함수가 전부 0이면 그래디언트가 0이다. 그리고 볼록이면 그래디언트 0이 곧 전역해다.

$f$ 가 이차형식 $\frac12 x^\top A x - b^\top x$ ($A \succ 0$)일 때는 갱신식이

$$x_j \leftarrow \frac{1}{a_{jj}}\Bigl(b_j - \sum_{k\ne j} a_{jk}x_k\Bigr)$$

로 떨어지는데, 이건 글자 그대로 선형계 $Ax=b$ 의 가우스-자이델 반복이다. 좌표 하강은 반복법 동네의 고전을 최적화 언어로 다시 쓴 것에 지나지 않고, 그래서 대각지배·양정부호 같은 조건이 왜 갑자기 튀어나오는지도 자연스럽다. 반대로 $A$ 가 병적으로 조건이 나쁘면 좌표 하강도 가우스-자이델과 똑같이 기어간다는 뜻이기도 하다.²

매끄럽지만 볼록이 아니면 이야기가 다르다. 파월(1973)은 3변수 연속 미분가능 함수에서 순환 좌표 하강이 정상점이 아닌 여섯 점 사이를 영원히 순환하는 예를 만들었다. 각 좌표방향 최소점이 유일하지 않다는 것이 사고의 원인이며, 이 조건이 왜 정리에 붙어 있는지를 보여 주는 반례다.

3. 비매끄러움이 분리되면 살고, 얽히면 죽는다[편집]

미분 불가능한 항이 끼면 위의 논리가 통째로 무너진다. 좌표별 부분도함수가 전부 0에 가깝다고 해서 부분미분(subdifferential)이 0을 포함하는 것은 아니기 때문이다. 비매끄러운 점에서는 좌표축 방향으로만 조사해서는 하강 방향을 놓칠 수 있다.

셍(Tseng 2001)의 정리가 정확히 이 지점을 정리했다. 목적함수가

$$F(x) = f(x) + \sum_{j=1}^{n} g_j(x_j)$$

꼴 — 매끄러운 부분 $f$ 하나에, 비매끄러운 부분은 좌표별로 완전히 분리된 $g_j$ 들의 합 — 이면 블록 좌표 하강의 모든 극한점이 정상점이고, $f$ 가 볼록이면 최소점이다. 직관은 이렇다. 비매끄러움이 좌표별로 분리돼 있으면 부분미분이 좌표별 부분미분의 곱집합이 되어, “좌표마다 최적”이 곧 “전체 최적”으로 승격된다. $\|\beta\|_1 = \sum_j |\beta_j|$ 가 정확히 이 형태이므로 라쏘가 이 정리의 대표 고객이다.

분리가 깨지면 즉시 고장 난다. 융합형 벌점 $|\beta_1-\beta_2|$ 를 넣은 다음 예를 보자.

$$f(\beta) = \tfrac12\beta_1^2 + \tfrac12(\beta_2-4)^2 + 3\,|\beta_1-\beta_2|$$

점 $(1,1)$ 에서 $\beta_1$ 만 $\delta$ 움직이면 $f = 5 + \delta + \tfrac12\delta^2 + 3|\delta|$, $\beta_2$ 만 움직여도 마찬가지로 $f$ 가 늘어난다. 좌표별로는 완벽하게 최적이다. 그런데 두 좌표를 함께 $(1+\delta,1+\delta)$ 로 옮기면 $f = 5 - 2\delta + \delta^2$ 라서 내려간다. 실제 최적점은 $(2,2)$ 이고 값은 4다. 좌표 하강은 $(1,1)$ 에 도달하는 순간 영원히 거기 앉아 있는다.

기하로 보면 벌점의 꺾인 능선이 대각선 $\beta_1=\beta_2$ 위에 놓여 있어서, 축 방향으로만 움직이는 알고리즘은 그 능선을 따라 내려가지 못한다. 융합 라쏘·전변분·그래프 벌점처럼 좌표를 얽는 비매끄러운 항이 있으면 좌표 하강을 그대로 쓰면 안 되고, 교대방향 승수법이나 원시-쌍대 계열로 넘어가거나, 얽힌 좌표를 한 블록으로 묶어 블록 단위로 정확히 푸는 우회로가 필요하다.³

4. 라쏘의 갱신식[편집]

이제 좌표 하강이 왜 라쏘의 표준 솔버가 됐는지가 계산 한 줄로 보인다. 목적함수

$$F(\beta) = \tfrac12\|y - X\beta\|_2^2 + \lambda\|\beta\|_1$$

에서 $\beta_j$ 만 남기고 나머지를 고정하면, 부분잔차 $r^{(-j)} = y - \sum_{k\ne j} x_k\beta_k$ 에 대해 부분문제가

$$\min_{t}\ \tfrac12\|r^{(-j)} - x_j t\|_2^2 + \lambda|t|$$

이고, 이건 한 변수짜리 문제라 닫힌 형태로 풀린다.

$$\beta_j \leftarrow \frac{\mathcal{S}_\lambda\bigl(x_j^\top r^{(-j)}\bigr)}{\|x_j\|_2^2}, \qquad \mathcal{S}_\lambda(z) = \mathrm{sign}(z)\,(|z|-\lambda)_+$$

즉 부분잔차와의 상관을 구해 연성 임계화하고 열의 제곱노름으로 나누는 것이 전부다. 열을 표준화해 두면 분모가 상수라 사실상 임계화 한 번이다. 임계값을 넘지 못한 변수는 정확히 0이 되고, 그래서 갱신 자체가 변수 선택을 겸한다.

구현에서 결정적인 것은 잔차를 매번 새로 만들지 않는 것이다. $\beta_j$ 가 $\Delta$ 만큼 바뀌면 $r \leftarrow r - \Delta\,x_j$ 로 갱신하면 되므로 좌표 하나에 $O(n)$, 전체 한 바퀴에 $O(np)$ 다. $n \gg p$ 인 경우에는 $x_j^\top y$ 와 활성 변수들 사이의 $x_j^\top x_k$ 를 미리 캐시해 두는 공분산 갱신이 더 싸다 — 이러면 좌표당 비용이 잔차 길이가 아니라 활성집합 크기에 비례한다.

5. 갱신 순서 — 순환·무작위·그리디[편집]

어떤 좌표를 다음에 고를 것인가는 생각보다 성능 차이가 크다.

• 순환(cyclic). $1,2,\dots,p$ 를 그대로 돈다. 구현이 가장 단순하고 캐시 지역성이 좋다. 최악의 경우 상관 구조가 나쁘면 특정 순서에서 극단적으로 느려질 수 있다는 것이 알려져 있고, 그래서 실무 코드는 순서를 한 번 섞어 두는 정도의 방어를 한다.
• 무작위(randomized). 매번 좌표를 균등하게(또는 좌표별 립시츠 상수 $L_j$ 에 비례하게) 뽑는다. 네스테로프(2012)가 이 방식에 대해 기댓값 기준 $O(pL R^2/k)$ 같은 명시적 복잡도를 준 것이 좌표 하강 이론의 전환점이었고, 리흐타릭-타카치가 이를 분리가능 비매끄러운 항이 있는 복합 문제로 확장했다. 이론이 깔끔한 쪽은 압도적으로 무작위 판본이다.
• 그리디(Gauss-Southwell). $\bigl|\nabla_j f\bigr|$ 가 가장 큰 좌표를 고른다. 한 스텝당 감소량이 가장 크지만, 최대값을 찾는 비용이 전체를 한 바퀴 도는 비용과 맞먹으면 남는 게 없다. 그래디언트를 싸게 유지할 수 있는 구조(희소 $X$, 힙 관리)에서만 값을 한다. 규칙별 수렴률을 립시츠 상수의 노름 차이로 정리한 분석(Nutini 외 2015)이 나오면서, 그리디가 무작위보다 최대 $p$ 배 빠를 수 있다는 것이 정량화됐다.

여기에 실무 최적화 하나가 더 붙는다. 라쏘 해는 대부분의 좌표가 0이므로, 0인 채 오래 머문 좌표는 매 바퀴 건드릴 필요가 없다. 활성집합만 반복해서 돌리고 가끔 전체를 한 바퀴 훑어 KKT 조건 위반이 없는지 확인하는 구조가 표준이 됐다.

6. glmnet — 왜 이게 표준이 됐나[편집]

glmnet(Friedman-Hastie-Tibshirani 2010)이 사실상의 레퍼런스 구현이 된 것은 좌표 하강 자체보다도 그 주변 설계 때문이다.

• 정규화 경로. 사용자는 $\lambda$ 하나를 알고 싶은 게 아니라 교차검증으로 고를 후보 경로 전체를 원한다. $\lambda_{\max}=\|X^\top y\|_\infty$ 에서 시작해 로그 등간격으로 100개쯤 내려가는 격자가 기본값이다.
• 웜스타트. 이전 $\lambda$ 의 해를 다음 문제의 초기값으로 넘긴다. 격자가 촘촘하면 이웃한 두 해가 거의 같아서 좌표 하강이 몇 바퀴 만에 끝난다. 경로 전체를 푸는 것이 한 점을 맨땅에서 푸는 것보다 싸다는 역설이 여기서 나온다.
• 활성집합 + 강한 규칙(strong rules). 다음 $\lambda$ 에서 0으로 남을 것이 거의 확실한 변수를 상관의 립시츠 성질로 미리 걸러 낸다(Tibshirani 외 2012). 휴리스틱이라 틀릴 수 있으므로 마지막에 KKT 조건을 전수 검사해 위반이 있으면 복구한다 — 속도는 휴리스틱에서, 정확성은 최적성 조건 검사에서 가져오는 구조다.
• GLM 확장. 로지스틱·포아송 회귀는 바깥에서 이차 근사(IRLS)를 한 겹 두르고 안쪽에서 가중 좌표 하강을 돌린다. 그래서 같은 커널로 일반화 선형 모형 전체를 덮는다.

여기에 $\ell_1$ 과 $\ell_2$ 를 섞은 엘라스틱 넷 벌점을 넣어도 갱신식은 분모에 $\lambda(1-\alpha)$ 가 하나 더 붙는 정도로 끝난다. 오히려 $\ell_2$ 항이 목적함수를 강볼록으로 만들어 수렴이 더 안정된다.

7. 친척들과 실무 메모[편집]

• SMO(Sequential Minimal Optimization). 서포트 벡터 머신 쌍대 문제는 등식 제약 $\sum_i \alpha_i y_i = 0$ 때문에 좌표 하나만 움직이면 제약이 깨진다. 그래서 두 개씩 묶어 움직이는 블록 좌표 하강을 쓴다. 블록 크기를 제약이 정한 사례.
• 교대최소제곱(ALS). 행렬 분해 $M \approx UV^\top$ 에서 $U$ 고정하고 $V$ 풀고, 다시 반대로. 블록이 행렬 하나 통째인 블록 좌표 하강이며, 각 블록 부분문제가 최소자승법이라 정확히 풀린다. 비볼록이라 전역해 보장은 없다.
• 기댓값 최대화·평균장 근사. 기댓값 최대화 알고리즘과 변분 추론의 좌표별 갱신도 구조적으로 같은 물건이다. 한 블록을 고정하고 나머지를 정확히 최적화하는 패턴은 통계 전반에 퍼져 있다.
• 병렬화가 어렵다. 좌표 하강은 본질적으로 순차적이다. 여러 좌표를 동시에 갱신하는 병렬 판본은 열들이 서로 상관돼 있으면 서로의 갱신을 과잉 반영해 발산할 수 있고, 동시 갱신 개수의 상한이 설계 행렬의 상관 구조에 걸린다. GPU 컴퓨팅으로 라쏘를 밀어붙이려다 좌절하는 지점이 대개 여기다.⁴
• 정지 조건. 목적함수 변화보다 한 바퀴 동안의 최대 좌표 변화량이나 KKT 조건 위반량을 쓰는 것이 정직하다. 웜스타트 경로에서는 앞 해가 이미 좋아서 목적함수가 거의 안 움직이는 것이 정상이기 때문이다.

8. 관련 문서[편집]

• 라쏘 · 엘라스틱 넷 · 능형회귀
• 최소각 회귀 · 근접 경사법 · 교대방향 승수법
• 볼록 최적화 · 카루시-쿤-터커 조건 · 약볼록 함수
• 반복법 · 가우스-자이델 방법 · 희소행렬
• 경사하강법 · 확률적 경사하강법 · 활성집합법
• 교차검증 · 기댓값 최대화 알고리즘 · 변분 추론

9. Footnotes[편집]

1. 사실 좌표 하강으로 라쏘를 푸는 아이디어 자체는 Fu(1998)의 “shooting” 알고리즘까지 거슬러 올라간다. 그런데 당시에는 최소각 회귀가 “경로 전체를 정확히 준다”는 화려한 결과와 함께 등장한 직후라 아무도 거들떠보지 않았다. 좋은 알고리즘이 10년 늦게 발견되는 것이 아니라, 발견돼 있었는데 10년 늦게 읽히는 경우가 이 바닥에는 꽤 있다. ↩

2. 그래서 “좌표 하강은 1차 방법 중 유일하게 조건수를 안 탄다” 같은 말을 들으면 일단 의심해야 한다. 좌표별로 정확히 최소화한다고 해서 등고선이 길쭉한 골짜기를 지그재그로 내려가는 운명이 바뀌지는 않는다. 좌표축에 정렬된 골짜기라면 한 방에 끝나고, 45도로 기울어진 골짜기라면 똑같이 고생한다. ↩

3. 이 반례를 처음 보면 “그러면 초기값을 잘 주면 되지 않나”라는 생각이 드는데, 문제는 저 정지점들이 대각선 위에 연속적으로 널려 있다는 것이다. 운이 나쁜 한 점이 아니라 정지점의 집합 자체가 두껍다. 초기값 운으로 해결할 수 있는 종류의 고장이 아니다. ↩

4. 그래서 대규모 분산 환경에서 희소 회귀를 풀 때는 좌표 하강을 고집하는 대신 교대방향 승수법으로 데이터를 쪼개는 쪽이 자주 선택된다. 단일 노드에서는 좌표 하강이 압승이지만, 노드가 늘어나는 순간 순차성이 그대로 통신 비용이 된다. 알고리즘 선택이 수학이 아니라 배치 구조에 끌려가는 흔한 사례. ↩