arXiv:2607.11146v1 cs.LG

Rank-Conditioned Sample Reuse for the Plackett--Luce Best-of-$K$ Objective

Melveena Jolly, Midhun Xavier

제출 2026-07-13

원문 초록

We study the coupled objective J_K^WOR = E_{S ~ PL-WOR_K}[max_{i in S} R_i]: the expected maximum reward of a size-K Plackett-Luce draw without replacement, the law of Gumbel-Top-K / Stochastic Beam Search decoding. This estimand differs from the conventional i.i.d. objective J_K^iid = E[max_{i<=K} R_i] targeted by existing sample-reuse Max@K estimators, and reusing their i.i.d. weights under the coupled sampler is provably biased (a closed-form three-item instance gives E[g_iid] = (4/5) grad J_K^WOR exactly; pass@K under the coupled sampler is the binary-reward special case). Generic joint-score REINFORCE is already unbiased for J_K^WOR; what it lacks is sample reuse. Our contribution is to instantiate standard rank-conditioned Horvitz-Thompson estimation for the J_K^WOR subset total: from one Gumbel-Top-n pool (n>K) and its observed priority threshold we build an estimator that reuses all C(n,K) embedded K-subsets, unbiased with an unbiased exact score-function surrogate gradient, plus a reward-sorted Max-specific dynamic program that collapses the C(n,K)-term subset sum (with K!-cost set probabilities) exactly to a one-dimensional integral. A fixed-Q quadrature evaluation costs O(n log n + nKQ) arithmetic and is numerically, not algebraically, exact; no epsilon-approximation rate is certified. Each nonzero degree-K Horvitz-Thompson term has finite second moment exactly when n >= 2K; under the same assumptions the full surrogate gradient has finite second moment whenever n >= 2K (sharpness there is open). At K=1 the construction recovers classical priority sampling. All quantities require only the values and differentiable computation graphs of the n+1 drawn items' probabilities, so finite structured sequence policies sampled by exact SBS are covered. A certified finite-Q quadrature bound and countably infinite support remain open. Validation code is included as ancillary files.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2607.11146v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.13692v1cs.LG공통 태그 Reinforcement Learning, Stochastic Optimization

분산 감소 정책 그래디언트는 거의 미니맥스-최적이다

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

표준 정책 그래디언트(Policy Gradient, PG) 알고리즘은 몬테카를로 업데이트에 의존하기 때문에 추정 분산이 높다는 문제를 가진다. 오프-정책 분산 감소(off-policy variance reduction)가 이 문제를 완화하지만, 현재로서는 최적의 샘플 복잡도(sample complexity)를 확립하려면 균일하게 유계인(uniformly bounded) 중요도 가중치(importance weights)와 같은 제한적인 가정이나 비현실적인 2차(second-order) 연산이 필요하다. 본 연구에서는 Loopless Variance-Reduced PG(LVR-PG)를 소개한다. 이는 재귀적 업데이트(recursive update)와 방어적 중요도 샘플링(defensive importance sampling)을 결합한 1차(first-order) 추정량들의 한 클래스를 추상화하는 통합 이론적 프레임워크로, PAGE-PG와 STORM-PG와 같은 기존 추정량들을 포함한다. 우리는 일반적인 파라메트릭 정책(parametric policy)에 대해 약한 그래디언트 지배(weak gradient domination) 조건 하에서 이 알고리즘 클래스가 $\tilde{\mathcal{O}}(ε^{-2})$의 라스트 이터레이트(last-iterate) 전역 수렴(global convergence)을 달성함을 증명한다. 우리는 순수하게 1차 업데이트만을 사용하여, 최소한의 가정 하에 그래디언트 전처리기(gradient preconditioner) 없이 이 보장을 확립한다. 최신 하한(lower bound)을 연속적인 파라메트릭 정책(continuous parametric policy)으로 확장함으로써, 우리는 $Ω(ε^{-2})$의 샘플 복잡도 한계를 확립하며, 이는 로그 인자(logarithmic factor)와 호라이즌(horizon) 항을 제외하면 우리의 프레임워크가 미니맥스 최적(minimax-optimal)임을 확인해 준다.

arXiv:2610.13871v1cs.LG공통 태그 Reinforcement Learning, Stochastic Optimization

영차 잔차 추적을 통한 부분 정보 확률적 최적화

Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking

