論文の概要: Improved Kernel Alignment Regret Bound for Online Kernel Learning
- arxiv url: http://arxiv.org/abs/2212.12989v3
- Date: Tue, 14 Nov 2023 07:41:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-15 19:28:27.709717
- Title: Improved Kernel Alignment Regret Bound for Online Kernel Learning
- Title（参考訳）: オンラインカーネル学習におけるカーネルアライメントの改善
- Authors: Junfan Li and Shizhong Liao
- Abstract要約: 提案手法は, 既往の結果よりも, 計算量や計算量が多くなるアルゴリズムを提案する。
核行列の固有値が指数関数的に減衰すると、我々のアルゴリズムは$O(sqrtmathcalA_T)$の後悔を、$O(ln2T)$の計算複雑性で楽しむ。
我々はアルゴリズムをバッチ学習に拡張し、以前の$Oを改善した$O(frac1TsqrtmathbbE[mathcalA_T])$over risk boundを得る。
- 参考スコア（独自算出の注目度）: 11.201662566974232
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we improve the kernel alignment regret bound for online kernel
learning in the regime of the Hinge loss function. Previous algorithm achieves
a regret of $O((\mathcal{A}_TT\ln{T})^{\frac{1}{4}})$ at a computational
complexity (space and per-round time) of $O(\sqrt{\mathcal{A}_TT\ln{T}})$,
where $\mathcal{A}_T$ is called \textit{kernel alignment}. We propose an
algorithm whose regret bound and computational complexity are better than
previous results. Our results depend on the decay rate of eigenvalues of the
kernel matrix. If the eigenvalues of the kernel matrix decay exponentially,
then our algorithm enjoys a regret of $O(\sqrt{\mathcal{A}_T})$ at a
computational complexity of $O(\ln^2{T})$. Otherwise, our algorithm enjoys a
regret of $O((\mathcal{A}_TT)^{\frac{1}{4}})$ at a computational complexity of
$O(\sqrt{\mathcal{A}_TT})$. We extend our algorithm to batch learning and
obtain a $O(\frac{1}{T}\sqrt{\mathbb{E}[\mathcal{A}_T]})$ excess risk bound
which improves the previous $O(1/\sqrt{T})$ bound.
- Abstract（参考訳）: 本稿では,Hinge損失関数の仕組みにおいて,オンラインカーネル学習に拘束されるカーネルアライメントの後悔を改善する。
事前のアルゴリズムは、$O((\mathcal{A}_TT\ln{T})^{\frac{1}{4}})$O(\sqrt{\mathcal{A}_TT\ln{T}})$の計算複雑性(空間と単位時間)において、$O(\sqrt{\mathcal{A}_TT\ln{T}})$を後悔する。
本稿では,従来の結果よりも後悔と計算の複雑さが優れているアルゴリズムを提案する。
結果は,核行列の固有値の減衰速度に依存する。
核行列の固有値が指数関数的に減衰すると、我々のアルゴリズムは$O(\sqrt{\mathcal{A}_T})$の後悔を、$O(\ln^2{T})$の計算複雑性で楽しむ。
さもなくば、我々のアルゴリズムは$O((\mathcal{A}_TT)^{\frac{1}{4}})$の計算複雑性で$O(\sqrt{\mathcal{A}_TT})$の後悔を楽しむ。
我々はアルゴリズムをバッチ学習に拡張し、以前の$O(1/\sqrt{T})$境界を改善した$O(\frac{1}{T}\sqrt{\mathbb{E}[\mathcal{A}_T]})$余剰リスク境界を得る。
関連論文リスト
- Structured Semidefinite Programming for Recovering Structured
Preconditioners [41.28701750733703]
正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。
我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
論文 参考訳（メタデータ） (2023-10-27T16:54:29Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Nearly Optimal Algorithms with Sublinear Computational Complexity for
Online Kernel Regression [13.510889339096117]
後悔と計算コストのトレードオフは、オンラインカーネル回帰の根本的な問題である。
AOGD-ALDとNONS-ALDの2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-14T07:39:09Z) - Improved Regret Bounds for Online Kernel Selection under Bandit Feedback [13.510889339096117]
過去の限界を改善する2種類の後悔境界を証明します。
2つのアルゴリズムを時間とともにオンラインカーネル選択に適用し、以前の$O(sqrtTlnK +Vert fVert2_mathcalH_imaxsqrtT,fracTsqrtmathcalR)$ expected bound ここで$mathcalR$は時間予算であることを示す。
論文 参考訳（メタデータ） (2023-03-09T03:40:34Z) - 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) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - 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) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z) - Statistically Efficient, Polynomial Time Algorithms for Combinatorial
Semi Bandits [3.9919781077062497]
アームの集合である$cal X の部分集合 0,1d$ 上の半帯域を考える。
この問題に対して、ESCB アルゴリズムは最小の既約値 $R(T) = cal OBig(d (ln m)2 (ln T) over Delta_min Big)$ を生成するが、計算複雑性 $cal O(|cal X|)$ を持つ。
論文 参考訳（メタデータ） (2020-02-17T21:32:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。