論文の概要: Improved Regret Bounds for Online Kernel Selection under Bandit Feedback

• arxiv url: http://arxiv.org/abs/2303.05018v1
• Date: Thu, 9 Mar 2023 03:40:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-10 16:11:40.486648
• Title: Improved Regret Bounds for Online Kernel Selection under Bandit Feedback
• Title（参考訳）: バンディットフィードバックによるオンラインカーネル選択における後悔領域の改善
• Authors: Junfan Li and Shizhong Liao
• Abstract要約: 過去の限界を改善する2種類の後悔境界を証明します。 2つのアルゴリズムを時間とともにオンラインカーネル選択に適用し、以前の$O(sqrtTlnK +Vert fVert2_mathcalH_imaxsqrtT,fracTsqrtmathcalR)$ expected bound ここで$mathcalR$は時間予算であることを示す。
• 参考スコア（独自算出の注目度）: 13.510889339096117
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we improve the regret bound for online kernel selection under bandit feedback. Previous algorithm enjoys a $O((\Vert f\Vert^2_{\mathcal{H}_i}+1)K^{\frac{1}{3}}T^{\frac{2}{3}})$ expected bound for Lipschitz loss functions. We prove two types of regret bounds improving the previous bound. For smooth loss functions, we propose an algorithm with a $O(U^{\frac{2}{3}}K^{-\frac{1}{3}}(\sum^K_{i=1}L_T(f^\ast_i))^{\frac{2}{3}})$ expected bound where $L_T(f^\ast_i)$ is the cumulative losses of optimal hypothesis in $\mathbb{H}_{i}=\{f\in\mathcal{H}_i:\Vert f\Vert_{\mathcal{H}_i}\leq U\}$. The data-dependent bound keeps the previous worst-case bound and is smaller if most of candidate kernels match well with the data. For Lipschitz loss functions, we propose an algorithm with a $O(U\sqrt{KT}\ln^{\frac{2}{3}}{T})$ expected bound asymptotically improving the previous bound. We apply the two algorithms to online kernel selection with time constraint and prove new regret bounds matching or improving the previous $O(\sqrt{T\ln{K}} +\Vert f\Vert^2_{\mathcal{H}_i}\max\{\sqrt{T},\frac{T}{\sqrt{\mathcal{R}}}\})$ expected bound where $\mathcal{R}$ is the time budget. Finally, we empirically verify our algorithms on online regression and classification tasks.
• Abstract（参考訳）: 本稿では,バンディットフィードバックによるオンラインカーネル選択に対する後悔度を向上する。 以前のアルゴリズムは、リプシッツ損失関数の期待バウンドとして$O((\Vert f\Vert^2_{\mathcal{H}_i}+1)K^{\frac{1}{3}}T^{\frac{2}{3}})を楽しんだ。 過去の限界を改善する2種類の後悔境界を証明する。 滑らかな損失関数に対して、$O(U^{\frac{2}{3}}K^{-\frac{1}{3}}(\sum^K_{i=1}L_T(f^\ast_i))^{\frac{2}{3}})$期待境界を持つアルゴリズムを提案し、$L_T(f^\ast_i)$は、$\mathbb{H}_{i}=\{f\in\mathcal{H}_i:\Vert f\Vert_{\mathcal{H}_i}\leq U\}$における最適仮説の累積損失である。 データ依存のバウンドは、以前の最悪のケースバウンドを保持し、候補カーネルがデータとマッチする場合にはより小さくなる。 リプシッツ損失関数に対しては、$O(U\sqrt{KT}\ln^{\frac{2}{3}}{T})$期待境界を漸近的に改善したアルゴリズムを提案する。 2つのアルゴリズムを時間制約付きオンラインカーネル選択に適用し、以前の$o(\sqrt{t\ln{k}} +\vert f\vert^2_{\mathcal{h}_i}\max\{\sqrt{t},\frac{t}{\sqrt{\mathcal{r}}}\})$が時間予算であるような新たな後悔の限界を証明します。 最後に、オンライン回帰および分類タスクにおけるアルゴリズムを実証的に検証する。

関連論文リスト

• Improved Kernel Alignment Regret Bound for Online Kernel Learning [11.201662566974232]
  提案手法は, 既往の結果よりも, 計算量や計算量が多くなるアルゴリズムを提案する。 核行列の固有値が指数関数的に減衰すると、我々のアルゴリズムは$O(sqrtmathcalA_T)$の後悔を、$O(ln2T)$の計算複雑性で楽しむ。 我々はアルゴリズムをバッチ学習に拡張し、以前の$Oを改善した$O(frac1TsqrtmathbbE[mathcalA_T])$over risk boundを得る。
  論文  参考訳（メタデータ） (2022-12-26T02:32:20Z)
• Eluder-based Regret for Stochastic Contextual MDPs [43.19667415823089]
  文脈マルコフ決定過程(CMDP)における後悔最小化のためのE-UC$3$RLアルゴリズムを提案する。 我々のアルゴリズムは効率的であり(効率的なオフライン回帰オラクルを仮定すると)、$ widetildeO(H3 sqrtT |S| |A|d_mathrmE(mathcalP)$の後悔の保証を享受する。
  論文  参考訳（メタデータ） (2022-11-27T20:38:47Z)
• Private Isotonic Regression [54.32252900997422]
  部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。 約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。 上記の境界は本質的に最良であることを示す。
  論文  参考訳（メタデータ） (2022-10-27T05:08:07Z)
• The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
  本稿では,スムーズで強靭なミニマックス最適化問題を再考する。 既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。 我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
  論文  参考訳（メタデータ） (2022-05-11T17:33:07Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Improved Regret Bounds for Online Submodular Maximization [10.089520556398575]
  我々は、各ステップ$tin[T]$において、固定凸からアクション$x_t$を選択し、コンパクトなドメインセット$mathcalK$を選択するオンライン最適化問題を考える。 ユーティリティ関数 $f_t(cdot)$ が明らかになり、アルゴリズムはペイオフ $f_t(x_t)$ を受け取る。
  論文  参考訳（メタデータ） (2021-06-15T02:05:35Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• 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)
• Adaptive Online Learning with Varying Norms [45.11667443216861]
  オンライン凸最適化アルゴリズムは、あるドメインで$w_t$を出力する。 この結果を用いて新しい「完全行列」型後悔境界を得る。
  論文  参考訳（メタデータ） (2020-02-10T17:22:08Z)

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

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