2019/06/21 by Avishek Ghosh, Ghosh, Avishek, Ashwin Pananjady +5 · 2 citations
Computer Science · Engineering · Mathematics · #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Statistics Theory (math.ST) #cs.IT #cs.LG #math.IT #math.ST #stat.ML #stat.TH
paper · pdf · doi:10.48550/arxiv.1906.09255
The first two authors contributed equally to this work and are ordered alphabetically
arxiv created 2019/06/21 · openalex publication_date 2019/06/21 · arxiv updated 2019/06/24 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
Max-affine regression refers to a model where the unknown regression function is modeled as a maximum of k unknown affine functions for a fixed k ≥ 1. This generalizes linear regression and (real) phase retrieval, and is closely related to convex regression. Working within a non-asymptotic framework, we study this problem in the high-dimensional setting assuming that k is a fixed constant, and focus on estimation of the unknown coefficients of the affine functions underlying the model. We analyze a natural alternating minimization (AM) algorithm for the non-convex least squares objective when the design is random. We show that the AM algorithm, when initialized suitably, converges with high probability and at a geometric rate to a small ball around the optimal coefficients. In order to initialize the algorithm, we propose and analyze a combination of a spectral method and a random search scheme in a low-dimensional space, which may be of independent interest. The final rate that we obtain is near-parametric and minimax optimal (up to a poly-logarithmic factor) as a function of the dimension, sample size, and noise variance. In that sense, our approach should be viewed as a direct and implementable method of enforcing regularization to alleviate the curse of dimensionality in problems of the convex regression type. As a by-product of our analysis, we also obtain guarantees on a classical algorithm for the phase retrieval problem under considerably weaker assumptions on the design distribution than was previously known. Numerical experiments illustrate the sharpness of our bounds in the various problem parameters.