論文の概要: Faster Matchings via Learned Duals

• arxiv url: http://arxiv.org/abs/2107.09770v1
• Date: Tue, 20 Jul 2021 21:11:09 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-22 23:43:33.618329
• Title: Faster Matchings via Learned Duals
• Title（参考訳）: 学習デュアルによる高速マッチング
• Authors: Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Sergei Vassilvitskii
• Abstract要約: 機械学習予測のアイデアと「スタート・ウォーム」原始二元アルゴリズムのアイデアを組み合わせる。 まず、予測可能な双対は実現不可能である可能性があるので、予測できない双対を近くの実現可能な解に効率的にマッピングするアルゴリズムを提供する。 第二に、一度双対が実現可能ならば、それらは最適ではないかもしれない。
• 参考スコア（独自算出の注目度）: 31.61057940283721
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A recent line of research investigates how algorithms can be augmented with machine-learned predictions to overcome worst case lower bounds. This area has revealed interesting algorithmic insights into problems, with particular success in the design of competitive online algorithms. However, the question of improving algorithm running times with predictions has largely been unexplored. We take a first step in this direction by combining the idea of machine-learned predictions with the idea of "warm-starting" primal-dual algorithms. We consider one of the most important primitives in combinatorial optimization: weighted bipartite matching and its generalization to $b$-matching. We identify three key challenges when using learned dual variables in a primal-dual algorithm. First, predicted duals may be infeasible, so we give an algorithm that efficiently maps predicted infeasible duals to nearby feasible solutions. Second, once the duals are feasible, they may not be optimal, so we show that they can be used to quickly find an optimal solution. Finally, such predictions are useful only if they can be learned, so we show that the problem of learning duals for matching has low sample complexity. We validate our theoretical findings through experiments on both real and synthetic data. As a result we give a rigorous, practical, and empirically effective method to compute bipartite matchings.
• Abstract（参考訳）: 最近の研究では、アルゴリズムを機械学習予測で拡張して、最悪の場合の下位境界を克服する方法が研究されている。 この領域は、特に競合するオンラインアルゴリズムの設計において、問題に関する興味深いアルゴリズム上の洞察を明らかにしている。 しかし、予測でアルゴリズムの実行時間を改善するという問題は、ほとんど解明されていない。 機械学習予測のアイデアと「ウォームスタート」原始双対アルゴリズムのアイデアを組み合わせることで、この方向への第一歩を踏み出す。 我々は組合せ最適化において最も重要なプリミティブの1つを考える:重み付き二部マッチングとその一般化は$b$マッチングである。 学習した双対変数を原始双対アルゴリズムで使用する際の3つの課題を同定した。 まず、予測された双対は実現不可能かもしれないので、予測できない双対を近くの実現可能な解に効率的にマップするアルゴリズムを与える。 第二に、双対が実現可能であれば、それらは最適ではないかもしれないので、それらを素早く最適な解を見つけるために使用できることを示す。 最後に,このような予測は学習可能な場合にのみ有効であるため,マッチングのための双対学習の問題はサンプル複雑性が低いことを示す。 実データと合成データの両方に関する実験を通じて理論的知見を検証する。 その結果,二成分マッチングを計算するための厳密で実用的,実証的に有効な手法が得られた。

関連論文リスト

• Dual Algorithmic Reasoning [9.701208207491879]
  本稿では,基礎となるアルゴリズム問題の双対性を利用してアルゴリズムを学習することを提案する。 アルゴリズム学習における最適化問題の2つの定義を同時に学習することで、より良い学習が可能になることを実証する。 次に、難易度の高い脳血管分類タスクにデプロイすることで、二元アルゴリズム推論の現実的な実用性を検証する。
  論文  参考訳（メタデータ） (2023-02-09T08:46:23Z)
• Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster $\text{L}$-/$\text{L}^\natural$-Convex Function Minimization [15.191184049312467]
  新たな研究のラインでは、マシンが学習した予測は、二部マッチングのような離散最適化問題に対するアルゴリズムのウォームスタートに有用である。 我々のフレームワークは、予測と全ての最適解の間の距離に比例した境界を提供する。 したがって、複数の最適解によらず、アルゴリズムを確実にウォームスタートさせることができる予測の初回学習性を与える。
  論文  参考訳（メタデータ） (2023-02-02T08:00:18Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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