Shape-constrained estimation techniques such as convex regression or log-concave density estimation o er attractive alternatives to traditional nonparametric methods. Shape-constrained estimation often has an easy- to-optimize likelihood, no tuning parameter, and an adaptivity property where the sample complexity adapts to the complexity of the underlying functions. In this dissertation, we posit that shape-constrained estimation has an additional advantage in that they are naturally suited to the high-dimensional regime, where the number of variables is large relative to the number of samples.

In the first part of this dissertation, we study high dimensional convex regression and demonstrate that convex regression surprisingly has the additive faithfulness property, where the additive approximation is guaranteed to capture all relevant variables even if the underlying function is not additive. We propose a practical variable selection procedure for high dimensional convex regression based on this observation. The overall work provides a practical smoothing-free semi-parametric generalization of the Lasso.

We generalize our work on high dimensional convex regression to discrete choice models, in which a consumer chooses between m items x₁,...,x_m with probability proportional to exp ƒ(x₁) for a utility function ƒ. We show that additive faithfulness applies also in this setting. We accordingly adapt our method to the estimation of the utility function. In the last part, we consider the problem of learning the orientation pattern in additive shape-constraint models. Brute force search in this problem requires times exponential in the dimensionality. We propose a relaxation approach, based on trend filtering and motivated by our identifiability analysis, that is computationally efficient and effective.

134 pages

Thesis Committee:
John Lafferty (Chair)
Aarti Singh
Larry Wasserman Yu
Ming Yuan (University of Wisconsin, Madison)

Tom M. Mitchell, Head, Machine Learning Department
Andrew W. Moore, Dean, School of Computer Science