머신러닝에서의 2차 경로 커널 보간 공식
Second-Order Path Kernel Interpolation Formulas in Machine Learning
한국어 초록
학습 데이터가 신경망 예측을 어떻게 형성하는지 이해하는 것은 현대 학습 이론의 핵심 문제입니다. 2020년 Pedro Domingos는 결정론적 경사하강법으로 학습된 모든 모델에 대해 유효한 보간 공식을 제안했습니다. 이 공식은 모델의 예측을 최적화 경로를 따른 데이터 종속 커널의 적분으로 표현하는데, 해당 커널은 테스트 데이터와 학습 데이터에서 모델의 그래디언트를 정렬시킵니다. 이러한 1차 특성화는 배치 기반 확률적 최적화로 학습된 모델에 대해서도 여전히 유효합니다. 본 논문에서는 이러한 보간 공식의 2차 형태를 개발합니다. 우리는 주요 경로 커널 보간이 곡률 가중치가 적용된 보간 항에 의해 보완됨을 보여줍니다. 확률적 경사하강법의 경우, 예측의 곡률을 미니배치 그래디언트 노이즈의 공분산과 결합하는 추가적인 샘플링 유발 성분이 나타납니다. 또한 우리는 모멘텀이 적용된 확률적 경사하강법으로 표현을 확장하며, 여기서는 보간 구조가 유지되되 가중치가 메모리 관련 인자에 의해 수정됩니다. 더 나아가, 우리는 최종 예측에 대한 집중 추정을 확립하여 기대되는 2차 표현 주변의 변동 스케일을 식별합니다. 종합적으로, 이러한 결과들은 신경망 예측에 대한 경로 커널 해석을 정교화합니다.
원문 초록
Understanding how training data shape neural network predictions is a central problem in modern learning theory. In 2020, Pedro Domingos proposed an interpolation formula valid for every model learned by deterministic gradient descent. It expresses the model's prediction as an integral, along the optimization path, of a data-dependent kernel that aligns the model's gradients at the test and training data. Such a first-order characterization remains valid for models trained with batch-based stochastic optimization. In this paper, we develop second-order forms of these interpolation formulas. We show that the leading path-kernel interpolation is supplemented by a curvature-weighted interpolation term. For stochastic gradient descent, an additional sampling-induced component appears, coupling the curvature of the prediction with the covariance of mini-batch gradient noise. We also extend the representation to stochastic gradient descent with momentum, where the interpolation structure is preserved but with the weights modified by a memory-related factor. Moreover, we establish a concentration estimate for the terminal prediction, identifying the fluctuation scale around the expected second-order representation. Together, these results provide a refinement of the path-kernel interpretation of neural network prediction.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.07495v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
하강 방향으로부터 학습: 일방 Hölder 정칙성 하의 적응형 경사하강법
Learning from the Descent Direction: Adaptive Gradient Descent under One-Sided Hölder Regularity
연속 미분 가능하고 비볼록일 수 있는 목적함수에 대해, 일방 Hölder 정칙성 하에서 적응형 경사하강법을 연구한다. 고전적인 Hölder 또는 Lipschitz 그래디언트 가정과 달리, 후자는 전체 그래디언트 변화를 제어하는 반면, 우리의 조건은 하강 부등식에 나타나는 방향 항만을 제한한다. 이는 그래디언트 변화가 크더라도 업데이트 방향에 직교하거나, 그 방향을 따라 유리한 경우 보다 덜 보수적인 스텝 크기를 허용할 수 있다. 양의 일방 Hölder 곡률 추정에 기반한 적응형 스칼라 스텝 방법을 제안하며, 이를 간단한 충분 감소(sufficient-decrease) 보호 장치와 결합한다. 수용된 업데이트 구간을 포함하는 볼록 영역 위의 비볼록 목적함수에 대해, Hölder 지수에 의해 결정되는 명시적 최적 반복 정류(stationarity) 한계를 증명한다. 미리 정해진 감소 스텝 크기 스킴과 달리, 이 방법은 국소 하강 기하에 적응한다. 방향 곡률과 전체 그래디언트 변화를 분리하도록 설계된 두 개의 풀 배치(full-batch) 벤치마크에서 접근법을 평가한다. 이진 분류 문제에서, 이 방법은 비교된 스칼라 그래디언트 방법들 중 최종 교차 엔트로피, 목적함수 값, 그래디언트 노름이 가장 낮고, 분류 마진이 가장 크다. 비볼록 Hölder 회귀 문제에서, 최종 목적함수 간극과 그래디언트 노름이 가장 낮다. 이 결과는 전체 그래디언트 변화가 하강을 방해하지 않는 방향으로 인해 부풀려질 때, 일방 Hölder 곡률이 효과적인 적응형 스텝 크기 신호임을 시사한다.
분산 경사하강법: 병목 구간과 예산 복잡도
Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexity
분산 경사하강법(decentralized gradient descent, DGD)은 에이전트 네트워크에서 분산 최적화 문제를 풀기 위해 널리 사용된다. 수렴 특성은 잘 이해되어 있지만, 규정된 정확도를 달성하는 데 필요한 통신 및 계산 자원에 대해서는 상대적으로 덜 알려져 있다. 본 논문에서는 자원 인식(resource-aware) 관점에서 DGD를 연구하고, 목표 오차 수준을 달성하는 데 필요한 통신-계산 예산을 특성화한다. 우리는 서로 다른 오차 규모에서 최적화 역학을 지배하는 요인이 달라지는 병목 중심(bottleneck-centric) 프레임워크를 제안한다. 구체적으로 초기화, 목적 함수 이질성(objective heterogeneity) 및 네트워크 연결성, 그래디언트 노이즈, 통신 노이즈가 지배하는 동작 구간을 식별한다. 이러한 효과를 포착하기 위해 두 가지 기본량인 그래디언트 다양성 대 네트워크 연결성 비율(gradient-Diversity-to-Network-connectivity Ratio, DNR)과 그래디언트 대 통신 노이즈 비율(Gradient-to-Communication-noise Ratio, GCR)을 도입한다. 이들이 최적화 과정에서 순차적으로 등장하는 병목의 순서와 그에 대응하는 예산 최적 동작 전략을 결정함을 보인다. 다단계 분석을 통해 규정된 정확도 달성에 필요한 예산 자원을 정량화하는 최적 보폭(stepsize) 선택과 명시적 예산-복잡도 상한을 도출한다. 결과 식은 전체 예산이 연속적인 병목에 대응하는 기여로 어떻게 분해되는지 밝히고, 목적 함수 이질성, 네트워크 연결성, 그래디언트 노이즈, 통신 노이즈 사이의 근본적 트레이드오프에 대한 통찰을 제공한다.
흐름 뒤의 지도: 동역학 시스템으로서의 유한 스텝 경사하강법
The Map Behind the Flow: Finite-Step Gradient Descent as a Dynamical System
심층 학습의 많은 현상은 동역학적 성질을 지닌다. 즉, 어떤 최솟값이 존재하는가뿐만 아니라, 경사하강법이 그 최솟값에 어떻게 도달하고, 어떤 것을 회피하거나 선택하는가에 관한 문제다. 안정성 경계(edge-of-stability) 거동, 날카로움(sharpness) 진동, 투석기(catapult) 위상, 균형 맞춤(balancing), 그리고 더 평탄한 표현을 향한 이동은 모두 학습 사상(training map) 자체의 효과이며, 소스텝 경사 흐름(gradient-flow) 극한으로는 제대로 포착되지 않는다. 본 논문은 고정 스텝 경사하강법을 심층 학습의 기본 구조—깊이, 인수분해, 너비, 데이터 결합, 활성화, 확률성—를 유지하는 정확히 풀 수 있는 모델의 계층 안에서 이산 동역학 시스템으로 연구한다. 출발점은 깊은 선형 체인의 균형 잡힌 스칼라 축소로, 사차(quartic) 손실과 안정성 경계 이후 거동이 명시적인 삼차(cubic) 그래디언트 사상을 제공한다. 자연스러운 대심도(large-depth) 스케일링 하에서 이 동역학은 보편적인 Ricker형 사상으로 수렴한다. 따라서 안정성 경계는 최적화의 붕괴가 아니라 학습 사상의 첫 번째 분기(bifurcation)다. 스칼라 동역학을 인수분해 모델에 다시 임베딩하면 이러한 체제들이 학습 현상으로 전환된다. 유한 스텝은 경사 흐름의 보존 법칙을 깨고 인수분해 불균형을 수축시키며, 잔여 진동은 매개변수를 더 평탄하고 균형 잡힌 표현 쪽으로 이동시킨다. 더 넓은 선형 네트워크는 스펙트럼 경계의 사다리를 생성하므로, 최적 학습률은 첫 번째 경계를 넘어서는 값일 수 있다. 데이터 결합, 비선형 활성화, 확률적 목표는 동일한 조직 원리를 보존한다. 즉, 유한 스텝 진동이 정렬, 균형 맞춤, 표현 선택을 이끈다. 따라서 학습률은 단순한 수치 안정성 매개변수가 아니다. 그것은 학습 동역학의 구조적 매개변수로서, 어트랙터를 결정하고 경사하강법이 선택하는 표현을 형성한다.
가우시안 설계 하 로지스틱 회귀에서 경사하강법의 유한 표본 성능
Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design
우리는 가우시안 설계 하 로지스틱 회귀의 매개변수 추정 문제를 고려한다: $n$개의 i.i.d. 표본 $\{(x_i,y_i)\}_{i=1}^n$로부터 고정된 미지 매개변수 $θ^*\in \mathbb{R}^d$ ($\|θ^*\|_2\ge 1$)를 추정하는 문제이며, 여기서 $x_i\sim N(0,I_d)$이고 $y_i|x_i \sim {\rm Bernoulli}(1/(1+\exp(-x_i^\top θ^*)))$이다. 우리의 주요 목표는 최대 가능도 목적함수(즉, 로지스틱 손실)에 대한 경사하강법(GD)의 유한 표본 추정 성능과 수렴 거동을 특성화하는 것이다. 작은 $O(1)$ 스텝 크기와 $0$ 초기화 하에서, GD가 $θ^*$의 작은 근방으로 선형 수렴하며 $\ell_2$ 오차가 $O(\sqrt{\|θ^*\|_2^5d/n})$ 차수에 달함을 보인다. 이는 비점근적 추정 오차율이 부족하고 훨씬 더 느린 매개변수 수렴을 보이는 기존 이론 결과를 실질적으로 넘어선다. 또한 큰 $Θ(\|θ^*\|_2)$ 스텝 크기 하에서 동일한 통계적 오차로의 더 빠른 국소 선형 수렴을 확립한다. 주요 기술적 구성요소는 로지스틱 손실의 그래디언트가 특정 근사 가역성 조건(AIC)을 만족함을 보이는 것이다. 이를 위해 covering과 peeling 논증을 통해 그래디언트가 모집단 대응량으로부터 벗어나는 정도를 균일하게 통제하고, 이어서 모집단 헤시안 행렬의 고유값에 기반한 정교한 분석으로 모집단 GD가 수축(contraction)임을 보인다. 마지막으로 Matsumoto and Mazumdar (2025)의 최근 연구를 바탕으로 고차원에서 더 날카로운 rate에 도달하는 새로운 효율적 추정량을 고안한다. 이는 기존 비점근적 보장이 $\|θ^*\|_2$에 대해 차 최적(sub-optimal) 의존성을 보임을, 그리고 많은 영역(regime)에서 $Θ(\sqrt{\|θ^*\|_2d/n})$가 tight한 추정 오차율임을 시사한다. 수치 예제를 제공하여 우리의 이론적 결과를 뒷받침한다.
Edge Flow: 안정성 경계에서 경사하강법을 위한 다루기 쉽고 예측 가능한 연속 시간 모델
Edge Flow: A Tractable and Predictive Continuous-Time Model for Gradient Descent at the Edge of Stability
심층 학습에서 경사하강법은 안정성 경계(EoS, edge of stability)에서 작동할 수 있으며, 이는 손실 헤시안의 최대 고유값이 안정성 임계값 $2/η$(여기서 $η$는 학습률) 근처를 머무는 영역이다. 그래디언트 흐름(gradient flow)과 하강 보조정리(descent lemma) 같은 고전적 분석 도구는 이 영역에 적용되지 않으므로, EoS에서 유효한 연속 시간 모델을 찾을 필요가 있다. 우리는 Edge Flow를 제안하는데, 이는 EoS에서 경사하강법 역학에 대한 다루기 쉽고, 충실하며, 예측 가능한 모델을 제공하는 세 개의 결합된 상미분방정식(ODE) 시스템이다. Edge Flow는 역학을 중심, 진동 방향, 진동 크기로 분해한다. 중심은 대칭화된 손실에 대한 수정된 그래디언트 흐름을 따르고, 방향은 Rayleigh 몫 역학을 통해 헤시안의 최고 고유벡터를 추적하며, 크기는 날카로움(sharpness)이 임계값 $2/η$를 초과하거나 미달하는지에 따라 지수적으로 증가하거나 감소한다. 중요한 것은, 날카로움 안정화가 결합된 역학을 통해 자기 안정화 피드백 루프로 나타난다는 점이다. Edge Flow를 이산화하는 데는 각 반복마다 그래디언트 평가 두 번과 헤시안-벡터 곱 한 번만 필요하다. 우리는 실험적으로 Edge Flow가 기존에 제안된 연속 시간 EoS 모델만큼 이상으로 경사하강법 역학을 충실히 추적하며, 추가로 EoS 시작 시 날카로움의 진동을 해석하고, 이 영역에서의 불안정성을 이해하고 완화하기 위한 원칙적 프레임워크를 제공함을 보인다.
Flatland: 큰 스텝 크기를 사용하는 경사하강법의 모험
Flatland: The Adventures of Gradient Descent with Large Step Sizes
신경망 학습은 종종 전역적으로 $L$-smooth하지 않은 목적 함수를 수반합니다. 이러한 함수들에 대해서는, 경사하강법(GD)의 수렴을 보장하는 가능한 가장 큰 스텝 크기가 무엇인지에 대한 질문에 답하는 것이 이론적으로나 실제적으로나 어렵습니다. 우리는 그래디언트의 국소적 리프시츠(또는 심지어 홀더) 연속성만을 요구하는 "큰" 스텝 크기에 대한 통합 정의를 제공함으로써 심층 학습의 이 오랜 미해결 문제를 다룹니다. 우리는 큰 스텝 크기를 생성함을 입증할 수 있는 1차 적응형 방법을 설계하고, 이 방법들이 학습 시작부터 안정성의 경계(EoS)에서 작동함을 보여줍니다. 특히, 손실은 비단조적으로 감소하며, 스텝 크기와 날카로움(sharpness, 즉 헤시안의 최대 고유값)의 곱은 학습 내내 2의 EoS 임계값 위에 머뭅니다. 우리의 방법을 사용하여 날카로움을 전역 최솟값까지 최소화할 수도 있습니다. 기대와 달리, 우리는 학습 초기에 전역적으로 평평한 영역에 도달하는 것이 수렴을 늦추고 네트워크의 일반화 능력을 위협할 수 있음을 발견했습니다. 자기 안정화 논증을 활용하여, 우리는 GD가 약간 더 날카로운 계곡으로 들어가도록 허용함으로써 성공하지 못했던 학습 실행을 매우 성공적인 것으로 전환합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.