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 \\geq 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