論文の概要: Phase transitions in nonparametric regressions
- arxiv url: http://arxiv.org/abs/2112.03626v6
- Date: Sat, 8 Jul 2023 01:16:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-11 23:07:17.046094
- Title: Phase transitions in nonparametric regressions
- Title(参考訳): 非パラメトリック回帰における相転移
- Authors: Ying Zhu
- Abstract要約: 平均積分二乗誤差(MISE)の最小値の最適値は、文献では$left(frac1nright)frac2gamma+22gamma+3$と記述されている。
本論文の基本的な貢献は、滑らかな関数クラスのために開発した計量エントロピー境界の集合である。
- 参考スコア(独自算出の注目度): 0.8376091455761261
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: When the unknown regression function of a single variable is known to have
derivatives up to the $(\gamma+1)$th order bounded in absolute values by a
common constant everywhere or a.e. (i.e., $(\gamma+1)$th degree of smoothness),
the minimax optimal rate of the mean integrated squared error (MISE) is stated
as $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$ in the literature.
This paper shows that: (i) if $n\leq\left(\gamma+1\right)^{2\gamma+3}$, the
minimax optimal MISE rate is $\frac{\log n}{n\log(\log n)}$ and the optimal
degree of smoothness to exploit is roughly $\max\left\{ \left\lfloor \frac{\log
n}{2\log\left(\log n\right)}\right\rfloor ,\,1\right\} $; (ii) if
$n>\left(\gamma+1\right)^{2\gamma+3}$, the minimax optimal MISE rate is
$\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$ and the optimal degree
of smoothness to exploit is $\gamma+1$. The fundamental contribution of this
paper is a set of metric entropy bounds we develop for smooth function classes.
Some of our bounds are original, and some of them improve and/or generalize the
ones in the literature (e.g., Kolmogorov and Tikhomirov, 1959). Our metric
entropy bounds allow us to show phase transitions in the minimax optimal MISE
rates associated with some commonly seen smoothness classes as well as
non-standard smoothness classes, and can also be of independent interest
outside the nonparametric regression problems.
- Abstract(参考訳): 単一の変数の未知回帰関数が、至る所で共通定数で有界な$(\gamma+1)$thの微分を持つことが知られている(つまり、$(\gamma+1)$thの滑らかさの次数)とき、平均積分二乗誤差(MISE)の最小値の最適値は、文学において$\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$と記述される。
本稿では,
(i)$n\leq\left(\gamma+1\right)^{2\gamma+3}$の場合、minimaxの最適ミゼレートは$\frac{\log n}{n\log(\log n)}$であり、最適な滑らか性はおよそ$\max\left\{ \left\lfloor \frac{\log n}{2\log\left(\log n\right)}\right\rfloor ,\,1\right\} $;である。
(ii)$n>\left(\gamma+1\right)^{2\gamma+3}$の場合、ミニマックス最適ミゼレートは$\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$であり、悪用するための滑らかさの最適度は$\gamma+1$である。
本論文の基本的な貢献は、滑らかな関数クラスのために開発した計量エントロピー境界の集合である。
私たちの境界のいくつかはオリジナルであり、そのうちのいくつかは文学(例えば、コルモゴロフとティホミロフ、1959)の改善と一般化である。
我々の計量エントロピー境界は、よく見られる滑らか性クラスと非標準滑らか性クラスに付随するミニマックス最適MISEレートの位相遷移を示すことができ、非パラメトリック回帰問題以外の独立した関心を持つこともできる。
関連論文リスト
- Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes [29.466981306355066]
固定学習率$eta$の勾配降下はスムーズな関数を表す局所最小値しか見つからないことを示す。
また、$n$のデータポイントのサポートの厳密な内部で、$widetildeO(n-4/5)$のほぼ最適MSE境界を証明します。
論文 参考訳(メタデータ) (2024-06-10T22:57:27Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳(メタデータ) (2024-02-01T07:21:32Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳(メタデータ) (2022-06-16T17:10:57Z) - Sharper Rates for Separable Minimax and Finite Sum Optimization via
Primal-Dual Extragradient Methods [39.87865197769047]
分離可能なミニマックス最適化問題 $min_x max_y f(x) - g(y) + h(x, y)$, where $f$ and $g$ have smoothness and strong convexity parameters $(Lx, mux)$, $(Ly, muy)$, and $h$ is convex-concave with a $(Lambdaxx, Lambdaxy, Lambdayymuyright)$。
論文 参考訳(メタデータ) (2022-02-09T18:57:47Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。
我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文 参考訳(メタデータ) (2021-04-06T15:34:14Z) - Infinite-Horizon Offline Reinforcement Learning with Linear Function
Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。
低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
論文 参考訳(メタデータ) (2021-03-17T18:18:57Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳(メタデータ) (2021-03-02T06:53:44Z) - Revisiting EXTRA for Smooth Distributed Optimization [70.65867695317633]
改良された$Oleft(left(fracLmu+frac11-sigma_2(W)right)logfrac1epsilon (1-sigma_2(W))right)$。
高速化されたEXTRAの通信複雑性は、$left(logfracLmu (1-sigma_2(W))right)$と$left(logfrac1epsilon (1。
論文 参考訳(メタデータ) (2020-02-24T08:07:08Z) - Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond [25.845034951660544]
我々は,一階述語法では改善できないことを示した。
我々は、$$quasar のアログ関数を計算する変種加速降下を開発する。
ファーストオーダーの方法では改善できません。
論文 参考訳(メタデータ) (2019-06-27T22:39:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。