More Like this

1. Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression

   Peng, Liangzu; Kümmerle, Christian; Vidal, René (December 2022, Neural Information Processing Systems)

   We advance both the theory and practice of robust ℓp-quasinorm regression for p ∈ (0,1] by using novel variants of iteratively reweighted least-squares (IRLS) to solve the underlying non-smooth problem. In the convex case, p =1, we prove that this IRLS variant converges globally at a linear rate under a mild, deterministic condition on the feature matrix called the stable range space property. In the non-convex case, p ∈ (0,1), we prove that under a similar condition, IRLS converges locally to the global minimizer at a superlinear rate of order 2−p; the rate becomes quadratic as p→0. We showcase the proposed methods in three applications: real phase retrieval, regression without correspondences, and robust face restoration. The results show that (1) IRLS can handle a larger number of outliers than other methods, (2) it is faster than competing methods at the same level of accuracy, (3) it restores a sparsely corrupted face image with satisfactory visual quality. 

   more » « less
2. Improved Convergence for $$\ell_\infty$$ and $$\ell_1$$ Regression via Iteratively Reweighted Least Squares

   Ene, Alina; Vladu, Adrian (June 2019, Proceedings of Machine Learning Research)

   The iteratively reweighted least squares method (IRLS) is a popular technique used in practice for solving regression problems. Various versions of this method have been proposed, but their theoretical analyses failed to capture the good practical performance. In this paper we propose a simple and natural version of IRLS for solving $$\ell_\infty$$ and $$\ell_1$$ regression, which provably converges to a $$(1+\epsilon)$$-approximate solution in $$O(m^{1/3}\log(1/\epsilon)/\epsilon^{2/3} + \log m/\epsilon^2)$$ iterations, where $$m$$ is the number of rows of the input matrix. Interestingly, this running time is independent of the conditioning of the input, and the dominant term of the running time depends sublinearly in $$\epsilon^{-1}$$, which is atypical for the optimization of non-smooth functions. This improves upon the more complex algorithms of Chin et al. (ITCS '12), and Christiano et al. (STOC '11) by a factor of at least $$1/\epsilon^2$$, and yields a truly efficient natural algorithm for the slime mold dynamics (Straszak-Vishnoi, SODA '16, ITCS '16, ITCS '17). 

   more » « less
3. Outlier-Robust Sparse Estimation via Non-Convex Optimization

   Cheng, Yu; Diakonikolas, Ilias; Ge, Rong; Gupta, Shivam; Kane, Daniel; Soltanolkotabi, Mahdi (January 2022, Advances in neural information processing systems)

   We explore the connection between outlier-robust high-dimensional statistics and non-convex optimization in the presence of sparsity constraints, with a focus on the fundamental tasks of robust sparse mean estimation and robust sparse PCA. We develop novel and simple optimization formulations for these problems such that any approximate stationary point of the associated optimization problem yields a near-optimal solution for the underlying robust estimation task. As a corollary, we obtain that any first-order method that efficiently converges to stationarity yields an efficient algorithm for these tasks. The obtained algorithms are simple, practical, and succeed under broader distributional assumptions compared to prior work. 

   more » « less
4. Outlier-Robust Sparse Estimation via Non-Convex Optimization

   Cheng, Yu; Diakonikolas, Ilias; Ge, Rong; Gupta, Shivam; Kane, Daniel M.; Soltanolkotabi, Mahdi (January 2022, Conference on Neural Information Processing Systems)

   We explore the connection between outlier-robust high-dimensional statistics and non-convex optimization in the presence of sparsity constraints, with a focus on the fundamental tasks of robust sparse mean estimation and robust sparse PCA. We develop novel and simple optimization formulations for these problems such that any approximate stationary point of the associated optimization problem yields a near-optimal solution for the underlying robust estimation task. As a corollary, we obtain that any first-order method that efficiently converges to stationarity yields an efficient algorithm for these tasks.1 The obtained algorithms are simple, practical, and succeed under broader distributional assumptions compared to prior work. 

   more » « less
5. Outlier-Robust Sparse Estimation via Non-Convex Optimization

   Cheng, Yu; Diakonikolas, Ilias; Ge, Rong; Gupta, Shivam; Kane, Daniel M.; Soltanolkotabi, Mahdi (January 2022, Proceedings of the 36th Conference on Neural Information Processing Systems)

   We explore the connection between outlier-robust high-dimensional statistics and non-convex optimization in the presence of sparsity constraints, with a focus on the fundamental tasks of robust sparse mean estimation and robust sparse PCA. We develop novel and simple optimization formulations for these problems such that any approximate stationary point of the associated optimization problem yields a near-optimal solution for the underlying robust estimation task. As a corollary, we obtain that any first-order method that efficiently converges to stationarity yields an efficient algorithm for these tasks. The obtained algorithms are simple, practical, and succeed under broader distributional assumptions compared to prior work. 

   more » « less