論文の概要: Online bipartite matching with imperfect advice

• arxiv url: http://arxiv.org/abs/2405.09784v1
• Date: Thu, 16 May 2024 03:04:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-17 15:30:35.790005
• Title: Online bipartite matching with imperfect advice
• Title（参考訳）: オンラインバイパーティイトマッチングと不完全なアドバイス
• Authors: Davin Choo, Themis Gouleakis, Chun Kai Ling, Arnab Bhattacharyya,
• Abstract要約: 本研究では, 学習強化手法が, 対向的到着モデルの下で1/2$-robustよりも厳密に優れた1-consistentと1-consistentの両方で成り立たないことを示す。 ランダム到着モデルでは,オンライン頂点に対する外部からのアドバイスを取り入れたアルゴリズムを設計するために,分散テストの手法を利用する方法を示す。
• 参考スコア（独自算出の注目度）: 22.9719415150789
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of online unweighted bipartite matching with $n$ offline vertices and $n$ online vertices where one wishes to be competitive against the optimal offline algorithm. While the classic RANKING algorithm of Karp et al. [1990] provably attains competitive ratio of $1-1/e > 1/2$, we show that no learning-augmented method can be both 1-consistent and strictly better than $1/2$-robust under the adversarial arrival model. Meanwhile, under the random arrival model, we show how one can utilize methods from distribution testing to design an algorithm that takes in external advice about the online vertices and provably achieves competitive ratio interpolating between any ratio attainable by advice-free methods and the optimal ratio of 1, depending on the advice quality.
• Abstract（参考訳）: オンラインの非重み付き二部マッチングと$n$オフラインの頂点と$n$オンラインの頂点との問題は、最適なオフラインアルゴリズムと競合することを望んでいる。 Karp et al [1990] の古典的 RANKing アルゴリズムは、1-1/e > 1/2$ の競合比を確実に達成するが、1-一貫性と1/2$-robust よりも厳密に優れた学習拡張法は存在しないことを示す。 一方, ランダム到着モデルでは, オンライン頂点に対する外部アドバイスを取り入れ, アドバイスフリーで達成可能な任意の比率と, アドバイス品質に応じて最適な1の比率を補間するアルゴリズムを設計するために, 分散テストの手法をいかに活用できるかを示す。

関連論文リスト

• Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
  各ラウンド$t$において、プレイヤーが2次的打撃コストと2次攻撃コストに応じてアクション$x_tをプレイし、アクションを切り替えるための2乗$ell$-normコストを加算する、スムーズなオンライン最適化(SOQO)問題について検討する。 この問題クラスは、スマートグリッド管理、適応制御、データセンター管理など、幅広いアプリケーションドメインと強いつながりを持っています。 本稿では, 最適に近い性能を同時に達成しつつ, 強健な対角性能を得るベスト・オブ・ザ・ワールドス・アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-31T22:59:23Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Optimal Best-Arm Identification in Bandits with Access to Offline Data [27.365122983434887]
  オフラインデータとオンライン学習を組み合わせることを検討する。 差分$が小さい場合、サンプルの複雑さに基づいて低い境界に一致するアルゴリズムを開発する。 我々のアルゴリズムは, サンプル当たりの平均取得コストが$tildeO(K)$で計算的に効率的であり, 下界問題の最適条件の注意深い評価に頼っている。
  論文  参考訳（メタデータ） (2023-06-15T11:12:35Z)
• Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees [28.737193318136725]
  我々は,ロバストネス保証 (LOMAR) を用いたエッジ重み付きオンラインバイパートイトマッチングの新しい手法を提案する。 LOMARは、平均ケースと最悪のケースのパフォーマンスの両方を達成する。
  論文  参考訳（メタデータ） (2023-05-31T20:41:42Z)
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion [56.92236659731376]
  本稿では,新しい解析手法を用いて,未知の非平滑な目的を最適化するアルゴリズムを提案する。 決定論的二階スムーズな目的のために、先進的な楽観的なオンライン学習技術を適用することで、新しい$O(delta0.5)All$が最適または最もよく知られた結果の回復を可能にする。
  論文  参考訳（メタデータ） (2023-02-07T22:09:20Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Online Adversarial Attacks [57.448101834579624]
  我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。 まず、オンライン脅威モデルの決定論的変種を厳格に分析する。 このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
  論文  参考訳（メタデータ） (2021-03-02T20:36:04Z)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)
• Online Learning with Vector Costs and Bandits with Knapsacks [8.340947016086739]
  オンライン学習にベクターコスト(OLVCp)を導入し、各時間に1,ldots,T$の$tのステップで、未知のベクターコストを発生させるアクションを実行する必要がある。 オンラインアルゴリズムの目標は、コストベクトルの和の$ell_p$ノルムを最小化することである。
  論文  参考訳（メタデータ） (2020-10-14T18:28:41Z)

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

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