{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T06:10:19Z","timestamp":1762063819277,"version":"build-2065373602"},"reference-count":36,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2022,8,28]],"date-time":"2022-08-28T00:00:00Z","timestamp":1661644800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Natural Science Foundation of China","award":["1167121"],"award-info":[{"award-number":["1167121"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Axioms"],"abstract":"<jats:p>We propose the Weak Rescaled Pure Super Greedy Algorithm (WRPSGA) for approximation with respect to a dictionary D in Hilbert space. The WRPSGA is simpler than some popular greedy algorithms. We show that the convergence rate of the RPSGA on the closure of the convex hull of the \u03bc-coherent dictionary D is optimal. Then, we design the Rescaled Pure Super Greedy Learning Algorithm (RPSGLA) for kernel-based supervised learning. We prove that the convergence rate of the RPSGLA can be arbitrarily close to the best rate O(m\u22121) under some mild assumptions.<\/jats:p>","DOI":"10.3390\/axioms11090437","type":"journal-article","created":{"date-parts":[[2022,8,28]],"date-time":"2022-08-28T21:22:56Z","timestamp":1661721776000},"page":"437","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Optimality of the Approximation and Learning by the Rescaled Pure Super Greedy Algorithms"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6202-8311","authenticated-orcid":false,"given":"Wenhui","family":"Zhang","sequence":"first","affiliation":[{"name":"School of Mathematics and LPMC, Nankai University, Tianjin 300071, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peixin","family":"Ye","sequence":"additional","affiliation":[{"name":"School of Mathematics and LPMC, Nankai University, Tianjin 300071, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5585-6215","authenticated-orcid":false,"given":"Shuo","family":"Xing","sequence":"additional","affiliation":[{"name":"School of Mathematics and LPMC, Nankai University, Tianjin 300071, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xu","family":"Xu","sequence":"additional","affiliation":[{"name":"School of Science, China University of Geosciences, Beijing 100083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,8,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1017\/S0962492900002816","article-title":"Nonlinear approximation","volume":"7","author":"DeVore","year":"1998","journal-title":"Acta. Numer."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF02678464","article-title":"Rates of convex approximation in non-Hilbert spaces","volume":"13","author":"Donahue","year":"1997","journal-title":"Constr. Approx."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"2150001","DOI":"10.1142\/S0219691321500016","article-title":"Efficiency of the weak rescaled pure greedy algorithm","volume":"19","author":"Jiang","year":"2021","journal-title":"Int. J. Wavelets Multiresolut. Inf. Process."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2250010","DOI":"10.1142\/S0219691322500102","article-title":"Unified error estimate for weak biorthogonal Greedy algorithms","volume":"20","author":"Jiang","year":"2022","journal-title":"Int. J. Wavelets Multiresolut. Inf. Process."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"231","DOI":"10.3934\/ipi.2015.9.231","article-title":"Sparse signals recovery from noisy measurements by Orthogonal Matching Pursuit","volume":"9","author":"Shen","year":"2015","journal-title":"Inverse. Probl. Imag."},{"key":"ref_6","first-page":"21","article-title":"Efficiency of orthogonal super greedy algorithm under the restricted isometry property","volume":"124","author":"Wei","year":"2019","journal-title":"J. Inequal. Appl."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1007\/s00365-021-09553-2","article-title":"Numerical integration and discrepancy under smoothness assumption and without it","volume":"55","author":"Temlyakov","year":"2022","journal-title":"Constr. Approx."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1663","DOI":"10.1007\/s10114-005-0913-x","article-title":"Adaptive algorithms of nonlinear approximation with finite terms","volume":"23","author":"Wei","year":"2007","journal-title":"Acta. Math. Sin."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jfa.2019.108286","article-title":"A unified way of analyzing some greedy algorithms","volume":"277","author":"Dereventsov","year":"2019","journal-title":"J. Funct. Anal."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF02124742","article-title":"Some remarks on greedy algorithms","volume":"5","author":"DeVore","year":"1996","journal-title":"Adv. Comput. Math."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"852","DOI":"10.1016\/j.acha.2015.10.008","article-title":"Rescaled pure greedy algorithm for Hilbert and Banach spaces","volume":"41","author":"Petrova","year":"2016","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1750029","DOI":"10.1142\/S0219691317500291","article-title":"Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries","volume":"15","author":"Shao","year":"2017","journal-title":"Int. J. Wavelets Multiresolut. Inf. Process"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.knosys.2015.12.011","article-title":"Learning and approximation capability of orthogonal super greedy algorithm","volume":"95","author":"Fang","year":"2016","journal-title":"Knowl-Based. Syst."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2040","DOI":"10.1109\/TIT.2011.2177632","article-title":"The orthogonal super greedy algorithm and applications in compressed sensing","volume":"58","author":"Liu","year":"2012","journal-title":"IEEE. T. Inform. Theory."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Shao, C.F., Chang, J.C., Ye, P.X., Zhang, W.H., and Xing, S. (2022). Almost optimality of the orthogonal super greedy algorithm for \u03bc-coherent dictionaries. Axioms, 11.","DOI":"10.3390\/axioms11050186"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1214\/009053607000000631","article-title":"Approximation and learning by greedy algorithms","volume":"36","author":"Barron","year":"2008","journal-title":"Ann. Stat."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.measurement.2014.04.012","article-title":"GA-SELM: Greedy algorithms for sparse extreme learning machine","volume":"55","author":"Alcin","year":"2014","journal-title":"Measurement"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.neunet.2013.03.001","article-title":"Convergence rate of the semi-supervised greedy algorithm","volume":"44","author":"Chen","year":"2013","journal-title":"Neural Netw."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1638","DOI":"10.1109\/TPWRS.2019.2955376","article-title":"A Greedy Algorithm for observability analysis","volume":"35","author":"Herrero","year":"2020","journal-title":"IEEE. Trans. Power. Syst."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1598","DOI":"10.1109\/TNNLS.2013.2265397","article-title":"Learning capability of the relaxed greedy algorithms","volume":"24","author":"Lin","year":"2013","journal-title":"IEEE. Trans. Neur. Net. Lear."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"107305","DOI":"10.1016\/j.knosys.2021.107305","article-title":"Two-stage routing with optimized guided search and greedy algorithm on proximity graph","volume":"229","author":"Xu","year":"2021","journal-title":"Knowl-Based. Syst."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1016\/j.jspi.2012.08.002","article-title":"Learning rates of multi-kernel regression by orthogonal greedy algorithm","volume":"143","author":"Chen","year":"2013","journal-title":"J. Stat. Plan. Infer."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s10092-016-0183-2","article-title":"Greedy strategies for convex optimization","volume":"54","author":"Nguyen","year":"2017","journal-title":"Calcolo"},{"key":"ref_24","unstructured":"Zhang, W.H., Ye, P.X., and Xing, S. Optimality of the rescaled pure greedy learning algorithms, unpublished manuscript."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1090\/S0002-9947-1950-0051437-7","article-title":"Theory of reproducing kernels","volume":"68","author":"Aronszajn","year":"1950","journal-title":"Trans. Amer. Math. Soc."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Cucker, F., and Zhou, D.X. (2007). Learning Theory: An aPproximation Theory Viewpoint, Cambridge University Press.","DOI":"10.1017\/CBO9780511618796"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1016\/j.acha.2011.01.001","article-title":"Concentration estimates for learning with l1 regularizer and data dependent hypothesis spaces","volume":"31","author":"Shi","year":"2011","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1821","DOI":"10.11650\/twjm\/1500406018","article-title":"Learning by nonsymmetric kernel with data dependent spaces and l1-regularizer","volume":"14","author":"Xiao","year":"2010","journal-title":"Taiwan. J. Math."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/j.jco.2006.06.007","article-title":"Multi-kernel regularized classifiers","volume":"23","author":"Wu","year":"2007","journal-title":"J. Complexity."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1016\/j.acha.2012.05.001","article-title":"Learning theory estimates for coefficient-based regularized regression","volume":"34","author":"Shi","year":"2013","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"ref_31","first-page":"83","article-title":"A vectorial kernel orthogonal greedy algorithm","volume":"6","author":"Wirtz","year":"2013","journal-title":"Dolomit. Res. Notes. Approx."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s10543-021-00870-3","article-title":"Sampling based approximation of linear functionals in reproducing kernel Hilbert spaces","volume":"62","author":"Santin","year":"2022","journal-title":"Bit. Numer. Math."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding","year":"1963","journal-title":"J. Amer. Statist. Assoc."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/s10208-015-9248-x","article-title":"Convex optimization on Banach spaces","volume":"16","author":"DeVore","year":"2016","journal-title":"Found. Comput. Math."},{"key":"ref_35","first-page":"252","article-title":"Greedy expansions in convex optimization","volume":"284","author":"Temlyakov","year":"2014","journal-title":"P. Steklov. I. Math."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s00365-014-9272-0","article-title":"Greedy approximation in convex optimization","volume":"41","author":"Temlyakov","year":"2015","journal-title":"Constr. Approx."}],"container-title":["Axioms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2075-1680\/11\/9\/437\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:19:00Z","timestamp":1760141940000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2075-1680\/11\/9\/437"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,28]]},"references-count":36,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2022,9]]}},"alternative-id":["axioms11090437"],"URL":"https:\/\/doi.org\/10.3390\/axioms11090437","relation":{},"ISSN":["2075-1680"],"issn-type":[{"type":"electronic","value":"2075-1680"}],"subject":[],"published":{"date-parts":[[2022,8,28]]}}}