혁펜하임의 “탄탄한” 컨벡스 최적화 (Convex Optimization) 4강

혁펜하임의 “탄탄한” 컨벡스 최적화는 머신러닝·딥러닝을 공부하는 사람들이 ‘최적화’를 진짜 수학적으로, 그러면서도 직관적으로 이해하도록 도와주는 한국어 강의 시리즈입니다.​​ 강의의 전체 구성, 수강 난이도, 어떤 수학/ML 배경이 연결되는지, 그리고 어떻게 활용하면 좋은지는 아래의 포스팅에 정리되어 있습니다.

 

[AI 인공지능 머신러닝 딥러닝] - 혁펜하임의 “탄탄한” 컨벡스 최적화 (Convex Optimization) 강의 소개

혁펜하임의 “탄탄한” 컨벡스 최적화 (Convex Optimization) 강의 소개

 

혁펜하임의 “탄탄한” 컨벡스 최적화 (Convex Optimization) 강의

 

 

 

[최적화] 4-1강. quasi-Newton methods - Broyden's method | 역행렬 안구하는 뉴턴법!?

이 영상은 혁펜하임 “탄탄한 컨벡스 최적화” 4-1강으로, quasi-Newton 방법의 아이디어를 소개하고 그중 가장 기본격인 Broyden’s method(브로이덴 방법)를 유도·설명하는 강의입니다.​ 

핵심 주제는 “뉴턴법처럼 빠르게 가고 싶지만, 매번 Hessian과 그 역행렬을 직접 구하기는 너무 비싸다”는 문제를 어떻게 해결하는지에 대한 것이라고 보면 됩니다.​ 

 

 

quasi-Newton의 기본 아이디어 

quasi-Newton 방법은 매 단계마다 진짜 Hessian을 계산하는 대신, “좋은 근사 행렬” B k ≈ ∇ 2 f ( x k ) B k ≈∇ 2 f(x k )이나 그 역행렬 H k ≈ ∇ 2 f ( x k ) − 1 H k ≈∇ 2 f(x k ) −1 를 점진적으로 업데이트해 가는 방식입니다.​ 

이렇게 하면 2차 정보(곡률)를 어느 정도 활용하면서도 계산량과 메모리를 크게 줄일 수 있어, 순수 뉴턴법보다 실용적이고 안정적인 알고리즘을 만들 수 있습니다.​ 

 

 

Broyden’s method의 역할 

Broyden’s method는 quasi-Newton 계열 중 가장 단순한 형태로, “현재까지의 움직임과 gradient 변화량을 만족시키도록 Jacobian/Hessian 근사 행렬을 rank-one 업데이트로 갱신하는 방법”입니다.​ 

뉴턴법에서 필요했던 Jacobian(혹은 Hessian) 역행렬을 매번 직접 재계산하지 않고, 이전 단계에서의 근사 행렬을 한 단계씩 수정해 나간다는 점이 핵심입니다.​ 

 

 

secant 조건과 rank-one 업데이트 

quasi-Newton 계열 공통의 출발점은 secant 조건입니다.​ 

 

- 파라미터 변화: s k = x k + 1 − x k s k =x k+1 −x k

- gradient 변화: y k = ∇ f ( x k + 1 ) − ∇ f ( x k ) y k =∇f(x k+1 )−∇f(x k )

 

이 둘을 연결하는 선형 근사 B k + 1 s k ≈ y k B k+1 s k ≈y k 를 만족시키도록, 기존 근사 B k B k 를 가장 적게 변경하는 행렬 B k + 1 B k+1 를 찾는 문제가 되고, Broyden’s method는 이 문제를 rank-one 업데이트로 푸는 한 가지 선택지입니다.​

이 때문에 매 단계 업데이트가 “기존 행렬 + 랭크 1 행렬” 꼴로 매우 단순하게 표현됩니다.​

 

 

랭크(행렬의 계수)

https://youtu.be/HMST0Yc7EXE?si=r8tnYNNXMuT7yaf1

랭크에 대한 더 자세한 설명

[AI 인공지능 머신러닝 딥러닝/인공지능 수학] - 혁펜하임의 "보이는" 선형대수학 (Linear Algebra) 2강

