Bi-level path following for cross validated solution of kernel quantile regression

ABSTRACT

Modeling of conditional quantiles requires specification of the quantile being estimated and can thus be viewed as a parameterized predictive modeling problem. Quantile loss is typically used, and it is indeed parameterized by a quantile parameter. In this paper we show how to follow the path of cross validated solutions to regularized kernel quantile regression. Even though the bi-level optimization problem we encounter for every quantile is non-convex, the manner in which the optimal cross-validated solution evolves with the parameter of the loss function allows tracking of this solution. We prove this property, construct the resulting algorithm, and demonstrate it on data. This algorithm allows us to efficiently solve the whole family of bi-level problems.

REFERENCES

• 1: Buchinsky, M. (1994). Changes in the u.s. wage structure 1963--1987: Application of quantile regression. Econometrica, 62, 405--458.
• 2: Eide, E., & Showalter, M. (1998). The effect of school quality on student performance: A quantile regression approach. Economics Letters, 58, 345--350.
• 3: Lacey Gunter , Ji Zhu, Efficient Computation and Model Selection for the Support Vector Regression, Neural Computation, v.19 n.6, p.1633-1655, June 2007 [doi>10.1162/neco.2007.19.6.1633]
• 4: Trevor Hastie , Saharon Rosset , Robert Tibshirani , Ji Zhu, The Entire Regularization Path for the Support Vector Machine, The Journal of Machine Learning Research, 5, p.1391-1415, 12/1/2004
• 5: Hastie, T., Tibshirani, R., & Friedman, J. (2001). Elements of statistical learning. Springer.
• 6: Kimeldorf, G., & Wahba, G. (1971). Some results on cheby-cheffian spline functions. Journal of Mathematical Analysis and Applications, 33, 82--95.
• 7: Koenker, R. (2005). Quantile regression. New York: Cambridge University Press.
• 8: Kunapuli, G., Bennett, K. P., Hu, J., & Pang, J.-S. (2007). Bilevel model selection for support vector machines. CRM Proceedings and Lecture Notes. American Mathematical Society, to appear.
• 9: Li, Y., Liu, Y., & Zhu, J. (2007). Quantile regression in reproducing kernel hilbert spaces. JASA, 102.
• 10: Nicolai Meinshausen, Quantile Regression Forests, The Journal of Machine Learning Research, 7, p.983-999, 12/1/2006
• 11: Claudia Perlich , Saharon Rosset , Richard D. Lawrence , Bianca Zadrozny, High-quantile modeling for customer wallet estimation and other applications, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281297]
• 12: Rosset, S. (2008). Bi-level path following for cross validated solution of kernel quantile regression. In preparation, evolving draft available at www.tau.ac.il/~saharon/papers/cvpath.pdf.
• 13: Rosset, S., & Zhu, J. (2007). Piecewise linear regularized solution paths. Annals of Statistics, 35.
• 14: Schölkopf, B., & Smola, A. (2002). Learning with kernels. MIT Press, Cambridge, MA.
• 15: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 16: Alex J. Smola , Bernhard Schölkopf, A tutorial on support vector regression, Statistics and Computing, v.14 n.3, p.199-222, August 2004 [doi>10.1023/B:STCO.0000035301.49549.88]
• 17: Ichiro Takeuchi , Quoc V. Le , Timothy D. Sears , Alexander J. Smola, Nonparametric Quantile Estimation, The Journal of Machine Learning Research, 7, p.1231-1264, 12/1/2006
• 18: Gang Wang , Dit-Yan Yeung , Frederick H. Lochovsky, Two-dimensional solution path for support vector regression, Proceedings of the 23rd international conference on Machine learning, p.993-1000, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143969]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory