論文の概要: Learning-Augmented Algorithms for Online Linear and Semidefinite Programming

• arxiv url: http://arxiv.org/abs/2209.10614v1
• Date: Wed, 21 Sep 2022 19:16:29 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-23 14:55:04.331903
• Title: Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
• Title（参考訳）: オンライン線形および半定義型プログラミングのための学習型アルゴリズム
• Authors: Elena Grigorescu, Young-San Lin, Sandeep Silwal, Maoyuan Song, Samson Zhou
• Abstract要約: Semidefinite Programming (SDP) は線形および二次的に制約されたプログラミングを一般化する統一フレームワークである。 SDPをカバーするための制約がオンラインに届くと、最適解を近似するためには、既知の不可能な結果が存在する。 予測器が正確であれば、これらの不可能な結果を効率よく回避し、最適解に対する定数係数近似を達成できることが示される。
• 参考スコア（独自算出の注目度）: 9.849604820019394
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Semidefinite programming (SDP) is a unifying framework that generalizes both linear programming and quadratically-constrained quadratic programming, while also yielding efficient solvers, both in theory and in practice. However, there exist known impossibility results for approximating the optimal solution when constraints for covering SDPs arrive in an online fashion. In this paper, we study online covering linear and semidefinite programs in which the algorithm is augmented with advice from a possibly erroneous predictor. We show that if the predictor is accurate, we can efficiently bypass these impossibility results and achieve a constant-factor approximation to the optimal solution, i.e., consistency. On the other hand, if the predictor is inaccurate, under some technical conditions, we achieve results that match both the classical optimal upper bounds and the tight lower bounds up to constant factors, i.e., robustness. More broadly, we introduce a framework that extends both (1) the online set cover problem augmented with machine-learning predictors, studied by Bamas, Maggiori, and Svensson (NeurIPS 2020), and (2) the online covering SDP problem, initiated by Elad, Kale, and Naor (ICALP 2016). Specifically, we obtain general online learning-augmented algorithms for covering linear programs with fractional advice and constraints, and initiate the study of learning-augmented algorithms for covering SDP problems. Our techniques are based on the primal-dual framework of Buchbinder and Naor (Mathematics of Operations Research, 34, 2009) and can be further adjusted to handle constraints where the variables lie in a bounded region, i.e., box constraints.
• Abstract（参考訳）: 半有限プログラミング(SDP)は、線形プログラミングと二次制約付き二次プログラミングの両方を一般化する統一的なフレームワークであり、理論と実際の両方において効率的な解法を得られる。 しかし、SDPをカバーするための制約がオンラインに届くと、最適解を近似する不可能な結果が知られている。 本稿では,線形プログラムと半定値プログラムを網羅し,そのアルゴリズムを誤予測器からのアドバイスで拡張する手法を提案する。 予測器が正確であれば、これらの不合理性の結果を効率よく回避し、最適解、すなわち一貫性に対する定数係数近似を達成できることが示される。 一方、もし予測器が不正確であれば、いくつかの技術的条件下では、古典的最適上界と厳密な下界、すなわちロバスト性の両方に一致する結果が得られる。 より広義には、(1)Bamas、Maggiori、およびSvensson(NeurIPS 2020)が研究した機械学習予測器で強化したオンライン・セット・カバー問題と、(2)Elad、Kale、Naor(ICALP 2016)によるオンライン・カバー・SDP問題の両方を拡張するフレームワークを導入する。 具体的には,線形プログラムを分数的なアドバイスと制約でカバーする一般的なオンライン学習支援アルゴリズムを求め,sdp問題をカバーする学習支援アルゴリズムの研究を開始する。 我々の手法は,buchbinder と naor (mathematics of operations research, 34, 2009) の初歩的枠組みに基づいており,変数が境界領域,すなわちボックス制約に存在する制約を扱うように,さらに調整することができる。

関連論文リスト

• A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives [4.9826534303287335]
  本稿では,線形制約付きオンラインパッキング問題に対する単純な学習拡張アルゴリズムの導入と解析を行う。 さらに、このような単純なブラックボックス解が最適である場合に必要かつ十分な条件を理解するという問題を提起する。
  論文  参考訳（メタデータ） (2024-06-05T18:39:28Z)
• Learning Adversarial MDPs with Stochastic Hard Constraints [37.24692425018]
  本研究では,制約付き意思決定プロセスにおけるオンライン学習問題について,対向的損失と厳しい制約を伴う検討を行った。 我々は,各エピソードの制約を高い確率で満たしながら,サブ線形後悔を実現するアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-03-06T12:49:08Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。 本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。 これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
  論文  参考訳（メタデータ） (2024-03-06T04:43:22Z)
• Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
  未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。 提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
  論文  参考訳（メタデータ） (2024-02-24T09:47:46Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• An Online Algorithm for Chance Constrained Resource Allocation [10.791923293928987]
  本稿では,オンライン資源配分問題 (RAP) を確率制約で検討する。 私たちの知る限りでは、オンラインRAP問題に制約が導入されるのはこれが初めてです。
  論文  参考訳（メタデータ） (2023-03-06T16:17:19Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Generalization Bounds for Data-Driven Numerical Linear Algebra [24.961270871124217]
  データ駆動アルゴリズムは、トレーニングされた入力サンプルから学習することで、未知のアプリケーション固有の分布からの入力に内部構造やパラメータを適用することができる。 いくつかの最近の研究は、数値線形代数における問題にこのアプローチを適用し、性能において顕著な経験的利得を得た。 本研究では、Gupta と Roughgarden が提案するデータ駆動アルゴリズム選択のためのPAC学習フレームワークにおいて、これらのアルゴリズムの一般化境界を証明する。
  論文  参考訳（メタデータ） (2022-06-16T02:23:45Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)

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

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