論文の概要: Online Algorithms via Minimax and Posterior Matching

• arxiv url: http://arxiv.org/abs/2608.01616v1
• Date: Mon, 03 Aug 2026 02:46:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-04 15:07:25.302891
• Title: Online Algorithms via Minimax and Posterior Matching
• Title（参考訳）: Minimax と Posterior Matching によるオンラインアルゴリズム
• Abstract要約: ミニマックスの観点からより統一的な方法論を開発する。 この単一原理は、いくつかの古典的オンライン分数問題に対して最適あるいはほぼ最適の保証を与えることを示す。
• 参考スコア（独自算出の注目度）: 5.995574493969049
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Competitive analysis is central to the study of online algorithms, but upper bounds are often highly problem-specific. We develop a more unifying methodology via the minimax viewpoint. Guided by Yao's principle, we reduce worst-case competitive analysis to Bayesian online design under an arbitrary correlated prior over arrival sequences. For such a prior, let $X^*$ be the hindsight-optimal fractional solution for the realized instance, and let $X^{(t)}=\mathbb E[X^*\mid \mathcal F_t]$ be its posterior process. Our guiding rule is posterior matching: at each time $t$, choose the feasible online action that tracks the current posterior $X^{(t)}$ as closely as the online constraints permit. We show that this single principle yields optimal or near-optimal guarantees for several classical online fractional problems, including set cover, load balancing, matching and more general resource-allocation problems, recovering or improving state-of-the-art bounds in these settings with norm/concave objectives. Via known rounding reductions, it also yields randomized integral guarantees for weighted paging, MTS on star metrics, and ski-rental. At a technical level, our analysis reduces competitive guarantees to key probabilistic inequalities for the vector martingales generated by the posterior of the offline optimum. The resulting framework gives a reusable route from Bayesian online design under arbitrary correlated priors to information-theoretic worst-case competitive guarantees.
• Abstract（参考訳）: 競合分析はオンラインアルゴリズムの研究の中心であるが、上位境界はしばしば問題固有のものである。 ミニマックスの観点からより統一的な方法論を開発する。 ヤオの原理に導かれ、我々はベイズオンラインデザインに対する最悪の競合分析を、到着前の任意の相関した前列の下で減らした。 そのような前もって、$X^*$ を実数体に対する後続最適分数解とし、$X^{(t)}=\mathbb E[X^*\mid \mathcal F_t]$ を後続過程とする。 毎回$t$で、現在のオンライン制約と同様に、現在の後方の$X^{(t)}$を追跡する実行可能なオンラインアクションを選択します。 この単一原理は、設定カバー、ロードバランシング、マッチング、より一般的なリソース割り当て問題、これらの設定における最先端境界の回復や改善など、いくつかの古典的なオンライン分断問題に対して、最適あるいは準最適に保証されることを示す。 既知の丸めの減少により、重み付けされたページング、MSSの恒星測度、スキーレンタルのランダム化された積分保証も得られる。 技術的レベルでは、我々の分析は、オフライン最適化の後部から発生するベクトルマルチンタレスの鍵確率的不等式に対する競合保証を減少させる。 結果として得られるフレームワークは、任意の相関した事前のベイジアンオンラインデザインから、情報理論上の最悪の競合保証への再利用可能なルートを提供する。

関連論文リスト

• Generalized Distributional Alignment Games for Unbiased Answer-Level Fine-Tuning [49.24876001249647]
  分散アライメントゲームフレームワークは、Answer-Level Fine-Tuning(ALFT)の強力な変分的視点を提供する これらのゲームの標準的なアルゴリズムは、小さなバッチから対数報酬を推定することに依存しており、ジェンセンの不等式により訓練を不安定にできる体系的なバイアスが生じる。 我々は、アライメントゲームを任意のブレグマン発散に一般化し、報酬を誘導する幾何の族に対して、証明可能な正確で偏りのない推定器を構築することができることを示す。
  論文  参考訳（メタデータ） (2026-05-04T10:34:42Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 本稿では,ウィンドウ/リスタートベースアルゴリズムと同様に,より単純な重みに基づくアルゴリズムを提案する。 我々のフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2026-01-03T04:50:21Z)
• Non-stationary Bandit Convex Optimization: A Comprehensive Study [28.086802754034828]
  Bandit Convex Optimizationは、シーケンシャルな意思決定問題のクラスである。 非定常環境でこの問題を研究する。 非定常性の標準的な3つの基準の下で、後悔を最小限に抑えることを目指しています。
  論文  参考訳（メタデータ） (2025-06-03T15:18:41Z)
• Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks [19.642496463491053]
  我々は、オンラインバイナリ分類を再考し、最良クラスのバイナリ損失との競合から、緩やかなベンチマークとの競合へと焦点を移した。 我々は、小さな入力摂動に対して頑健な予測器の比較、ガウス平滑化下での良好な性能、あるいは所定の出力マージンを維持することを検討する。 我々のアルゴリズムは、VC次元とインスタンス空間の複雑さにのみ依存する後悔の保証を達成する。
  論文  参考訳（メタデータ） (2025-04-14T18:00:23Z)
• Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
  フェデレートされた学習は、参加者のプライバシを備えた機械学習モデルを可能にする。 トレーニングやフィードバックのない問題に対して、差分にプライベートな分散手法は存在しない。 証明可能な収束保証付き分散アルゴリズム$alpha$-$sf NormEC$を導入する。
  論文  参考訳（メタデータ） (2025-02-19T07:10:32Z)
• Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimization [78.82586283794886]
  $chi2$-Preference Optimization(chi$PO)は、オーバー最適化に対して確実に堅牢なオフラインアライメントアルゴリズムである。 $chi$POは、正規化による不確実性に直面して悲観主義の原理を実装している。 $chi$POの単純さと強力な保証により、オーバー最適化に対して確実に堅牢な、実用的で汎用的なオフラインアライメントアルゴリズムとなった。
  論文  参考訳（メタデータ） (2024-07-18T11:08:40Z)
• Federated Online and Bandit Convex Optimization [27.565740560571292]
  適応的相手に対する分散オンラインおよび帯域幅凸最適化の問題点について検討する。 機械がクエリポイントの1階勾配情報にアクセスできる場合、協調は有益ではないことを示す。 私たちの研究は、限られたフィードバックでフェデレートされたオンライン最適化を体系的に理解するための最初の試みです。
  論文  参考訳（メタデータ） (2023-11-29T12:29:54Z)
• Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
  各ラウンド$t$において、プレイヤーが2次的打撃コストと2次攻撃コストに応じてアクション$x_tをプレイし、アクションを切り替えるための2乗$ell$-normコストを加算する、スムーズなオンライン最適化(SOQO)問題について検討する。 この問題クラスは、スマートグリッド管理、適応制御、データセンター管理など、幅広いアプリケーションドメインと強いつながりを持っています。 本稿では, 最適に近い性能を同時に達成しつつ, 強健な対角性能を得るベスト・オブ・ザ・ワールドス・アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-31T22:59:23Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Online Adversarial Attacks [57.448101834579624]
  我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。 まず、オンライン脅威モデルの決定論的変種を厳格に分析する。 このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
  論文  参考訳（メタデータ） (2021-03-02T20:36:04Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  線形回帰と文脈的帯域幅という2つの古典的高次元オンライン学習問題を再考する。 従来の手法が失敗した場合にアルゴリズムが成功することを示す。
  論文  参考訳（メタデータ） (2020-10-08T17:59:05Z)

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

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