論文の概要: Rank-Conditioned Sample Reuse for the Plackett--Luce Best-of-$K$ Objective
- arxiv url: http://arxiv.org/abs/2607.11146v1
- Date: Mon, 13 Jul 2026 06:37:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-14 17:47:21.357988
- Title: Rank-Conditioned Sample Reuse for the Plackett--Luce Best-of-$K$ Objective
- Title（参考訳）: クラケットのランクコンディション・サンプル・リユース--Luce Best-of-K$ Objective
- Abstract要約: J_KWOR = E_S PL-WOR_K[max_i in S R_i]: サイズ-K プラケット-リュックドローの期待最大報酬を交換せずに得る。
我々は、すべての C(n,K) 埋め込み K-部分集合を再利用する推定器を構築し、偏りのない正確なスコア関数のサロゲート勾配でバイアスを取らない。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
- Abstract（参考訳）: 我々は,J_K^WOR = E_{S ~ PL-WOR_K}[max_{i in S} R_i] を,Gumbel-Top-K / Stochastic Beam Search decodingの法則であるサイズ-K Plackett-Luce のドローの最大値として期待できる値として,結合対象の J_K^WOR = E_{S ~ PL-WOR_K}[max_{i in S} R_i] について検討する。
この推定法は、既存のサンプル再利用Max@K推定器をターゲットとした従来のi.d.d. objective J_K^iid = E[max_{i<=K} R_i] と異なり、結合されたサンプリング器の下での重みの再利用は、確実に偏りがある(クローズドフォームの3テムインスタンスは、E[g_iid] = (4/5) grad J_K^WOR を正確に与える。
ジェネリックなジョイントスコアREINFORCEは、既にJ_K^WORには偏っていない。
我々の貢献は、J_K^WOR部分集合全体の標準ランク条件Horvitz-Thompson推定をインスタンス化することである: 1つのGumbel-Top-nプール(n>K)とその観測優先度から、すべてのC(n,K)埋め込みK-部分集合を再利用する推定器を構築し、非バイアスの正確なスコア関数のサロゲート勾配に偏らず、C(n,K)項の部分和を(K!
固定Q二次評価はO(n log n + nKQ)演算を犠牲にし、数値的には代数的には正確ではない。
それぞれの非零次数-K ホルヴィッツ-トンプソン項は、n >= 2K のときちょうど有限第二モーメントを持ち、同じ仮定の下では、全代理勾配は n >= 2K のときいつでも有限第二モーメントを持つ(シャープネスは開である)。
K=1で、構造は古典的な優先度サンプリングを回復する。
すべての量には n+1 個の描画項目の確率の値と微分可能な計算グラフしか必要としないため、正確な SBS でサンプリングされた有限構造シーケンスポリシーがカバーされる。
証明された有限 Q 次有界かつ数え切れないほど無限の支持は開である。
検証コードは補助ファイルとして含まれる。
関連論文リスト
- A uniform elliptic reduction, an order-matching criterion, and precision benchmarks for the strong-coupling Birman-Schwinger analysis of the lattice three-boson trimer [0.0]
Z2 上の3ボソン格子シュレーディンガー作用素の強結合解析を、例外的準同型 K = pi において提示する。
我々は、対応するスペクトルギャップとフレドホルム行列式過小評価因子2 + O(mu-2)を厳格に確立する。
時間反転不変モータにおける位相帯域絶縁体のパリティに基づく分類と平行な構造を描いている。
論文 参考訳（メタデータ） (2026-08-12T09:40:29Z) - Discretization and Statistical Consistency of Functional Flow Matching [0.0]
有限ランク再構成の強い一貫した列に対して、有限条件速度目標の強い$L2$収束を証明した。
学習フローに対して、集団重ね合わせ経路に直接結合すると、終端ワッサーシュタイン境界が得られる。
論文 参考訳（メタデータ） (2026-08-05T07:05:47Z) - Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
論文 参考訳（メタデータ） (2026-07-28T09:29:37Z) - Gram-Certified Resource Continuation for Structured Quantum Representation Audits [0.0]
構造化量子表現処理のためのグラム認証資源継続法を開発した。
連続性は最終的なシュミット級天井を克服できないことを示す。
これらのノイズのない古典的な結果は、汎用的な40量子ビットのシミュラビリティを確立したり、ハードウェアの性能を主張したり、量子的優位性を確立したりしない。
論文 参考訳（メタデータ） (2026-07-11T15:38:24Z) - Laplace-Fisher Gate Identities for Optimal Matrix-Gated Blended Score Estimation [0.0]
Laplace-Fisher Gate Identity (LFGI)
ベイズ逆問題に対する正規化密度評価のための有限参照LFGI推定器
LFGIと既知のモデルエビデンスを用いた実験は、ガウスと非ガウスの両方の設定における絶対的なエビデンス校正をチェックする。
論文 参考訳（メタデータ） (2026-06-23T21:00:32Z) - Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。
我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
論文 参考訳（メタデータ） (2025-09-20T20:18:49Z) - Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。
我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。
次に,新しい2段階クラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-02T05:10:40Z) - Convergence Rates of Constrained Expected Improvement [11.79168261900291]
制約付き予測改善法(CEI)は、制約付きブラックボックス最適化のための一般的なCBO法である。
我々は,CEIの収束速度を,その単純な後悔の上界を解析して検討した。
ガウス過程から$f$ と $c$ がサンプリングされると仮定すると、CEI は高い確率で同じ収束率が得られることを示す。
論文 参考訳（メタデータ） (2025-05-16T14:44:13Z) - Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications [2.0584253077707477]
目的関数 $J(cdot)$ の定常点を求めるグラディエント・Descent (SGD) 法の収束特性について検討した。
この結果は、すべての定常点が大域最小値である性質を持つ invex' 関数のクラスに適用できる。
論文 参考訳（メタデータ） (2023-12-05T15:22:39Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。
繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。
要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
論文 参考訳（メタデータ） (2021-12-29T14:47:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。