論文の概要: Warm-starting Push-Relabel

• arxiv url: http://arxiv.org/abs/2405.18568v1
• Date: Tue, 28 May 2024 20:26:05 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-30 21:53:22.879173
• Title: Warm-starting Push-Relabel
• Title（参考訳）: ウォームスタートPush-Relabel
• Authors: Sami Davies, Sergei Vassilvitskii, Yuyan Wang,
• Abstract要約: Push-Relabelは、最も有名なネットワークフローアルゴリズムの1つである。 我々は、予測フローで温度上昇開始するPush-Relabelに関する最初の理論的保証を提供する。 次に、ウォームスタートしたPush-Relabelが実際にうまく動作することを示す実験を紹介します。
• 参考スコア（独自算出の注目度）: 14.331671559400835
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Push-Relabel is one of the most celebrated network flow algorithms. Maintaining a pre-flow that saturates a cut, it enjoys better theoretical and empirical running time than other flow algorithms, such as Ford-Fulkerson. In practice, Push-Relabel is even faster than what theoretical guarantees can promise, in part because of the use of good heuristics for seeding and updating the iterative algorithm. However, it remains unclear how to run Push-Relabel on an arbitrary initialization that is not necessarily a pre-flow or cut-saturating. We provide the first theoretical guarantees for warm-starting Push-Relabel with a predicted flow, where our learning-augmented version benefits from fast running time when the predicted flow is close to an optimal flow, while maintaining robust worst-case guarantees. Interestingly, our algorithm uses the gap relabeling heuristic, which has long been employed in practice, even though prior to our work there was no rigorous theoretical justification for why it can lead to run-time improvements. We then provide experiments that show our warm-started Push-Relabel also works well in practice.
• Abstract（参考訳）: Push-Relabelは、最も有名なネットワークフローアルゴリズムの1つである。 カットを飽和させるプレフローを維持することで、Ford-Fulkersonのような他のフローアルゴリズムよりも理論的および経験的な実行時間を楽しむことができる。 実際には、Push-Relabelは理論的な保証が約束できるものよりも高速である。 しかし、Push-Relabelを任意の初期化で実行する方法は、必ずしもプレフローやカット飽和ではない。 我々は,予測フローでPush-Relabelを温めるための最初の理論的保証を提供する。 興味深いことに、我々のアルゴリズムは長い間使われてきたギャップを許容するヒューリスティックを使っており、我々の研究以前には、それが実行時改善に繋がる理由に関する厳密な理論的正当化は存在しなかった。 次に、ウォームスタートしたPush-Relabelが実際にうまく動作することを示す実験を紹介します。

関連論文リスト

• Sparse is Enough in Fine-tuning Pre-trained Large Language Models [98.46493578509039]
  我々はSparse Increment Fine-Tuning (SIFT) という勾配に基づくスパース微調整アルゴリズムを提案する。 GLUE Benchmark や Instruction-tuning などのタスクで有効性を検証する。
  論文  参考訳（メタデータ） (2023-12-19T06:06:30Z)
• Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz [66.22095739795068]
  符号ベースの手法は、パラメータ更新にのみ符号情報を使用するにもかかわらず、堅牢な性能を達成する能力によって注目されている。 符号に基づく手法の現在の収束解析は、一階加速度と二階加速度の強い仮定に依存する。 本稿では,より現実的な第1次および第2次加速度の仮定の下で,それらの収束を解析する。
  論文  参考訳（メタデータ） (2023-10-23T06:48:43Z)
• FuzzyFlow: Leveraging Dataflow To Find and Squash Program Optimization Bugs [92.47146416628965]
  FuzzyFlowはプログラム最適化をテストするために設計されたフォールトローカライゼーションとテストケース抽出フレームワークである。 我々は、データフロープログラム表現を活用して、完全に再現可能なシステム状態と最適化のエリア・オブ・エフェクトをキャプチャする。 テスト時間を削減するため,テスト入力を最小限に抑えるアルゴリズムを設計し,再計算のためのメモリ交換を行う。
  論文  参考訳（メタデータ） (2023-06-28T13:00:17Z)
• (Almost) Provable Error Bounds Under Distribution Shift via Disagreement Discrepancy [8.010528849585937]
  我々は、ラベルのないテストデータを用いて、分散シフト中のディープニューラルネットワークのエラーに対して(ほぼ)保証された上限を導出する。 特に、我々の境界は単純で直感的な条件を必要とし、これは以前の経験的な研究によって十分に正当化される。 この損失は、マルチクラス不一致の最大化を必要とする将来のメソッドのドロップイン代替になることを期待しています。
  論文  参考訳（メタデータ） (2023-06-01T03:22:15Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  本稿では,ニューラルネットワークのための新しい学習フレームワークであるCascaded Forward(CaFo)アルゴリズムを提案する。 FFとは異なり、我々のフレームワークは各カスケードブロックのラベル分布を直接出力する。 我々のフレームワークでは、各ブロックは独立して訓練できるので、並列加速度システムに容易に展開できる。
  論文  参考訳（メタデータ） (2023-03-17T02:01:11Z)
• Practical Network Acceleration with Tiny Sets: Hypothesis, Theory, and Algorithm [38.742142493108744]
  そこで本研究では,小さなトレーニングセットのみを用いてネットワークを高速化するアルゴリズムを提案する。 22%のレイテンシ削減のために、ImageNet-1kでは、平均7パーセントのポイントで、従来の方法を上回っている。
  論文  参考訳（メタデータ） (2023-03-02T05:10:31Z)
• A Stable, Fast, and Fully Automatic Learning Algorithm for Predictive Coding Networks [65.34977803841007]
  予測符号化ネットワークは、ベイズ統計学と神経科学の両方にルーツを持つ神経科学にインスパイアされたモデルである。 シナプス重みに対する更新規則の時間的スケジュールを変更するだけで、元の規則よりもずっと効率的で安定したアルゴリズムが得られることを示す。
  論文  参考訳（メタデータ） (2022-11-16T00:11:04Z)
• Learning-Augmented Maximum Flow [3.0712335337791288]
  本稿では,予測を用いて最大流れ計算を高速化するフレームワークを提案する。 我々は,$m$のエッジフローネットワークと予測フローが与えられた場合,最大フローを$O(meta)$時間で計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-26T14:02:41Z)
• Formalizing Preferences Over Runtime Distributions [25.899669128438322]
  アルゴリズムよりも好みを記述したスコアリング関数を特徴付けるために,ユーティリティ理論のアプローチを用いる。 本稿では,不特定容量分布のモデル化における最大エントロピー手法の活用法を示す。
  論文  参考訳（メタデータ） (2022-05-25T19:43:48Z)
• Convolutional Sparse Coding Fast Approximation with Application to Seismic Reflectivity Estimation [9.005280130480308]
  2～5回の反復で畳み込みスパース符号の良好な近似を生成する古典的反復しきい値アルゴリズムの高速化版を提案する。 提案手法の性能は, 合成シナリオと実データシナリオの両方において, 地震インバージョン問題によって実証される。
  論文  参考訳（メタデータ） (2021-06-29T12:19:07Z)
• Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
  未知(典型的には非生成)関数を有界ノルムで最適化する問題を考察する。 我々は「高速だが非ローバスト」と「スロー」に基づく高速スローGP-UCBに基づくアルゴリズムを提案する。 ある種の依存関係は、汚職レベルによっては要求できない、と我々は主張する。
  論文  参考訳（メタデータ） (2020-03-04T09:46:58Z)

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

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