107강에서 볼록성이 국소를 전역으로 승격 시킨다고 했습니다. 임계점 하나면 답이고, 어디서 출발하든 같은 곳에 도착합니다.
그런데 "언제 도착하는지"는 말하지 않았습니다.
볼록 ⟹ 도착한다 볼록 ⟹ 도착한다
이것만으로는 알고리즘을 설계할 수 없습니다. 걸음을 얼마나 크게 디딜지, 몇 번 만에 원하는 정확도에 닿을지를 알려면 정성적 성질을 정량화 해야 합니다.
이 강의가 상수 두 개를 정합니다.
μ I ⪯ H f ( x ) ⪯ L I μ I ⪯ H f ( x ) ⪯ L I
**아래에서 받치는 μ μ L L
f ( a ) + ∇ f ⋅ h + μ 2 ∥ h ∥ 2 ≤ f ( a + h ) ≤ f ( a ) + ∇ f ⋅ h + L 2 ∥ h ∥ 2 f ( a ) + ∇ f ⋅ h + 2 μ ∥ h ∥ 2 ≤ f ( a + h ) ≤ f ( a ) + ∇ f ⋅ h + 2 L ∥ h ∥ 2
함수가 두 포물면 사이에 갇힙니다. 아래 포물면이 "얼마나 빨리 내려갈 수 있는지"를 보장하고, 위 포물면이 "얼마나 크게 걸어도 되는지"를 정합니다.
그리고 그 비가 이 과목이 93강부터 예고해 온 양입니다.
κ = L μ κ = μ L
강볼록 상수 μ μ L L
두 부등식을 쓰고 그 기하적 뜻을 말할 수 있습니다.
기울기의 립시츠 조건이 L L
한 걸음의 보장된 감소량을 계산할 수 있습니다.
기울기 크기로 최적성 간격을 어림할 수 있습니다.
문제. f ( x , y ) = 1 2 ( x 2 + 100 y 2 ) f ( x , y ) = 2 1 ( x 2 + 1 0 0 y 2 ) u ⊤ H u u ⊤ H u
생각의 실마리. 99강에서 u ⊤ H u u ⊤ H u 가장 덜 휘는 정도와 가장 많이 휘는 정도 가 우리가 찾는 두 상수입니다.
풀이. (1) H = diag ( 1 , 100 ) H = d i a g ( 1 , 1 0 0 ) 1 1 100 1 0 0
μ = λ min = 1 , L = λ max = 100 , κ = 100 μ = λ m i n = 1 , L = λ m a x = 1 0 0 , κ = 1 0 0
(2)와 (3) 검산에서
방향
\mathbf{u}^{\top}H\mathbf
μ ≤ ⋅ ≤ L μ ≤ ⋅ ≤ L
0.00 0 . 0 0 1.000000 1 . 0 0 0 0 0 0 예
0.79 0 . 7 9 50.500000 5 0 . 5 0 0 0 0 0 예
1.57 1 . 5 7 100.000000 1 0 0 . 0 0 0 0 0 0 예
1.20 1 . 2 0 87.000989 8 7 . 0 0 0 9 8 9 예
모든 방향이 [ 1 , 100 ] [ 1 , 1 0 0 ]
이 문제에서 배우는 것: 강볼록과 매끄러움.
μ μ x x H f ( x ) ⪰ μ I H f ( x ) ⪰ μ I f f μ μ
L L x x H f ( x ) ⪯ L I H f ( x ) ⪯ L I f f L L
두 조건이 함수를 위아래로 조입니다.
조건
뜻
보장하는 것
H ⪰ μ I H ⪰ μ I 어디서나 최소한 이만큼 휩니다
진행이 멈추지 않습니다
H ⪯ L I H ⪯ L I 어디서나 이보다 심하게 휘지 않습니다
큰 걸음이 안전합니다
μ μ L L μ ≤ L μ ≤ L H H
κ = L μ ≥ 1 κ = μ L ≥ 1
κ = 1 κ = 1 κ κ κ = 1 κ = 1 1 1
일반 함수에서는 상수가 영역에 의존합니다. 위 예는 이차함수라 헤세가 상수여서 μ μ L L e x e x
바로 확인 1.
확인 1-1. μ μ L L
답. μ I ⪯ H ⪯ L I μ I ⪯ H ⪯ L I
확인 1-2. κ κ
답. L / μ L / μ 1 1
확인 1-3. κ = 1 κ = 1
답. 원입니다.
문제. 같은 함수를 봅니다.μ = 1 μ = 1 200000 2 0 0 0 0 0 μ = 2 μ = 2
생각의 실마리. 107강의 일차 조건은 f ≥ f ≥ 강볼록이면 접평면보다 포물면만큼 더 위에 있을 것 입니다.
풀이. (1) 100강의 테일러 정리에서 H ⪰ μ I H ⪰ μ I
f ( a + h ) ≥ f ( a ) + ∇ f ( a ) ⋅ h + μ 2 ∥ h ∥ 2 f ( a + h ) ≥ f ( a ) + ∇ f ( a ) ⋅ h + 2 μ ∥ h ∥ 2
(2)와 (3) 검산에서
μ μ 위반 횟수
1.0 1 . 0 0 0
2.0 2 . 0 13082 1 3 0 8 2
μ = 1 μ = 1 μ = 2 μ = 2 μ = 1 μ = 1
이 문제에서 배우는 것: 강볼록 부등식.
강볼록의 동치 조건. 다음이 서로 동치입니다.
형태
진술
헤세
H ⪰ μ I H ⪰ μ I
일차
f(\mathbf{x})\ge f(\mathbf{a})+\nabla f(\mathbf{a})\cdot(\mathbf{x}-\mathbf{a})+\frac\mu2\lVert\mathbf{x}-\mathbf{a}\rVert^
기울기
(\nabla f(\mathbf{x})-\nabla f(\mathbf{a}))\cdot(\mathbf{x}-\mathbf{a})\ge\mu\lVert\mathbf{x}-\mathbf{a}\rVert^
정의
f − μ 2 ∥ ⋅ ∥ 2 f − 2 μ ∥ ⋅ ∥ 2
넷째 줄이 가장 깔끔한 정의 입니다. 포물면을 빼고도 여전히 볼록하다는 뜻이며, 미분가능성을 요구하지 않아 가장 넓게 적용됩니다.
둘째 줄이 실용적입니다. 여기서 두 가지가 곧바로 나옵니다.
첫째, 최소가 유일합니다. x ∗ x ∗ ∇ f ( x ∗ ) = 0 ∇ f ( x ∗ ) = 0
f ( x ) ≥ f ( x ∗ ) + μ 2 ∥ x − x ∗ ∥ 2 f ( x ) ≥ f ( x ∗ ) + 2 μ ∥ x − x ∗ ∥ 2
x ≠ x ∗ x = x ∗
둘째, 최소점과의 거리가 잡힙니다. 심화 4에서 다룹니다.
μ μ ( x + y ) 2 ( x + y ) 2 μ = 0 μ = 0 y = − x y = − x
함수
μ μ 최소
1 2 ( x 2 + 100 y 2 ) 2 1 ( x 2 + 1 0 0 y 2 ) 1 1 유일합니다
(x+y)^
0 0 직선 전체입니다
e^
0 0 없습니다
μ > 0 μ > 0
바로 확인 2.
확인 2-1. 강볼록 하한 부등식을 쓰세요.
답. f ( a + h ) ≥ f ( a ) + ∇ f ⋅ h + μ 2 ∥ h ∥ 2 f ( a + h ) ≥ f ( a ) + ∇ f ⋅ h + 2 μ ∥ h ∥ 2
확인 2-2. 가장 일반적인 정의를 쓰세요.
답. f − μ 2 ∥ ⋅ ∥ 2 f − 2 μ ∥ ⋅ ∥ 2
확인 2-3. μ > 0 μ > 0
답. 최소의 존재와 유일성입니다.
문제. 같은 함수를 봅니다.L L L = 100 L = 1 0 0 L = 50 L = 5 0
생각의 실마리. 강볼록이 아래에서 받쳤으니 매끄러움은 위에서 누를 것 입니다. 같은 테일러 정리에 H ⪯ L I H ⪯ L I
풀이. (1)
f ( a + h ) ≤ f ( a ) + ∇ f ( a ) ⋅ h + L 2 ∥ h ∥ 2 f ( a + h ) ≤ f ( a ) + ∇ f ( a ) ⋅ h + 2 L ∥ h ∥ 2
(2) 검산에서
L L 위반 횟수
100.0 1 0 0 . 0 0 0
50.0 5 0 . 0 100547 1 0 0 5 4 7
L = 100 L = 1 0 0
(3) 검산에서 기울기 차이의 비가
∥ ∇ f ( x ) − ∇ f ( y ) ∥ ∥ x − y ∥ ∈ [ 1.000001 , 100.000000 ] ∥ x − y ∥ ∥ ∇ f ( x ) − ∇ f ( y ) ∥ ∈ [ 1 . 0 0 0 0 0 1 , 1 0 0 . 0 0 0 0 0 0 ]
**최대가 정확히 L = 100 L = 1 0 0 μ = 1 μ = 1
이 문제에서 배우는 것: 매끄러움은 기울기의 립시츠 조건입니다.
L L
형태
진술
헤세
H ⪯ L I H ⪯ L I
상한
f(\mathbf{x})\le f(\mathbf{a})+\nabla f(\mathbf{a})\cdot(\mathbf{x}-\mathbf{a})+\frac L2\lVert\mathbf{x}-\mathbf{a}\rVert^
립시츠
∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥ ∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥
정의
L 2 ∥ ⋅ ∥ 2 − f 2 L ∥ ⋅ ∥ 2 − f
셋째 줄이 이름의 근거 입니다. "매끄럽다"는 말이 미분가능하다는 뜻이 아니라 기울기가 급격히 변하지 않는다 는 뜻입니다.
매끄러움은 기울기의 변화율에 대한 제한입니다 매끄러움은 기울기의 변화율에 대한 제한입니다
왜 립시츠 조건과 헤세 조건이 같은지 는 98강에서 봤습니다. 헤세가 ∇ f ∇ f
∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ sup ∥ H ∥ 2 ⋅ ∥ x − y ∥ ∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ sup ∥ H ∥ 2 ⋅ ∥ x − y ∥
이고 90강에서 ∥ H ∥ 2 = λ max ∥ H ∥ 2 = λ m a x
두 부등식을 나란히 놓으면 그림이 보입니다.
f ( a ) + ∇ f ⋅ h + μ 2 ∥ h ∥ 2 ⏟ 아래 포물면 ≤ f ( a + h ) ≤ f ( a ) + ∇ f ⋅ h + L 2 ∥ h ∥ 2 ⏟ 위 포물면 아래 포물면 f ( a ) + ∇ f ⋅ h + 2 μ ∥ h ∥ 2 ≤ f ( a + h ) ≤ 위 포물면 f ( a ) + ∇ f ⋅ h + 2 L ∥ h ∥ 2
함수가 두 포물면 사이에 갇힙니다. 두 포물면은 h = 0 h = 0
포물면
역할
아래
최소가 어디쯤인지 보장합니다
위
한 걸음이 얼마나 안전한지 보장합니다
문제 4에서 위 포물면을 쓰고 문제 5에서 아래 포물면을 씁니다.
바로 확인 3.
확인 3-1. L L
답. f ( a + h ) ≤ f ( a ) + ∇ f ⋅ h + L 2 ∥ h ∥ 2 f ( a + h ) ≤ f ( a ) + ∇ f ⋅ h + 2 L ∥ h ∥ 2
확인 3-2. 매끄러움의 립시츠 형태를 쓰세요.
답. ∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥ ∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥
확인 3-3. "매끄럽다"가 뜻하는 바를 쓰세요.
답. 기울기가 급격히 변하지 않는다는 뜻입니다.
문제. 위 포물면을 씁니다.x − η ∇ f ( x ) x − η ∇ f ( x ) η = 1 / L η = 1 / L η η
생각의 실마리. 상한 부등식은 h h h = − η ∇ f h = − η ∇ f
풀이. (1) g = ∇ f ( x ) g = ∇ f ( x ) h = − η g h = − η g
f ( x − η g ) ≤ f ( x ) − η ∥ g ∥ 2 + L η 2 2 ∥ g ∥ 2 = f ( x ) − η ( 1 − L η 2 ) ∥ g ∥ 2 f ( x − η g ) ≤ f ( x ) − η ∥ g ∥ 2 + 2 L η 2 ∥ g ∥ 2 = f ( x ) − η ( 1 − 2 L η ) ∥ g ∥ 2
(2) η = 1 / L η = 1 / L 1 / 2 1 / 2
f ( x − 1 L g ) ≤ f ( x ) − 1 2 L ∥ g ∥ 2 f ( x − L 1 g ) ≤ f ( x ) − 2 L 1 ∥ g ∥ 2
검산에서 x = ( 3 , 0.5 ) x = ( 3 , 0 . 5 ) f = 17.000000 f = 1 7 . 0 0 0 0 0 0 ∥ g ∥ 2 = 2509.000000 ∥ g ∥ 2 = 2 5 0 9 . 0 0 0 0 0 0 12.545000 1 2 . 5 4 5 0 0 0 12.589550 1 2 . 5 8 9 5 5 0 보장선을 넘습니다.
(3) 검산에서
η η 새 f f
감소량
보장선
0.005 0 . 0 0 5 7.580112 7 . 5 8 0 1 1 2 9.419888 9 . 4 1 9 8 8 8 12.545000 1 2 . 5 4 5 0 0 0
0.010 0 . 0 1 0 4.410450 4 . 4 1 0 4 5 0 12.589550 1 2 . 5 8 9 5 5 0 12.545000 1 2 . 5 4 5 0 0 0
0.019 0 . 0 1 9 14.455624 1 4 . 4 5 5 6 2 4 2.544376 2 . 5 4 4 3 7 6 12.545000 1 2 . 5 4 5 0 0 0
0.021 0 . 0 2 1 19.437985 1 9 . 4 3 7 9 8 5 − 2.437985 − 2 . 4 3 7 9 8 5 12.545000 1 2 . 5 4 5 0 0 0
마지막 줄에서 감소량이 음수 입니다. 손실이 오히려 늘었습니다.
이 문제에서 배우는 것: 하강 보조정리.
하강 보조정리. f f L L 0 < η ≤ 1 / L 0 < η ≤ 1 / L
f ( x − η ∇ f ( x ) ) ≤ f ( x ) − η 2 ∥ ∇ f ( x ) ∥ 2 f ( x − η ∇ f ( x ) ) ≤ f ( x ) − 2 η ∥ ∇ f ( x ) ∥ 2
이며 η = 1 / L η = 1 / L 1 2 L ∥ ∇ f ∥ 2 2 L 1 ∥ ∇ f ∥ 2
이 한 줄이 경사하강법이 작동하는 이유 전부 입니다. 기울기가 0 0
매끄러움이 "한 걸음이 안전하다"를 보장합니다 매끄러움이 " 한 걸음이 안전하다 " 를 보장합니다
η η 1 − L η / 2 1 − L η / 2
0 < η < 2 L = 0.02 0 < η < L 2 = 0 . 0 2
99강 심화 5에서 유도한 것과 정확히 같습니다. 그때는 선형 점화식의 수렴 조건으로 얻었고 여기서는 매끄러움 부등식으로 얻었습니다. 검산에서 η = 0.019 η = 0 . 0 1 9 η = 0.021 η = 0 . 0 2 1
최적 η η 1 / L 1 / L 도 보입니다. 감소량 η ( 1 − L η / 2 ) ∥ g ∥ 2 η ( 1 − L η / 2 ) ∥ g ∥ 2 η η 0 0
1 − L η = 0 ⟹ η = 1 L 1 − L η = 0 ⟹ η = L 1
상한 부등식만 놓고 보면 1 / L 1 / L 입니다. 검산에서 η = 0.01 = 1 / L η = 0 . 0 1 = 1 / L
주의할 점이 있습니다. 이것은 보장된 감소이지 실제 최적은 아닙니다. 특정 방향에서는 더 큰 걸음이 나을 수 있으나, 모든 경우에 안전한 값이 1 / L 1 / L
바로 확인 4.
확인 4-1. 하강 보조정리를 쓰세요.
답. η ≤ 1 / L η ≤ 1 / L f f η 2 ∥ ∇ f ∥ 2 2 η ∥ ∇ f ∥ 2
확인 4-2. 감소가 보장되는 η η
답. 0 < η < 2 / L 0 < η < 2 / L
확인 4-3. 상한 부등식에서 최적 η η
답. 1 / L 1 / L
문제. 아래 포물면을 씁니다.∥ ∇ f ∥ 2 ∥ ∇ f ∥ 2 f − f ∗ f − f ∗
생각의 실마리. 하한 부등식을 h h f ∗ f ∗
풀이. (1) 하한 부등식에서
f ∗ = x f ( x ) ≥ h [ f ( a ) + ∇ f ⋅ h + μ 2 ∥ h ∥ 2 ] f ∗ = x min f ( x ) ≥ h min [ f ( a ) + ∇ f ⋅ h + 2 μ ∥ h ∥ 2 ]
오른쪽 이차식의 최소는 h = − ∇ f / μ h = − ∇ f / μ
f ( a ) − 1 2 μ ∥ ∇ f ( a ) ∥ 2 f ( a ) − 2 μ 1 ∥ ∇ f ( a ) ∥ 2
이므로 정리하면
∥ ∇ f ( a ) ∥ 2 ≥ 2 μ ( f ( a ) − f ∗ ) ∥ ∇ f ( a ) ∥ 2 ≥ 2 μ ( f ( a ) − f ∗ )
(2) 검산에서 f ∗ = 0 f ∗ = 0
점
\lVert\nabla f\rVert^
2 μ ( f − f ∗ ) 2 μ ( f − f ∗ ) 비
( 3 , 0.5 ) ( 3 , 0 . 5 ) 2509.0000 2 5 0 9 . 0 0 0 0 34.0000 3 4 . 0 0 0 0 73.79 7 3 . 7 9
( 0.1 , 1 ) ( 0 . 1 , 1 ) 10000.0100 1 0 0 0 0 . 0 1 0 0 100.0100 1 0 0 . 0 1 0 0 99.99 9 9 . 9 9
( 5 , 0 ) ( 5 , 0 ) 25.0000 2 5 . 0 0 0 0 25.0000 2 5 . 0 0 0 0 1.00 1 . 0 0
언제나 비가 1 1 입니다.
(3) 셋째 줄에서 정확히 1 1 ( 5 , 0 ) ( 5 , 0 ) μ μ
이 문제에서 배우는 것: 폴랴크-워야시에비치 부등식.
PL 부등식. f f μ μ
1 2 ∥ ∇ f ( x ) ∥ 2 ≥ μ ( f ( x ) − f ∗ ) 2 1 ∥ ∇ f ( x ) ∥ 2 ≥ μ ( f ( x ) − f ∗ )
입니다.
이 부등식이 수렴 증명의 핵심 도구 입니다. 문제 4의 하강 보조정리와 합치면 곧바로 결과가 나옵니다.
f ( x k + 1 ) − f ∗ ≤ f ( x k ) − f ∗ − 1 2 L ∥ ∇ f ∥ 2 ≤ ( 1 − μ L ) ( f ( x k ) − f ∗ ) f ( x k + 1 ) − f ∗ ≤ f ( x k ) − f ∗ − 2 L 1 ∥ ∇ f ∥ 2 ≤ ( 1 − L μ ) ( f ( x k ) − f ∗ )
한 걸음마다 최적성 간격이 ( 1 − 1 / κ ) ( 1 − 1 / κ ) 110강에서 이 유도를 정식으로 합니다.
매끄러움이 걸음을 보장하고 강볼록이 그 걸음을 진전으로 바꿉니다 매끄러움이 걸음을 보장하고 강볼록이 그 걸음을 진전으로 바꿉니다
뒤집어 쓰면 종료 조건이 됩니다.
f ( x ) − f ∗ ≤ 1 2 μ ∥ ∇ f ( x ) ∥ 2 f ( x ) − f ∗ ≤ 2 μ 1 ∥ ∇ f ( x ) ∥ 2
검산에서
점
실제 f-f^
상한
( 3 , 0.5 ) ( 3 , 0 . 5 ) 17.000000 1 7 . 0 0 0 0 0 0 1254.500000 1 2 5 4 . 5 0 0 0 0 0
( 0.1 , 1 ) ( 0 . 1 , 1 ) 50.005000 5 0 . 0 0 5 0 0 0 5000.005000 5 0 0 0 . 0 0 5 0 0 0
상한이 헐겁습니다. μ = 1 μ = 1
기울기가 작다 ≠ 최소에 가깝다 기울기가 작다 = 최소에 가깝다
μ μ
바로 확인 5.
확인 5-1. PL 부등식을 쓰세요.
답. 1 2 ∥ ∇ f ∥ 2 ≥ μ ( f − f ∗ ) 2 1 ∥ ∇ f ∥ 2 ≥ μ ( f − f ∗ )
확인 5-2. 언제 등호가 성립합니까?
답. μ μ
확인 5-3. 최적성 간격의 상한을 쓰세요.
답. ∥ ∇ f ∥ 2 / ( 2 μ ) ∥ ∇ f ∥ 2 / ( 2 μ )
상수
정의
역할
μ μ H ⪰ μ I H ⪰ μ I 아래에서 받칩니다
L L H ⪯ L I H ⪯ L I 위에서 누릅니다
κ = L / μ κ = L / μ 조건수
수렴 속도를 정합니다
부등식
형태
강볼록 하한
f\ge f(\mathbf{a})+\nabla f\cdot\mathbf{h}+\frac\mu2\lVert\mathbf{h}\rVert^
매끄러움 상한
f\le f(\mathbf{a})+\nabla f\cdot\mathbf{h}+\frac L2\lVert\mathbf{h}\rVert^
기울기 립시츠
∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥ ∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥
하강 보조정리
η ≤ 1 / L η ≤ 1 / L η 2 ∥ ∇ f ∥ 2 2 η ∥ ∇ f ∥ 2
PL 부등식
1 2 ∥ ∇ f ∥ 2 ≥ μ ( f − f ∗ ) 2 1 ∥ ∇ f ∥ 2 ≥ μ ( f − f ∗ )
결과
근거
감소 보장 η < 2 / L η < 2 / L
매끄러움
최적 η = 1 / L η = 1 / L
매끄러움
최소 유일
강볼록
수렴률 1 − 1 / κ 1 − 1 / κ
둘 다
자주 하는 실수
바로잡기
μ μ L L 전 영역의 극값입니다
매끄러움을 미분가능으로 읽습니다
기울기의 립시츠 조건입니다
기울기가 작으면 다 왔다고 봅니다
μ μ
η η 2 / L 2 / L 발산합니다
문제 6. f = 1 2 x ⊤ A x f = 2 1 x ⊤ A x μ μ L L
답. A A
문제 7. f = 1 2 ∥ x ∥ 2 f = 2 1 ∥ x ∥ 2 κ κ
답. H = I H = I μ = L = 1 μ = L = 1 κ = 1 κ = 1
문제 8. ∥ A x − b ∥ 2 ∥ A x − b ∥ 2 L L
답. 헤세가 2 A ⊤ A 2 A ⊤ A L = 2 σ max 2 L = 2 σ m a x 2
문제 9. 문제 8의 μ μ 0 0
답. 2 σ min 2 2 σ m i n 2 A A 0 0
문제 10. κ κ
답. 1 1
문제 11. 안전한 학습률의 범위를 L L
답. 0 < η < 2 / L 0 < η < 2 / L
문제 12. L = 50 L = 5 0
답. 1 / 50 = 0.02 1 / 5 0 = 0 . 0 2
문제 13. 하강 보조정리에서 η = 1 / L η = 1 / L
답. 1 2 L ∥ ∇ f ∥ 2 2 L 1 ∥ ∇ f ∥ 2
문제 14. PL 부등식을 쓰고 등호 조건을 쓰세요.
답. 1 2 ∥ ∇ f ∥ 2 ≥ μ ( f − f ∗ ) 2 1 ∥ ∇ f ∥ 2 ≥ μ ( f − f ∗ ) μ μ
문제 15. μ = 0 μ = 0
답. ( x + y ) 2 ( x + y ) 2 y = − x y = − x
문제 16. 강볼록의 가장 일반적인 정의를 쓰세요.
답. f − μ 2 ∥ ⋅ ∥ 2 f − 2 μ ∥ ⋅ ∥ 2
문제 17. μ > 0 μ > 0
답. 정확히 하나입니다.
문제 18. ∥ ∇ f ∥ = 1 0 − 3 ∥ ∇ f ∥ = 1 0 − 3 μ = 1 0 − 4 μ = 1 0 − 4
답. ( 1 0 − 3 ) 2 / ( 2 × 1 0 − 4 ) = 5 × 1 0 − 3 ( 1 0 − 3 ) 2 / ( 2 × 1 0 − 4 ) = 5 × 1 0 − 3
심화 1. 두 부등식을 테일러 정리에서 유도하세요.
100강의 라그랑주 나머지 형태를 씁니다. 선분 위의 어떤 c c
f ( a + h ) = f ( a ) + ∇ f ( a ) ⋅ h + 1 2 h ⊤ H ( c ) h f ( a + h ) = f ( a ) + ∇ f ( a ) ⋅ h + 2 1 h ⊤ H ( c ) h
여기에 99강의 레일리 몫 부등식을 적용 합니다. H ( c ) ⪰ μ I H ( c ) ⪰ μ I
h ⊤ H ( c ) h ≥ μ ∥ h ∥ 2 h ⊤ H ( c ) h ≥ μ ∥ h ∥ 2
이고 H ( c ) ⪯ L I H ( c ) ⪯ L I
h ⊤ H ( c ) h ≤ L ∥ h ∥ 2 h ⊤ H ( c ) h ≤ L ∥ h ∥ 2
두 부등식을 테일러 식에 넣으면 곧바로 나옵니다. ■ ■
증명이 세 줄인 이유 는 준비가 끝나 있었기 때문입니다.
재료
어디서
테일러 정리
100강
레일리 몫
99강, 86강
조건 μ I ⪯ H ⪯ L I μ I ⪯ H ⪯ L I
이 강의
"모든 점에서"가 필요한 이유 도 증명에서 드러납니다. c c 선분 위 모든 점에서 조건이 성립 해야 합니다. 한 점에서만 성립하면 쓸 수 없습니다.
미분가능하지 않아도 성립합니다. 문제 2와 문제 3의 넷째 줄 정의를 쓰면 C 2 C 2
f − μ 2 ∥ ⋅ ∥ 2 이 볼록 ⟺ μ -강볼록 f − 2 μ ∥ ⋅ ∥ 2 이 볼록 ⟺ μ - 강볼록
∣ x ∣ + x 2 ∣ x ∣ + x 2 μ = 2 μ = 2
심화 2. 하강 보조정리에서 수렴 정리를 유도하세요.
문제 4와 문제 5를 합칩니다. 110강의 결과를 미리 세워 봅니다.
η = 1 / L η = 1 / L
f ( x k + 1 ) ≤ f ( x k ) − 1 2 L ∥ ∇ f ( x k ) ∥ 2 f ( x k + 1 ) ≤ f ( x k ) − 2 L 1 ∥ ∇ f ( x k ) ∥ 2
양변에서 f ∗ f ∗ ∥ ∇ f ∥ 2 ≥ 2 μ ( f − f ∗ ) ∥ ∇ f ∥ 2 ≥ 2 μ ( f − f ∗ )
f ( x k + 1 ) − f ∗ ≤ ( f ( x k ) − f ∗ ) − 2 μ 2 L ( f ( x k ) − f ∗ ) = ( 1 − 1 κ ) ( f ( x k ) − f ∗ ) f ( x k + 1 ) − f ∗ ≤ ( f ( x k ) − f ∗ ) − 2 L 2 μ ( f ( x k ) − f ∗ ) = ( 1 − κ 1 ) ( f ( x k ) − f ∗ )
반복하면 지수적 감소 입니다.
f ( x k ) − f ∗ ≤ ( 1 − 1 κ ) k ( f ( x 0 ) − f ∗ ) f ( x k ) − f ∗ ≤ ( 1 − κ 1 ) k ( f ( x 0 ) − f ∗ )
정확도 ε ε 를 구합니다. ( 1 − 1 / κ ) k ≤ ε ( 1 − 1 / κ ) k ≤ ε
k ≥ log ( 1 / ε ) − log ( 1 − 1 / κ ) ≈ κ log 1 ε k ≥ − log ( 1 − 1 / κ ) log ( 1 / ε ) ≈ κ log ε 1
걸음 수가 조건수에 비례합니다.
κ κ ε = 1 0 − 6 ε = 1 0 − 6
1 1 14 1 4
10 1 0 138 1 3 8
100 1 0 0 1382 1 3 8 2
10^
138155 1 3 8 1 5 5
조건수가 백 배면 걸음도 백 배 입니다. 93강 심화 5에서 예고한 대로이며, 111강과 112강이 이 의존성을 줄이려는 시도입니다.
방법
걸음 수의 의존성
경사하강법
κ κ
모멘텀(네스테로프)
κ κ
뉴턴법
조건수와 무관(국소적으로)
둘째 줄이 놀랍습니다. 모멘텀 하나로 κ κ κ κ κ = 1 0 4 κ = 1 0 4 138155 1 3 8 1 5 5 1382 1 3 8 2
심화 3. μ μ L L
이론은 두 상수를 알고 있다고 가정합니다. 실무에서는 모릅니다.
L L
방법
내용
멱반복
H v H v λ max λ m a x
학습률 탐색
발산하는 η η 2 / η 2 / η
역추적 직선탐색
매 걸음 조건을 확인하며 줄입니다
이론적 상한
구조에서 계산합니다
셋째 줄이 가장 실용적 입니다. 하강 보조정리의 조건
f ( x − η g ) ≤ f ( x ) − η 2 ∥ g ∥ 2 f ( x − η g ) ≤ f ( x ) − 2 η ∥ g ∥ 2
을 매 걸음 확인하고, 어기면 η η L L
넷째 줄의 예 를 들면, 로지스틱 회귀의 손실은 L ≤ 1 4 ∥ X ∥ 2 2 L ≤ 4 1 ∥ X ∥ 2 2 1 / 4 1 / 4
μ μ λ min λ m i n
정규화가 μ μ 손실에 λ 2 ∥ w ∥ 2 2 λ ∥ w ∥ 2
H → H + λ I ⟹ μ → μ + λ H → H + λ I ⟹ μ → μ + λ
μ ≥ λ μ ≥ λ
κ = L + λ μ + λ κ = μ + λ L + λ
로 줄어듭니다. **λ λ κ → 1 κ → 1
정규화는 일반화만이 아니라 최적화도 돕습니다 정규화는 일반화만이 아니라 최적화도 돕습니다
대가는 편향 입니다. 원래 문제가 아닌 다른 문제를 푸는 셈이며, 210강의 편향-분산 분해에서 이 저울질을 다룹니다.
심화 4. 강볼록에서 최적점과의 거리를 잡으세요.
문제 5에서 함숫값의 간격을 잡았습니다. 위치의 간격 도 잡을 수 있습니다.
x ∗ x ∗ ∇ f ( x ∗ ) = 0 ∇ f ( x ∗ ) = 0 x x x ∗ x ∗
( ∇ f ( x ) − 0 ) ⋅ ( x − x ∗ ) ≥ μ ∥ x − x ∗ ∥ 2 ( ∇ f ( x ) − 0 ) ⋅ ( x − x ∗ ) ≥ μ ∥ x − x ∗ ∥ 2
왼쪽에 코시-슈바르츠를 쓰면
∥ ∇ f ( x ) ∥ ∥ x − x ∗ ∥ ≥ μ ∥ x − x ∗ ∥ 2 ∥ ∇ f ( x ) ∥ ∥ x − x ∗ ∥ ≥ μ ∥ x − x ∗ ∥ 2
이고 양변을 ∥ x − x ∗ ∥ ∥ x − x ∗ ∥
∥ x − x ∗ ∥ ≤ ∥ ∇ f ( x ) ∥ μ ∥ x − x ∗ ∥ ≤ μ ∥ ∇ f ( x ) ∥
101강 심화 5에서 예고한 식 이며 이제 증명됐습니다.
세 가지 간격을 정리합니다.
재는 것
상한
위치 ∥ x − x ∗ ∥ ∥ x − x ∗ ∥
∥ ∇ f ∥ / μ ∥ ∇ f ∥ / μ
함숫값 f-f^
∥ ∇ f ∥ 2 / ( 2 μ ) ∥ ∇ f ∥ 2 / ( 2 μ )
기울기 ∥ ∇ f ∥ ∥ ∇ f ∥
L ∥ x − x ∗ ∥ L ∥ x − x ∗ ∥
셋째 줄은 매끄러움에서 나옵니다. 립시츠 조건에 y = x ∗ y = x ∗
둘째와 셋째를 합치면 함숫값의 하한 도 나옵니다.
f ( x ) − f ∗ ≥ 1 2 L ∥ ∇ f ( x ) ∥ 2 f ( x ) − f ∗ ≥ 2 L 1 ∥ ∇ f ( x ) ∥ 2
PL 부등식의 반대 방향 이며, 결국
1 2 L ∥ ∇ f ∥ 2 ≤ f − f ∗ ≤ 1 2 μ ∥ ∇ f ∥ 2 2 L 1 ∥ ∇ f ∥ 2 ≤ f − f ∗ ≤ 2 μ 1 ∥ ∇ f ∥ 2
함숫값 간격이 기울기 제곱과 κ κ 합니다. κ κ
조건수가 좋은 문제에서만 기울기를 믿을 수 있습니다 조건수가 좋은 문제에서만 기울기를 믿을 수 있습니다
심화 5. 두 상수가 없거나 무한할 때를 논하세요.
이론은 0 < μ ≤ L < ∞ 0 < μ ≤ L < ∞ 실제로는 어느 쪽도 보장되지 않습니다.
L = ∞ L = ∞
f ( x ) = ∣ x ∣ 3 / 2 f ( x ) = ∣ x ∣ 3 / 2
는 볼록이고 미분가능하지만 f ′ ′ = 3 4 ∣ x ∣ − 1 / 2 f ′ ′ = 4 3 ∣ x ∣ − 1 / 2 어떤 고정 η η
대응
내용
역추적 직선탐색
매 걸음 η η
신뢰영역
걸음 크기를 직접 제한합니다
기울기 클리핑
큰 기울기를 잘라냅니다
셋째 줄이 실무의 표준 입니다. 순환신경망처럼 기울기가 폭발하는 구조에서 필수이며, 249강에서 다룹니다.
μ = 0 μ = 0
f ( x k ) − f ∗ ≤ L ∥ x 0 − x ∗ ∥ 2 2 k f ( x k ) − f ∗ ≤ 2 k L ∥ x 0 − x ∗ ∥ 2
O ( 1 / k ) O ( 1 / k )
조건
수렴률
ε ε
μ > 0 μ > 0 L < ∞ L < ∞ (1-1/\kappa)^
O ( κ log 1 ε ) O ( κ log ε 1 )
μ = 0 μ = 0 L < ∞ L < ∞ O ( 1 / k ) O ( 1 / k ) O ( 1 / ε ) O ( 1 / ε )
매끄럽지 않음
O ( 1 / k ) O ( 1 / k ) O ( 1 / ε 2 ) O ( 1 / ε 2 )
셋째 줄이 열등경사법 입니다. ∣ x ∣ ∣ x ∣
신경망은 어느 줄에도 없습니다. 비볼록이라 μ μ L L 최소 근처에서 국소적으로 적용 되기 때문이며, 107강 심화 3에서 말한 그대로입니다.
이론은 보장이 아니라 설계의 언어입니다 이론은 보장이 아니라 설계의 언어입니다
심화 6. 109강으로 어떻게 이어지는지 정리하세요.
이 강의에서 재료를 다 모았습니다.
재료
무엇을 보장하나
하강 보조정리
한 걸음이 값을 줄입니다
PL 부등식
그 감소가 최적성 간격에 비례합니다
η < 2 / L η < 2 / L 걸음이 안전합니다
κ κ 얼마나 걸릴지 정합니다
109강이 알고리즘을 세웁니다.
x k + 1 = x k − η ∇ f ( x k ) x k + 1 = x k − η ∇ f ( x k )
세 강의가 이 한 줄에 모입니다.
강의
이 식에 기여한 것
96
− ∇ f − ∇ f
107
볼록이면 도착점이 전역 최소입니다
108
η η
109강은 이 알고리즘의 실제 거동 을 봅니다. 지그재그가 언제 생기는지, 조건수가 어떻게 나타나는지, 언제 멈출지를 다룹니다.
110강이 수렴을 증명합니다. 심화 2에서 미리 세운 유도를 정식으로 하고, μ = 0 μ = 0
111강과 112강이 개선합니다. 심화 2의 표에서 본 대로 모멘텀이 κ κ κ κ
04단원은 κ 와 싸우는 이야기입니다 04 단원은 κ 와 싸우는 이야기입니다
그 싸움의 무기가 96강 심화 3에서 이미 제시됐습니다. 어떤 노름으로 "가장 가파름"을 재느냐를 바꾸면 유효 조건수가 달라집니다. 111강의 Adam이 대각 척도를, 112강의 뉴턴법이 헤세 척도를 씁니다.
import numpy as np
rng = np.random.default_rng(20260809)
# --- 문제 1: 두 상수 mu 와 L ---------------------------------------------
H = np.array([[1.0, 0.0], [0.0, 100.0]])
w = np.linalg.eigvalsh(H)
mu, L = w[0], w[-1]
print(" f = (x^2 + 100 y^2)/2, H = diag(1, 100)")
print(" mu = lambda_min = %.1f, L = lambda_max = %.1f, kappa = L/mu = %.1f" % (mu, L, L/mu))
f = lambda x: 0.5*(x @ H @ x)
gf = lambda x: H @ x
print(" 방향 u^T H u mu <= . <= L")
for th in [0.0, np.pi/4, np.pi/2, 1.2]:
u = np.array([np.cos(th), np.sin(th)]); q = u @ H @ u
print(" %6.2f rad %10.6f %s" % (th, q, "예" if mu - 1e-12 <= q <= L + 1e-12 else "아니오"))
# f = (x^2 + 100 y^2)/2, H = diag(1, 100)
# mu = lambda_min = 1.0, L = lambda_max = 100.0, kappa = L/mu = 100.0
# 방향 u^T H u mu <= . <= L
# 0.00 rad 1.000000 예
# 0.79 rad 50.500000 예
# 1.57 rad 100.000000 예
# 1.20 rad 87.000989 예
# --- 문제 2: 강볼록 하한 부등식 ------------------------------------------
print(" 강볼록: f(x) >= f(a) + grad.h + (mu/2)|h|^2 위반 횟수 / 200000")
A = rng.uniform(-3, 3, (200000, 2)); B = rng.uniform(-3, 3, (200000, 2))
Hd = np.diag(np.diag(H))
fa = 0.5*np.einsum('ij,jk,ik->i', A, H, A)
fb = 0.5*np.einsum('ij,jk,ik->i', B, H, B)
ga = A @ H
hh = B - A
lin = fa + np.einsum('ij,ij->i', ga, hh)
print(" mu = %.1f 일 때 위반 %d" % (mu, int((fb < lin + 0.5*mu*np.einsum('ij,ij->i', hh, hh) - 1e-9).sum())))
print(" mu = %.1f 로 키우면 위반 %d" % (2.0, int((fb < lin + 0.5*2.0*np.einsum('ij,ij->i', hh, hh) - 1e-9).sum())))
# 강볼록: f(x) >= f(a) + grad.h + (mu/2)|h|^2 위반 횟수 / 200000
# mu = 1.0 일 때 위반 0
# mu = 2.0 로 키우면 위반 13082
# mu = 1 이 이 함수의 정확한 상수입니다. 더 키우면 부등식이 깨집니다.
# --- 문제 3: 매끄러움 상한 부등식 ----------------------------------------
print(" L-매끄러움: f(x) <= f(a) + grad.h + (L/2)|h|^2 위반 횟수 / 200000")
print(" L = %.1f 일 때 위반 %d" % (L, int((fb > lin + 0.5*L*np.einsum('ij,ij->i', hh, hh) + 1e-9).sum())))
print(" L = %.1f 로 줄이면 위반 %d" % (50.0, int((fb > lin + 0.5*50.0*np.einsum('ij,ij->i', hh, hh) + 1e-9).sum())))
print(" 기울기 립시츠: |grad f(x) - grad f(y)| <= L |x - y|")
dg = (A - B) @ H
ratio = np.linalg.norm(dg, axis=1) / np.maximum(np.linalg.norm(A - B, axis=1), 1e-12)
print(" 비 |dgrad|/|dx| 의 최대 %.6f, 최소 %.6f (L = %.1f, mu = %.1f)" % (ratio.max(), ratio.min(), L, mu))
# L-매끄러움: f(x) <= f(a) + grad.h + (L/2)|h|^2 위반 횟수 / 200000
# L = 100.0 일 때 위반 0
# L = 50.0 로 줄이면 위반 100547
# 기울기 립시츠: |grad f(x) - grad f(y)| <= L |x - y|
# 비 |dgrad|/|dx| 의 최대 100.000000, 최소 1.000001 (L = 100.0, mu = 1.0)
# 비가 정확히 [mu, L] 안에 들어옵니다.
# --- 문제 4: 한 걸음의 감소량 --------------------------------------------
print(" L-매끄러움에서 eta = 1/L 로 한 걸음 내디디면")
print(" f(x - eta g) <= f(x) - (1/(2L))|g|^2")
x = np.array([3.0, 0.5])
g = gf(x); eta = 1.0/L
print(" 현재 f = %.6f, |g|^2 = %.6f" % (f(x), g @ g))
print(" 보장된 감소량 >= %.6f" % (0.5/L*(g @ g)))
print(" 실제 f(new) = %.6f, 실제 감소 %.6f" % (f(x - eta*g), f(x) - f(x - eta*g)))
print(" eta 새 f 감소량 보장선")
for e in [0.005, 0.01, 0.019, 0.021]:
print(" %6.3f %11.6f %10.6f %10.6f" % (e, f(x - e*g), f(x) - f(x - e*g), 0.5/L*(g @ g)))
# L-매끄러움에서 eta = 1/L 로 한 걸음 내디디면
# f(x - eta g) <= f(x) - (1/(2L))|g|^2
# 현재 f = 17.000000, |g|^2 = 2509.000000
# 보장된 감소량 >= 12.545000
# 실제 f(new) = 4.410450, 실제 감소 12.589550
# eta 새 f 감소량 보장선
# 0.005 7.580112 9.419888 12.545000
# 0.010 4.410450 12.589550 12.545000
# 0.019 14.455624 2.544376 12.545000
# 0.021 19.437985 -2.437985 12.545000
# eta = 0.021 > 2/L = 0.02 이면 감소량이 음수입니다. 손실이 늘어납니다.
# --- 문제 5: PL 부등식과 최적성 간격 -------------------------------------
print(" 강볼록에서 |grad f(x)|^2 >= 2 mu (f(x) - f*)")
print(" 점 |grad|^2 2 mu (f - f*) 비")
for p in [np.array([3.0,0.5]), np.array([0.1,1.0]), np.array([5.0,0.0])]:
gg = gf(p); lhs2 = gg @ gg; rhs2 = 2*mu*f(p)
print(" %s %11.4f %13.4f %7.2f" % (np.round(p,1), lhs2, rhs2, lhs2/rhs2))
print(" 최적성 간격 상한: f(x) - f* <= |grad|^2/(2 mu)")
for p in [np.array([3.0,0.5]), np.array([0.1,1.0])]:
gg = gf(p)
print(" %s 실제 %.6f 상한 %.6f" % (np.round(p,1), f(p), (gg @ gg)/(2*mu)))
# 강볼록에서 |grad f(x)|^2 >= 2 mu (f(x) - f*)
# 점 |grad|^2 2 mu (f - f*) 비
# [3. 0.5] 2509.0000 34.0000 73.79
# [0.1 1. ] 10000.0100 100.0100 99.99
# [5. 0.] 25.0000 25.0000 1.00
# 최적성 간격 상한: f(x) - f* <= |grad|^2/(2 mu)
# [3. 0.5] 실제 17.000000 상한 1254.500000
# [0.1 1. ] 실제 50.005000 상한 5000.005000
# (5,0) 은 mu 의 고유벡터 방향이라 비가 정확히 1 입니다. 상한이 헐거운 것은 mu 가 작기 때문입니다.
문제 4의 마지막 줄이 이 강의의 요지입니다. η = 0.021 η = 0 . 0 2 1 2 / L = 0.02 2 / L = 0 . 0 2
매끄러움이 걸음을 보장하고 강볼록이 그 걸음을 진전으로 바꿉니다 매끄러움이 걸음을 보장하고 강볼록이 그 걸음을 진전으로 바꿉니다
109강에서 이 걸음을 반복합니다.
μ μ L L κ κ 강볼록 하한 부등식을 쓰세요.
강볼록의 가장 일반적인 정의를 쓰세요.
매끄러움 상한 부등식을 쓰세요.
매끄러움의 립시츠 형태를 쓰세요.
하강 보조정리와 안전한 η η
상한 부등식에서 최적 η η
PL 부등식과 등호 조건을 쓰세요.
최적점과의 거리 상한을 쓰세요.
정답.
μ I ⪯ H ⪯ L I μ I ⪯ H ⪯ L I L / μ L / μ 1 1 f ( a + h ) ≥ f ( a ) + ∇ f ⋅ h + μ 2 ∥ h ∥ 2 f ( a + h ) ≥ f ( a ) + ∇ f ⋅ h + 2 μ ∥ h ∥ 2 f − μ 2 ∥ ⋅ ∥ 2 f − 2 μ ∥ ⋅ ∥ 2 f ( a + h ) ≤ f ( a ) + ∇ f ⋅ h + L 2 ∥ h ∥ 2 f ( a + h ) ≤ f ( a ) + ∇ f ⋅ h + 2 L ∥ h ∥ 2 ∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥ ∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥ η ≤ 1 / L η ≤ 1 / L η 2 ∥ ∇ f ∥ 2 2 η ∥ ∇ f ∥ 2 0 < η < 2 / L 0 < η < 2 / L 1 / L 1 / L 1 2 ∥ ∇ f ∥ 2 ≥ μ ( f − f ∗ ) 2 1 ∥ ∇ f ∥ 2 ≥ μ ( f − f ∗ ) μ μ ∥ x − x ∗ ∥ ≤ ∥ ∇ f ∥ / μ ∥ x − x ∗ ∥ ≤ ∥ ∇ f ∥ / μ
기호
읽는 법
뜻
μ μ 강볼록 상수
아래에서 받치는 곡률입니다
L L 매끄러움 상수
위에서 누르는 곡률입니다
κ = L / μ κ = L / μ 조건수
수렴 속도를 정합니다
H ⪰ μ I H ⪰ μ I 준정치 부등식
H − μ I H − μ I
하강 보조정리
descent lemma
한 걸음의 감소를 보장합니다
PL 부등식
Polyak-Lojasiewicz
기울기가 최적성 간격을 지배합니다
립시츠 상수
Lipschitz constant
변화율의 상한입니다
역추적 직선탐색
backtracking line search
L L
f^
최솟값
min f min f
다음 109강에서는 경사하강법 을 세웁니다. 96강의 최급강하 방향, 107강의 볼록성, 이 강의의 두 부등식이 한 줄의 알고리즘에 모입니다. 그 알고리즘이 실제로 어떻게 움직이는지, 조건수가 클 때 왜 지그재그로 가는지 를 수치로 보고, 멈추는 기준을 정합니다.