論文の概要: Phase transitions in nonparametric regressions
- arxiv url: http://arxiv.org/abs/2112.03626v7
- Date: Thu, 2 Nov 2023 20:53:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-06 18:52:28.383889
- Title: Phase transitions in nonparametric regressions
- Title(参考訳): 非パラメトリック回帰における相転移
- Authors: Ying Zhu
- Abstract要約: 平均積分二乗誤差(MISE)の最小値の最適値は、文献では$left(frac1nright)frac2gamma+22gamma+3$と記述されている。
本論文の基本的な貢献は、滑らかな関数クラスのために開発した計量エントロピー境界の集合である。
- 参考スコア(独自算出の注目度): 1.6912763514570508
- 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レートの位相遷移を示すことができ、非パラメトリック回帰問題以外の独立した関心を持つこともできる。
関連論文リスト
- 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 [77.57736777744934]
この論文は、広く使用されている加速勾配追跡を再検討し、拡張する。
私たちの複雑さは $cal O(frac1epsilon5/7)$ と $cal 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) - Classes of ODE solutions: smoothness, covering numbers, implications for
noisy function fitting, and the curse of smoothness phenomenon [0.8376091455761261]
ODE のクラスの滑らかさの度合いと「サイズ」が、関連する解のクラスの「サイズ」に影響を与えることを示す。
我々の結果は「ODEのクラスの滑らかさの程度と「サイズ」が関連する解のクラスの「サイズ」にどのように影響するか」という答えを提供する。
論文 参考訳(メタデータ) (2020-11-23T12:54:54Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。