論文の概要: On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure
- arxiv url: http://arxiv.org/abs/2211.15129v1
- Date: Mon, 28 Nov 2022 08:40:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-29 14:46:18.247609
- Title: On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure
- Title（参考訳）: グローバル・ローカル構造をもつマルチタスク帯域における表現学習のサンプル複雑さについて
- Authors: Alessio Russo, Alexandre Proutiere
- Abstract要約: マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
- 参考スコア（独自算出の注目度）: 77.60508571062958
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the sample complexity of learning the optimal arm for
multi-task bandit problems. Arms consist of two components: one that is shared
across tasks (that we call representation) and one that is task-specific (that
we call predictor). The objective is to learn the optimal (representation,
predictor)-pair for each task, under the assumption that the optimal
representation is common to all tasks. Within this framework, efficient
learning algorithms should transfer knowledge across tasks. We consider the
best-arm identification problem for a fixed confidence, where, in each round,
the learner actively selects both a task, and an arm, and observes the
corresponding reward. We derive instance-specific sample complexity lower
bounds satisfied by any $(\delta_G,\delta_H)$-PAC algorithm (such an algorithm
identifies the best representation with probability at least $1-\delta_G$, and
the best predictor for a task with probability at least $1-\delta_H$). We
devise an algorithm OSRL-SC whose sample complexity approaches the lower bound,
and scales at most as $H(G\log(1/\delta_G)+ X\log(1/\delta_H))$, with $X,G,H$
being, respectively, the number of tasks, representations and predictors. By
comparison, this scaling is significantly better than the classical best-arm
identification algorithm that scales as $HGX\log(1/\delta)$.
- Abstract（参考訳）: マルチタスクバンディット問題に対する最適アーム学習のサンプル複雑性について検討した。
アームはタスク間で共有されるもの(表現と呼ぶもの)とタスク固有のもの(予測子と呼ばれるもの)の2つのコンポーネントで構成されています。
目的は、最適表現がすべてのタスクに共通であると仮定して、各タスクの最適な(表現、予測)ペアを学ぶことである。
このフレームワークでは、効率的な学習アルゴリズムはタスク間で知識を転送する必要がある。
各ラウンドにおいて、学習者はタスクとアームの両方を積極的に選択し、対応する報酬を観察する。
我々は、任意の$(\delta_g,\delta_h)$-pacアルゴリズムで満たされるインスタンス固有のサンプル複雑性下限を導出する(そのようなアルゴリズムは、最良表現を少なくとも1-\delta_g$、確率が少なくとも1-\delta_h$のタスクの最適予測器として識別する)。
我々は,サンプル複雑性が下限に近づくアルゴリズムosrl-scを考案し,最大で$h(g\log(1/\delta_g)+x\log(1/\delta_h))$,$x,g,h$ をそれぞれタスク数,表現数,予測値として拡張する。
比較として、このスケーリングは$hgx\log(1/\delta)$でスケールする古典的なベストアーム識別アルゴリズムよりもはるかに優れている。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Active Representation Learning for General Task Space with Applications
in Robotics [44.36398212117328]
本稿では,テキスト対話型表現学習のためのアルゴリズムフレームワークを提案する。
この枠組みの下では、双線型および特徴ベースの非線形ケースから一般的な非線形ケースまで、いくつかのインスタンス化を提供する。
我々のアルゴリズムは平均で20%-70%のベースラインを上回ります。
論文 参考訳（メタデータ） (2023-06-15T08:27:50Z) - Improved Active Multi-Task Representation Learning via Lasso [44.607652031235716]
本稿では,L1-regularized-relevance-based(nu1$)戦略の優位性を示す。
また、サンプルコストに敏感な設定で$nu1$ベースの戦略の可能性を特徴付けます。
論文 参考訳（メタデータ） (2023-06-05T03:08:29Z) - Globally Optimal Algorithms for Fixed-Budget Best Arm Identification [16.500749121196986]
すべての可能なパラメータに対する大域的最適化の結果,最適速度を特徴付ける。
遅延最適追跡(DOT)と呼ばれる概念的アルゴリズムを導入することで、この速度が実際に達成可能であることを示す。
論文 参考訳（メタデータ） (2022-06-09T17:42:19Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - Fast Learning for Renewal Optimization in Online Task Scheduling [18.935043109084543]
本稿では,リニューアル・リワードシステムのオンライン最適化について考察する。
タスク型ベクトルの確率分布は未知である。
提案アルゴリズムは,古典的なRobins-Monroイテレーションに従って更新される補助変数を用いる。
論文 参考訳（メタデータ） (2020-07-18T22:44:13Z) - A No-Free-Lunch Theorem for MultiTask Learning [19.645741778058227]
すべてのタスク$P_t$が共通の最適分類器$h*,$を共有する、一見好都合な分類シナリオを考える。
このようなレジームは、$n$と$N$の両方のミニマックスレートを許容するが、適応アルゴリズムは存在しない。
論文 参考訳（メタデータ） (2020-06-29T03:03:29Z) - On the Theory of Transfer Learning: The Importance of Task Diversity [114.656572506859]
一般的な関数クラス$mathcalF circ MathcalH$において、$f_j circ h$という形の関数によってパラメータ化される$t+1$タスクを考える。
多様なトレーニングタスクに対して、最初の$t$のトレーニングタスク間で共有表現を学ぶのに必要なサンプルの複雑さが、$C(mathcalH) + t C(mathcalF)$であることを示す。
論文 参考訳（メタデータ） (2020-06-20T20:33:59Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。