2018/03/21 by Miles E. Lopes, Lopes, Miles E., Shusen Wang +3
Computer Science · Engineering · #Advanced Multi-Objective Optimization Algorithms #Computation (stat.CO) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1803.08021
openalex publication_date 2018/03/21 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
Over the course of the past decade, a variety of randomized algorithms have\nbeen proposed for computing approximate least-squares (LS) solutions in\nlarge-scale settings. A longstanding practical issue is that, for any given\ninput, the user rarely knows the actual error of an approximate solution\n(relative to the exact solution). Likewise, it is difficult for the user to\nknow precisely how much computation is needed to achieve the desired error\ntolerance. Consequently, the user often appeals to worst-case error bounds that\ntend to offer only qualitative guidance. As a more practical alternative, we\npropose a bootstrap method to compute a posteriori error estimates for\nrandomized LS algorithms. These estimates permit the user to numerically assess\nthe error of a given solution, and to predict how much work is needed to\nimprove a "preliminary" solution. In addition, we provide theoretical\nconsistency results for the method, which are the first such results in this\ncontext (to the best of our knowledge). From a practical standpoint, the method\nalso has considerable flexibility, insofar as it can be applied to several\npopular sketching algorithms, as well as a variety of error metrics. Moreover,\nthe extra step of error estimation does not add much cost to an underlying\nsketching algorithm. Finally, we demonstrate the effectiveness of the method\nwith empirical results.\n