Learning Capability of Relaxed Greedy Algorithms
Abstract
In the practice of machine learning, one often encounters problems in which noisy data are abundant while the learning targets are imprecise and elusive. To these challenges, most of the traditional learning algorithms employ hypothesis spaces of large capacity. This has inevitably led to high computational burdens and caused considerable machine sluggishness. Utilizing greedy algorithms in this kind of learning environment has greatly improved machine performance. The best existing learning rate of various greedy algorithms is proved to achieve the order of (m/logm) -1/2 , where m is the sample size. In this paper, we provide a relaxed greedy algorithm and study its learning capability. We prove that the learning rate of the new relaxed greedy algorithm is faster than the order m -1/2 . Unlike many other greedy algorithms, which are often indecisive issuing a stopping order to the iteration process, our algorithm has a clearly established stopping criteria.
Department(s)
Mathematics
Document Type
Article
DOI
https://doi.org/10.1109/TNNLS.2013.2265397
Keywords
Algorithm, generalization error, learning theory, orthogonal greedy algorithm, relaxed greedy algorithm
Publication Date
2013
Recommended Citation
Lin, Shaobo, Yuanhua Rong, Xingping Sun, and Zongben Xu. "Learning capability of relaxed greedy algorithms." IEEE transactions on neural networks and learning systems 24, no. 10 (2013): 1598-1608.
Journal Title
IEEE transactions on neural networks and learning systems