論文の概要: Multitask Learning via Shared Features: Algorithms and Hardness
- arxiv url: http://arxiv.org/abs/2209.03112v1
- Date: Wed, 7 Sep 2022 13:04:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-08 13:13:27.137174
- Title: Multitask Learning via Shared Features: Algorithms and Hardness
- Title(参考訳): 共有機能によるマルチタスク学習:アルゴリズムとハードネス
- Authors: Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan Ullman, Lydia
Zakynthinou
- Abstract要約: マージン$gamma$のハーフスペースの概念クラスに対する時間学習アルゴリズムを提案する。
さらに,属性効率モデルでは学べない概念クラスが存在すると仮定すると,属性効率モデルでは学べるが効率的に学べない概念クラスを構築することができることを示す。
- 参考スコア(独自算出の注目度): 14.45796459531414
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the computational efficiency of multitask learning of Boolean
functions over the $d$-dimensional hypercube, that are related by means of a
feature representation of size $k \ll d$ shared across all tasks. We present a
polynomial time multitask learning algorithm for the concept class of
halfspaces with margin $\gamma$, which is based on a simultaneous boosting
technique and requires only $\textrm{poly}(k/\gamma)$ samples-per-task and
$\textrm{poly}(k\log(d)/\gamma)$ samples in total.
In addition, we prove a computational separation, showing that assuming there
exists a concept class that cannot be learned in the attribute-efficient model,
we can construct another concept class such that can be learned in the
attribute-efficient model, but cannot be multitask learned efficiently --
multitask learning this concept class either requires super-polynomial time
complexity or a much larger total number of samples.
- Abstract(参考訳): すべてのタスクで共有されるサイズ$k \ll d$の特徴表現によって関連づけられた$d$-dimensional hypercube上のブール関数のマルチタスク学習の計算効率について検討する。
ハーフスペースを持つ概念クラスに対して多項式時間マルチタスク学習アルゴリズムを提案する。これは同時ブースティング手法に基づいており、サンプル当たり$\textrm{poly}(k/\gamma)$サンプルと$\textrm{poly}(k\log(d)/\gamma)$サンプルのみを必要とする。
さらに,属性効率モデルでは学習できない概念クラスが存在すると仮定して,属性効率モデルでは学習できないがマルチタスクでは効率的に学習できない概念クラスを構築することができることを示す。
関連論文リスト
- Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations [40.77319247558742]
目的関数 $f_*:mathbbRdtomathbbR$ を加法構造で学習する際の計算複雑性について検討する。
2層ニューラルネットワークの勾配学習により,$f_*$の大規模なサブセットを効率的に学習できることを実証した。
論文 参考訳(メタデータ) (2024-06-17T17:59:17Z) - Provable Benefits of Multi-task RL under Non-Markovian Decision Making
Processes [56.714690083118406]
マルコフ決定過程 (MDP) 下でのマルチタスク強化学習 (RL) において, 共有潜在構造の存在は, シングルタスクRLと比較して, サンプル効率に有意な利益をもたらすことが示されている。
このような利点が、部分的に観測可能なMDP(POMDP)やより一般的な予測状態表現(PSR)といった、より一般的なシーケンシャルな意思決定問題にまで拡張できるかどうかを検討する。
提案手法は,全てのPSRに対してほぼ最適ポリシーを求めるための,証明可能なアルゴリズム UMT-PSR を提案し,PSR の合同モデルクラスが有するマルチタスク学習の利点が示されることを示す。
論文 参考訳(メタデータ) (2023-10-20T14:50:28Z) - Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks [69.38572074372392]
本稿では,複数タスクにおける非線形モデルを用いたトレーニング中に特徴学習が発生することを示す最初の結果を示す。
私たちのキーとなる洞察は、マルチタスク事前トレーニングは、通常タスク間で同じラベルを持つポイントを整列する表現を好む擬似コントラスト的損失を誘導するということです。
論文 参考訳(メタデータ) (2023-07-13T16:39:08Z) - Improved Active Multi-Task Representation Learning via Lasso [44.607652031235716]
本稿では,L1-regularized-relevance-based(nu1$)戦略の優位性を示す。
また、サンプルコストに敏感な設定で$nu1$ベースの戦略の可能性を特徴付けます。
論文 参考訳(メタデータ) (2023-06-05T03:08:29Z) - Joint Representation Training in Sequential Tasks with Shared Structure [40.1056491921582]
マルチタスク行列RLの設定のための共有行列RLアルゴリズムを提案する。
我々は$P$タスクに対する後悔を$O(PHdsqrtNH)$から$O((HdsqrtrP + HPsqrtrd)sqrtNH)$ over $N$ episodes of horizon$H$へと改善できることを示した。
論文 参考訳(メタデータ) (2022-06-24T18:10:00Z) - 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) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳(メタデータ) (2020-11-09T18:32:22Z) - 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) - Backward Feature Correction: How Deep Learning Performs Deep
(Hierarchical) Learning [66.05472746340142]
本稿では,SGD による階層的学習 _efficiently_ と _automatically_ を学習目標として,多層ニューラルネットワークがどのように行うかを分析する。
我々は、下位機能のエラーを上位層と共にトレーニングする際に自動的に修正できる"後方特徴補正"と呼ばれる新しい原則を確立する。
論文 参考訳(メタデータ) (2020-01-13T17:28:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。