論文の概要: A parametric algorithm is optimal for non-parametric regression of smooth functions

• arxiv url: http://arxiv.org/abs/2412.14744v1
• Date: Thu, 19 Dec 2024 11:22:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-20 13:30:27.022367
• Title: A parametric algorithm is optimal for non-parametric regression of smooth functions
• Title（参考訳）: パラメトリックアルゴリズムは滑らかな関数の非パラメトリック回帰に最適である
• Authors: Davide Maran, Marcello Restelli,
• Abstract要約: PADUAは、この設定に最適なサンプル複雑性を持つ最初のパラメトリックアルゴリズムである。 PADUAは最先端の手法に匹敵する性能を示すが,計算時間はごくわずかである。
• 参考スコア（独自算出の注目度）: 44.32603181895527
• License:
• Abstract: We address the regression problem for a general function $f:[-1,1]^d\to \mathbb R$ when the learner selects the training points $\{x_i\}_{i=1}^n$ to achieve a uniform error bound across the entire domain. In this setting, known historically as nonparametric regression, we aim to establish a sample complexity bound that depends solely on the function's degree of smoothness. Assuming periodicity at the domain boundaries, we introduce PADUA, an algorithm that, with high probability, provides performance guarantees optimal up to constant or logarithmic factors across all problem parameters. Notably, PADUA is the first parametric algorithm with optimal sample complexity for this setting. Due to this feature, we prove that, differently from the non-parametric state of the art, PADUA enjoys optimal space complexity in the prediction phase. To validate these results, we perform numerical experiments over functions coming from real audio data, where PADUA shows comparable performance to state-of-the-art methods, while requiring only a fraction of the computational time.
• Abstract（参考訳）: 一般関数 $f:[-1,1]^d\to \mathbb R$ の回帰問題は、学習者が訓練点 $\{x_i\}_{i=1}^n$ を選択すると、全領域にわたって一様誤差を生じる。 この設定は、歴史的に非パラメトリック回帰(nonparametric regression)として知られており、関数の滑らかさの度合いにのみ依存するサンプル複雑性を確立することを目的としている。 領域境界における周期性を仮定し,確率の高いアルゴリズムPADUAを導入する。 特にPADUAは、この設定に最適なサンプル複雑性を持つ最初のパラメトリックアルゴリズムである。 この特徴により、非パラメトリック状態とは違い、PADUAは予測フェーズにおいて最適な空間複雑性を享受できることが証明される。 これらの結果を検証するため,PADUAは最先端の手法に匹敵する性能を示すが,計算時間はほんの少ししか要しない実音声データから得られる関数に対して数値実験を行う。

関連論文リスト

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• Parameter-Agnostic Optimization under Relaxed Smoothness [25.608968462899316]
  本研究では,モメンタムを用いた正規化グラディエントDescence (NSGD-M) が,問題パラメータの事前知識を必要とせずに,速度-最適の複雑性を実現できることを示す。 決定論的設定では、指数係数は、バックトラックラインサーチによるグラディエント・ディクスト(Gradient Descent)を用いることで、中和することができる。
  論文  参考訳（メタデータ） (2023-11-06T16:39:53Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Convergence analysis of online algorithms for vector-valued kernel regression [0.42970700836450487]
  オンライン学習アルゴリズムを用いて雑音の多いベクトル値データから回帰関数を近似する問題を考察する。 RKHSノルムの期待二乗誤差は$C2 (m+1)-s/(2+s)$でバウンドできることを示し、$m$は現在の処理データの数である。
  論文  参考訳（メタデータ） (2023-09-14T15:10:47Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。 任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
  論文  参考訳（メタデータ） (2023-01-16T02:57:37Z)
• Private optimization in the interpolation regime: faster rates and hardness results [9.405458160620533]
  プライベートでない凸最適化では、勾配法は非補間法よりも、全てのサンプル損失を同時に最小化する解が存在するという問題にはるかに早く収束する。 プライベートサンプルの複雑さは指数関数的に改善した(近辺)。
  論文  参考訳（メタデータ） (2022-10-31T05:18:27Z)
• An Algebraically Converging Stochastic Gradient Descent Algorithm for Global Optimization [14.336473214524663]
  アルゴリズムの主要な構成要素は、目的関数の値に基づくランダム性である。 アルゴリズムの収束を代数学で証明し、パラメータ空間でチューニングする。 アルゴリズムの効率性とロバスト性を示す数値的な例をいくつか提示する。
  論文  参考訳（メタデータ） (2022-04-12T16:27:49Z)
• Finite-Sample Analysis for Two Time-scale Non-linear TDC with General Smooth Function Approximation [27.149240954363496]
  我々は,一般のオフ・ポリシー設定にバインドされた有限サンプル誤差を明示的に特徴付ける新しい手法を開発した。 本手法は,一般的なスムーズな関数近似を用いた広範囲なT型学習アルゴリズムに適用できる。
  論文  参考訳（メタデータ） (2021-04-07T00:34:11Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。