标题： 逼近与贪婪算法的学习 显示英文标题

标题： Approximation and learning by greedy algorithms

摘要： 我们研究了利用贪婪算法从希尔伯特空间$\mathcal{H}$中逼近给定元素$f$的问题，并探讨了这些方法在统计学习理论回归问题中的应用。 我们改进了关于正交贪婪算法、松弛贪婪算法以及前向逐步投影算法收敛速度的现有理论。 对于所有这些算法，我们证明了针对多种函数类别的收敛结果，而不仅仅是与字典凸包相关的那些函数类。 接着，我们展示了这些收敛速度的界如何导致贪婪算法在学习性能方面的新理论。 特别是，我们基于 IEEE Trans. Inform. Theory 42 (1996) 2118--2132 中的结果，构建了基于贪婪逼近的学习算法，这些算法具有普遍一致性，并对大量函数类提供可证明的收敛速度。 在学习背景下使用贪婪算法非常有吸引力，因为它与使用通用字典的标准模型选择相比，大大减少了计算负担。 显示英文摘要

摘要： We consider the problem of approximating a given element $f$ from a Hilbert space $\mathcal{H}$ by means of greedy algorithms and the application of such procedures to the regression problem in statistical learning theory. We improve on the existing theory of convergence rates for both the orthogonal greedy algorithm and the relaxed greedy algorithm, as well as for the forward stepwise projection algorithm. For all these algorithms, we prove convergence results for a variety of function classes and not simply those that are related to the convex hull of the dictionary. We then show how these bounds for convergence rates lead to a new theory for the performance of greedy algorithms in learning. In particular, we build upon the results in [IEEE Trans. Inform. Theory 42 (1996) 2118--2132] to construct learning algorithms based on greedy approximations which are universally consistent and provide provable convergence rates for large classes of functions. The use of greedy algorithms in the context of learning is very appealing since it greatly reduces the computational burden when compared with standard model selection using general dictionaries.