Optimal convergence rate of the universal estimation error

详细信息    查看全文

• 作者：E. Weinan ; Yao Wang
• 刊名：Research in the Mathematical Sciences
• 出版年：2017
• 出版时间：December 2017
• 年：2017
• 卷：4
• 期：1
• 全文大小：620KB
• 刊物类别：Mathematics, general; Applications of Mathematics; Computational Mathematics and Numerical Analysis;
• 刊物主题：Mathematics, general; Applications of Mathematics; Computational Mathematics and Numerical Analysis;
• 出版者：Springer International Publishing
• ISSN：2197-9847
• 卷排序：4

文摘

We study the optimal convergence rate for the universal estimation error. Let \(\mathcal {F}\) be the excess loss class associated with the hypothesis space and n be the size of the data set, we prove that if the Fat-shattering dimension satisfies \(\text {fat}_{\epsilon } (\mathcal {F})= O(\epsilon ^{-p})\), then the universal estimation error is of \(O(n^{-1/2})\) for \(p<2\) and \(O(n^{-1/p})\) for \(p>2\). Among other things, this result gives a criterion for a hypothesis class to achieve the minimax optimal rate of \(O(n^{-1/2})\). We also show that if the hypothesis space is the compact supported convex Lipschitz continuous functions in \(\mathbb {R}^d\) with \(d>4\), then the rate is approximately \(O(n^{-2/d})\).