論文の概要: A No-Free-Lunch Theorem for MultiTask Learning
- arxiv url: http://arxiv.org/abs/2006.15785v4
- Date: Wed, 5 Aug 2020 18:05:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 14:12:44.529663
- Title: A No-Free-Lunch Theorem for MultiTask Learning
- Title（参考訳）: マルチタスク学習のためのノーランチ理論
- Authors: Steve Hanneke and Samory Kpotufe
- Abstract要約: すべてのタスク$P_t$が共通の最適分類器$h*,$を共有する、一見好都合な分類シナリオを考える。
このようなレジームは、$n$と$N$の両方のミニマックスレートを許容するが、適応アルゴリズムは存在しない。
- 参考スコア（独自算出の注目度）: 19.645741778058227
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multitask learning and related areas such as multi-source domain adaptation
address modern settings where datasets from $N$ related distributions $\{P_t\}$
are to be combined towards improving performance on any single such
distribution ${\cal D}$. A perplexing fact remains in the evolving theory on
the subject: while we would hope for performance bounds that account for the
contribution from multiple tasks, the vast majority of analyses result in
bounds that improve at best in the number $n$ of samples per task, but most
often do not improve in $N$. As such, it might seem at first that the
distributional settings or aggregation procedures considered in such analyses
might be somehow unfavorable; however, as we show, the picture happens to be
more nuanced, with interestingly hard regimes that might appear otherwise
favorable.
In particular, we consider a seemingly favorable classification scenario
where all tasks $P_t$ share a common optimal classifier $h^*,$ and which can be
shown to admit a broad range of regimes with improved oracle rates in terms of
$N$ and $n$. Some of our main results are as follows:
$\bullet$ We show that, even though such regimes admit minimax rates
accounting for both $n$ and $N$, no adaptive algorithm exists; that is, without
access to distributional information, no algorithm can guarantee rates that
improve with large $N$ for $n$ fixed.
$\bullet$ With a bit of additional information, namely, a ranking of tasks
$\{P_t\}$ according to their distance to a target ${\cal D}$, a simple
rank-based procedure can achieve near optimal aggregations of tasks' datasets,
despite a search space exponential in $N$. Interestingly, the optimal
aggregation might exclude certain tasks, even though they all share the same
$h^*$.
- Abstract（参考訳）: マルチタスク学習やマルチソースドメイン適応といった関連分野は、n$ 関連ディストリビューションのデータセットを$\{p_t\}$ から組み合わせて、このようなディストリビューション ${\cal d}$ でパフォーマンスを向上させるという、現代的な設定に対処している。
複数のタスクからの寄与を考慮に入れたパフォーマンスバウンダリを期待する一方で、ほとんどの分析結果は、タスク当たりのサンプル数$n$でベストに改善されるバウンダリをもたらすが、ほとんどの場合、$N$では改善されない。
このように、このような分析で考慮された分布的設定や集約手順は、一見すると好ましくないかもしれないが、私たちが示すように、この図は、たまたま、よりニュアンスで、他の場合は好ましくないような、興味深いほど硬い状態である。
特に私たちは,すべてのタスクが共通の最適分類器である$h^*,$を共有して,n$とn$という面でoracleレートが向上した広範なレジームを許容できるような,好都合な分類シナリオを考えています。
以下の結果が得られた: $\bullet$ このようなレジームは、n$ と $n$の両方を占めるミニマックスレートを認めているが、適応アルゴリズムは存在しない。
目的の${\cal d}$ までの距離に応じてタスクのランキングが$\{p_t\}$ という追加情報を持つ$\bullet$ 単純なランクベースの手順は、検索スペースが$n$で指数関数的であるにもかかわらず、タスクのデータセットのほぼ最適な集約を実現できる。
興味深いことに、最適な集約は、すべて同じ$h^*$を共有しているにもかかわらず、特定のタスクを除外するかもしれない。
関連論文リスト
- Metalearning with Very Few Samples Per Task [19.78398372660794]
タスクが共有表現によって関連づけられるバイナリ分類について検討する。
ここでは、データ量は、見る必要のあるタスク数$t$と、タスク当たりのサンプル数$n$で測定されます。
我々の研究は、分布のないマルチタスク学習の特性とメタとマルチタスク学習の削減をもたらす。
論文 参考訳（メタデータ） (2023-12-21T16:06:44Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Minimax Optimal Algorithms with Fixed-$k$-Nearest Neighbors [13.231906521852718]
大規模なデータセットを小さなグループに分割する分散学習シナリオを考察する。
分類,回帰,密度推定のための固定k$-NN情報を集約する最適ルールを提案する。
十分多数のグループに固定された$k$の分散アルゴリズムは、乗算対数係数までの最小誤差率を得ることを示す。
論文 参考訳（メタデータ） (2022-02-05T01:59:09Z) - Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
我々は、リッチな観測空間を持つより現実的な非依存的RLの設定と、近似的ポリシーを含まないような固定されたポリシーのクラス$Pi$を考える。
我々は,MDPの階数$d$の誤差が有界な設定のためのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-22T03:20:40Z) - On the Power of Multitask Representation Learning in Linear MDP [61.58929164172968]
本稿では,線形マルコフ決定過程(MDP)におけるマルチタスク表現学習の統計的メリットについて分析する。
簡単な最小二乗アルゴリズムが $tildeO(H2sqrtfrackappa MathcalC(Phi)2 kappa dNT+frackappa dn) というポリシーを学ぶことを証明した。
論文 参考訳（メタデータ） (2021-06-15T11:21:06Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。