論文の概要: Dimension Reduction in Contextual Online Learning via Nonparametric
Variable Selection
- arxiv url: http://arxiv.org/abs/2009.08265v2
- Date: Mon, 3 Oct 2022 03:38:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-17 08:34:58.992664
- Title: Dimension Reduction in Contextual Online Learning via Nonparametric
Variable Selection
- Title（参考訳）: 非パラメトリック変数選択による文脈オンライン学習における次元削減
- Authors: Wenhao Li, Ningyuan Chen, L. Jeff Hong
- Abstract要約: 文献によれば、最適の後悔は$tildeO(T(d_x*+d_y+1)/(d_x*+d_y+2))$である。
我々は,非パラメトリックな設定にLASSOを適用するために,ビンニングや投票などの新しいアイデアを取り入れたtextitBV-LASSO という変数選択アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 8.250528027387196
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a contextual online learning (multi-armed bandit) problem with
high-dimensional covariate $\mathbf{x}$ and decision $\mathbf{y}$. The reward
function to learn, $f(\mathbf{x},\mathbf{y})$, does not have a particular
parametric form. The literature has shown that the optimal regret is
$\tilde{O}(T^{(d_x+d_y+1)/(d_x+d_y+2)})$, where $d_x$ and $d_y$ are the
dimensions of $\mathbf x$ and $\mathbf y$, and thus it suffers from the curse
of dimensionality. In many applications, only a small subset of variables in
the covariate affect the value of $f$, which is referred to as
\textit{sparsity} in statistics. To take advantage of the sparsity structure of
the covariate, we propose a variable selection algorithm called
\textit{BV-LASSO}, which incorporates novel ideas such as binning and voting to
apply LASSO to nonparametric settings. Our algorithm achieves the regret
$\tilde{O}(T^{(d_x^*+d_y+1)/(d_x^*+d_y+2)})$, where $d_x^*$ is the effective
covariate dimension. The regret matches the optimal regret when the covariate
is $d^*_x$-dimensional and thus cannot be improved. Our algorithm may serve as
a general recipe to achieve dimension reduction via variable selection in
nonparametric settings.
- Abstract（参考訳）: 我々は、高次元共変量 $\mathbf{x}$ と決定 $\mathbf{y}$ を持つ文脈的オンライン学習(多武装バンディット)問題を考える。
学習する報酬関数 $f(\mathbf{x},\mathbf{y})$ は、特定のパラメトリック形式を持たない。
文献によれば、最適後悔は$\tilde{O}(T^{(d_x+d_y+1))/(d_x+d_y+2)})$であり、$d_x$と$d_y$は$\mathbf x$と$\mathbf y$の次元であり、従って次元の呪いに苦しむ。
多くのアプリケーションでは、共変量の変数の小さなサブセットのみが$f$の値に影響し、統計学では \textit{sparsity} と呼ばれる。
共変量体の疎度構造を生かした変数選択アルゴリズムである「textit{BV-LASSO}」を提案する。
我々のアルゴリズムは, 後悔の$\tilde{O}(T^{(d_x^*+d_y+1))/(d_x^*+d_y+2)})$, ここで$d_x^*$は有効共変次元である。
後悔は、共変量が$d^*_x$-dimensionalであるときに最適な後悔と一致し、改善できない。
本アルゴリズムは,非パラメトリック設定における可変選択による次元減少を実現するための一般的なレシピとして機能する。
関連論文リスト
- Online Learning of Halfspaces with Massart Noise [47.71073318490341]
我々はMassartノイズの存在下でのオンライン学習の課題について検討する。
計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。
我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-05-21T17:31:10Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z) - Combinatorial Semi-Bandit in the Non-Stationary Environment [27.394284055156795]
スイッチングケースと動的ケースの両方において,非定常半帯域問題について検討する。
別の手法を用いることで、我々のアルゴリズムは $mathcal S$ あるいは $mathcal V$ のパラメータをもはや知る必要がなくなるが、後悔する境界は準最適になる可能性がある。
論文 参考訳（メタデータ） (2020-02-10T07:10:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。