많은 최적화(optimization) 문제에서는 그래디언트(gradient)의 일부에만 직접 접근할 수 있으며, 나머지 성분은 함수 평가를 통해 추론해야 합니다. 이러한 구조는 수행적 예측(performative prediction), 수행적 강화학습(performative reinforcement learning), 그리고 블랙박스 하위 레벨을 갖는 이단계 최적화(bilevel optimization)에서 발생합니다. 본 논문에서는 사용 가능한 그래디언트 성분과 잔차의 이동 추정치를 결합하는 부분 정보 확률적 최적화(Partially Informed Stochastic Optimization, PISO)를 제안합니다. PISO는 각 영차(zeroth-order) 관측을 이 추정치 중심으로 정렬함으로써, 무작위 탐침으로 인한 분산이 잔차의 크기가 아닌 추적 오차에 의존하도록 만듭니다. 이를 통해 명시적인 수축 메커니즘과 모멘텀(momentum)에 대한 원리적 해석을 갖춘 무작위 스케치 반복(iteration)을 도출합니다. 매끄러운 비볼록 목적 함수에 대해, 접근 불가능한 그래디언트 성분에 대한 균일한 경계를 요구하지 않으면서 잔차의 변동과 초기 크기에 의존하는 수렴(convergence) 보장을 확립합니다. 독립적으로 샘플링된 함수 평가와 가우시안 또는 구면 탐침을 사용할 때, PISO는 립시츠 그래디언트 조건에서 \(O(d^{2}\varepsilon^{-6})\), 추가적인 립시츠 헤시안(Hessian) 가정 하에서는 \(O(d^{2}\varepsilon^{-5})\)의 우수한 함수 평가 복잡도를 달성합니다. 이러한 수렴 속도는 업데이트당 단 하나의 탐침 방향, 두 개의 함수 샘플, 그리고 하나의 기지 성분 샘플만을 필요로 합니다. 또한 본 분석은 배치 처리를 통해 배포 횟수를 줄이는 대신 관측치를 교환하는 방식을 정량화합니다. 다섯 가지 설정 전반에서, PISO 변형들은 세 가지 설정에서 유사한 오라클 접근을 갖는 테스트된 베이스라인 대비 성능을 향상시키고, 이단계 라우팅에서는 유사한 해에 더 빠르게 도달하며, 수행적 강화학습에서는 반응 모델(response-model)의 도함수가 없는 방법 중 가장 뛰어난 성능을 보입니다.

arXiv:2610.10878v1cs.CL공통 태그 Language Modeling, Reinforcement Learning

에이전틱 온-정책 증류를 위한 확률적 교사 개입

Stochastic Teacher Intervention for Agentic On-Policy Distillation

온-정책(on-policy) 증류(OPD)는 학생이 생성한 롤아웃(rollout)에 대한 조밀한 토큰(token) 수준 감독을 통해 더 강력한 교사로부터 학생 언어 모델(language model)로 역량을 효율적으로 전이하며, 수학적 추론과 같은 복잡한 작업에서 유망한 성과를 보여주었다. 그러나 다중 턴(multi-turn) 에이전틱 작업에서는 학생의 결정이 이후의 관측을 형성하므로 턴을 거치며 초기 오류가 누적된다. 그 결과로 생성된 궤적은 교사의 롤아웃 분포에서 벗어날 수 있어, 교사의 토큰 수준 감독이 덜 신뢰할 수 있게 되거나 OPD 학습(training)에 오히려 역효과를 낼 수도 있다. 이러한 문제를 해결하기 위해, 본 논문에서는 다중 턴 에이전틱 OPD를 위한 확률적 교사 개입 프레임워크인 STI-OPD를 제안한다. 다중 턴 상호작용 과정에서 STI-OPD는 신뢰할 수 있는 감독 정보의 획득을 극대화하기 위해 교사-학생 정책 불일치에 기반한 교사 개입을 사용하여 학생이 제안한 행동을 교사가 생성한 행동으로 대체한다. 나아가 기존 임계값 기반 또는 고정 일정 접근법의 한계를 해결하기 위해, KL 발산을 사용해 정책 불일치를 추정하고 이를 개입 확률로 매핑하는 확률적 개입 전략을 개발한다. 이 확률로부터 개입 여부를 샘플링함으로써, STI-OPD는 교사의 제어와 학생의 탐험(exploration) 사이의 균형을 적응적으로 맞춘다. 이렇게 생성된 혼합 정책 궤적으로부터 학습하기 위해, 본 논문에서는 원래의 OPD 목적 함수를 보존하도록 교사가 생성한 응답과 학생 정책 간의 토큰 샘플링 불일치를 보정하는 중요도 가중 역방향 KL(Importance-Weighted Reverse KL) 목적 함수를 도입한다. 도구 통합 추론 및 장기적(long-horizon) 상호작용 전반에 걸쳐, STI-OPD는 평가된 모든 벤치마크와 학생 크기에서 가장 강력한 기존 OPD 기준선(baseline)을 능가한다. 소거 연구(ablation)를 통해 불일치 기반 개입과 중요도 가중치가 모두 이러한 성능 향상에 기여함을 추가로 확인하였다.

arXiv:2609.35297v3cs.LG공통 태그 Language Modeling, Stochastic Optimization

