파라미터화된 마르코프 연쇄의 정상 평균에 대한 무편향 도함수 추정
Unbiased Derivative Estimation for Stationary Mean of Parameterized Markov chains
한국어 초록
파라미터화된 마르코프 연쇄 계열과 관련된 정상 평균들의 그래디언트(gradient)에 대한 무편향 추정을 위한 새로운 접근법을 제안합니다. 우리의 추정기는 마르코프 연쇄의 혼합 속도(mixing rate)가 느릴 때 특히 효율적입니다. 우리의 접근법은 주어진 데이터 점에서 천이 밀도(transition density)와 그 그래디언트(gradient)를 평가할 수 있는 오라클(oracle) 외에는 특정한 파라미터화를 요구하지 않으며, 밀도 함수 자체에 대한 추가적인 지식은 필요하지 않습니다. 이는 우리의 추정기를 신경망(neural network)과 관련된 파라미터화에 적합하게 만듭니다. 해당 추정기는 효율성 측면에서 큰 개선을 달성할 잠재력이 있습니다. 수치 실험을 통해 이론적으로 예측된 우수한 성능이 확인되었습니다.
원문 초록
We propose a new approach to unbiased estimation of the gradients of the stationary means associated with parametrized families of Markov chains. Our estimators are particularly efficient when the Markov chains have slow mixing rate. Our approach does not require a specific parametrization except for an oracle to evaluate the transition density and its gradient at a given data point without any additional knowledge about the density function itself. It makes our estimator suitable for parametrizations associated with neural networks. The estimator can potentially achieve large improvement in terms of efficiency. Numerical experiments confirm the good performance predicted by the theory.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.11487v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
다중 스케일 행렬 가중치를 통한 온라인 역 선형 최적화의 정밀 후회 상한
Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
고정된 알려지지 않은 선형 효용(utility)을 갖는 온라인 역 선형 최적화를 연구한다. 각 라운드에서 환경(environment)은 컴팩트 행동 집합을 제시하고, 학습자(learner)는 그 집합에서 행동(action)을 추천하며, 환경은 동일한 집합 위에서 효용을 최대화하는 행동을 반환한다. 효용 벡터와 행동이 $d$차원 유클리드 단위 구(unit ball) 안에 있을 때, 시간 지평(time horizon)을 알 필요 없이 모든 시간 지평에 대해 기대 후회(regret)---최적 행동 대비 누적 효용 부족분---가 $O(\sqrt d)$인 무작위 알고리즘을 제시한다. $d$에 대한 의존성은 $T\ge d$인 지평에 대한 알려진 $\Omega(\sqrt d)$ 하한에 의해 상수 배수까지 최적이다. 우리 알고리즘은 기하학적으로 간격을 둔 스케일에서 다항식 특징(feature) 공간上的 행렬 곱셈 가중(matrix multiplicative weights)을 유지한다. 선형 프로그램(linear program)을 풀어 추천 분포를 선택하고, 이용 가능한 행동과 피드백 행동을 비교하여 점수 행렬을 갱신한다. 유리수 oracle 출력과 피드백 행동 하에서, 선형 최적화 oracle에 상대적으로 계산 가능한 구현이 $O(\sqrt d)$ 후회 상한을 유지한다. 차원, 지평, 입력 길이에 대해 다항 시간 실행 복잡도로 동일한 rate를 달성할 수 있는지는 열려 있다.
Step Law는 소규모 언어 모델에도 전이되는가? 59M 파라미터 미만에서의 실증적 재보정
Does Step Law Transfer to Small-Scale Language Models? An Empirical Recalibration Below 59M Parameters
Step Law는 언어 모델 사전학습 시 최적 피크 학습률 η*와 배치 크기 B*에 대한 멱법칙(power-law) 공식을 제공한다. 원 저자들은 59M~1B 파라미터 모델에서 이를 보정했으며, N < 59M인 소규모 모델 영역은 실증적으로 검증한 적이 없다. 이 영역은 단일 GPU 학습, 해석 가능성 연구, 교육용 실험, 메모리·비용상 더 큰 모델을 쓰기 어려운 환경에서 중요하다. 우리는 Step Law가 소규모 언어 모델에도 전이되는지 검증한다. 세 가지 결과를 가정한다. H1: 원래 계수를 그대로 쓸 수 있다. H2: 멱법칙 형태는 유지되나 계수가 다르다. H3: 이 영역에서는 멱법칙이 최적점을 설명하지 못한다. 모든 실험은 2048 토큰 BPE 어휘, AdamW, warmup-cosine 스케줄을 사용하는 단일 nanoGPT/TinyStories 파이프라인에서 수행했다. 각 (N, D) 셀의 최적점은 평활화된 학습 손실에 대해 log-log 좌표에서 국소 이차 근사를 통해 손실 표면 L(η, B)에서 추출했다. 최종 데이터셋은 서로 다른 (N, D) 셀 29개와 분석에 사용 가능한 run 935개를 포함한다. 주 재적합은 작업 구간 4 <= D/N <= 600에서 25개 셀(815 runs)을 사용한다. 풀링 데이터에서는 H2를 채택한다. 함수 형태는 유지되나 계수는 원 논문과 다르다. η*(N, D) = 0.0985 N^(-0.508) D^(0.238) (R^2 = 0.834)와 B*(D) = 3.6 × 10^(-4) D^(0.931) (R^2 = 0.950)를 얻었다. Step Law의 구조적 주장인 B*의 N 비의존성은 재현된다(p = 0.87). 다만 B*가 D에 따라 증가하는 기울기는 원 논문의 거의 2배다. Step Law를 직접 전이하면 최적 학습률을 체계적으로 과대 추정한다. η_SL / η*의 중앙값 비는 약 4.0배이며, 범위는 2.4배에서 6.6배이다.
영차(Newton) 동역학을 위한 형식적 운동론: Stein 보정 헤시안 추정과 곡률-분산 트레이드오프
A Formal Kinetic Theory for Zeroth-Order Newton Dynamics:Stein-Corrected Hessian Estimation and Curvature--Variance Trade-offs
영차(Newton)형 방법은 그래디언트와 헤시안을 사용할 수 없을 때 유용하지만, 1차 그래디언트 없는(gradient-free) 방법과는 상당히 다르게 동작한다. 우리는 블랙박스 함수값으로부터 그래디언트와 헤시안을 모두 추정하는 알고리즘을 위한 운동론적 프레임워크를 개발한다. 순진한 무작위 방향 헤시안 추정기는 2차 함수에서조차 편향된 것으로 드러난다; 가우시안 평활화된 목적함수의 헤시안을 추정하려면 가우시안-Stein 보정이 필요하다. 역헤시안의 선형화는 두 가지 노이즈 채널을 드러낸다: 역헤시안으로 전처리(preconditioned)된 그래디언트 노이즈, 그리고 역-헤시안 샌드위치를 통해 전달되는 헤시안 노이즈. 노이즈가 있는 오라클 하에서 두 번째 채널은 2차 차분 인수 $μ_H^{-4}$를 담는다. 작은 질량의 운동론적 리프트(lift)는 유한 단계 Newton 업데이트를 과소감쇠(underdamped) 위상 공간 모델과 연결한다; 과감쇠(overdamped) 공간적 한계는 스텝 크기, 배치 크기, 평활화 반경, 정규화 사이의 곡률-분산 트레이드오프를 드러내는 Lyapunov 경계를 산출한다. 수치 실험은 추정기 항등식, 그래디언트 및 헤시안 분산 법칙, 차원 스케일링, 역 섭동 정확도, 그리고 쿼리 예산 및 정규화 ablation 하에서의 최적화 동작을 확인한다.
유한 궤적로부터 에르고딕 동역학 시스템 학습
Learning Ergodic Dynamical Systems from a Finite Trajectory
우리는 에르고딕(ergodic) 확률적 동역학 시스템의 단일 유한 궤적로부터 학습하는 문제를 고려한다. 더 구체적으로, 시간 동질(time-homogeneous) 마르코프(Markov) 과정을 정의하는 이산 시간 자율 확률 시스템을 연구한다. 먼저 비선형 최소자승법(nonlinear least squares)으로 최적 1-단계 예측 함수를 추정하고, 과정의 불변 측도(invariant measure)에 대해 측정된 높은 확률 보장(high-probability guarantees)을 도출한다. 이러한 결과는 궤적 데이터의 비독립적·비동일분포적 특성이 고전적 통계적 학습 분석을 어떻게 수정하는지를 명시적으로 보여준다. 그런 다음 이 프레임워크를 고차 시스템과 유한 상태 공간으로 확장한다. 마지막으로, 동일한 최소자승법과 농도(concentration) 논증이 쿠프만 연산자(Koopman operator) 학습으로 자연스럽게 확장됨을 보인다. 우리의 접근법은 통계적 학습 이론과 마르코프 사슬에 대한 정량적 에르고딕 이론의 도구를 결합한다. 특히, 균일 기하학적 에르고딕(uniformly geometrically ergodic) 마르코프 사슬의 힐베르트 공간 값 가법 함수(additive functional)에 대한 농도 부등식(concentration inequality)에 의존한다.
데이터 기반 블록 교체 스케줄링
Data Driven Block Replacement Scheduling
우리는 \textit{블록 교체 정책(block replacement policy)} 하에서 $N$대의 독립 동형 기계를 유지·관리하기 위한 데이터 기반 알고리즘을 개발한다. 이 정책에서는 각 기계가 고장 시 교체되고, 모든 기계가 길이 $k$의 정규 간격으로 일괄 교체된다. 수명 분포가 알려지지 않은 경우 운영 데이터로부터 비용을 최소화하는 간격 $k^*$를 학습하는 것이 목표이다. 각 의사결정 시점마다 운영자는 $k \in \{1, 2, \ldots, K\}$를 선택하고, 그 결과 고장 이력(완전 수명과 우측 검열(right-censored) 수명의 혼합)을 관측하며, 갱신 함수(renewal function)에 의해 결정되는 단위 시간당 비용을 부담한다. 이를 확률적 다중 팔 밴딧(stochastic multi-armed bandit)으로 형식화하고, $O(K \log T)$ 후회(regret)를 달성하는 Hoeffding 및 Bernstein 기반 하한 신뢰 구간(lower-confidence-bound) 알고리즘을 제안하며, 이는 Lai--Robbins 하한과 일치한다. 블록 교체에 고유한 중첩 관측(nested observation) 성질을 활용한 상관 변형(correlated variants)은 $O((K-k^*)\log T)$ 후회를 달성하고, 차선 arm $k < k^*$에 대한 직접 pull은 $O(1)$번만 필요하다. 보완적으로 Kaplan--Meier 갱신 알고리즘은 검열 데이터로부터 수명 분포를 비모수적으로 추정하여, 거의 확실(almost-sure)한 정책 일관성을 달성하고 장기 구간에서 실증적으로 거의 0에 가까운 추가 후회를 보인다. 또한 평균 비용 MDP 두 가지를 분석한다. 경과 시간(time-elapsed) 형식화는 임의의 수명 분포에 대해 블록 교체가 해당 정책 클래스 내에서 최적임을 보이고, 연령 벡터(age-vector) 형식화는 증가하는 고장률(increasing failure rate) 분포 하에서 단조 임계값(monotone threshold) 구조를 증명하며 gold-standard 비용 벤치마크를 제공한다. 수치 실험은 이론적 순서를 확인하고, 최적 블록 교체와 연령 의존(age-dependent) 교체 사이의 구조적 비용 격차를 밝힌다.
비팽창 이중 시간 스케일 확률적 근사: 고정 스케줄 1/4 장벽과 바이어스 보정 가속
Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration
비팽창 이중 시간 스케일 확률적 근사는 유일한 균형으로의 수축이 아니라, 느린 확률적 Krasnoselskii--Mann(KM) 고정점 반복에 의해 지배된다. 우리는 수축적 빠른 사상(contractive fast map)과 비팽창 축소 느린 사상(non-expansive reduced slow map) 하에서 이 영역을 연구한다. 먼저 유한 수평선 하한을 증명하여, 임의의 주어진 느린 스텝 크기 스케줄 $(β_k)$에 대해 고전적 KM 잔차 스케일 $(\sum_{i<N}β_i(1-β_i))^{-1}$이 해당 비정규화 KM 업데이트에 대해 최악의 경우 sharp함을 보인다. 원시 빠른 추적(fast-tracking) 누출 스케일과 결합하면, 이는 이전에 관찰된 $k^{-1/4+o(1)}$ 최종 반복(last-iterate) 평균제곱 잔차 지수를 설명한다. 그다음 빠른 추적 오차에 대한 1차 의존성을 상쇄하는 잔차 전처리(residual-preconditioned) 느린 오라클을 도입한다. 중첩 Tikhonov-KM 알고리즘에서 보정되지 않은 오라클은 총 샘플 비율 $T^{-1/4+o(1)}$을, 보정된 오라클은 $T^{-1/3+o(1)}$을 달성한다. 이 개선은 모든 내부 루프 샘플을 계산한 뒤 느린 오라클 바이어스를 빠른 오차에 대한 1차에서 2차로 바꾸는 데서 온다. 마지막으로, 중첩 방법의 반복적인 내부 루프 비용이 매끄러운 도함수 오라클 모델에서 회피될 수 있음을 보인다. 빠른 균형과 누출 전처리기(leakage preconditioner)를 모두 온라인으로 추적하는 단일 루프 알고리즘이 반복당 $O(1)$개의 원시 샘플로 $T^{-1/2+o(1)}$을 달성한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.