論文の概要: On the Saturation Effects of Spectral Algorithms in Large Dimensions
- arxiv url: http://arxiv.org/abs/2503.00504v1
- Date: Sat, 01 Mar 2025 14:21:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-05 19:24:49.401305
- Title: On the Saturation Effects of Spectral Algorithms in Large Dimensions
- Title（参考訳）: 大次元スペクトルアルゴリズムの飽和効果について
- Authors: Weihao Lu, Haobo Zhang, Yicheng Li, Qian Lin,
- Abstract要約: 本研究の主な焦点は,大規模なスペクトルアルゴリズムの飽和効果を大規模に検討することである。
飽和効果は, 原条件$s>tau$で, 固定次元設定では$s>2tau$で発生する。
- 参考スコア（独自算出の注目度）: 14.63552944833659
- License:
- Abstract: The saturation effects, which originally refer to the fact that kernel ridge regression (KRR) fails to achieve the information-theoretical lower bound when the regression function is over-smooth, have been observed for almost 20 years and were rigorously proved recently for kernel ridge regression and some other spectral algorithms over a fixed dimensional domain. The main focus of this paper is to explore the saturation effects for a large class of spectral algorithms (including the KRR, gradient descent, etc.) in large dimensional settings where $n \asymp d^{\gamma}$. More precisely, we first propose an improved minimax lower bound for the kernel regression problem in large dimensional settings and show that the gradient flow with early stopping strategy will result in an estimator achieving this lower bound (up to a logarithmic factor). Similar to the results in KRR, we can further determine the exact convergence rates (both upper and lower bounds) of a large class of (optimal tuned) spectral algorithms with different qualification $\tau$'s. In particular, we find that these exact rate curves (varying along $\gamma$) exhibit the periodic plateau behavior and the polynomial approximation barrier. Consequently, we can fully depict the saturation effects of the spectral algorithms and reveal a new phenomenon in large dimensional settings (i.e., the saturation effect occurs in large dimensional setting as long as the source condition $s>\tau$ while it occurs in fixed dimensional setting as long as $s>2\tau$).
- Abstract（参考訳）: 飽和効果は、元々はカーネルリッジ回帰(KRR)が回帰関数が過度に滑らかであるときに情報理論の下界を達成できないという事実を指していたが、ほぼ20年間観察され、最近になってカーネルリッジ回帰や固定次元領域上の他のスペクトルアルゴリズムに対して厳密に証明された。
本稿では,KRR,勾配降下等を含む大規模スペクトルアルゴリズムの飽和効果を,$n \asymp d^{\gamma}$で探索することを目的とする。
より正確には、我々はまず、カーネル回帰問題に対する改善されたミニマックス下限を大規模設定で提案し、早期停止戦略による勾配流が、この下限を達成する推定器(対数係数まで)をもたらすことを示す。
KRRの結果と同様に、異なる資格を持つ大規模(最適チューニングされた)スペクトルアルゴリズムの正確な収束率(上界と下界の両方)を更に決定することができる。
特に、これらの正確な速度曲線($\gamma$に沿って変化する)は周期的プラトー挙動と多項式近似障壁を示す。
その結果、スペクトルアルゴリズムの飽和効果を完全に表現し、大きな次元設定で新しい現象を明らかにすることができる(すなわち、飽和効果はソース条件 $s>\tau$ のとき大次元設定で発生し、固定次元設定では $s>2\tau$ となる)。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms [28.046728466038022]
ベクトル値出力を持つ多種多様な正規化アルゴリズムの理論的特性について検討する。
ベクトル値出力によるリッジ回帰に対するいわゆる飽和効果を厳密に検証する。
有限サンプルリスク一般ベクトル値スペクトルアルゴリズムの上限について述べる。
論文 参考訳（メタデータ） (2024-05-23T16:45:52Z) - A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。
i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。
その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
論文 参考訳（メタデータ） (2024-04-18T16:46:08Z) - From Zero to Hero: How local curvature at artless initial conditions leads away from bad minima [9.50832466973301]
複雑な損失景観のケーススタディとして,位相探索問題に焦点をあてる。
スペクトルの遷移が起こり、方向が失われ、システムが悪いミニマに閉じ込められることを示す。
我々の分析は、有限次元の勾配勾配勾配ダイナミクスを促進する新しいメカニズムに光を当てている。
論文 参考訳（メタデータ） (2024-03-04T19:12:13Z) - Quantum state tomography via non-convex Riemannian gradient descent [13.100184125419691]
本研究では,kappa$のスケール依存性を改善する量子状態トモグラフィースキームを導出する。
この改良は、非多様体勾配(RGD)アルゴリズムの適用によるものである。
超高速収束とほぼ最適誤差境界の理論的結果は数値的な結果と相関する。
論文 参考訳（メタデータ） (2022-10-10T14:19:23Z) - Restricted Strong Convexity of Deep Learning Models with Smooth
Activations [31.003601717265006]
本研究では,スムーズなアクティベーション機能を持つディープラーニングモデルの最適化問題について検討する。
Restricted Strong Convexity (RSC) に基づく最適化の新しい解析手法を提案する。
深層学習モデルのためのRCCに基づくGDの幾何収束性を確立するための最初の結果である。
論文 参考訳（メタデータ） (2022-09-29T21:24:26Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Accelerated SGD for Non-Strongly-Convex Least Squares [14.010916616909743]
非強凸設定における最小二乗回帰問題の近似を考察する。
本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-03-03T14:39:33Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - Gradient Boosted Binary Histogram Ensemble for Large-scale Regression [60.16351608335641]
本研究では,2値ヒストグラム分割とアンサンブル学習に基づくテキストグラディエント2値ヒストグラムアンサンブル(GBBHE)と呼ばれる大規模回帰問題に対する勾配向上アルゴリズムを提案する。
実験では, 勾配向上回帰木 (GBRT) などの他の最先端アルゴリズムと比較して, GBBHEアルゴリズムは大規模データセット上での実行時間が少なく, 有望な性能を示す。
論文 参考訳（メタデータ） (2021-06-03T17:05:40Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。