論文の概要: Learning-Augmented Online Bipartite Fractional Matching

• arxiv url: http://arxiv.org/abs/2505.19252v1
• Date: Sun, 25 May 2025 18:15:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 16:58:43.006171
• Title: Learning-Augmented Online Bipartite Fractional Matching
• Title（参考訳）: オンライン二部分節マッチングの学習支援
• Authors: Davin Choo, Billy Jin, Yongho Shin,
• Abstract要約: 各反復において提案されたマッチングの形式でアルゴリズムにアドバイスが与えられたとき、オンライン二部分数マッチングについて検討する。 我々のアルゴリズムは、アドバイスフォローとアドバイスフリーのアルゴリズムをランダムに選択する単純な「コインフリップ」戦略を支配している。 任意のアルゴリズムで達成可能な堅牢性と一貫性のトレードオフに縛られる硬さを確立する。
• 参考スコア（独自算出の注目度）: 7.721815606607016
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online bipartite matching is a fundamental problem in online optimization, extensively studied both in its integral and fractional forms due to its theoretical significance and practical applications, such as online advertising and resource allocation. Motivated by recent progress in learning-augmented algorithms, we study online bipartite fractional matching when the algorithm is given advice in the form of a suggested matching in each iteration. We develop algorithms for both the vertex-weighted and unweighted variants that provably dominate the naive "coin flip" strategy of randomly choosing between the advice-following and advice-free algorithms. Moreover, our algorithm for the vertex-weighted setting extends to the AdWords problem under the small bids assumption, yielding a significant improvement over the seminal work of Mahdian, Nazerzadeh, and Saberi (EC 2007, TALG 2012). Complementing our positive results, we establish a hardness bound on the robustness-consistency tradeoff that is attainable by any algorithm. We empirically validate our algorithms through experiments on synthetic and real-world data.
• Abstract（参考訳）: オンライン二分法マッチングはオンライン最適化における基本的な問題であり、その理論的重要性とオンライン広告や資源配分といった実践的応用により、その積分形式と分数形の両方で広く研究されている。 学習強化アルゴリズムの最近の進歩に触発され、各反復において提案されたマッチングの形でアルゴリズムにアドバイスが与えられたときに、オンライン二部分数マッチングを研究する。 我々は,提案アルゴリズムとアドバイスフリーアルゴリズムをランダムに選択する「コインフリップ」戦略を確実に支配する頂点重み付き変種と非重み付き変種の両方のアルゴリズムを開発する。 さらに, 頂点重み設定のアルゴリズムは, 小さな入札仮定の下でAdWords問題に拡張され, Mahdian, Nazerzadeh, Saberi (EC 2007 TALG 2012) のセミナーよりも大幅に改善された。 ポジティブな結果を補うことで、どんなアルゴリズムでも達成可能な堅牢性と一貫性のトレードオフに縛られる硬さを確立します。 我々は、合成および実世界のデータに関する実験を通じて、我々のアルゴリズムを実証的に検証する。

関連論文リスト

• Efficient Methods for Non-stationary Online Learning [61.63338724659592]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 また、さらに強化された測度、すなわち「インターバル・ダイナミック・リピート」を研究し、ラウンド当たりの射影数を$mathcalO(log2 T)$から$$$$に減らした。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  大規模ネットワークにおける最適なソース配置をオンラインで学習するためのグラフカーネルマルチアームバンディットアルゴリズムであるGrab-UCBを提案する。 適応グラフ辞書モデルを用いて,ネットワークプロセスを記述する。 我々は、ネットワークパラメータに依存する性能保証を導出し、シーケンシャルな意思決定戦略の学習曲線にさらに影響を及ぼす。
  論文  参考訳（メタデータ） (2023-07-07T15:03:42Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  本稿では,UnRolled Federated Learning (SURF)を導入する。 提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
  論文  参考訳（メタデータ） (2023-05-24T17:26:22Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  バイレベル最適化は、幅広い機械学習モデルに適用されている。 既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。 そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-30T05:29:52Z)
• An Improved Reinforcement Learning Algorithm for Learning to Branch [12.27934038849211]
  ブランチ・アンド・バウンド(B&B)は最適化の一般的な方法である。 本稿では,新しい強化学習に基づくB&Bアルゴリズムを提案する。 提案アルゴリズムの性能を3つの公開研究ベンチマークで評価した。
  論文  参考訳（メタデータ） (2022-01-17T04:50:11Z)
• Adversarial Deep Learning for Online Resource Allocation [12.118811903399951]
  私たちはディープニューラルネットワークを使って、リソース割り当てと価格の問題に対するオンラインアルゴリズムをゼロから学習しています。 私たちの研究は、最悪のパフォーマンス保証の観点から、ディープニューラルネットワークを使用してオンラインアルゴリズムを設計した初めてのものです。
  論文  参考訳（メタデータ） (2021-11-19T15:48:43Z)
• Of Moments and Matching: Trade-offs and Treatments in Imitation Learning [26.121994149869767]
  我々は、モーメントマッチングのレンズを通して、過去の模倣学習アルゴリズムの大規模なファミリの統一ビューを提供する。 学習者と専門家の行動の相違を考慮することで、政策パフォーマンスの限界を導出することができる。 AdVILとAdRILという2つの新しいアルゴリズムテンプレートを、強力な保証、シンプルな実装、競争力のある実証的パフォーマンスで導出します。
  論文  参考訳（メタデータ） (2021-03-04T18:57:11Z)
• Online Deterministic Annealing for Classification and Clustering [0.0]
  本稿では,クラスタリングと分類のためのオンラインプロトタイプベースの学習アルゴリズムを提案する。 本稿では,提案アルゴリズムが競合学習ニューラルネットワークを構成することを示し,その学習規則をオンライン近似アルゴリズムとして定式化する。
  論文  参考訳（メタデータ） (2021-02-11T04:04:21Z)
• Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training [10.14260510961573]
  機械学習アプローチを用いて、オンラインアロケーション(二部マッチング)のアルゴリズムを見つけるという課題に対処する。 本稿では,従来のオンライン予算マッチング問題であるAdWords問題に着目し,理論的および実用的意義の両面から考察する。
  論文  参考訳（メタデータ） (2020-10-16T14:33:11Z)

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

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