Editing Openai/69265508-3618-8006-8039-974c385cf126 (section)

===== 제안하는 방법/모델/이론의 핵심 아이디어 =====

====== 3.1 EGGROLL: 저랭크 ES 알고리즘 ======

논문의 주인공은 EGGROLL(Evolution Guided General Optimization via Low-rank Learning) 입니다. 요지를 풀어서 쓰면:
# 풀랭크 노이즈 대신 저랭크 노이즈 사용 - 기존 ES: E∼N(0,I)E \sim \mathcal{N}(0, I)E∼N(0,I), W′=W+σEW' = W + \sigma EW′=W+σE. - EGGROLL: - A∈Rm×r,B∈Rn×rA \in \mathbb{R}^{m\times r}, B \in \mathbb{R}^{n\times r}A∈Rm×r,B∈Rn×r 를 i.i.d. 대칭 분포에서 샘플링하고, - E=1rAB⊤E = \sqrt{\frac{1}{r}}AB^\topE=r1AB⊤ 를 perturbation으로 사용.arXiv<ref>{{cite web|title=arXiv|url=https://arxiv.org/pdf/2511.16652|publisher=arxiv.org|access-date=2025-11-26}}</ref> - 이렇게 하면 레이어당 노이즈 저장량이 mn→r(m+n)mn \rightarrow r(m+n)mn→r(m+n) 로 줄고, - 추가 연산량도 O(mnN) → O((m+n)rN) 로 줄어듭니다.arXiv<ref>{{cite web|title=arXiv|url=https://arxiv.org/pdf/2511.16652|publisher=arxiv.org|access-date=2025-11-26}}</ref>
# 업데이트는 여전히 풀랭크 - population에 대해 여러 개의 저랭크 업데이트 EiE_iEi 를 평균하면, - 최종 업데이트 랭크는 rank(∑iEi)≤min⁡(Nr,m,n)\text{rank}(\sum_i E_i) \le \min(Nr, m, n)rank(∑iEi)≤min(Nr,m,n) 이 됩니다. - 실험에서는 Nr가 m,n보다 크도록 잡아서 사실상 풀랭크 업데이트가 되게 합니다. 즉, 계산은 저랭크처럼, 업데이트는 풀랭크처럼.arXiv<ref>{{cite web|title=arXiv|url=https://arxiv.org/pdf/2511.16652|publisher=arxiv.org|access-date=2025-11-26}}</ref>
# 하드웨어 친화 구현 - LoRA와 유사하게, 각 개체의 저랭크 A,BA,BA,B 를 “어댑터”로 보고, - 기저 모델의 forward activation을 공유하면서, 특수한 batched matmul 커널로 모든 개체의 AB⊤AB^\topAB⊤를 한 번에 적용합니다. - 또한 counter-based RNG(예: JAX PRNG)를 사용해 필요할 때마다 노이즈를 재생성하므로, 노이즈 자체를 메모리에 오래 들고 있을 필요가 없습니다.arXiv<ref>{{cite web|title=arXiv|url=https://arxiv.org/pdf/2511.16652|publisher=arxiv.org|access-date=2025-11-26}}</ref>
# 알고리즘 레벨에서의 ES 구조는 그대로 - Salimans et al. 식의 병렬 ES 알고리즘을 계승하되, - “노이즈 생성 + 평가 + 가중 평균” 파이프라인이 모두 저랭크 버전으로 바뀝니다.arXiv<ref>{{cite web|title=arXiv|url=https://arxiv.org/pdf/2511.16652|publisher=arxiv.org|access-date=2025-11-26}}</ref>

====== 3.2 이론: O(1/r) 수렴하는 저랭크 ES 업데이트 ======

저자들은 “이 저랭크 업데이트가 원래 풀랭크 ES 업데이트를 얼마나 잘 근사하는가?” 를 수식으로 분석합니다. 핵심은:
* 우선 ES를 행렬 가우시안 분포 위의 정책으로 다시 쓰고, 그 gradient를 score function(∇ log p) 형태로 표현합니다.arXiv<ref>{{cite web|title=arXiv|url=https://arxiv.org/pdf/2511.16652|publisher=arxiv.org|access-date=2025-11-26}}</ref>
* 저랭크 케이스에서는 직접적인 density p(E)p(E)p(E)를 쓰기 어렵기 때문에, - Z=1rAB⊤+ϵZ = \sqrt{\frac{1}{r}}AB^\top + \epsilonZ=r1AB⊤+ϵ (여기서 ε는 작은 가우시안 잡음) 형태로 완전히 정의된 분포 p(Z)p(Z)p(Z)를 만들고, - 이 분포의 score function을 이용해 gradient를 작성합니다.arXiv<ref>{{cite web|title=arXiv|url=https://arxiv.org/pdf/2511.16652|publisher=arxiv.org|access-date=2025-11-26}}</ref>
* 이론의 메인 결과(Theorem 2): - 적당한 조건(피트니스 f가 bounded, 노이즈 분포가 대칭 등) 하에서, - 저랭크 근사 gradient g^rLR \hat{g}^{LR}_rg^rLR와 진짜 풀랭크 ES gradient gTrueg_\text{True}gTrue 의 거리(프로베니우스 노름)가 ∥g^rLR−gTrue∥F=O ⁣(1r)\| \hat{g}^{LR}_r - g_\text{True} \|_F = O\!\left(\frac{1}{r}\right)∥g^rLR−gTrue∥F=O(r1) 로 줄어든다고 증명합니다.arXiv<ref>{{cite web|title=arXiv|url=https://arxiv.org/pdf/2511.16652|publisher=arxiv.org|access-date=2025-11-26}}</ref>
* 이 O(1/r)는 일반적인 “파라미터 수 r이 증가할 때 중심극한정리(CL T)가 주는 O(1/√r)보다 빠른” 수렴률로, - 그 이유는 대칭 분포를 쓴 덕에 홀수차 누적(generalized cumulant)이 0이 되어, 4차부터 지배되기 때문이라고 설명합니다.arXiv<ref>{{cite web|title=arXiv|url=https://arxiv.org/pdf/2511.16652|publisher=arxiv.org|access-date=2025-11-26}}</ref>
* 또한, 실제 marginal 분포 p(zij)p(z_{ij})p(zij)에 대해 score × density를 그림 3에 시각화해 보면, - r=1에서도 그럭저럭 괜찮은 근사이고, r≥10 정도면 거의 limit 가우시안과 구분이 안 되는 것을 보여 줍니다.arXiv<ref>{{cite web|title=arXiv|url=https://arxiv.org/pdf/2511.16652|publisher=arxiv.org|access-date=2025-11-26}}</ref>

이론적으로 '''“랭크가 작아도 생각보다 훨씬 괜찮다”'''는 근거를 준 셈입니다.