2021/08/11 by Philipp Trunschke, Trunschke, Philipp · 2 citations
Computer Science · Engineering · Mathematics · #15A69 #41A30 #62J02 #65Y20 #68Q25 #Applied mathematics #Combinatorics #Computer science #Convergence (economics) #FOS: Computer and information sciences #FOS: Mathematics #Function (biology) #Image and Signal Denoising Methods #Machine Learning (cs.LG) #Mathematical optimization #Mathematics #Monte Carlo method #Nonlinear system #Norm (philosophy) #Numerical Analysis (math.NA) #Probability (math.PR) #Rank (graph theory) #Rate of convergence #Sparse and Compressive Sensing Techniques #Statistics #Tensor decomposition and applications #cs.LG #cs.NA #math.NA #math.PR #msc:15A69 #msc:41A30 #msc:62J02 #msc:65Y20 #msc:68Q25
paper · pdf · doi:10.48550/arxiv.2108.05237
published in arXiv (Cornell University) (Cornell University) · 29 pages, 6 figures, 2 tables
arxiv created 2021/08/11 · openalex publication_date 2021/08/11 · arxiv updated 2021/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of approximating a function in general nonlinear subsets of L2 when only a weighted Monte Carlo estimate of the L2-norm can be computed. Of particular interest in this setting is the concept of sample complexity, the number of samples that are necessary to recover the best approximation. Bounds for this quantity have been derived in a previous work and depend primarily on the model class and are not influenced positively by the regularity of the sought function. This result however is only a worst-case bound and is not able to explain the remarkable performance of iterative hard thresholding algorithms that is observed in practice. We reexamine the results of the previous paper and derive a new bound that is able to utilize the regularity of the sought function. A critical analysis of our results allows us to derive a sample efficient algorithm for the model set of low-rank tensors. The viability of this algorithm is demonstrated by recovering quantities of interest for a classical high-dimensional random partial differential equation.