論文の概要: Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation
- arxiv url: http://arxiv.org/abs/2606.00703v1
- Date: Sat, 30 May 2026 12:22:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-02 21:34:28.663635
- Title: Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation
- Title（参考訳）: 圧縮ガウス平均推定への還元によるビット制約確率最適化のための情報理論下界
- Abstract要約: 低精度事前トレーニング (FP8, MXFP4, NVFP4) は現在、フロンティア言語モデルの標準となっている。
我々は、Bビット量子化された1次オラクルについて研究し、anunboundはTラウンドで相互作用し、各ラウンドにおいて、その勾配のBビット適応的なパブリックコイン記述を受信する。
実測値と実測値との整合性について, 実測値と実測値との整合性について検討した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Low-precision pretraining (FP8, MXFP4, NVFP4) is now standard for frontier language models, yet the literature is almost entirely achievability -- algorithms and empirical scaling laws -- with no matching characterization of what is information-theoretically possible. We study a B-bit quantized stochastic first-order oracle: an optimizer interacts for T rounds and receives, each round, a B-bit adaptive public-coin description of its stochastic gradient. Our main contribution is an exact reduction from optimizing a strongly convex quadratic family to interactively compressed Gaussian mean estimation -- under the B-bit oracle the query carries no information, so optimization collapses exactly onto a sequential distributed-estimation problem. This yields two unconditional lower bounds, a communication bound TB = Omega(d) and a statistical bound T = Omega(sigma^2 d / eps^2), and the sharp product-form bound T = Omega((sigma^2 d / eps^2) max{1, d/B}). The product form is also unconditional: a B-bit transcript carries at most O(TB / sigma^2) of Fisher trace about the mean, so bits rather than dimension limit the recoverable information, and combined with the multivariate van Trees inequality this gives the bound directly, without bounded-likelihood-ratio truncation. We give a near-matching achievability result with exact per-round bit accounting under a bounded-dynamic-range oracle, tight up to a logarithmic factor; the lower bound is for truly Gaussian (unbounded) gradients, and closing this oracle gap is left open. A sequential rate-distortion perspective extends the reduction to correlated and drifting oracles and corrects an earlier conjecture: positive noise correlation raises the bound by (1+rho)/(1-rho) rather than relaxing it. The bounds give an information-theoretic baseline for any low-bit gradient path, not an optimality claim about deployed FP4 systems.
- Abstract（参考訳）: 低精度の事前トレーニング(FP8、MXFP4、NVFP4)は現在、フロンティア言語モデルの標準となっているが、この文献は、ほぼ完全に達成可能であり、アルゴリズムと経験的スケーリング法則であり、情報理論上可能なものと同等のキャラクタリゼーションはない。
最適化器はTラウンドで相互作用し,各ラウンドにおいて,Bビット適応的な確率勾配のパブリックコイン記述を受信する。
我々の主な貢献は、強い凸二次系列の最適化から対話的に圧縮されたガウス平均推定への正確な還元であり、Bビットオラクルの下では、クエリは情報を持たないので、最適化は逐次分散推定問題に完全に崩壊する。
これは、通信境界 TB = Omega(d) と統計境界 T = Omega(sigma^2 d / eps^2) と、鋭積形式境界 T = Omega((sigma^2 d / eps^2) max{1, d/B} である。
積形式も無条件であり、Bビットの転写文字はフィッシャー平均について多くの O(TB / sigma^2) をトレースするので、次元よりもむしろビットが回復可能な情報を制限する。
実測値から対数係数まで厳密な境界は真にガウス的(非有界な)勾配であり、このオラクルギャップを閉じたままである。
逐次速度歪みの観点は、相関とドリフトのオラクルへの還元を延長し、以前の予想を補正する: 正のノイズ相関は、それを緩和するよりも、(1+rho)/(1-rho)で境界を上昇させる。
境界は、任意の低ビット勾配パスに対する情報理論ベースラインを与え、デプロイされたFP4システムに対する最適性のクレームは与えない。
関連論文リスト
- Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise [7.7753818665096945]
勾配雑音を考慮したスムーズな非適応最適化のためのシャープな下界を証明した。
これは標準上界と一致し、[Arvani et al.] によって提起された、ほぼ確実に有界なオラクル誤差が有界な分散よりも優れているかどうかの問題を解く。
論文 参考訳（メタデータ） (2026-08-10T01:45:56Z) - Towards Scalable Persistence-Based Topological Optimization [44.16669776030478]
永続性に基づく位相最適化は、点クラウド $X の部分集合 mathbbRd$ を $L(X) = ell(mathrmDgm(X))$ という形の目的を最小化することによって変形する。
実際、最適化は2つの結合した問題によって制限される: 永続ホモロジーは典型的にはサブサンプル上で計算され、結果として生じる位相勾配は非常にスパースであり、非ゼロ更新を受けるアンカーポイントはわずかである。
論文 参考訳（メタデータ） (2026-05-09T15:47:20Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。
一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。
グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
論文 参考訳（メタデータ） (2026-02-26T15:27:53Z) - Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits [53.773695219320125]
重み付き雑音下での2階最適化の理論的理解に向けて第一歩を踏み出す。
勾配とヘッセン切断に基づく新しいアルゴリズムを導入し、基本限界にほぼ一致する高い確率上の境界を証明した。
論文 参考訳（メタデータ） (2025-10-12T16:36:54Z) - Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。
二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
論文 参考訳（メタデータ） (2025-09-23T09:14:39Z) - Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex
Optimization [9.019243171993553]
トレーニングステップ$T$とStep-size$eta$は、滑らかな凸最適化(SCO)問題の認定に影響を与える可能性がある。
まず、グラディエントDescent(GD)とグラディエントDescent(SGD)の厳密な過剰リスク低境界を提供する。
近年の作業は、より良い速度で達成できるが、トレーニング時間が長い場合には改善が減少する。
論文 参考訳（メタデータ） (2023-03-19T20:24:33Z) - A lower confidence sequence for the changing mean of non-negative right
heavy-tailed observations with bounded mean [9.289846887298854]
信頼シーケンスは、時間パラメトリックカバレッジ保証付き予測可能なパラメータシーケンスに対する適応されたセット列を生成する。
この研究は、スラックが0に収束するランニング平均条件付き期待値に対して、漸近的でない低CSを構成する。
論文 参考訳（メタデータ） (2022-10-20T09:50:05Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳（メタデータ） (2022-04-20T07:14:21Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳（メタデータ） (2022-01-05T15:17:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。