혁펜하임의 "보이는" 선형대수학 (Linear Algebra) 2강

 

 

 

알고리즘 흐름

영상에서 정리하는 Broyden 계열 알고리즘의 흐름은 대략 다음과 같습니다.​

 

1. 초기점 x 0 x 0 와 초기 근사 행렬 B 0 B 0 (보통 스칼라 배의 항등행렬) 선택

2. 현재 gradient를 이용해 Newton-like 방향 p k = − B k − 1 ∇ f ( x k ) p k =−B k −1 ∇f(x k ) 또는 그 변형을 계산

3. step size(라인 서치 등)로 새 점 x k + 1 = x k + α k p k x k+1 =x k +α k p k 업데이트

4. s k , y k s k ,y k 를 구한 뒤, secant 조건을 만족하는 형태로 B k + 1 B k+1 를 rank-one로 갱신

5. 수렴할 때까지 반복

 

이렇게 하면 뉴턴법보다 훨씬 적은 비용으로 “곡률을 고려한 방향”을 매번 얻을 수 있습니다.​

 

 

 

한계와 이후 확장

강의 후반에서는 Broyden’s method의 단점으로, 업데이트된 근사 행렬이 대칭/양의정부호(positive definite) 특성을 보장하지 못해, 방향이 항상 descent direction이 되지 않을 수 있다는 점을 짚습니다.​

이 단점을 보완한 보다 실용적인 quasi-Newton 기법으로 BFGS, DFP 등이 있고, 이어지는 4-3강에서 “BFGS & DFP | quasi-Newton 끝판왕”이라는 제목으로 이런 방법들을 더 체계적으로 다룹니다.

 

 

[최적화] 4-2강. Symmetric rank-one (SR1) 내적만 알면 걍 이해돼!

이 링크는 혁펜하임 “탄탄한 컨벡스 최적화” 시리즈의 4-2강인 Symmetric Rank-One(SR1) 방법 강의입니다.​ 

quasi-Newton 계열 중에서, 헤시안 또는 그 역행렬을 대칭(symmetric) rank-one 업데이트로 근사하는 방법을 설명하는 내용입니다.​

 

 

강의 위치와 주제 

이 강의는 4-1강 Broyden 방법, 4-3강 BFGS/DFP 사이에 위치한 quasi-Newton 파트의 한 축으로, “내적만 알면 이해할 수 있는 SR1 업데이트”를 목표로 합니다.​​ 

즉, 뉴턴법의 2계 정보(곡률)를 직접 쓰기보다는, 이전 스텝의 움직임과 gradient 변화를 이용해 대칭 rank-one 행렬로 Hessian 근사를 갱신하는 방식을 다룹니다.​ 

 

 

SR1 아이디어 핵심 

SR1도 다른 quasi-Newton들처럼 secant 조건 B k + 1 s k ≈ y k B k+1 s k ≈y k 를 만족시키도록 Hessian 근사 B k B k 를 업데이트합니다.​ 

이때 “가능한 한 적게 고치는” 해 중에서 대칭 + rank-one인 갱신을 선택한 것이 SR1이고, 그래서 이름 그대로 Symmetric Rank-One 업데이트가 됩니다.​ 

 

 

왜 따로 볼 만한지 

SR1은 이론적으로는 곡률 정보(특히 일부 비양의정부호 상황)까지 더 잘 반영할 수 있어, BFGS와는 다른 장점을 가지는 quasi-Newton 방법입니다.​ 

강의에서는 내적과 기본 선형대수만으로 SR1 공식을 차근차근 유도하고, 이전 시간의 Broyden 방법과, 이후의 BFGS/DFP와 어떤 점이 다른지 대비해 주기 때문에 quasi-Newton 전체 그림을 잡는 데 도움이 됩니다.​

 

 

 

[최적화] 4-3강. BFGS & DFP | 콰지-뉴턴법 (quasi-Newton) 끝판왕!

이 영상은 혁펜하임 “탄탄한 컨벡스 최적화” 4-3강으로, quasi-Newton 계열의 대표 알고리즘인 BFGS와 DFP를 “콰지-뉴턴 끝판왕” 관점에서 정리하는 강의입니다.​ 

