Machine Learning Department
School of Computer Science, Carnegie Mellon University


Shape-Constrained Estimation in High Demensions

Min Xu

June 2015

Ph.D. Thesis


Keywords: NA

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 x1,...,xm with probability proportional to exp ƒ(x1) 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

SCS Technical Report Collection
School of Computer Science