2019/06/21 by Avishek Ghosh, Ghosh, Avishek, Ashwin Pananjady +5
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)
paper · pdf · doi:10.48550/arxiv.1906.09255
openalex publication_date 2019/06/21 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
Max-affine regression refers to a model where the unknown regression function\nis modeled as a maximum of k unknown affine functions for a fixed k \≥ 1.\nThis generalizes linear regression and (real) phase retrieval, and is closely\nrelated to convex regression. Working within a non-asymptotic framework, we\nstudy this problem in the high-dimensional setting assuming that k is a fixed\nconstant, and focus on estimation of the unknown coefficients of the affine\nfunctions underlying the model. We analyze a natural alternating minimization\n(AM) algorithm for the non-convex least squares objective when the design is\nrandom. We show that the AM algorithm, when initialized suitably, converges\nwith high probability and at a geometric rate to a small ball around the\noptimal coefficients. In order to initialize the algorithm, we propose and\nanalyze a combination of a spectral method and a random search scheme in a\nlow-dimensional space, which may be of independent interest. The final rate\nthat we obtain is near-parametric and minimax optimal (up to a poly-logarithmic\nfactor) as a function of the dimension, sample size, and noise variance. In\nthat sense, our approach should be viewed as a direct and implementable method\nof enforcing regularization to alleviate the curse of dimensionality in\nproblems of the convex regression type. As a by-product of our analysis, we\nalso obtain guarantees on a classical algorithm for the phase retrieval problem\nunder considerably weaker assumptions on the design distribution than was\npreviously known. Numerical experiments illustrate the sharpness of our bounds\nin the various problem parameters.\n