論文の概要: Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms
- arxiv url: http://arxiv.org/abs/2610.30948v1
- Date: Thu, 22 Oct 2026 09:01:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-24 02:08:44.294188
- Title: Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms
- Title（参考訳）: スペクトルアルゴリズムのランダム射影:ソボレフノルムの最適速度
- Abstract要約: 本稿では,一般条件下でのRPベースのスペクトルアルゴリズムの一般化性能を包括的かつ改良した分析法を提案する。
我々は,最小値の最小値と対数因子とを一致させるソボレフ法則の最適学習率を確立する。
結果は回帰関数に対する一様有界性仮定に依存しない。
- 参考スコア（独自算出の注目度）: 8.643508678668292
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Random projections (RP) offer an effective method for reducing computational and storage overhead while preserving the geometric structure of data. However, existing studies have primarily focused on the optimal generalization performance of specific kernel-regularized algorithms with RP in the well-specified setting and under restrictive conditions. In this paper, we provide a comprehensive and improved analysis of the generalization performance of RP-based spectral algorithms under general conditions \change{without sacrificing statistical efficiency}. By leveraging the embedding property of the reproducing kernel Hilbert space (RKHS) and a refined analysis of the operator similarity, we establish optimal learning rates in Sobolev norms that match the minimax lower bounds up to logarithmic factors. For two common implementations of RP, randomized sketches and Nyström sub-sampling (uniform or leverage-based), we show that the projection dimension required for optimality is proportional to the average or maximal effective dimension, yielding a significant reduction in computational cost while maintaining the statistical efficiency. Our results do not rely on the uniform boundedness assumption on the regression function and are valid across a wide range of source conditions, i.e., $s> α_0-1/β$, where $s,β$, and $α_0$ denote the smoothness index, capacity index, and the embedding index, respectively. In the benign case when $α_0=1/β$, the optimality holds for all $s\in (0,2τ]$ with $τ$ and $γ$ denoting the qualification index and norm index. Experimental results demonstrate both the theoretical validity and the practical effectiveness of the proposed method.
- Abstract（参考訳）: ランダムプロジェクション(RP)は、データの幾何学的構造を保ちながら、計算と記憶のオーバーヘッドを削減する効果的な方法を提供する。
しかし、既存の研究では、厳密な設定と制約条件下でのRPを用いた特定のカーネル正規化アルゴリズムの最適一般化性能に主に焦点を当てている。
本稿では,一般条件である \change{witherificing statistics efficiency} の下で,RPベースのスペクトルアルゴリズムの一般化性能を包括的かつ改良した解析を行う。
再生カーネルヒルベルト空間(RKHS)の埋め込み特性と演算子類似性の洗練された解析を利用して、最小最大下界を対数的因子に合わせるソボレフノルムの最適学習率を確立する。
RP,ランダム化されたスケッチ,およびNyströmサブサンプリング(一様あるいはレバレッジベース)の2つの一般的な実装に対して,最適性に必要な射影次元が平均あるいは最大実効次元に比例し,統計的効率を維持しながら計算コストの大幅な削減をもたらすことを示す。
我々の結果は回帰関数上の一様有界性仮定に頼らず、例えば$s> α_0-1/β$, $s,β$, $α_0$はそれぞれ滑らか度指数、キャパシティ指数、埋め込み指数を表す。
α_0=1/β$の良さの場合、任意の$s\in (0,2τ]$に対して$τ$と$γ$は資格指数とノルム指数を表す。
実験により,提案手法の理論的妥当性と実用性の両方を実証した。
関連論文リスト
- Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms [0.22940141855172028]
分散カーネルベースロバスト勾配勾配勾配(DKRGD)アルゴリズムの最適学習率を適切に選択したスケールパラメータ$$。
重要な技術的貢献は、作用素の積に対してはるかにシャープな境界を提供する新しいエラー解析である。
論文 参考訳（メタデータ） (2026-09-10T15:30:01Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Principled Algorithms for Optimizing Generalized Metrics in Binary Classification [53.604375124674796]
一般化されたメトリクスを最適化するアルゴリズムを導入し、$H$-consistency と finite-sample generalization bounds をサポートする。
提案手法は,メトリクス最適化を一般化したコスト依存学習問題として再検討する。
我々は,理論性能を保証する新しいアルゴリズムMETROを開発した。
論文 参考訳（メタデータ） (2025-12-29T01:33:42Z) - FastPart: Over-Parameterized Stochastic Gradient Descent for Sparse optimisation on Measures [3.377298662011438]
本稿では,コニックパーティクルグラディエントDescent(CPGD)のスケーラビリティを高めるために,ランダム特徴と協調してグラディエントDescent戦略を利用する新しいアルゴリズムを提案する。
以下の重要な結果を示す厳密な数学的証明を提供する: $mathrm(i)$ 降下軌道に沿った解測度の総変動ノルムは有界であり、安定性を確保し、望ましくない発散を防ぐ。$mathrm(ii)$ 収束率$O(log(K)/sqrtK)$$$$$K以上の大域収束保証を確立する。
論文 参考訳（メタデータ） (2023-12-10T20:41:43Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Quantization-Based Optimization: Alternative Stochastic Approximation of
Global Optimization [0.0]
NP-hard問題における目的関数のエネルギーレベルを定量化するための大域的最適化アルゴリズムを提案する。
数値実験により,提案アルゴリズムはNP-ハード最適化問題の解法において従来の学習法よりも優れていた。
論文 参考訳（メタデータ） (2022-11-08T03:01:45Z) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。
本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。
3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
論文 参考訳（メタデータ） (2022-09-27T09:06:37Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Gradient Descent Averaging and Primal-dual Averaging for Strongly Convex
Optimization [15.731908248435348]
強凸の場合の勾配降下平均化と主双進平均化アルゴリズムを開発する。
一次二重平均化は出力平均化の観点から最適な収束率を導出し、SC-PDAは最適な個々の収束を導出する。
SVMとディープラーニングモデルに関するいくつかの実験は、理論解析の正確性とアルゴリズムの有効性を検証する。
論文 参考訳（メタデータ） (2020-12-29T01:40:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。