LionMuon: 효율적인 학습을 위한 스펙트럼 및 부호 하강 교차 기법

LionMuon: Alternating Spectral and Sign Descent for Efficient Training

언어 모델 사전학습에는 막대한 양의 연산량이 소모되며, 적절한 옵티마이저를 사용하면 이를 상당 부분 절감할 수 있습니다. Muon의 스펙트럼 스텝은 부호(sign) 스텝보다 더 강력한 방향을 제공하지만 연산 비용이 큽니다. 매 스텝마다 전체 행렬에 대해 뉴턴-슐츠 반복(Newton-Schulz iterations)을 수행하며, 분산 학습 환경에서는 추가적인 올리듀스(all-reduce)가 발생합니다. 반면 Lion 및 Signum과 같은 부호 스텝은 비용이 저렴하며 각 디바이스에 국소적으로 유지됩니다. 본 논문에서는 $P$ 반복마다 한 번의 Muon 스텝을 수행하고 그 사이에는 Lion 스텝을 수행하며, 두 방식이 단일 듀얼 EMA 모멘텀 버퍼를 공유하는 LionMuon을 제안합니다. Muon의 연산 및 통신 비용은 $P$ 스텝마다 한 번만 발생하며, 옵티마이저 상태 메모리는 AdamW의 절반 수준입니다. 단일 EMA 변형인 SignMuon만으로도 이미 Muon 대비 성능 향상을 보입니다. 저자들은 주기 $P$가 Muon과 Lion의 매끄러움(smoothness) 및 노이즈 상수를 보간하며 LionMuon이 두 방법보다 더 빠른 조건을 제시하는 꼬리가 두꺼운 노이즈(heavy-tailed noise) 환경에서의 복잡도 한계를 증명합니다. FineWeb으로 학습된 124M 및 355M 모델에서 $P=2$ 및 $P=5$인 LionMuon은 동일한 토큰 수에서 Muon, AdamW, Lion, Signum보다 더 낮은 손실을 달성합니다. 4개 GPU 데이터 병렬 학습 환경의 PCIe 상에서 LionMuon은 Muon의 최종 손실에 도달하면서도 소요 시간(wall-clock)을 3분의 1 줄였으며, 정확한 그래디언트를 유지하면서도 노출되는 통신량 증가 없이 통신 효율적인 Muon 변형인 Dion 및 MuonBP보다 더 우수한 손실 성능을 보입니다. 코드: https://github.com/brain-lab-research/lion-muon

arXiv:2609.27581v1cs.LG공통 태그 Language Modeling, Stochastic Optimization

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배이다.

arXiv:2609.28145v1cs.LG공통 태그 Language Modeling, Reinforcement Learning

RL은 RL 이전에 시작된다: 더 나은 강화학습을 위한 온-정책 증류

RL Starts before RL: On Policy Distillation for Better Reinforcement Learning

강화learning(RL)은 추론을 향상시키지만, 성능은 학습이 시작되는 정책에 달려 있다. 우리는 온-정책 증류(OPD)를 RL을 위한 준비 단계로 두고 연구하며, 그 이점이 증류된 모델의 초기 정확도 개선을 넘어서는지 묻는다. 동일한 RL 설정에서 OPD로 초기화한 학생 모델은 직접 RL로 학습한 모델, 또는 지도 미세조정 뒤 RL을 적용한 모델보다 더 높은 최종 성능에 도달한다. 이 이점은 OPD가 즉각적인 정확도 향상을 거의 주지 않을 때에도 나타날 수 있다. RL 이전 Pass@k만으로는 이 이점을 완전히 설명하지 못한다: 비슷하거나 더 높은 값이 RL 이후 더 나은 성능으로 이어지지는 않을 수 있다. 행동 분석은 top-1 일치를 넘어 교사 분포와의 정렬이 가능한 설명임을 가리킨다. 이러한 정렬은 더 높은 품질의 추론 경로를 선호하면서, RL이 결과 피드백으로 더 다듬을 수 있는 대안들을 남겨 둘 수 있다. 또한 궤적 출처와 발산 목표가 이후 RL을 위한 증류의 가치에 어떻게 영향을 미치는지 살핀다. 표준 역방향 KL OPD는 RL 이전에 더 낫지만, 순방향 KL OPD는 그 이후에 앞서게 된다. 교사가 생성한 증류 궤적을 쓰면 역방향 KL은 두 단계 모두에서 앞선다. 이는 선호되는 증류 목표가 궤적 출처와 뒤이어지는 학습 모두에 달려 있음을 시사한다. 우리 결과는 OPD를 RL 준비 단계로 평가하고, 이후 학습 뒤 달성한 성능을 기준으로 증류 방식을 고르는 접근을 뒷받침한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.