jmlr jmlr2013 jmlr2013-74 jmlr2013-74-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Lauren A. Hannah, David B. Dunson
Abstract: We propose a new, nonparametric method for multivariate regression subject to convexity or concavity constraints on the response function. Convexity constraints are common in economics, statistics, operations research, financial engineering and optimization, but there is currently no multivariate method that is stable and computationally feasible for more than a few thousand observations. We introduce convex adaptive partitioning (CAP), which creates a globally convex regression model from locally linear estimates fit on adaptively selected covariate partitions. CAP is a computationally efficient, consistent method for convex regression. We demonstrate empirical performance by comparing the performance of CAP to other shape-constrained and unconstrained regression methods for predicting weekly wages and value function approximation for pricing American basket options. Keywords: adaptive partitioning, convex regression, nonparametric regression, shape constraint, treed linear model
N´ stor Aguilera and Pedro Morin. Approximating optimization problems over convex functions. e Numerische Mathematik, 111(1):1–34, 2008. N´ stor Aguilera and Pedro Morin. On convex functions and the finite element method. SIAM e Journal on Numerical Analysis, 47(1):3139–3157, 2009. N´ stor Aguilera, Liliana Forzani, and Pedro Morin. On uniform consistent estimators for convex e regression. Journal of Nonparametric Statistics, 23(4):897–908, 2011. Yacine A¯t-Sahalia and Jefferson Duarte. Nonparametric option pricing under shape restrictions. ı Journal of Econometrics, 116(1–2):9–47, 2003. William P. Alexander and Scott D. Grimshaw. Treed regression. Journal of Computational and Graphical Statistics, 5(2):156–175, 1996. Gad Allon, Michael Beenstock, Steven Hackman, Ury Passy, and Alexander Shapiro. Nonparametric estimation of concave production technologies by entropic methods. Journal of Applied Econometrics, 22(4):795–816, 2007. Herman J. Bierens and Donna K. Ginther. Integrated conditional moment testing of quantile regression models. Empirical Economics, 26(1):307–324, 2001. Melanie Birke and Holger Dette. Estimating a convex function in nonparametric regression. Scandinavian Journal of Statistics, 34(2):384–404, 2007. Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, United Kingdom, 2004. Stephen Boyd, Seung-Jean Kim, Lieven Vandenberghe, and Arash Hassibi. A tutorial on geometric programming. Optimization and Engineering, 8(1):67–127, 2007. 3289 H ANNAH AND D UNSON Leo Breiman. Hinging hyperplanes for regression, classification, and function approximation. IEEE Transactions on Information Theory, 39(3):999–1013, 1993. Leo Breiman. Bagging predictors. Machine Learning, 24(2):123–140, 1996. Leo Breiman. Randomizing outputs to increase prediction accuracy. Machine Learning, 40(3): 229–242, 2000. Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. Classification and Regression Trees. Chapman & Hall/CRC, Boca Raton, Florida, 1984. Hugh D. Brunk. Maximum likelihood estimates of monotone parameters. The Annals of Mathematical Statistics, 26(4):607–616, 1955. Jacques F. Carriere. Valuation of the early-exercise price for options using simulations and nonparametric regression. Insurance: Mathematics and Economics, 19(1):19–30, 1996. I-Shou Chang, Li-Chu Chien, Chao A. Hsiung, Chi-Chung Wen, and Yuh-Jenn Wu. Shape restricted regression with random Bernstein polynomials. IMS Lecture Notes-Monograph Series, 54:187– 202, 2007. Probal Chaudhuri, Min-Ching Huang, Wei-Yin Loh, and Ruji Yao. Piecewise-polynomial regression trees. Statistica Sinica, 4(1):143–167, 1994. Probal Chaudhuri, Wen-Da Lo, Wei-Yin Loh, and Ching-Ching Yang. Generalized regression trees. Statistica Sinica, 5(1):641–666, 1995. Madeleine Cule and Richard Samworth. Theoretical properties of the log-concave maximum likelihood estimator of a multidimensional density. Electronic Journal of Statistics, 4:254–270, 2010. Madeleine Cule, Richard Samworth, and Michael Stewart. Maximum likelihood estimation of a multi-dimensional log-concave density. Journal of the Royal Statistical Society, Series B, 72(5): 545–607, 2010. Warren Dent. A note on least squares fitting of functions constrained to be either nonnegative, nondecreasing or convex. Management Science, 20(1):130–132, 1973. Alin Dobra and Johannes Gehrke. SECRET: a scalable linear regression tree algorithm. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 481–487, Berlin, Germany, 2002. ACM. Richard L. Dykstra. An algorithm for restricted least squares regression. Journal of the American Statistical Association, 78(384):837–842, 1983. Donald A. S. Fraser and H´ l` ne Massam. A mixed primal-dual bases algorithm for regression under ee inequality constraints. Application to concave regression. Scandinavian Journal of Statistics, 16 (1):65–74, 1989. Jerome H. Friedman. Multivariate adaptive regression splines. The Annals of Statistics, 19(1): 1–141, 1991. 3290 M ULTIVARIATE C ONVEX R EGRESSION WITH A DAPTIVE PARTITIONING Paul Glasserman. Monte Carlo Methods in Financial Engineering. Springer Verlag, New York, New York, 2004. Gene H. Golub, Michael Heath, and Grace Wahba. Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics, 21(2):215–223, 1979. Michael Grant and Stephen Boyd. Graph implementations for nonsmooth convex programs. In V. Blondel, S. Boyd, and H. Kimura, editors, Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences, pages 95–110. Springer-Verlag Limited, 2008. http: //stanford.edu/˜boyd/graph_dcp.html. Michael Grant and Stephen Boyd. CVX: Matlab software for disciplined convex programming, version 2.0 beta. http://cvxr.com/cvx, September 2012. Piet Groeneboom, Geurt Jongbloed, and Jon A. Wellner. Estimation of a convex function: characterizations and asymptotic theory. Annals of Statistics, 29(6):1653–1698, 2001. L´ szl´ Gy¨ rfi, Michael Kohler, Adam Krzy˙ ak, and Harro Walk. A Distribution-Free Theory of a o o z Nonparametric Regression. Springer, New York, New York, 2002. Peter Hall and Li-Shan Huang. Nonparametric kernel regression subject to monotonicity constraints. The Annals of Statistics, 29(3):624–647, 2001. Lauren A. Hannah and David B. Dunson. Bayesian nonparametric multivariate convex regression. Technical Report arXiv:1109.0322v1, Department of Statistical Science, Duke University, Durham, North Carolina, 2011. Lauren A. Hannah and David B. Dunson. Ensemble methods for convex regression with applications to geometric programming based circuit design. In Proceedings of the 29th Annual International Conference on Machine Learning, Edinburgh, United Kingdom, 2012. D. L. Hanson and Gordon Pledger. Consistency in concave regression. The Annals of Statistics, 4 (6):1038–1050, 1976. Martin B. Haugh and Leonid Kogan. Pricing American options: a duality approach. Operations Research, 52(2):258–270, 2004. Daniel J. Henderson and Christopher F. Parmeter. Imposing economic constraints in nonparametric regression: survey, implementation and extension. In Q. Li and J. S. Racine, editors, Nonparametric Econometric Methods (Advances in Econometrics), volume 25, pages 433–469. Emerald Publishing Group Limited, Bingley, United Kingdom, 2009. Clifford Hildreth. Point estimates of ordinates of concave functions. Journal of the American Statistical Association, 49(267):598–619, 1954. Charles A. Holloway. On the estimation of convex functions. Operations Research, 27(2):401–407, 1979. Arezou Keshavarz, Yang Wang, and Stephen Boyd. Imputing a convex objective function. In Proceedings of the IEEE International Symposium on Intelligent Control, pages 613–619, Denver, Colorado, 2011. 3291 H ANNAH AND D UNSON Jintae Kim, Jaeseo Lee, Lieven Vandenberghe, and C.K.-Ken Yang. Techniques for improving the accuracy of geometric-programming based analog circuit design optimization. In Proceedings of the IEEE International Conference on Computer Aided Design, pages 863–870, San Jose, California, 2004. Farinaz Koushanfar, Mehrdad Majzoobi, and Miodrag Potkonjak. Nonparametric combinatorial regression for shape constrained modeling. IEEE Transactions on Signal Processing, 58(2):626– 637, 2010. Timo Kuosmanen. Representation theorem for convex nonparametric least squares. Econometrics Journal, 11(2):308–325, 2008. Timo Kuosmanen and Andrew L. Johnson. Data envelopment analysis as nonparametric leastsquares regression. Operations Research, 58(1):149–160, 2010. Eunji Lim. Response surface computation via simulation in the presence of convexity constraints. In Proceedings of the 2010 Winter Simulation Conference, pages 1246–1254, Baltimore, Maryland, 2010. Eunji Lim and Peter W. Glynn. Consistency of multi-dimensional convex regression. Operations Research, 60(1):196–208, 2012. Francis A. Longstaff and Eduardo S. Schwartz. Valuing American options by simulation: a simple least-squares approach. Review of Financial Studies, 14(1):113–147, 2001. Alessandro Magnani and Stephen Boyd. Convex piecewise-linear fitting. Optimization and Engineering, 10(1):1–17, 2009. Enno Mammen. Nonparametric regression under qualitative smoothness assumptions. The Annals of Statistics, 19(2):741–759, 1991. Mary C. Meyer. Inference using shape-restricted regression splines. Annals of Applied Statistics, 2 (3):1013–1033, 2008. Mary C. Meyer, Amber J. Hackstadt, and Jennifer A. Hoeting. Bayesian estimation and inference for generalised partial linear models using shape-restricted splines. Journal of Nonparametric Statistics, 23(4):867–884, 2011. Renato D. C. Monteiro and Ilan Adler. Interior path following primal-dual algorithms. Part II: convex quadratic programming. Mathematical Programming, 44(1–3):43–66, 1989. Brian Neelon and David B. Dunson. Bayesian isotonic regression and trend analysis. Biometrics, 60(2):398–406, 2004. Andrew Nobel. Histogram regression estimation using data-dependent partitions. The Annals of Statistics, 24(3):1084–1105, 1996. Duncan Potts and Claude Sammut. Incremental learning of linear model trees. Machine Learning, 61(1):5–48, 2005. 3292 M ULTIVARIATE C ONVEX R EGRESSION WITH A DAPTIVE PARTITIONING Warren B. Powell. Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley-Interscience, Hoboken, New Jersey, 2007. J. Ross Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, Inc., San Mateo, California, 1993. Carl E. Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning. MIT Press, Cambridge, Massachusetts, 2006. Sanghamitra Roy, Weijen Chen, Charlie Chung-Ping Chen, and Yu Hen Hu. Numerically convex forms and their application in gate sizing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 26(9):1637–1647, 2007. Dominic Schuhmacher and Lutz D¨ mbgen. Consistency of multivariate log-concave density estiu mators. Statistics & Probability Letters, 80(5-6):376–380, 2010. Emilio Seijo and Bodhisattva Sen. Nonparametric least squares estimation of a multivariate convex regression function. The Annals of Statistics, 39(3):1580–1607, 2011. Thomas S. Shively, Thomqw W. Sager, and Stephen G. Walker. A Bayesian approach to nonparametric monotone function estimation. Journal of the Royal Statistical Society, Series B, 71 (1):159–175, 2009. Thomas S. Shively, Stephen G. Walker, and Paul Damien. Nonparametric function estimation subject to monotonicity, convexity and other shape constraints. Journal of Econometrics, 161(2): 166–181, 2011. Huseyin Topaloglu and Warren B. Powell. An algorithm for approximating piecewise linear concave functions from sample gradients. Operations Research Letters, 31(1):66–76, 2003. Alejandro Toriello, George Nemhauser, and Martin Savelsbergh. Decomposing inventory routing problems with approximate value functions. Naval Research Logistics, 57(8):718–727, 2010. John N. Tsitsiklis and Benjamin Van Roy. Optimal stopping of Markov processes: Hilbert space theory, approximation algorithms, and an application to pricing high-dimensional financial derivatives. IEEE Transactions on Automatic Control, 44(10):1840–1851, 1999. John N. Tsitsiklis and Benjamin Van Roy. Regression methods for pricing complex American-style options. IEEE Transactions on Neural Networks, 12(4):694–703, 2001. Berwin A. Turlach. Shape constrained smoothing using smoothing splines. Computational Statistics, 20(1):81–103, 2005. Hal R. Varian. The nonparametric approach to demand analysis. Econometrica, 50(4):945–973, 1982. Hal R. Varian. The nonparametric approach to production analysis. Econometrica, 52(3):579–597, 1984. Yongqiao Wang and He Ni. Multivariate convex support vector regression with semidefinite programming. Knowledge-Based Systems, 30:87–94, 2012. 3293 H ANNAH AND D UNSON C. F. Jeff Wu. Some algorithms for concave and isotonic regression. In S. H. Zanakis and J. S. Rustagi, editors, Studies in the Management Sciences, volume 19, pages 105–116. North-Holland, Amsterdam, 1982. 3294