Nonparametric function estimation is a quintessential problem in statistical data-analysis with widespread applications in online advertising, econometrics, operations research, etc. We consider the problem of estimating functions are (a) smooth and have (b) shape constraints (monotonicity, convexity, etc.). This leads to an infinite-dimensional convex quadratic optimization problem posing computational challenges. We propose a framework to jointly achieve goals (a), (b). Time permitting, we will discuss the problem of fitting a multivariate convex function to data.
joint work with Rahul Mazumder
In many learning settings, it is beneficial to augment the main features with pairwise interactions. Such interaction models can be enhanced by performing variable selection under the so-called “strong hierarchy” constraint. Existing convex optimization based algorithms face difficulties in handling problems where the number of main features is beyond a thousand. We propose convex first order algorithms to exactly solve the problem with up to a billion variables on a single machine. We also discuss how to solve the original nonconvex problem via a tailored branch-and-bound algorithm.