論文の概要: Learning-Augmented Online Minimization with Dual Predictions
- arxiv url: http://arxiv.org/abs/2606.05380v1
- Date: Wed, 03 Jun 2026 19:29:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-05 22:39:44.364695
- Title: Learning-Augmented Online Minimization with Dual Predictions
- Title（参考訳）: 双対予測による学習強化オンライン最小化
- Authors: Christian Coester, Alexa Tudose, Alexander Turoczy,
- Abstract要約: 本稿では,オンライン問題の一般的なクラスとして,計量的タスクシステムと層集合被覆という2つの学習強化アルゴリズムを提案する。
両アルゴリズムは、線形プログラムに対する最適解の機械学習予測を用いて、理論的保証を改善する。
- 参考スコア（独自算出の注目度）: 46.123625291724345
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present learning-augmented algorithms for two general classes of online minimization problems: metrical task systems and laminar set cover. Both algorithms achieve improved theoretical guarantees using machine-learned predictions of an optimal solution to the dual linear program. Unlike optimal primal solutions, which can change drastically under tiny instance perturbations, these dual solutions are much more stable, which ensures the existence of good (and learnable) predictions for families of similar instances. While previous work has used dual predictions in offline settings and for online maximization problems, our algorithms are, to the best of our knowledge, the first demonstration that such dual predictions can be effective for online minimization. Our theoretical results are complemented by experiments on the $k$-server problem and the parking permit problem.
- Abstract（参考訳）: オンライン最小化問題の2つの一般的なクラス、すなわちメートル法タスクシステムとラミナー集合被覆に対する学習強化アルゴリズムを提案する。
両アルゴリズムは、線形プログラムに対する最適解の機械学習予測を用いて、理論的保証を改善する。
小さなインスタンスの摂動の下で劇的に変化する最適原始解とは異なり、これらの双対解はより安定であり、類似したインスタンスの族に対する良い(かつ学習可能な)予測の存在を保証する。
以前の研究では、オフライン設定やオンラインの最大化問題に二重予測を使用していたが、我々のアルゴリズムは、私たちの知る限りでは、そのような二重予測がオンラインの最小化に有効であることを示す最初の実証である。
我々の理論的結果は、$k$サーバ問題とパーキング許可問題の実験によって補完される。
関連論文リスト
- A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives [4.9826534303287335]
本稿では,線形制約付きオンラインパッキング問題に対する単純な学習拡張アルゴリズムの導入と解析を行う。
さらに、このような単純なブラックボックス解が最適である場合に必要かつ十分な条件を理解するという問題を提起する。
論文 参考訳（メタデータ） (2024-06-05T18:39:28Z) - Near-Optimal Solutions of Constrained Learning Problems [85.48853063302764]
機械学習システムでは、振る舞いを縮小する必要性がますます顕在化している。
これは、双対ロバスト性変数を満たすモデルの開発に向けた最近の進歩によって証明されている。
この結果から, 豊富なパラメトリゼーションは非次元的, 有限な学習問題を効果的に緩和することが示された。
論文 参考訳（メタデータ） (2024-03-18T14:55:45Z) - Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。
本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。
これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
論文 参考訳（メタデータ） (2024-03-06T04:43:22Z) - Dual Interior Point Optimization Learning [16.02181642119643]
本稿では,予備的アプローチを補完し,品質保証を提供する2つの実現可能な解の学習方法について検討する。
提案した双対完備化手法は、双対問題の構造を活用できない最適化プロキシの学習方法よりも優れている。
論文 参考訳（メタデータ） (2024-02-04T20:06:20Z) - Efficient Methods for Non-stationary Online Learning [63.268670895111654]
動的後悔と適応的後悔を最適化する効率的な方法を提案する。
提案アルゴリズムでは,各ラウンドで1つの勾配クエリと1つの関数評価しか必要としない。
また、さらに強力な測度、すなわち「内部的動的後悔」を研究し、ラウンド当たりの射影数を$O(log2 T)$から$$$$に減らした。
論文 参考訳（メタデータ） (2023-09-16T07:30:12Z) - Learning-Augmented Algorithms for Online Linear and Semidefinite
Programming [9.849604820019394]
Semidefinite Programming (SDP) は線形および二次的に制約されたプログラミングを一般化する統一フレームワークである。
SDPをカバーするための制約がオンラインに届くと、最適解を近似するためには、既知の不可能な結果が存在する。
予測器が正確であれば、これらの不可能な結果を効率よく回避し、最適解に対する定数係数近似を達成できることが示される。
論文 参考訳（メタデータ） (2022-09-21T19:16:29Z) - Faster Matchings via Learned Duals [31.61057940283721]
機械学習予測のアイデアと「スタート・ウォーム」原始二元アルゴリズムのアイデアを組み合わせる。
まず、予測可能な双対は実現不可能である可能性があるので、予測できない双対を近くの実現可能な解に効率的にマッピングするアルゴリズムを提供する。
第二に、一度双対が実現可能ならば、それらは最適ではないかもしれない。
論文 参考訳（メタデータ） (2021-07-20T21:11:09Z) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。
目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。
機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
論文 参考訳（メタデータ） (2020-10-22T04:51:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。