Title: Structure in high-dimensional non-parametric problems: Two modern vignettes

Abstract: Non-parametric estimation problems in high dimensions see applications across scientific disciplines. However, they suffer from the curse of dimensionality: The number of samples required to achieve a prescribed error tolerance grows exponentially in the ambient dimension. It is thus of interest to impose natural structure in such problems to ensure both sample-efficiency and computational tractability. This talk will present two modern takes on classical problems in this space. The first is the problem of fitting high dimensional convex functions from noisy observations, also known as convex regression. In order to avoid the curse of dimensionality, we study the problem of "max-affine" regression, in which the underlying convex function is equipped with additional structure and can be written as the point-wise maximum of a small number of affine functions. We analyze a well-known alternating minimization heuristic for this task, showing that it converges to the true model, at the optimal rate, under some random design assumptions. The second vignette concerns the single-index model, which is a widely used semi-parametric model for non-linear dimensionality reduction. We describe a new, computationally efficient methodology for parameter estimation under this model that generalizes known heuristics for special cases, and achieves automatic adaptation to the noise level of the problem. Consequently, when the signal-to-noise to noise ratio in the model is high, we significantly reduce the bias in classical approaches in order to provide much sharper parameter estimates. Throughout the talk, connections will be made to phase retrieval, which is a widely studied special case of both of these problems. The talk is based on joint work with Dean P. Foster, Avishek Ghosh, Adityanand Guntuboyina, Kannan Ramchandran, and Martin J. Wainwright.


Bio: Ashwin Pananjady is a Ph.D. student in the EECS Department at UC Berkeley, advised by Martin Wainwright and Thomas Courtade. His interests are in statistics, machine learning, information theory, and optimization. He is a recipient of the inaugural Lawrence Brown PhD student award from the Institute of Mathematical Statistics, an Outstanding Graduate Student Instructor award from UC Berkeley, and the Governor's Gold Medal from IIT Madras.