Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression
Authors: Deeksha Adil, Richard Peng, Sushant Sachdeva
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments demonstrate that it performs even better than our theoretical bounds, beats the standard Matlab/CVX implementation for solving these problems by 10 50x, and is the fastest among available implementations in the high-accuracy regime. In this section, we detail our results from experiments studying the performance of our algorithm, p-IRLS. We implemented our algorithm in Matlab on a standard desktop machine, and evaluated its performance on two types of instances, random instances for p-regression, and graphs for p-Laplacian minimization. |
| Researcher Affiliation | Academia | Deeksha Adil Department of Computer Science University of Toronto deeksha@cs.toronto.edu Richard Peng School of Computer Science Georgia Institute of Technology rpeng@cc.gatech.edu Sushant Sachdeva Department of Computer Science University of Toronto sachdeva@cs.toronto.edu |
| Pseudocode | Yes | Algorithm 1 p-IRLS Algorithm |
| Open Source Code | Yes | Code for this work is available at https://github.com/utoronto-theory/p IRLS. |
| Open Datasets | Yes | 1. Random Matrices: We want to solve the problem minx k Ax bkp. In these instances we use random matrices A and b, where every entry of the matrix is chosen uniformly at random between 0 and 1. 2. Graphs: We use the graphs described in [RCL19]. The set of vertices is generated by choosing vectors in [0, 1]10 uniformly at random and the edges are created by connecting the 10 nearest neighbours. Weights of each edge is specified by a gaussian type function (Eq 3.1,[RCL19]). |
| Dataset Splits | No | The paper does not provide specific train/validation/test dataset splits, percentages, or sample counts. |
| Hardware Specification | Yes | All experiments were performed on MATLAB 2018b on a Desktop ubuntu machine with an Intel Core i5-4570 CPU @ 3.20GHz 4 processor and 4GB RAM. |
| Software Dependencies | Yes | All experiments were performed on MATLAB 2018b on a Desktop ubuntu machine with an Intel Core i5-4570 CPU @ 3.20GHz 4 processor and 4GB RAM. |
| Experiment Setup | Yes | We normalize the instances by running our algorithm once and dividing the vector b by the norm of the final objective, so that our norms at the end are around 1. We do this for every instance before we measure the runtime or the iteration count for uniformity and to avoid numerical precision issues. ... For the graph instances, we fix the dimension of the space from which we choose vertices to 10 and the number of labelled vertices to be 10. The graph instances are generated using the code [Rio19] by [RCL19]. Other details specific to the experiment are given in the captions. Precision set to " = 10 8. |