論文の概要: Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffs

• arxiv url: http://arxiv.org/abs/2602.06545v1
• Date: Fri, 06 Feb 2026 09:50:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-09 22:18:26.325798
• Title: Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffs
• Title（参考訳）: オンライン線形最適化のためのスタイン法操作:CLTに基づく最適トレードオフ
• Authors: Zhiyu Zhang, Aaditya Ramdas,
• Abstract要約: 確率的極限定理の証明の基礎となる古典的なフレームワークであるスタイン法が計算効率の良いOLOアルゴリズムとして動作可能であることを示す。 関連する後悔と総損失上限は「加法的にシャープ」であり、これは従来のBig-O最適性を上回ることを意味する。 我々のアルゴリズムは、オンライン勾配降下(OGD)と乗算重み更新(MWU)の総損失上限を改善する。
• 参考スコア（独自算出の注目度）: 40.656446349258964
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Adversarial online linear optimization (OLO) is essentially about making performance tradeoffs with respect to the unknown difficulty of the adversary. In the setting of one-dimensional fixed-time OLO on a bounded domain, it has been observed since Cover (1966) that achievable tradeoffs are governed by probabilistic inequalities, and these descriptive results can be converted into algorithms via dynamic programming, which, however, is not computationally efficient. We address this limitation by showing that Stein's method, a classical framework underlying the proofs of probabilistic limit theorems, can be operationalized as computationally efficient OLO algorithms. The associated regret and total loss upper bounds are "additively sharp", meaning that they surpass the conventional big-O optimality and match normal-approximation-based lower bounds by additive lower order terms. Our construction is inspired by the remarkably clean proof of a Wasserstein martingale central limit theorem (CLT) due to Röllin (2018). Several concrete benefits can be obtained from this general technique. First, with the same computational complexity, the proposed algorithm improves upon the total loss upper bounds of online gradient descent (OGD) and multiplicative weight update (MWU). Second, our algorithm can realize a continuum of optimal two-point tradeoffs between the total loss and the maximum regret over comparators, improving upon prior works in parameter-free online learning. Third, by allowing the adversary to randomize on an unbounded support, we achieve sharp in-expectation performance guarantees for OLO with noisy feedback.
• Abstract（参考訳）: 逆オンライン線形最適化(英語: Adversarial Online linear optimization、OLO)とは、本質的には、敵の未知の難しさに関して、パフォーマンスのトレードオフを行うことである。 有界領域上の一次元固定時間OLOの設定において、Cover (1966) 以降、達成可能なトレードオフは確率的不等式によって支配され、これらの記述結果は動的プログラミングによってアルゴリズムに変換することができ、計算的に効率的ではない。 確率的極限定理の証明の基礎となる古典的なフレームワークであるスタインの手法が計算効率の良いOLOアルゴリズムとして動作可能であることを示すことにより、この制限に対処する。 関連する後悔と総損失上限は「加法的に鋭く」、つまり従来のビッグオ最適性を超え、正規近似に基づく下限を加法的下次項で一致させる。 我々の構成は、レーリン (2018) によるワッサーシュタイン・マルティンゲール中心極限定理 (CLT) の驚くほどクリーンな証明に着想を得たものである。 この一般的な技術からいくつかの具体的な利点を得ることができる。 第一に、同じ計算量で、提案アルゴリズムは、オンライン勾配降下(OGD)と乗算重み更新(MWU)の合計損失上限を改善する。 第2に、パラメータフリーオンライン学習における先行研究の改善により、総損失とコンパレータに対する最大後悔との間の最適2点トレードオフの連続性を実現できる。 第3に,非有界なサポートで敵にランダム化を許すことで,雑音フィードバックを伴ってOLOの探索性能を著しく向上させる。

関連論文リスト

• Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe [61.68406997155879]
  State-of-the-art Large Language Model (LLM) プルーニング手法は階層的に動作し、階層ごとのプルーニングエラーを最小限に抑え、完全な再トレーニングを回避する。 既存の手法は、刈り上げ対象の重量相互作用を無視する欲求凸に依存する。 提案手法は, 層ごとのプルーニング誤差を大幅に低減し, 最先端のGPTアーキテクチャにおいて高いベースラインを達成し, メモリ効率を保っている。
  論文  参考訳（メタデータ） (2025-10-15T16:13:44Z)
• Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback [34.7178680288326]
  Stradi et al.(2024) は、マルコフ決定過程に制約のある最初のベスト・オブ・ボス・ワールドズ・アルゴリズムを提案した。 本稿では,CMDPにおける帯域幅フィードバックを用いたベスト・オブ・ワールドズ・アルゴリズムを提案する。 本アルゴリズムは政策最適化手法に基づいており, 占有率に基づく手法よりも効率的である。
  論文  参考訳（メタデータ） (2024-10-03T07:44:40Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
  オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。 我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-01T17:59:19Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。