論文の概要: Sharp Analysis of Random Fourier Features in Classification
- arxiv url: http://arxiv.org/abs/2109.10623v1
- Date: Wed, 22 Sep 2021 09:49:27 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-23 19:11:45.073303
- Title: Sharp Analysis of Random Fourier Features in Classification
- Title（参考訳）: 分類におけるランダムフーリエ特徴のシャープ解析
- Authors: Zhu Li
- Abstract要約: ランダムなフーリエ特徴分類が,Omega(sqrtn log n)$機能のみで,O(sqrtn)$学習率を達成できることを初めて示す。
- 参考スコア（独自算出の注目度）: 9.383533125404755
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the theoretical properties of random Fourier features classification
with Lipschitz continuous loss functions such as support vector machine and
logistic regression. Utilizing the regularity condition, we show for the first
time that random Fourier features classification can achieve $O(1/\sqrt{n})$
learning rate with only $\Omega(\sqrt{n} \log n)$ features, as opposed to
$\Omega(n)$ features suggested by previous results. Our study covers the
standard feature sampling method for which we reduce the number of features
required, as well as a problem-dependent sampling method which further reduces
the number of features while still keeping the optimal generalization property.
Moreover, we prove that the random Fourier features classification can obtain a
fast $O(1/n)$ learning rate for both sampling schemes under Massart's low noise
assumption. Our results demonstrate the potential effectiveness of random
Fourier features approximation in reducing the computational complexity
(roughly from $O(n^3)$ in time and $O(n^2)$ in space to $O(n^2)$ and
$O(n\sqrt{n})$ respectively) without having to trade-off the statistical
prediction accuracy. In addition, the achieved trade-off in our analysis is at
least the same as the optimal results in the literature under the worst case
scenario and significantly improves the optimal results under benign regularity
conditions.
- Abstract（参考訳）: 支持ベクトルマシンやロジスティック回帰といったリプシッツ連続損失関数を用いたランダムフーリエ特徴分類の理論的性質について検討する。
正規性条件を利用すると、ランダムなフーリエ特徴分類が$O(1/\sqrt{n})$学習率を$\Omega(\sqrt{n} \log n)$特徴のみで達成できることが、以前の結果から示唆された$Omega(n)$特徴とは対照的に初めて示される。
本研究は,必要な特徴量を削減するための標準的な特徴量サンプリング手法と,最適な一般化特性を維持しつつ,特徴量をさらに削減する問題依存サンプリング手法について述べる。
さらに,無作為フーリエ特徴分類は,マッサートの低雑音条件下での2つのサンプリングスキームにおいて,高速なo(1/n)$学習率を得ることができることを証明した。
この結果から,計算複雑性を減少させる確率的フーリエ関数の有効性(大まかには$O(n^3)$,$O(n^2)$から$O(n^2)$,$O(n\sqrt{n})$)が,統計的予測精度のトレードオフを伴わずに得られることを示した。
また,本分析で得られたトレードオフは,最悪の場合における文献の最適結果と少なくとも同じであり,良性正規性条件下での最適結果を大幅に改善する。
関連論文リスト
- Model-adapted Fourier sampling for generative compressed sensing [7.130302992490975]
測定行列が一意行列からランダムにサブサンプリングされたとき, 生成的圧縮センシングについて検討した。
我々は,textitO(kd| boldsymbolalpha|_22)$の測定精度を改良したモデル適応サンプリング戦略を構築した。
論文 参考訳（メタデータ） (2023-10-08T03:13:16Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Average case analysis of Lasso under ultra-sparse conditions [4.568911586155097]
回帰器の数が大きくなると、線形モデルに対する最小絶対収縮・選択演算子(Lasso)の性能を解析する。
完全サポート回復のための得られた境界は、以前の文献で与えられたものを一般化したものである。
論文 参考訳（メタデータ） (2023-02-25T14:50:32Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳（メタデータ） (2022-06-05T21:32:33Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Stochastic Bias-Reduced Gradient Methods [44.35885731095432]
モロー・吉田関数の任意の有界な$x_star$の低バイアスで低コストな平滑化である。
論文 参考訳（メタデータ） (2021-06-17T13:33:05Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Wind Field Reconstruction with Adaptive Random Fourier Features [0.0]
本研究では, 空間的手法による水平近傍風況の再現について検討した。
物理的に動機付けられた発散ペナルティ用語 $|nabla cdot beta(pmb x)|2$ や、ソボレフノルムのペナルティも含んでいる。
最適分布の周波数をサンプリングする適応ハスティングアルゴリズムを考案する。
論文 参考訳（メタデータ） (2021-02-04T01:42:08Z) - Tight Nonparametric Convergence Rates for Stochastic Gradient Descent
under the Noiseless Linear Model [0.0]
このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。
特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
論文 参考訳（メタデータ） (2020-06-15T08:25:50Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。