論文の概要: Using Multilevel Circulant Matrix Approximate to Speed Up Kernel
Logistic Regression
- arxiv url: http://arxiv.org/abs/2108.08605v1
- Date: Thu, 19 Aug 2021 10:30:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-20 22:54:25.284130
- Title: Using Multilevel Circulant Matrix Approximate to Speed Up Kernel
Logistic Regression
- Title（参考訳）: マルチレベル循環行列近似を用いたカーネルロジスティック回帰の高速化
- Authors: Junna~Zhang, Shuisheng~Zhou,~Cui~Fu and Zhuan Zhang
- Abstract要約: 我々は、記憶空間を節約し、KLRの解を加速するために、MCM(Multilevel circulant matrix)近似カーネル行列を用いる。
提案手法は,KLRをメモリ消費の少ない大規模問題に対してスケーラブルにし,コストを犠牲にすることなく精度テストに収束させる。
- 参考スコア（独自算出の注目度）: 3.1427994341585688
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Kernel logistic regression (KLR) is a classical nonlinear classifier in
statistical machine learning. Newton method with quadratic convergence rate can
solve KLR problem more effectively than the gradient method. However, an
obvious limitation of Newton method for training large-scale problems is the
$O(n^{3})$ time complexity and $O(n^{2})$ space complexity, where $n$ is the
number of training instances. In this paper, we employ the multilevel circulant
matrix (MCM) approximate kernel matrix to save in storage space and accelerate
the solution of the KLR. Combined with the characteristics of MCM and our
ingenious design, we propose an MCM approximate Newton iterative method. We
first simplify the Newton direction according to the semi-positivity of the
kernel matrix and then perform a two-step approximation of the Newton direction
by using MCM. Our method reduces the time complexity of each iteration to $O(n
\log n)$ by using the multidimensional fast Fourier transform (mFFT). In
addition, the space complexity can be reduced to $O(n)$ due to the built-in
periodicity of MCM. Experimental results on some large-scale binary and
multi-classification problems show that our method makes KLR scalable for
large-scale problems, with less memory consumption, and converges to test
accuracy without sacrifice in a shorter time.
- Abstract（参考訳）: カーネルロジスティック回帰(カーネルロジスティックレグレッション、KLR)は、統計機械学習における古典的非線形分類法である。
二次収束率を持つニュートン法は勾配法よりも効率的にKLR問題を解くことができる。
しかし、大規模な問題を訓練するためのニュートン法の明らかな制限は、$O(n^{3})$時間複雑性と$O(n^{2})$空間複雑性であり、$n$はトレーニングインスタンスの数である。
本稿では,多レベル循環行列(mcm)近似カーネル行列を用いて保存空間を節約し,klrの解を高速化する。
MCMの特徴と創発的設計を組み合わせることで,MCM近似ニュートン反復法を提案する。
まず、カーネル行列の半有界性に応じてニュートン方向を単純化し、次にmcmを用いてニュートン方向の2段階近似を行う。
本手法は多次元高速フーリエ変換(mfft)を用いて各イテレーションの時間複雑性を$o(n \log n)$に低減する。
さらに、空間複雑性は MCM の組込み周期性により$O(n)$に縮めることができる。
いくつかの大規模バイナリおよびマルチクラス化問題に対する実験結果から,我々の手法は,KLRをメモリ消費の少ない大規模問題に対してスケーラブルにし,短時間で犠牲なく精度を検証できることを示した。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Large-Scale Gaussian Processes via Alternating Projection [23.79090469387859]
本稿では,カーネル行列のサブブロックのみにアクセスする反復的手法を提案する。
我々のアルゴリズムは、交互プロジェクションに基づくもので、GPを非常に大きなデータセットにスケールするという現実的な課題の多くを解決し、各イテレーション時間と空間の複雑さを$mathcalO(n)で解決している。
論文 参考訳（メタデータ） (2023-10-26T04:20:36Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Orthogonal Directions Constrained Gradient Method: from non-linear
equality constraints to Stiefel manifold [16.099883128428054]
直交方向制約法(ODCGM)という新しいアルゴリズムを提案する。
ODCGMはベクトル空間へのプロジェクションのみを必要とする。
以上より, ODCGMは, ほぼ最適のオラクル複合体を呈することを示した。
論文 参考訳（メタデータ） (2023-03-16T12:25:53Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - FKreg: A MATLAB toolbox for fast Multivariate Kernel Regression [5.090316990822874]
非一様FFT(NUFFT)を用いた高速多変量カーネル回帰のための新しいツールボックスを提案する。
NUFFTは$Oleft(N+Mlog M right)$複雑さと精度制御性を備えた$M$グリッドポイントのアルゴリズムを実装している。
帯域幅選択問題は、Fast Monte-Carloを用いて自由度を推定する。
論文 参考訳（メタデータ） (2022-04-16T04:52:44Z) - Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
微分可能な行列平方根と逆平方根を計算するためのより効率的な2つの変種を提案する。
前方伝搬には, Matrix Taylor Polynomial (MTP) を用いる方法と, Matrix Pad'e Approximants (MPA) を使用する方法がある。
一連の数値実験により、両方の手法がSVDやNSの繰り返しと比較してかなりスピードアップすることが示された。
論文 参考訳（メタデータ） (2022-01-29T10:00:35Z) - Fast $L^2$ optimal mass transport via reduced basis methods for the
Monge-Amp$\grave{\rm e}$re equation [0.0]
パラメータ化されたMonge-Amp$graverm e$re方程式を解くための機械学習的手法を提案する。
いくつかの挑戦的な数値実験により,モンジュ=アンプ=グラバーム=e$re方程式を解くための手法の精度と高効率性を実証した。
論文 参考訳（メタデータ） (2021-12-03T12:30:46Z) - Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
我々は、混合性は最適な後悔を伴うアルゴリズムを得るための強力なツールであることを示した。
結果として得られる手法は、しばしば計算の複雑さに悩まされ、実用性が低下した。
論文 参考訳（メタデータ） (2021-10-08T08:22:05Z) - Newton-LESS: Sparsification without Trade-offs for the Sketched Newton
Update [88.73437209862891]
2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。
本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。
ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
論文 参考訳（メタデータ） (2021-07-15T17:33:05Z) - The Fast Kernel Transform [21.001203328543006]
本稿では,FKT(Fast Kernel Transform:高速カーネル変換)を提案する。
FKT はガウス、マテルン、ラショナル四次共分散関数や物理的に動機付けられたグリーン関数など、幅広い種類のカーネルに容易に適用できる。
本稿では、時間と精度のベンチマークを提供することによりFKTの有効性と汎用性を説明し、それを近隣埋め込み(t-SNE)とガウス過程を大規模実世界のデータセットに拡張する。
論文 参考訳（メタデータ） (2021-06-08T16:15:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。