論文の概要: Nearly Optimal Algorithms with Sublinear Computational Complexity for
Online Kernel Regression
- arxiv url: http://arxiv.org/abs/2306.08320v1
- Date: Wed, 14 Jun 2023 07:39:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-16 19:57:10.545493
- Title: Nearly Optimal Algorithms with Sublinear Computational Complexity for
Online Kernel Regression
- Title（参考訳）: オンラインカーネル回帰に対する線形計算複雑度をもつ近似アルゴリズム
- Authors: Junfan Li and Shizhong Liao
- Abstract要約: 後悔と計算コストのトレードオフは、オンラインカーネル回帰の根本的な問題である。
AOGD-ALDとNONS-ALDの2つの新しいアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 13.510889339096117
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The trade-off between regret and computational cost is a fundamental problem
for online kernel regression, and previous algorithms worked on the trade-off
can not keep optimal regret bounds at a sublinear computational complexity. In
this paper, we propose two new algorithms, AOGD-ALD and NONS-ALD, which can
keep nearly optimal regret bounds at a sublinear computational complexity, and
give sufficient conditions under which our algorithms work. Both algorithms
dynamically maintain a group of nearly orthogonal basis used to approximate the
kernel mapping, and keep nearly optimal regret bounds by controlling the
approximate error. The number of basis depends on the approximate error and the
decay rate of eigenvalues of the kernel matrix. If the eigenvalues decay
exponentially, then AOGD-ALD and NONS-ALD separately achieves a regret of
$O(\sqrt{L(f)})$ and $O(\mathrm{d}_{\mathrm{eff}}(\mu)\ln{T})$ at a
computational complexity in $O(\ln^2{T})$. If the eigenvalues decay
polynomially with degree $p\geq 1$, then our algorithms keep the same regret
bounds at a computational complexity in $o(T)$ in the case of $p>4$ and $p\geq
10$, respectively. $L(f)$ is the cumulative losses of $f$ and
$\mathrm{d}_{\mathrm{eff}}(\mu)$ is the effective dimension of the problem. The
two regret bounds are nearly optimal and are not comparable.
- Abstract（参考訳）: 後悔と計算コストのトレードオフは、オンラインカーネルレグレッションの基本的な問題であり、このトレードオフに取り組んでいた以前のアルゴリズムは、線形計算の複雑さで最適な後悔の境界を維持することはできない。
本稿では,aogd-aldとnons-aldの2つの新しいアルゴリズムを提案する。
どちらのアルゴリズムも、カーネルマッピングを近似するために使用されるほぼ直交基底の群を動的に維持し、近似誤差を制御することでほぼ最適な後悔境界を維持する。
基底の数は、カーネル行列の固有値の近似誤差と崩壊率に依存する。
固有値が指数関数的に減衰すると、AOGD-ALD と NONS-ALD は $O(\sqrt{L(f)})$ と $O(\mathrm{d}_{\mathrm{eff}}(\mu)\ln{T})$ を、$O(\ln^2{T})$ の計算複雑性でそれぞれ後悔する。
固有値が次数$p\geq 1$で多項式的に減衰した場合、我々のアルゴリズムは、それぞれ$p>4$ と $p\geq 10$ の場合、同じ後悔境界を$o(T)$ の計算複雑性で保持する。
l(f)$ は$f$ の累積損失であり、$\mathrm{d}_{\mathrm{eff}}(\mu)$ は問題の有効次元である。
2つの後悔境界はほぼ最適であり、同等ではない。
関連論文リスト
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
潜在変数モデル学習の課題について検討する。
このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。
一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
論文 参考訳（メタデータ） (2024-11-23T23:13:24Z) - Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback [30.337826346496385]
線形マルコフ決定過程におけるオンライン強化学習について,敵対的損失と帯域幅フィードバックを用いて検討した。
既存の手法と比較して、後悔性能を向上させるアルゴリズムを2つ導入する。
論文 参考訳（メタデータ） (2023-10-17T19:43:37Z) - Regret-Optimal Federated Transfer Learning for Kernel Regression with Applications in American Option Pricing [8.723136784230906]
本稿では、中央プランナーがデータセットにアクセス可能なフェデレーショントランスファー学習のための最適反復スキームを提案する。
我々の目標は、生成されたパラメータの累積偏差を$thetai(t)_t=0T$で最小化することである。
後悔と最適化のアルゴリズム内で対称性を活用することで, $mathcalO(Np2)$少なめの初等演算を伴って動作する,ほぼ後悔のいく$_optimalを開発する。
論文 参考訳（メタデータ） (2023-09-08T19:17:03Z) - 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) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - 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) - 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) - 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) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。