論文の概要: Learning-Augmented Maximum Flow

• arxiv url: http://arxiv.org/abs/2207.12911v1
• Date: Tue, 26 Jul 2022 14:02:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-27 13:30:29.358711
• Title: Learning-Augmented Maximum Flow
• Title（参考訳）: 学習強化最大流れ
• Authors: Adam Polak, Maksym Zub
• Abstract要約: 本稿では,予測を用いて最大流れ計算を高速化するフレームワークを提案する。 我々は,$m$のエッジフローネットワークと予測フローが与えられた場合,最大フローを$O(meta)$時間で計算するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 3.0712335337791288
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a framework for speeding up maximum flow computation by using predictions. A prediction is a flow, i.e., an assignment of non-negative flow values to edges, which satisfies the flow conservation property, but does not necessarily respect the edge capacities of the actual instance (since these were unknown at the time of learning). We present an algorithm that, given an $m$-edge flow network and a predicted flow, computes a maximum flow in $O(m\eta)$ time, where $\eta$ is the $\ell_1$ error of the prediction, i.e., the sum over the edges of the absolute difference between the predicted and optimal flow values. Moreover, we prove that, given an oracle access to a distribution over flow networks, it is possible to efficiently PAC-learn a prediction minimizing the expected $\ell_1$ error over that distribution. Our results fit into the recent line of research on learning-augmented algorithms, which aims to improve over worst-case bounds of classical algorithms by using predictions, e.g., machine-learned from previous similar instances. So far, the main focus in this area was on improving competitive ratios for online problems. Following Dinitz et al. (NeurIPS 2021), our results are one of the firsts to improve the running time of an offline problem.
• Abstract（参考訳）: 予測を用いて最大流量の計算を高速化するフレームワークを提案する。 予測は、フロー、すなわち、エッジへの非負のフロー値の割り当てであり、フローの保存特性を満たすが、必ずしも実際のインスタンスのエッジ容量を尊重するとは限らない(これは学習時に未知であったためである)。 我々は,$m$-edgeフローネットワークと予測フローを与えられた場合,最大フローを$o(m\eta)$ timeで計算し,$\eta$は予測値の$\ell_1$誤差である。 さらに,フローネットワーク上の分布へのオラクルアクセスを考慮すれば,予測値である$\ell_1$の誤差を最小限に抑えることができる。 本研究は,従来の類似事例からの機械学習による予測を用いて,古典的アルゴリズムの最悪のケース境界を超えて改善することを目的としている。 これまでのところ、この分野の主な焦点はオンライン問題に対する競争比率の改善だった。 Dinitz et al. (NeurIPS 2021)に続いて、オフライン問題の実行時間を改善する最初の試みの1つである。

関連論文リスト

• Competitive strategies to use "warm start" algorithms with predictions [12.970501425097645]
  本稿では,温暖化開始アルゴリズムの学習と予測利用の問題点について考察する。 この設定では、アルゴリズムは問題のインスタンスと解の予測を与える。 我々は、$k$の予測を考慮に入れたより強力なベンチマークに対して、競争力のある保証を与えます。
  論文  参考訳（メタデータ） (2024-05-06T17:38:20Z)
• Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions [19.537289123577022]
  有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。 対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2024-01-02T07:46:33Z)
• Towards Understanding and Improving GFlowNet Training [71.85707593318297]
  本稿では,学習したサンプリング分布と目標報酬分布を比較するための効率的な評価手法を提案する。 本稿では,高解像度のx$,相対的エッジフローポリシーのパラメータ化,新しい軌道バランス目標を提案する。
  論文  参考訳（メタデータ） (2023-05-11T22:50:41Z)
• Scheduling with Speed Predictions [10.217102227210669]
  本稿では,ジョブの処理時間ではなく,マシンの速度が不明な速度ロスのスケジューリング問題について検討する。 我々の主な結果は、$mineta2 (1+epsilon)2 (1+epsilon)(2+2/alpha)$近似を達成するアルゴリズムである。 予測が正確であれば、この近似は以前最もよく知られた2-1/m$の近似よりも改善される。
  論文  参考訳（メタデータ） (2022-05-02T23:39:41Z)
• Deep Equilibrium Optical Flow Estimation [80.80992684796566]
  最近のSOTA(State-of-the-art)光フローモデルでは、従来のアルゴリズムをエミュレートするために有限ステップの更新操作を使用する。 これらのRNNは大きな計算とメモリオーバーヘッドを課し、そのような安定した推定をモデル化するために直接訓練されていない。 暗黙的層の無限レベル固定点として直接流れを解く手法として,Deep equilibrium Flow estimatorを提案する。
  論文  参考訳（メタデータ） (2022-04-18T17:53:44Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。 本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。 実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
  論文  参考訳（メタデータ） (2022-02-22T18:37:23Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Online Multivalid Learning: Means, Moments, and Prediction Intervals [16.75129633574157]
  本稿では,様々な意味で「多値」な文脈予測手法を提案する。 得られた見積もりは、単に限界ではなく、$ Y$ラベルのさまざまな統計を正しく予測します。 我々のアルゴリズムは逆選択の例を扱うので、任意の点予測法の残差の統計量を予測するのに等しく使用できる。
  論文  参考訳（メタデータ） (2021-01-05T19:08:11Z)
• Leveraging Predictions in Smoothed Online Convex Optimization via Gradient-based Algorithms [18.64335888217192]
  オンライン凸最適化は、時間的変化のあるステージコストと追加のスイッチングコストで検討する。 スイッチングコストはすべてのステージにカップリングをもたらすため、長期的な予測は品質の低下に悩まされる傾向がある。 本稿では,勾配に基づくオンラインアルゴリズムReceding Horizon Inexact Gradient (RHIG)を導入し,その性能を動的後悔によって解析する。
  論文  参考訳（メタデータ） (2020-11-25T06:25:51Z)
• Consistent Structured Prediction with Max-Min Margin Markov Networks [84.60515484036239]
  二項分類のためのマックスマージン法は、最大マージンマルコフネットワーク(M3N$)の名前で構造化予測設定まで拡張されている。 我々は、学習問題を"max-min"マージンの定式化で定義し、結果のメソッドmax-minマージンマルコフネットワーク(M4N$)を命名することで、そのような制限を克服する。 マルチクラス分類,順序回帰,シーケンス予測,ランキング実験により,提案手法の有効性が示された。
  論文  参考訳（メタデータ） (2020-07-02T10:48:42Z)

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

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