Fugu-MT 論文翻訳(概要): Pure Exploration and Regret Minimization in Matching Bandits

論文の概要: Pure Exploration and Regret Minimization in Matching Bandits

arxiv url: http://arxiv.org/abs/2108.00230v1
Date: Sat, 31 Jul 2021 12:37:51 GMT
ステータス: 処理完了
システム内更新日: 2021-08-03 15:35:22.548654
Title: Pure Exploration and Regret Minimization in Matching Bandits
Title（参考訳）: マッチング帯域における純粋探索とレグレット最小化
Authors: Flore Sentenac, Jialin Yi, Cl\'ement Calauz\`enes, Vianney Perchet, Milan Vojnovic
Abstract要約: 本研究では, 隣接行列上のランク1の仮定を利用して, サンプルの複雑さを低減できることを証明した。重み付きグラフで最適なマッチングを見つけることは、標準的な問題である。
参考スコア（独自算出の注目度）: 19.205538784019936
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Finding an optimal matching in a weighted graph is a standard combinatorial problem. We consider its semi-bandit version where either a pair or a full matching is sampled sequentially. We prove that it is possible to leverage a rank-1 assumption on the adjacency matrix to reduce the sample complexity and the regret of off-the-shelf algorithms up to reaching a linear dependency in the number of vertices (up to poly log terms).
Abstract（参考訳）: 重み付きグラフにおける最適マッチングを見つけることは標準組合せ問題である。ペアか完全マッチングのいずれかが順次サンプリングされる半帯域バージョンについて検討する。隣接行列上の rank-1 の仮定を活用し、標本の複雑さとオフ・ザ・シェルフアルゴリズムの後悔を減少させ、頂点数(ポリログ項まで)の線形依存性に達することを証明できる。

関連論文リスト

An SDP-based Branch-and-Cut Algorithm for Biclustering [0.0]
本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
論文参考訳（メタデータ） (2024-03-17T21:43:19Z)
Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling [10.824999179337558]
行列全体よりも小さい部分行列上で推定アルゴリズムを実行する方がよく、時には最適であることを示す。我々の境界は、各エントリを局所的なサンプリング確率の関数として推定する難しさを特徴付ける。
論文参考訳（メタデータ） (2024-02-29T23:24:43Z)
An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文参考訳（メタデータ） (2023-06-15T15:37:31Z)
Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
我々は、一様収束論の極限を超えるフレームワークを通して、最適な高確率リスク境界を提供する。我々のフレームワークは、置換不変予測器の残余誤差を高い確率リスク境界に変換する。具体的には, 1-inclusion graph アルゴリズムの特定のアグリゲーションが最適であることを示す。
論文参考訳（メタデータ） (2023-04-18T17:57:31Z)
Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。予測と高い確率で、新しい過剰なリスク境界を提供する。我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文参考訳（メタデータ） (2022-11-03T12:40:24Z)
On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
ランダム・座標降下法(PURE-CD)を用いた原始双対アルゴリズムの複雑性境界を証明した。バイマックス性能問題を解くための優れた外挿が得られることが示されている。
論文参考訳（メタデータ） (2022-01-19T16:14:27Z)
Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文参考訳（メタデータ） (2022-01-05T13:37:27Z)
Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文参考訳（メタデータ） (2021-11-14T21:49:58Z)
An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-21T00:56:33Z)
Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文参考訳（メタデータ） (2020-04-23T05:00:21Z)

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