앞에서 본 Broyden·SR1을 포함하는 Broyden family 전체 틀 속에서, 왜 실전에서는 BFGS/DFP가 가장 널리 쓰이는지 그 이유와 수식 유도를 같이 다룹니다.​ 

 

 

강의의 큰 흐름 

강의 초반에는 먼저 BFGS가 단순 Broyden 방법과 무엇이 다른지, 특히 positive definite(PD) 행렬을 유지하면서 Hessian을 근사한다는 점을 강조합니다.​ 

이후 PD 행렬의 정의·성질, 왜 quasi-Newton에서 PD가 중요한지, 그리고 weighted Frobenius norm을 이용해 “가장 적게 수정되는” 업데이트를 찾는 최적화 문제로부터 BFGS/DFP 공식을 유도합니다.​ 

 

 

positive definite와 quasi-Newton 

영상 중간에서는 PD 행렬에 대해 다음과 같은 포인트를 상당히 자세히 짚습니다.​ 

 

- 정의: 모든 0이 아닌 벡터 x x에 대해 x ⊤ A x > 0 x ⊤ Ax>0이면 A A는 positive definite

- 의미:

-- 역행렬이 항상 존재

-- 모든 고유값이 양수 → “곡률이 항상 위로 볼록”

-- 이차형 x ⊤ A x x ⊤ Ax가 항상 양수이므로, descent direction 보장 등에 직접 연결

 

quasi-Newton에서 사용하는 Hessian 역근사 H k H k 가 PD이면, − H k ∇ f ( x k ) −H k ∇f(x k )가 항상 descent 방향이 되는 등, 알고리즘의 안정성과 수렴 성질에 핵심적인 역할을 한다고 설명합니다.​

 

 

BFGS / DFP 업데이트 직관

BFGS와 DFP는 모두 secant 조건 B k + 1 s k = y k B k+1 s k =y k 를 만족하면서, 이전 근사 B k B k 또는 H k H k 를 rank-two 업데이트로 바꾸는 quasi-Newton 방법입니다.​

강의에서는

- “차이가 최소가 되도록” 하는 최적화 문제를 Frobenius norm(여기서는 weighted Frobenius norm)으로 세우고

- 그 해로서 BFGS, DFP 업데이트 공식을 유도한 뒤

- 두 방법 모두 PD를 유지한다는 사실(조건 s k ⊤ y k > 0 s k ⊤ y k >0 하에서)을 설명합니다.​

 

 

이 과정을 통해, 단순 암기용 수식이 아니라 “왜 이런 모양으로 업데이트해야 Hessian이 예쁘게 근사되는지”를 이해하게 하는 구조입니다.​

 

 

 

라인 서치와 Broyden family

후반부에는 BFGS/DFP가 실제로 잘 동작하려면 line search가 어떻게 들어가야 하는지, 특히 Wolfe 조건 등을 만족하도록 step size를 잡아야 s k ⊤ y k > 0 s k ⊤ y k >0가 보장되고 PD 유지가 가능하다는 점을 다룹니다.​ 마지막에는 Broyden family 전체( SR1, BFGS, DFP 를 포함하는 연속적인 업데이트 계열)를 간단히 소개하며, BFGS가 실전에서 가장 많이 쓰이는 이유와 L-BFGS와 같은 확장 알고리즘으로 자연스럽게 이어집니다.​

 

 

 

이 강의에서 얻을 수 있는 것

- “gradient descent ↔ Newton ↔ quasi-Newton(BFGS/DFP)”까지 이어지는 큰 그림

- PD, Hessian 근사, secant 조건, rank-two 업데이트의 관계에 대한 직관

- 왜 여러 라이브러리(예: L-BFGS, BFGS 기반 최적화)가 딥러닝·통계·수치최적화에서 표준처럼 쓰이는지에 대한 배경 이해​

 

컨벡스 최적화 이론을 실질적인 수치 알고리즘 수준까지 끌어올리고 싶을 때, 이 강의가 quasi-Newton 파트의 핵심 정리 역할을 한다고 볼 수 있습니다.

 

 

 

[AI 인공지능 머신러닝 딥러닝] - 혁펜하임의 “탄탄한” 컨벡스 최적화 (Convex Optimization) 5강

혁펜하임의 “탄탄한” 컨벡스 최적화 (Convex Optimization) 5강