Convex Regression: Theory, Practice, and Applications

• Author / Creator

  Balazs, Gabor

• This thesis explores theoretical, computational, and practical aspects of convex (shape-constrained) regression, providing new excess risk upper bounds, a comparison of convex regression techniques with theoretical guarantee, a novel heuristic training algorithm for max-affine representations, and applications in convex stochastic programming. The new excess risk upper bound is developed for the general empirical risk minimization setting without any shape constraints, and provides a probabilistic guarantee for cases with unbounded hypothesis classes, targets, and noise models. The strength of the general result is demonstrated by applying it to linear regression under the squared loss both for lasso and ridge regression, as well as for convex nonparametric least squares estimation, in each case allowing one to obtain near-minimax upper bounds on the risk. Next, cutting plane and alternating direction method of multipliers algorithms are compared for training the max-affine least squares estimators; estimators for which we provide explicit excess risk bounds. These techniques are also extended for the partitioned convex formulation (which is shown to enjoy optimal minimax rates). We also provide an empirical study of various heuristics for solving the non-convex optimization problem underlying the partitioned convex formulation. A novel max-affine estimator is designed, which scales well for large sample sizes and improves the generalization error of current techniques in many cases. Its training time is proportional to the adaptively set model size, making it computationally attractive for estimation problems where the target can be efficiently approximated by max-affine functions. Realistic convex regression applications are synthetized for the convex stochastic programming framework such as an energy storage optimization using a solar source with an Economy 7 tariff pricing model, as well as a multiproduct assembly problem of operating a beer brewery.

• Subjects / Keywords

  • Max-affine estimator
  • Convex stochastic programming
  • Convex regression
  • Excess risk upper bound
  • Empirical risk minimization

• Graduation date

  Fall 2016

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3T43J98B

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.