論文の概要: A Smoothed Analysis of Online Lasso for the Sparse Linear Contextual Bandit Problem

• arxiv url: http://arxiv.org/abs/2007.08561v1
• Date: Thu, 16 Jul 2020 18:48:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-09 22:22:11.968557
• Title: A Smoothed Analysis of Online Lasso for the Sparse Linear Contextual Bandit Problem
• Title（参考訳）: Sparse Linear Contextual Bandit 問題に対するオンラインラッソの平滑化解析
• Authors: Zhiyuan Liu, Huazheng Wang, Bo Waggoner, Youjian (Eugene) Liu, Lijun Chen
• Abstract要約: 簡単なオンラインのLassoは、残酷な$mathcalO(sqrtkTlog d)$で、疎線形コンテキストバンドリットをサポートすることを証明している。 この結果の特別な構造は、摂動が探査期間にどのように影響するかを明確に特徴付ける。
• 参考スコア（独自算出の注目度）: 25.5073029104128
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the sparse linear contextual bandit problem where the parameter $\theta$ is sparse. To relieve the sampling inefficiency, we utilize the "perturbed adversary" where the context is generated adversarilly but with small random non-adaptive perturbations. We prove that the simple online Lasso supports sparse linear contextual bandit with regret bound $\mathcal{O}(\sqrt{kT\log d})$ even when $d \gg T$ where $k$ and $d$ are the number of effective and ambient dimension, respectively. Compared to the recent work from Sivakumar et al. (2020), our analysis does not rely on the precondition processing, adaptive perturbation (the adaptive perturbation violates the i.i.d perturbation setting) or truncation on the error set. Moreover, the special structures in our results explicitly characterize how the perturbation affects exploration length, guide the design of perturbation together with the fundamental performance limit of perturbation method. Numerical experiments are provided to complement the theoretical analysis.
• Abstract（参考訳）: パラメータ$\theta$がスパースであるスパース線形文脈帯域問題について検討する。 サンプリング非効率を緩和するために、コンテキストが逆向きに生成されるが、ランダムな非適応的摂動が小さい「摂動逆」を用いる。 簡単なオンラインラッソは、$d \gg T$ が有効次元の個数であり、$k$ と $d$ が実効次元および周辺次元の個数である場合でも、残差が $\mathcal{O}(\sqrt{kT\log d})$ でスパース線形文脈帯域をサポートすることを証明している。 Sivakumar et al. (2020) の最近の研究と比較すると、我々の分析は事前条件処理、適応摂動(適応摂動はi.dの摂動設定に反する)、あるいは誤差セットのトランケーションに依存していない。 さらに, 本研究の特殊構造は, 摂動が探査期間に与える影響を明示し, 摂動法の基本的な性能限界とともに摂動の設計を導く。 理論的解析を補完する数値実験が提供されている。

関連論文リスト

• Lasso Bandit with Compatibility Condition on Optimal Arm [10.216425987201333]
  文脈特徴のスパース部分のみが期待される報酬関数に影響を及ぼすような疎線型バンドイット問題を考える。 本稿では,強制サンプリング手法を適用したアルゴリズムを提案し,提案アルゴリズムが$O(textpolylog dT)$ regretを達成したことを証明した。
  論文  参考訳（メタデータ） (2024-06-02T18:11:47Z)
• FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Bandits [8.908421753758475]
  高次元スパース線形帯域は、シーケンシャルな意思決定問題の効率的なモデルとして機能する。 データプライバシの懸念により、我々は、共同でプライベートな高次元の疎線形帯域について検討する。 FLIPHATは,プライバシパラメータの点で最適に後悔することを示す。
  論文  参考訳（メタデータ） (2024-05-22T22:19:12Z)
• Exploration via linearly perturbed loss minimisation [4.856378369489158]
  本稿では,構造的バンディット問題に対する線形損失摂動(EVILL)による探索を紹介する。 一般化された線形包帯の場合、EVILLは乱れ歴史探索(PHE)に還元され、ランダムな乱れ報酬のトレーニングによって探索が行われる。 本稿では,従来のPHE方式では存在しないデータ依存摂動について提案する。
  論文  参考訳（メタデータ） (2023-11-13T18:54:43Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback [98.7678704343537]
  我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。 我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
  論文  参考訳（メタデータ） (2022-05-15T08:27:12Z)
• LSDAT: Low-Rank and Sparse Decomposition for Decision-based Adversarial Attack [74.5144793386864]
  LSDATは、入力サンプルのスパース成分と対向サンプルのスパース成分によって形成される低次元部分空間における摂動を加工する。 LSDは画像ピクセル領域で直接動作し、スパース性などの非$ell$制約が満たされることを保証します。
  論文  参考訳（メタデータ） (2021-03-19T13:10:47Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。