論文の概要: Contextual Bandits with Online Neural Regression

• arxiv url: http://arxiv.org/abs/2312.07145v1
• Date: Tue, 12 Dec 2023 10:28:51 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-13 16:39:57.418887
• Title: Contextual Bandits with Online Neural Regression
• Title（参考訳）: オンラインニューラル回帰を用いた文脈帯域
• Authors: Rohan Deb, Yikun Ban, Shiliang Zuo, Jingrui He, Arindam Banerjee
• Abstract要約: オンライン回帰と関連するニューラルコンテキスト帯域(NeuCBs)におけるニューラルネットワークの利用について検討する。 既存の結果をワイドネットワークで使うと、$mathcalO(sqrtT)$ regretを2乗の損失でオンラインレグレッションで簡単に表示できる。 正方形損失とKL損失の両方を持つオンラインレグレッションに対して$mathcalO(log T)$ regretを示し、その後、それぞれ$tildemathcalO(sqrtKT)$と$tildemathcalOに変換する。
• 参考スコア（独自算出の注目度）: 46.82558739203106
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Recent works have shown a reduction from contextual bandits to online regression under a realizability assumption [Foster and Rakhlin, 2020, Foster and Krishnamurthy, 2021]. In this work, we investigate the use of neural networks for such online regression and associated Neural Contextual Bandits (NeuCBs). Using existing results for wide networks, one can readily show a ${\mathcal{O}}(\sqrt{T})$ regret for online regression with square loss, which via the reduction implies a ${\mathcal{O}}(\sqrt{K} T^{3/4})$ regret for NeuCBs. Departing from this standard approach, we first show a $\mathcal{O}(\log T)$ regret for online regression with almost convex losses that satisfy QG (Quadratic Growth) condition, a generalization of the PL (Polyak-\L ojasiewicz) condition, and that have a unique minima. Although not directly applicable to wide networks since they do not have unique minima, we show that adding a suitable small random perturbation to the network predictions surprisingly makes the loss satisfy QG with unique minima. Based on such a perturbed prediction, we show a ${\mathcal{O}}(\log T)$ regret for online regression with both squared loss and KL loss, and subsequently convert these respectively to $\tilde{\mathcal{O}}(\sqrt{KT})$ and $\tilde{\mathcal{O}}(\sqrt{KL^*} + K)$ regret for NeuCB, where $L^*$ is the loss of the best policy. Separately, we also show that existing regret bounds for NeuCBs are $\Omega(T)$ or assume i.i.d. contexts, unlike this work. Finally, our experimental results on various datasets demonstrate that our algorithms, especially the one based on KL loss, persistently outperform existing algorithms.
• Abstract（参考訳）: 近年の研究では,コンテキストバンディットからオンライン回帰まで,[foster and rakhlin, 2020, foster and krishnamurthy, 2021]という仮定の下での削減が示されている。 本研究では,このようなオンライン回帰と関連するNeuCB(NeuCBs)に対するニューラルネットワークの利用について検討する。 広域ネットワークに対する既存の結果を用いることで、正方形損失を伴うオンライン回帰に対する ${\mathcal{o}}(\sqrt{t})$ regret が容易に示され、この還元により、neucbsに対する${\mathcal{o}}(\sqrt{k} t^{3/4})$ regret が示される。 この標準的なアプローチとは別に、まず、QG(Quadratic Growth)条件を満たすほとんど凸な損失、PL(Polyak-\L ojasiewicz)条件の一般化、およびユニークなミニマを持つオンライン回帰に対して、$\mathcal{O}(\log T)$後悔を示す。 特定のミニマが存在しないため,広帯域ネットワークに直接適用できないが,ネットワーク予測に適切な小さな乱乱摂動を加えると,損失がユニークなミニマでQGを満たすことが予想される。 このような乱雑な予測に基づいて、オンライン回帰に対する${\mathcal{o}}(\log t)$の後悔を二乗損失とkl損失の両方で示し、それらを$\tilde{\mathcal{o}}(\sqrt{kt})$と$\tilde{\mathcal{o}}(\sqrt{kl^*} + k)$でneucbに変換する。 別として、NeuCB に対する既存の後悔境界は、この研究とは異なり、$\Omega(T)$ または i.d. コンテキストであることを示す。 最後に,様々なデータセットを用いた実験結果から,本アルゴリズム,特にkl損失に基づくアルゴリズムが,既存のアルゴリズムよりも永続的に優れていることが分かる。

関連論文リスト

• Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes [29.466981306355066]
  固定学習率$eta$の勾配降下はスムーズな関数を表す局所最小値しか見つからないことを示す。 また、$n$のデータポイントのサポートの厳密な内部で、$widetildeO(n-4/5)$のほぼ最適MSE境界を証明します。
  論文  参考訳（メタデータ） (2024-06-10T22:57:27Z)
• A Unified Scheme of ResNet and Softmax [8.556540804058203]
  回帰問題を理論的に解析する: $| langle exp(Ax) + A x, bf 1_n rangle-1 ( exp(Ax) + Ax ) この回帰問題は、ソフトマックス回帰とResNetを組み合わせた統一的なスキームである。
  論文  参考訳（メタデータ） (2023-09-23T21:41:01Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Robust Nonparametric Regression under Poisoning Attack [13.470899588917716]
  敵攻撃者は、$N$のトレーニングデータセットから最大$q$のサンプル値を変更することができる。 初期解法はハマー損失最小化に基づくM推定器である。 最後の見積もりは、任意の$q$に対してほぼ最小値であり、最大$ln N$ factorまでである。
  論文  参考訳（メタデータ） (2023-05-26T09:33:17Z)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。 スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。 また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
  論文  参考訳（メタデータ） (2023-04-05T07:24:19Z)
• Generalization and Stability of Interpolating Neural Networks with Minimal Width [37.908159361149835]
  補間系における勾配によって訓練された浅層ニューラルネットワークの一般化と最適化について検討する。 トレーニング損失数は$m=Omega(log4 (n))$ニューロンとニューロンを最小化する。 m=Omega(log4 (n))$のニューロンと$Tapprox n$で、テスト損失のトレーニングを$tildeO (1/)$に制限します。
  論文  参考訳（メタデータ） (2023-02-18T05:06:15Z)
• When Expressivity Meets Trainability: Fewer than $n$ Neurons Can Work [59.29606307518154]
  幅が$m geq 2n/d$($d$は入力次元)である限り、その表現性は強く、すなわち、訓練損失がゼロの少なくとも1つの大域最小化器が存在することを示す。 また、実現可能な領域がよい局所領域であるような制約付き最適化の定式化も検討し、すべてのKKT点がほぼ大域最小値であることを示す。
  論文  参考訳（メタデータ） (2022-10-21T14:41:26Z)
• Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR [13.165557713537389]
  我々は、強い適応性(SA)アルゴリズムを、動的後悔を制御するための原則的な方法と見なせることを示した。 我々は,オンラインKernel Ridge Regression(KRR)の最小限の最適性を確立する,ある罰則による新たな下限を導出する。
  論文  参考訳（メタデータ） (2021-11-22T21:52:47Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  我々は、ソボレフ空間のクラス上の後悔の上限を$W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$ とする。 上界は minimax regret analysis で支えられ、$beta> fracd2$ または $p=infty$ の場合、これらの値は(本質的に)最適である。
  論文  参考訳（メタデータ） (2021-02-06T15:05:14Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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