미분이 없는 점에서 기울기를 대신하는 하위미분을 세우고 최적성 조건 0 ∈ ∂f를 증명합니다. L1과 ReLU가 0에서 갖는 것, 클라크 미분과 자동미분의 선택, 강볼록성과 L-매끄러움이 켤레에서 자리를 바꾼다는 쌍대까지 다룹니다.
PALDYN Team//50 MIN READ
11MATH
고급
볼록해석 · 하위기울기
희소 오토인코더로 언어 모델의 활성값을 해석하는 팀이 있습니다. 은닉 벡터를 넓은 사전 위의 몇 개 안 되는 성분으로 풀어 쓰려고, 재구성 오차에 계수의 L1 노름을 벌점으로 더해 PyTorch에서 Adam으로 학습합니다. 학습이 끝나고 계수를 들여다보니 이상합니다. 절반 넘는 성분이 0.001이나 −0.0007 같은 작은 값에 머물러 있을 뿐 정확히 0인 성분은 거의 없습니다. 희소하게 만들려고 L1을 넣었는데 희소하지 않습니다. 같은 코드의 인코더에는 ReLU가 들어 있고, 리뷰어 한 명이 묻습니다. torch.abs의 0에서의 기울기는 몇으로 계산되고 ReLU는 0에서 몇을 내는가, 그 값은 어디서 온 것이고 다른 값을 골랐다면 결과가 달라지는가. 둘 다 0이라는 답이 나오지만, 그 0이 맞는 답인지는 아무도 확신하지 못합니다.
지난 글은 경사하강이 수많은 보간 해 가운데 무엇을 고르는지에서 끝났고, 그 마지막에 거울 하강과 브레그먼 발산을 라그랑주 조건 한 줄로 넘겼습니다. 이 글부터 A4 「볼록해석과 최적화 이론」 단원이 그 한 줄을 제대로 세웁니다. 출발점은 젠센 부등식에서 정의한 볼록함수와 손실 지형에서 쓴 헤세 판정인데, 둘 다 함수가 미분 가능하다고 가정했습니다. L1 벌점, ReLU, 핵노름, 힌지 손실은 정확히 최적점이 놓이는 자리에서 꺾입니다. 이 글은 미분이 없는 점에서 기울기를 대신할 대상을 세우고, 그것으로 최적성 조건을 정확히 쓰고, 수렴 정리가 늘 가정하는 강볼록성과 매끄러움이 사실 한 성질의 두 얼굴이라는 것을 증명합니다.
볼록성의 특징화
볼록집합과 에피그래프
집합 C⊆Rn 안의 두 점을 잇는 선분이 늘 C 안에 머물면, 곧 x,z∈C 와 t∈[0,1] 에 대해 (1−t)x+tz∈C 이면 C 를 볼록집합이라 부릅니다. 공, 반공간, 초평면, 단체가 볼록이고 도넛 모양이나 두 공의 합집합은 볼록이 아닙니다. 볼록집합끼리의 교집합은 다시 볼록이라, 부등식 제약을 여럿 건 실현 가능 영역도 각 제약이 볼록이면 볼록입니다.
함수 쪽 정의는 젠센 부등식 글에서 쓴 그대로입니다. f((1−t)x+tz)≤(1−t)f(x)+tf(z) 가 모든 x,z 와 t∈[0,1] 에서 성립하면 f 가 볼록함수입니다. 두 정의를 잇는 다리가 에피그래프입니다. 함수 f 의 그래프와 그 위쪽 전체, 곧 epif={(x,s):s≥f(x)} 를 그렇게 부르고, f 가 볼록함수인 것과 epif 가 볼록집합인 것은 같은 말입니다. 함수에 관한 질문을 n+1 차원 집합에 관한 질문으로 옮기는 이 번역 덕분에, 아래에서 기울기가 없는 점의 「기울기」를 집합을 받치는 평면의 기울기로 정의할 수 있게 됩니다.
1차 조건
f 가 미분 가능하면 볼록성은 한 점의 정보로 바뀝니다. f 가 볼록인 것과
f(z)≥f(x)+⟨∇f(x),z−x⟩(모든x,z)
가 같습니다. 오른쪽은 x 에서의 접평면이고, 접평면이 그래프 전체를 아래에서 받친다는 말입니다. 그림의 f(x)=x2/2 에서 x=1 의 접선은 y=x−1/2 이고, z2/2−(z−1/2)=(z−1)2/2≥0 이라 정말로 포물선이 늘 그 위에 있습니다.
증명의 앞쪽은 정의에서 극한을 하나 취하는 것입니다. 볼록성에서 f(x+t(z−x))≤f(x)+t(f(z)−f(x)) 이고, 양변에서 f(x) 를 빼고 t 로 나눈 뒤 t→0+ 로 보내면 왼쪽이 방향미분 ⟨∇f(x),z−x⟩ 가 되어 부등식이 나옵니다. 거꾸로 접평면 부등식이 있으면 w=(1−t)x+tz 에서 x 와 z 쪽으로 부등식을 하나씩 쓰고 1−t 와 t 를 곱해 더하면 기울기 항이 (1−t)(x−w)+t(z−w)=0 으로 사라져 볼록성의 정의가 남습니다. 1차 조건에서 곧장 나오는 귀결이 하나 있는데, ∇f(x∗)=0 이면 모든 z 에서 f(z)≥f(x∗) 라는 것입니다. 볼록함수에서는 정상점이 곧 전역 최소점이고, 국소 최소점도 전부 전역 최소점입니다.
2차 조건
두 번 미분 가능하면 조건이 한 단계 더 국소적이 됩니다. f 가 볼록인 것과 모든 점에서 헤세 행렬이 양의 준정부호, 곧 ∇2f(x)⪰0 인 것이 같습니다. 1차원으로 줄여 보면 g(t)=f(x+tv) 의 이계도함수가 v⊤∇2f(x+tv)v 이고, 모든 직선 위에서 함수가 볼록인 것이 곧 전체가 볼록인 것이라 1차원의 「이계도함수가 음이 아니다」로 충분합니다. 손실 지형 글에서 헤세의 고윳값으로 극소와 안장점을 갈랐던 판정의 대역적 판본입니다.
세 특징화는 각자 쓰임이 다릅니다. 정의는 미분이 없어도 쓰이고, 에피그래프는 기하적 그림을 주고, 1차 조건은 미분이 있을 때 최적성을 한 줄로 주고, 2차 조건은 실제로 확인하기 가장 쉽습니다. 이 글의 나머지는 1차 조건을 미분이 없는 점까지 넓히는 일입니다.
확장실수값 함수
유효 정의역
제약이 있는 문제를 다루려면 함수가 +∞ 를 값으로 가져도 되게 하는 편이 편합니다. f:Rn→R∪{+∞} 꼴을 확장실수값 함수라 부르고, 값이 유한한 점의 집합 domf={x:f(x)<∞} 를 유효 정의역이라 부릅니다. 볼록성의 정의는 +∞ 에 대한 산술 규칙(a+∞=∞, 그리고 t>0 일 때 t⋅∞=∞)만 정하면 그대로 쓰이고, 볼록함수의 유효 정의역은 자동으로 볼록집합입니다.
이 일반화에는 조건이 둘 붙습니다. 어디서도 −∞ 를 갖지 않고 적어도 한 점에서 유한하면 진볼록 함수(proper convex function)라 부르고, 에피그래프가 닫힌집합이면 닫힌 함수라 부릅니다. 닫혀 있다는 것은 하반연속, 곧 xk→x 이면 f(x)≤liminff(xk) 와 같습니다. 이 조건이 없으면 최소값이 존재하지 않는 병적인 예가 생기고, 다음 글의 이중 켤레 정리도 닫힌 진볼록 함수에서만 성립합니다. 이 글에서 다루는 함수는 따로 말하지 않으면 전부 닫힌 진볼록 함수입니다.
인디케이터 함수
볼록집합 C 에 대해 C 안에서 0, 밖에서 +∞ 인 함수를 ιC 로 쓰고 인디케이터 함수라 부릅니다. 확률론의 지시함수(안에서 1, 밖에서 0)와 이름이 비슷하지만 다른 물건입니다. 이것의 쓸모는 제약을 목적식 안으로 넣는 데 있습니다. C 위에서 g 를 최소화하는 문제가 제약 없는 문제 minxg(x)+ιC(x) 와 정확히 같아집니다. C 밖으로 나가면 목적값이 무한대이므로 최소점이 저절로 C 안에 머뭅니다.
이렇게 쓰면 제약 최적화와 비제약 최적화가 한 이론이 되고, 대가로 목적식이 미분 불가능해집니다. ιC 는 C 의 경계에서 0에서 무한대로 뛰므로 경계 위의 최적점에서 기울기를 말할 수 없습니다. L1 벌점이 0에서 꺾이는 것과 제약 경계에서 목적식이 무한대로 뛰는 것을 같은 도구로 다루려는 것이 다음 절의 하위미분입니다.
하위미분
하위기울기
1차 조건의 접평면 부등식에서 ∇f(x) 자리에 들어갈 수 있는 벡터를 전부 모으는 것으로 정의를 시작합니다. 벡터 g 가
f(z)≥f(x)+⟨g,z−x⟩(모든z)
를 만족하면 g 를 x 에서의 하위기울기라 부르고, x 에서의 하위기울기 전체의 집합을 하위미분∂f(x) 라 부릅니다. 기하적으로 g 는 에피그래프를 (x,f(x)) 에서 받치는 평면의 기울기이고, 하위미분은 그런 평면이 몇 개나 있는지를 모은 것입니다.
f 가 x 에서 미분 가능한 볼록함수이면 ∂f(x)={∇f(x)} 로 원소가 하나뿐입니다. 받치는 평면이 접평면 하나밖에 없기 때문입니다. 꺾인 점에서는 여럿이 됩니다. f(x)=∣x∣ 는 원점에서 기울기가 −1 에서 1 사이인 직선이면 무엇이든 그래프 아래에 놓이므로 ∂∣x∣(0)=[−1,1] 이고, 0이 아닌 점에서는 {sign(x)} 입니다. 하위미분을 x 의 함수로 그리면 계단 함수가 0에서 세로 선분으로 이어진 모양, 곧 점 하나에 집합 하나를 대응시키는 집합값 사상이 됩니다.
인디케이터 함수의 하위미분도 바로 계산됩니다. x∈C 에서 g∈∂ιC(x) 라는 조건은 C 안의 모든 z 에 대해 0≥⟨g,z−x⟩ 이고, 이것은 g 가 C 의 어느 점으로 향하는 방향과도 둔각을 이룬다는 뜻입니다. 이런 g 의 모임을 C 의 x 에서의 법선뿔NC(x) 라 부릅니다. 내부의 점에서는 {0} 이고, 구간 [−1,1] 의 오른쪽 끝 1에서는 [0,∞) 입니다.
볼록함수의 유효 정의역 내부에서는 하위미분이 언제나 비어 있지 않고 유계인 닫힌 볼록집합입니다. 이것은 내부의 점 (x,f(x)) 가 에피그래프의 경계에 있으므로 거기서 받치는 초평면이 존재한다는 분리 정리의 결과이고, 그 초평면이 수직이 아니라는 것을 확인하면 하위기울기가 하나 나옵니다. 경계에서는 비어 있을 수 있습니다. −x 를 [0,∞) 위에서 보면 0에서 기울기가 −∞ 로 가므로 받치는 직선이 없습니다.
최적성 조건
정의를 이렇게 세우면 최적성 조건은 증명이 한 줄입니다.
x∗∈argminf⟺0∈∂f(x∗)
0∈∂f(x∗) 를 정의대로 풀면 모든 z 에 대해 f(z)≥f(x∗)+⟨0,z−x∗⟩=f(x∗) 이고, 이것이 바로 x∗ 가 전역 최소점이라는 말입니다. 거꾸로 읽어도 똑같습니다. 미분 가능할 때의 ∇f(x∗)=0 이 「수평인 받침 평면이 있다」로 일반화되었고, 볼록성이 아니라 하위미분의 정의가 전역성을 실어 나릅니다. 대신 하위미분은 볼록이 아닌 함수에서는 대부분의 점에서 비어 버리므로, 이 조건이 쓸모 있는 것은 볼록함수에서입니다.
이 조건이 실제 문제에서 쓰이려면 ∂f 를 계산할 수 있어야 하고, 실제 목적식은 거의 늘 매끄러운 데이터 항과 꺾인 벌점 항의 합이라 합의 하위미분이 필요합니다.
합의 규칙
g 가 미분 가능한 볼록함수이고 h 가 볼록함수이면
∂(g+h)(x)=∇g(x)+∂h(x)
입니다. ⊇ 는 접평면 부등식과 하위기울기 부등식을 더하면 바로 나옵니다. ⊆ 가 일입니다. v∈∂(g+h)(x) 라 하고 임의의 z 와 t∈(0,1] 에 대해 xt=x+t(z−x) 를 둡니다. 하위기울기 부등식에서 g(xt)+h(xt)≥g(x)+h(x)+t⟨v,z−x⟩ 이고, h 의 볼록성에서 h(xt)≤h(x)+t(h(z)−h(x)) 입니다. 둘을 이으면
g(xt)−g(x)+t(h(z)−h(x))≥t⟨v,z−x⟩
이고, t 로 나누고 t→0+ 로 보내면 첫 항이 ⟨∇g(x),z−x⟩ 가 되어 h(z)≥h(x)+⟨v−∇g(x),z−x⟩ 가 남습니다. 곧 v−∇g(x)∈∂h(x) 입니다.
둘 다 미분 불가능하면 ∂(g+h)⊇∂g+∂h 는 언제나 맞지만 등호에는 정의역이 충분히 겹친다는 조건(한쪽의 정의역 내부가 다른 쪽 정의역과 만난다는 식의 제약 자격)이 필요합니다. 머신러닝 목적식은 거의 다 데이터 항이 매끄러우므로 위의 형태로 충분합니다. 이것과 최적성 조건을 합치면 매끄러운 항 g 와 꺾인 항 h 의 합을 최소화하는 점은 정확히
−∇g(x∗)∈∂h(x∗)
인 점입니다. 제약 문제 minx∈Cg(x) 에 h=ιC 를 넣으면 −∇g(x∗)∈NC(x∗), 곧 「내려가는 방향이 실현 가능 영역 밖을 향한다」가 되고, 이것이 중급 56번의 KKT 조건이 볼록 문제에서 갖는 기하적 모양입니다. 예로 [−1,1] 위에서 (x−2)2 를 최소화하면 x∗=1 에서 −∇g(1)=2∈[0,∞)=N[−1,1](1) 이 성립합니다.
0에서의 꺾임
L1과 1차원 라쏘
L1 벌점이 왜 정확한 0을 만드는지가 이 조건 하나로 풀립니다. 가장 작은 경우는 1차원
f(w)=21(w−a)2+λ∣w∣
입니다. 최적성 조건은 0∈(w−a)+λ∂∣w∣ 이고, 경우를 셋으로 나누면 됩니다. w>0 이면 w=a−λ 인데 이것이 양수려면 a>λ 여야 하고, w<0 이면 w=a+λ 로 a<−λ 가 필요합니다. 남은 w=0 에서는 조건이 a∈[−λ,λ], 곧 ∣a∣≤λ 입니다. 셋을 모으면
w∗=sign(a)max(∣a∣−λ,0)
이고, λ=1 일 때 a=3 이면 w∗=2, a=0.6 이면 w∗=0 입니다. 그림에서 보듯 ∂f 의 그래프는 0에서 높이 2λ 짜리 세로 선분을 품고, 그 선분이 가로축을 지나면 해가 정확히 0에 섭니다. a 가 [−λ,λ] 의 어디에 있든 해가 꼼짝하지 않는다는 것이 희소성의 정체입니다. 매끄러운 L2 벌점 λw2/2 였다면 해는 a/(1+λ) 로 줄어들 뿐 a=0 인 한 0이 되지 않습니다. 이 해를 주는 사상을 고급 13번이 근접 연산자로 다시 읽습니다.
여러 차원의 라쏘 2n1∥Xw−y∥2+λ∥w∥1 도 좌표마다 같은 모양입니다. 데이터 항의 기울기를 r=X⊤(Xw−y)/n 이라 하면 최적점의 조건은 0이 아닌 좌표에서 rj=−λsign(wj), 0인 좌표에서 ∣rj∣≤λ 입니다. 데이터가 그 좌표를 끌어당기는 힘이 λ 를 넘지 못하면 그 좌표는 정확히 0에 머뭅니다. 첫머리의 계수들이 0 근처를 떠돈 이유도 여기서 보입니다. 하위기울기법은 이 집합에서 원소 하나, 곧 sign(0)=0 을 골라 기울기처럼 씁니다. 0을 조금만 벗어나도 벌점 쪽 기울기가 ±λ 로 튀어 반대쪽으로 밀어내므로 좌표가 0을 사이에 두고 걸음 크기만큼 진동하고, 걸음이 유한한 한 정확히 0에 내려앉을 일이 없습니다.
클라크 미분
ReLU는 볼록이라 위의 정의가 그대로 들어맞고 ∂ReLU(0)=[0,1] 입니다. 그런데 신경망 전체는 볼록이 아니고, 볼록이 아닌 함수에서 하위미분은 대개 비어 있습니다. −∣x∣ 를 0에서 아래로 받치는 직선은 하나도 없습니다. 그래서 비볼록 함수에 쓰는 일반화가 따로 있습니다.
f 가 국소적으로 립시츠이면 라데마허 정리에 따라 거의 모든 점에서 미분 가능합니다. 미분 가능한 점들의 집합을 D 라 할 때
∂Cf(x)=conv{limk→∞∇f(xk):xk→x,xk∈D}
를 클라크 일반화 미분이라 부릅니다. x 로 다가가는 점들에서 본 기울기의 극한값을 모두 모아 볼록 껍질을 취한 것입니다. 볼록함수에서는 앞의 하위미분과 정확히 같고, 연속적으로 미분 가능한 점에서는 {∇f(x)} 입니다. ReLU의 0에서는 왼쪽에서 오는 기울기 0과 오른쪽에서 오는 1의 껍질이라 [0,1], −∣x∣ 의 0에서는 [−1,1] 입니다. 클라크 정지점, 곧 0∈∂Cf(x) 인 점은 비볼록 비매끄러운 최적화 이론이 「수렴했다」고 말할 때 가리키는 대상입니다. 다만 볼록이 아니므로 이 조건은 최적성의 필요조건일 뿐 충분조건이 아닙니다.
자동미분의 선택
PyTorch와 JAX는 ReLU의 0에서의 미분으로 0을, ∣x∣ 의 0에서의 미분으로 sign(0)=0 을 씁니다. 둘 다 클라크 미분의 원소이니 그 한 점만 보면 정당한 선택입니다. 「어느 값을 골라도 된다」를 정확히 쓰려면 세 가지를 구별해야 합니다.
첫째, 연쇄법칙은 클라크 미분에서 등식이 아니라 포함 관계일 뿐입니다. 그래서 각 단계가 정당한 원소를 골라도 합성 전체의 결과는 클라크 미분 밖에 떨어질 수 있습니다. Kakade와 Lee(2018)가 든 예가 h(x)=ReLU(x)−ReLU(−x) 입니다. 이 함수는 어디서나 x 와 같아서 미분은 늘 1인데, 자동미분은 0에서 ReLU′(0)=s 를 두 번 써서 s+s=2s 를 냅니다. s=0 이면 0, s=1 이면 2이고 참값 1을 내는 것은 s=1/2 뿐입니다. 어느 s 도 모든 프로그램에서 옳지는 않습니다.
둘째, 그 어긋남이 일어나는 입력은 측도가 0인 집합입니다. Lee 등(2020)은 조각마다 해석적인 함수로 짠 프로그램에서 자동미분이 참 미분과 다른 입력의 집합이 르베그 측도 0임을 보였고, Bolte와 Pauwels(2021)는 자동미분의 출력이 보존장(conservative field)이라는 집합값 사상의 원소라는 것과 그 보존장을 따라가는 SGD가 보존장의 정지점으로 수렴한다는 것을 증명했습니다. 초기화와 데이터가 연속 분포를 따르면 정확한 산술에서는 확률 1로 그 측도 0 집합을 밟지 않으므로, s 를 무엇으로 고르든 이론의 수렴 보장은 같습니다. 정확한 서술은 「한 점의 선택은 정당하고, 합성의 결과는 틀릴 수 있지만 측도 0인 곳에서만 틀리며, 그래서 수렴 이론이 바뀌지 않는다」입니다.
셋째, 부동소수점은 정확한 산술이 아닙니다. 활성값이 정확히 0.0이 되는 일은 생각보다 자주 생기고, Bertoin 등(2021)은 16비트처럼 정밀도가 낮을 때 ReLU′(0) 의 선택이 학습 곡선을 실제로 바꿀 수 있음을 보고했습니다. 이론이 「상관없다」고 하는 것은 측도 0 집합이 정말로 측도 0일 때의 이야기입니다. 활성함수의 미분에서 ReLU의 도함수를 계단으로 적고 0을 넘어갔던 자리가 이 세 겹의 이야기를 품고 있었습니다.
강볼록성과 매끄러움
강볼록성
볼록함수는 바닥이 평평할 수 있습니다. 최소점이 여럿이거나, 최소점 근처에서 너무 완만해서 함수값이 조금 줄어도 점은 멀리 떨어져 있을 수 있습니다. 이것을 막는 조건이 강볼록성입니다. f−2μ∥x∥2 가 볼록이면 f 를 μ-강볼록이라 부르고, 하위기울기로 쓰면 모든 x 와 g∈∂f(x) 에 대해
f(z)≥f(x)+⟨g,z−x⟩+2μ∥z−x∥2
입니다. 받치는 평면이 아니라 받치는 포물면이 있다는 말이고, 두 번 미분 가능하면 ∇2f⪰μI 와 같습니다. 이 부등식을 x1 에서 x2 로, x2 에서 x1 로 한 번씩 쓰고 더하면 함수값이 지워져
⟨g1−g2,x1−x2⟩≥μ∥x1−x2∥2
가 남습니다. 하위미분이라는 집합값 사상이 이 성질을 가질 때 강단조라 부릅니다. 강볼록 함수의 최소점은 하나뿐이고(두 최소점에 g1=g2=0 을 넣으면 거리가 0), 강볼록의 부등식에 최소점 x∗ 와 g=0 을 넣으면 f(z)−f(x∗)≥2μ∥z−x∗∥2 로 함수값의 차이가 거리를 통제합니다. 라쏘처럼 λ∥w∥1 만 붙은 목적식은 강볼록이 아니어서 해가 여럿일 수 있고, 엘라스틱넷이 L2 항을 조금 더하는 이유가 여기에 있습니다.
L-매끄러움
반대쪽 조건이 매끄러움입니다. 기울기가 립시츠, 곧 ∥∇f(x)−∇f(z)∥≤L∥x−z∥ 이면 f 를 L-매끄러움이라 부릅니다. 경사하강법 유도에서 이 조건으로부터 하강 보조정리
f(z)≤f(x)+⟨∇f(x),z−x⟩+2L∥z−x∥2
를 얻었고, 학습률 상한 2/L 이 거기서 나왔습니다. 위에서 덮는 포물면이 있다는 말이고, 볼록이고 두 번 미분 가능하면 ∇2f⪯LI 와 같습니다. 두 조건이 함께 서면 함수가 아래로는 곡률 μ 짜리, 위로는 L 짜리 포물면 사이에 끼고, 그 비 κ=L/μ 를 조건수라 부릅니다. 이차함수 f(x)=21x⊤Ax 에서는 μ 와 L 이 A 의 가장 작은 고윳값과 가장 큰 고윳값이고, 이 글의 예 A=diag(4,1) 은 μ=1, L=4, κ=4 입니다.
켤레의 쌍대
두 조건을 잇는 것이 켤레함수
f∗(y)=supx{⟨x,y⟩−f(x)}
입니다. 기울기가 y 인 직선을 아래에서 밀어 올려 그래프에 닿게 할 때 그 직선의 절편이 −f∗(y) 입니다. 정의와 기하는 고급 12번 · 「르장드르–펜첼 변환과 쌍대성: 문제를 뒤집어 푸는 법」이 본격적으로 다루고, 여기서는 쌍대 정리에 필요한 만큼만 씁니다. 이차함수에서는 ⟨x,y⟩−21x⊤Ax 의 기울기 y−Ax 를 0으로 두어 x=A−1y 에서 최대가 되고 f∗(y)=21y⊤A−1y 입니다. 고윳값이 4와 1에서 1/4 과 1로 바뀌므로, f 의 μ=1 과 L=4 가 f∗ 에서는 매끄러움 상수 1=1/μ 와 강볼록 상수 1/4=1/L 이 됩니다. 이 맞바꿈이 이차함수에 한정된 사실이 아니라는 것이 이 절의 정리입니다.
정리 1. 닫힌 진볼록 함수 f 가 μ-강볼록이면 f∗ 는 어디서나 미분 가능하고 ∇f∗ 는 1/μ-립시츠입니다.
증명. 고정한 y 에서 x↦⟨x,y⟩−f(x) 는 μ-강오목이고 상반연속이며 ∥x∥→∞ 에서 −∞ 로 가므로 최대점이 존재하고, 강오목성 때문에 하나뿐입니다. 그 최대점을 x(y) 라 하면 최적성 조건 0∈∂(f−⟨⋅,y⟩)(x(y)) 에서 y∈∂f(x(y)) 입니다. 이제 두 점 y,z 를 잡습니다. f∗(z)≥⟨x(y),z⟩−f(x(y))=f∗(y)+⟨x(y),z−y⟩ 이고, 같은 식을 x(z) 로 쓰면 f∗(y)≥f∗(z)+⟨x(z),y−z⟩ 입니다. 두 식을 합치면
0≤f∗(z)−f∗(y)−⟨x(y),z−y⟩≤⟨x(z)−x(y),z−y⟩
입니다. 한편 y∈∂f(x(y)) 와 z∈∂f(x(z)) 에 강단조성을 쓰고 코시–슈바르츠를 쓰면 μ∥x(z)−x(y)∥2≤⟨z−y,x(z)−x(y)⟩≤∥z−y∥∥x(z)−x(y)∥ 이라 ∥x(z)−x(y)∥≤∥z−y∥/μ 입니다. 이것을 위 부등식의 오른쪽에 넣으면 나머지 항이 ∥z−y∥2/μ 이하가 되므로 f∗ 는 y 에서 미분 가능하고 ∇f∗(y)=x(y) 이며, 방금 보인 부등식이 곧 ∇f∗ 의 1/μ-립시츠성입니다.
정리 2.f 가 어디서나 유한한 미분 가능한 볼록함수이고 L-매끄러우면, f∗ 는 ∂f∗ 가 비어 있지 않은 모든 점에서 1/L-강볼록의 부등식을 만족합니다.
증명. y=∇f(x) 라 하면 ⟨z,y⟩−f(z) 의 기울기가 z=x 에서 0이므로 f∗(y)=⟨x,y⟩−f(x) 입니다. 임의의 w 에 대해 정의에서 f∗(w)≥⟨z,w⟩−f(z) 이고, 하강 보조정리로 f(z) 를 위에서 누르면
f∗(w)≥⟨z,w⟩−f(x)−⟨y,z−x⟩−2L∥z−x∥2
가 모든 z 에서 성립합니다. z=x+(w−y)/L 을 넣고 정리하면 오른쪽이 ⟨x,w⟩−f(x)+2L1∥w−y∥2 이고, f∗(y) 의 표현을 쓰면
f∗(w)≥f∗(y)+⟨x,w−y⟩+2L1∥w−y∥2
입니다. 첫 부등식에서 x∈∂f∗(y) 도 함께 나오고, ∂f∗(y) 가 비어 있지 않은 점은 정확히 어떤 x 에 대해 y=∇f(x) 인 점입니다. 따라서 그런 모든 y 와 그 하위기울기에서 강볼록의 부등식이 성립합니다.
다음 글에서 증명할 이중 켤레 정리 f∗∗=f 를 더하면 두 정리는 역방향까지 닫힙니다. 닫힌 진볼록 함수에 대해 f 가 μ-강볼록인 것과 f∗ 가 1/μ-매끄러운 것이 같은 성질입니다. 바닥이 평평하지 않다는 성질과 곡면이 갑자기 휘지 않는다는 성질이 켤레를 사이에 두고 같은 말이 됩니다.
공강제성과 PL 부등식
쌍대가 바로 값을 치르는 자리가 있습니다. L-매끄러운 볼록함수에서 yi=∇f(xi) 라 하면 정리 2의 증명에서 xi∈∂f∗(yi) 였고, f∗ 의 1/L-강볼록성에서 나오는 강단조성을 쓰면 곧바로
⟨∇f(x1)−∇f(x2),x1−x2⟩≥L1∥∇f(x1)−∇f(x2)∥2
입니다. 이것을 공강제성(co-coercivity)이라 부릅니다. 립시츠 조건은 기울기의 차이를 위에서만 누르는데, 볼록성이 더해지면 기울기의 차이가 점의 차이와 같은 방향을 향하도록 강제된다는 말입니다. 이것으로 학습률 η≤2/L 의 경사하강 한 걸음이 비확장 사상이라는 것이 바로 나옵니다. Δx=x1−x2, Δg 를 기울기의 차이라 하면 ∥Δx−ηΔg∥2≤∥Δx∥2−η(2/L−η)∥Δg∥2 이고, 경사하강법 글의 2/L 상한이 함수값이 아니라 점 사이의 거리에서도 같은 자리에 있다는 것이 보입니다.
강볼록성과 함께 쓰면 부등식이 둘 더 나옵니다. 첫째는 함수값의 차이를 기울기로 양쪽에서 누르는
2L1∥∇f(x)∥2≤f(x)−f(x∗)≤2μ1∥∇f(x)∥2
입니다. 왼쪽은 하강 보조정리에서 f(x∗)≤f(x−∇f(x)/L)≤f(x)−∥∇f(x)∥2/(2L) 로, 오른쪽은 강볼록 부등식에서 f(x)−f(x∗)≤⟨∇f(x),x−x∗⟩−2μ∥x−x∗∥2 를 ∥x−x∗∥ 에 대한 이차식으로 보고 최대값을 취하면 나옵니다. 오른쪽만 떼어 낸 것이 PL 부등식이고, 볼록이 아니어도 이것 하나만 있으면 경사하강이 선형 수렴한다는 것이 고급 14번의 출발점이 됩니다. 둘째는 공강제성을 f−2μ∥x∥2, 곧 (L−μ)-매끄러운 볼록함수에 적용해 정리한
⟨Δg,Δx⟩≥μ+LμL∥Δx∥2+μ+L1∥Δg∥2
입니다. 학습률을 η=2/(μ+L) 로 두고 x2=x∗ 를 넣으면 ∥Δg∥2 의 계수가 정확히 0이 되어
∥xk+1−x∗∥≤κ+1κ−1∥xk−x∗∥
이 남습니다. 예의 μ=1, L=4 에서는 η=0.4, 수축률 3/5=0.6 입니다. 조건수가 수렴 속도를 정한다는 익숙한 이야기가 매끄러움과 강볼록성의 쌍대에서 한 줄로 나온 것입니다.
다시 L1과 ReLU로
코드로 확인하기
첫머리의 장면을 작게 재현합니다. 계수 여덟 개 중 셋만 0이 아닌 라쏘 문제를 하위기울기법과 좌표 하강으로 풀고, 좌표 하강의 해가 최적성 조건을 만족하는지 직접 확인합니다. 좌표 하강은 한 좌표씩 위의 1차원 해 sign(a)max(∣a∣−λ,0) 을 되풀이하는 방법입니다. 이어서 ReLU(x)−ReLU(−x) 의 자동미분과, 이차함수 예의 켤레와 수축률을 확인합니다.
import numpy as npnp.set_printoptions(suppress=True, linewidth=100)rng = np.random.default_rng(0)n, p, lam = 100, 8, 0.1X = rng.standard_normal((n, p))beta = np.array([2.0, -1.5, 0, 0, 1.0, 0, 0, 0])y = X @ beta + 0.5 * rng.standard_normal(n)def grad_data(w): # 매끄러운 부분 (1/2n)||Xw-y||^2 의 기울기 return X.T @ (X @ w - y) / n# 1) 하위기울기법: |w| 자리에 sign(w)를 넣는다 (sign(0) = 0)w = np.zeros(p)for k in range(1, 5001): w -= 0.5 / np.sqrt(k) * (grad_data(w) + lam * np.sign(w))print("하위기울기법 :", np.round(w, 4))print("정확히 0인 성분:", int(np.sum(w == 0)))# 2) 좌표 하강: 한 좌표씩 0 ∈ ∂f 를 닫힌 꼴로 푼다v = np.zeros(p)col = (X ** 2).sum(0) / nfor _ in range(200): for j in range(p): r = y - X @ v + X[:, j] * v[j] a = X[:, j] @ r / n / col[j] v[j] = np.sign(a) * max(abs(a) - lam / col[j], 0.0)print("좌표 하강 :", np.round(v, 4) + 0.0)# 3) 최적성 조건 점검: 0 ∈ ∇g(v) + lam * ∂|v|g = grad_data(v)nz = v != 0print("0이 아닌 좌표의 g + lam*sign:", np.abs(g[nz] + lam * np.sign(v[nz])).max().round(10))print("0인 좌표의 |g| 최댓값 (<= lam?):", np.abs(g[~nz]).max().round(4))# 4) relu(x) - relu(-x) = x 인데 자동미분은 0에서 무엇을 내나relu_grad = lambda x, s: np.where(x > 0, 1.0, np.where(x < 0, 0.0, s))for s in (0.0, 0.5, 1.0): print(f"relu'(0)={s}: d/dx[relu(x)-relu(-x)] at 0 ->", relu_grad(0.0, s) + relu_grad(-0.0, s))# 5) 강볼록·매끄러움 쌍대: f = (4 x1^2 + x2^2)/2, mu=1, L=4A = np.diag([4.0, 1.0])H_conj = np.linalg.inv(A)print("f* 의 헤세 고윳값:", np.linalg.eigvalsh(H_conj))x = np.array([1.0, 1.0])eta = 2 / (1 + 4)for k in range(5): x = x - eta * A @ x print(k + 1, np.round(np.linalg.norm(x), 4))
다섯 덩어리가 각각 한 주장을 확인합니다. 하위기울기법은 5,000걸음 뒤에도 0이어야 할 다섯 좌표가 0.0001에서 0.0011 사이를 떠돌고 정확한 0은 하나도 없습니다. 좌표 하강은 같은 세 좌표를 남기고 나머지 다섯을 정확히 0으로 둡니다. 그 해에서 0이 아닌 좌표의 조건 rj+λsign(wj)=0 은 기계 정밀도로 성립하고, 0인 좌표에서는 데이터가 당기는 힘이 최대 0.0942로 λ=0.1 을 넘지 않습니다. 최적성 조건이 계산 가능한 검사가 된 것입니다. 자동미분은 ReLU′(0) 의 선택에 따라 0, 1, 2를 내고 1/2일 때만 참값과 맞습니다. 이차함수의 켤레는 헤세 고윳값이 1/4 과 1이고, η=0.4 의 경사하강은 거리를 걸음마다 정확히 0.6배로 줄입니다(1.4142→0.8485→0.5091).
리뷰어의 질문에 답할 수 있습니다. torch.abs의 0에서의 기울기 0과 ReLU의 0에서의 0은 둘 다 하위미분의 정당한 원소이고, 한 점만 보면 무엇을 골라도 됩니다. 계수가 0 근처를 떠도는 것은 그 선택 탓이 아니라 하위기울기법이라는 방법 탓입니다. 하위미분은 0에서 구간인데 하위기울기법은 그 구간의 한 점을 기울기처럼 다뤄 0을 넘나들며 진동하고, 걸음을 줄여 가야 겨우 수렴하며 그 속도도 O(1/k) 에 머뭅니다. 정확한 0을 원하면 최적성 조건의 집합 전체를 쓰는 갱신, 곧 좌표 하강이나 다음다음 글의 근접 경사법을 쓰거나, 학습이 끝난 뒤 조건 ∣rj∣≤λ 로 0인 좌표를 판정해야 합니다. 그리고 ReLU의 선택이 바꾸는 것은 측도 0 집합에서의 값뿐이라 이론적 수렴은 그대로지만, 낮은 정밀도로 학습한다면 그 측도 0 집합이 실제로는 비어 있지 않다는 것을 기억해 둘 일입니다.
연습
λ=0.8 일 때 f(w)=21(w+2.5)2+λ∣w∣ 의 최소점을 최적성 조건으로 구하고, 그 점에서 0∈∂f 가 성립하는지 확인하세요.
a=−2.5 이고 ∣a∣>λ 라 w∗=sign(a)(∣a∣−λ)=−1.7 입니다. w∗<0 이라 하위미분이 한 점이고 (−1.7+2.5)+0.8×(−1)=0 입니다.
f(x)=max(0,x,2x) 의 0에서의 하위미분을 구하고, 0이 최소점인지 판정하세요.
0에서 세 조각이 모두 같은 값 0을 가지므로 하위미분은 세 기울기 0, 1, 2의 볼록 껍질 [0,2] 입니다. 0이 그 안에 있으므로 0은 최소점이고 최소값은 0입니다.
f(x)=21(6x12+2x22) 의 μ, L 과 켤레 f∗ 의 강볼록 상수·매끄러움 상수를 구하고, η=2/(μ+L) 의 경사하강이 거리를 한 걸음에 몇 배로 줄이는지 구하세요.
헤세가 diag(6,2) 라 μ=2, L=6 입니다. f∗(y)=21(y12/6+y22/2) 라 강볼록 상수 1/6=1/L, 매끄러움 상수 1/2=1/μ 입니다. η=1/4 이고 좌표마다 1−6/4=−0.5, 1−2/4=0.5 배가 되므로 거리는 0.5배이며, (κ−1)/(κ+1)=2/4 와 맞습니다.
3번의 함수에서 x=(1,1) 일 때 f(x)−f(x∗) 와 기울기 노름 제곱으로 만든 두 경계를 계산해 부등식이 성립하는지 확인하세요.
f(1,1)=(6+2)/2=4, f(x∗)=0 이고 ∇f=(6,2) 라 ∥∇f∥2=40 입니다. 경계는 40/12=3.33 과 40/4=10 이라 3.33≤4≤10 이 성립합니다.
h(x)=ReLU(x)+ReLU(−x) 를 자동미분하면 0에서 ReLU′(0)=s 에 따라 무엇이 나오나요. 그 값은 ∂h(0) 에 들어 있나요.
둘째 항에서 연쇄법칙으로 −1 이 곱해져 s−s=0 이 나옵니다. h(x)=∣x∣ 라 ∂h(0)=[−1,1] 이고 0은 그 안에 있으므로, 이 프로그램에서는 어느 s 를 골라도 정당한 하위기울기가 나옵니다.
구간 [1,3] 위에서 x2 를 최소화하는 문제를 x2+ι[1,3](x) 로 쓰고, 최적성 조건으로 최소점을 확인하세요.
x=1 에서 법선뿔은 (−∞,0] 이라 하위미분이 2+(−∞,0]=(−∞,2] 이고 0을 품으므로 x∗=1 입니다. 내부의 점에서는 하위미분이 {2x} 이고 2x>0 이라 조건이 성립하지 않습니다.
이 글은 미분이 없는 점에서 기울기를 대신하는 하위미분을 세우고, 최적성 조건을 0∈∂f 한 줄로 만들고, L1이 정확한 0을 만드는 것과 하위기울기법이 그러지 못하는 것을 같은 조건에서 읽었습니다. ReLU의 0에서의 값은 한 점에서는 정당하고 합성에서는 틀릴 수 있지만 측도 0에서만 틀린다는 세 겹의 서술로 정리했고, 강볼록성과 매끄러움이 켤레를 사이에 두고 자리를 바꾼다는 것을 증명해 공강제성과 조건수의 수렴률을 거기서 꺼냈습니다. 다음 글 고급 12번 · 「르장드르–펜첼 변환과 쌍대성: 문제를 뒤집어 푸는 법」은 이 글에서 증명에 필요한 만큼만 쓴 켤레함수를 정면으로 다룹니다. 이중 켤레 정리로 이 글의 두 정리를 역방향까지 닫고, 라그랑주 쌍대와 슬레이터 조건으로 KKT를 쌍대성의 특수한 경우로 다시 세웁니다.
갱신 −ηP⁻¹∇를 노름의 최급강하로 읽고 헤세·가우스–뉴턴·피셔·경험적 피셔의 관계를 정리한 뒤, 준뉴턴과 3차 정규화, K-FAC의 크로네커 인수분해와 그 독립 가정, Shampoo의 −1/4 지수, Muon의 스펙트럴 노름 유도를 차례로 세워 이들이 어디서 일치하는지 보입니다.