2018/03/12 by Junhong Lin, Volkan Cevher, Lin, Junhong +1
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical methods in inverse problems #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1803.04371
openalex publication_date 2018/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate regularized algorithms combining with projection for least-squares regression problem over a Hilbert space, covering nonparametric regression over a reproducing kernel Hilbert space. We prove convergence results with respect to variants of norms, under a capacity assumption on the hypothesis space and a regularity condition on the target function. As a result, we obtain optimal rates for regularized algorithms with randomized sketches, provided that the sketch dimension is proportional to the effective dimension up to a logarithmic factor. As a byproduct, we obtain similar results for Nyström regularized algorithms. Our results are the first ones with optimal, distribution-dependent rates that do not have any saturation effect for sketched/Nyström regularized algorithms, considering both the attainable and non-attainable cases.