Download the full-sized PDF of Convex Regression: Theory, Practice, and ApplicationsDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Convex Regression: Theory, Practice, and Applications Open Access


Other title
convex regression
excess risk upper bound
max-affine estimator
empirical risk minimization
convex stochastic programming
Type of item
Degree grantor
University of Alberta
Author or creator
Balazs, Gabor
Supervisor and department
Szepesvari, Csaba (Computing Science)
Schuurmans, Dale (Computing Science)
Examining committee member and department
Greiner, Russ (Computing Science)
Gyorgy, Andras (Computing Science)
Mizera, Ivan (Mathematical and Statistical Sciences)
Sen, Bodhisattva (Statistics)
Department of Computing Science
Statistical Machine Learning
Date accepted
Graduation date
2016-06:Fall 2016
Doctor of Philosophy
Degree level
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.
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. 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.
Citation for previous publication
G. Balazs, A. Gyorgy, Cs. Szepesvari : Near-optimal max-affine estimators for convex regression. AISTATS, 2015.G. Balazs, A. Gyorgy, Cs. Szepesvari : Chaining bounds for empirical risk minimization. arXiv:1609.01872v1, 2016.G. Balazs, A. Gyorgy, Cs. Szepesvari : Max-affine estimators for convex stochastic programming. arXiv:1609.06331v1, 2016.

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 2296137
Last modified: 2016:11:16 14:02:02-07:00
Filename: Balazs_Gabor_201609_PhD.pdf
Original checksum: f39a26dd36536cf83f765119818cbd2a
Well formed: true
Valid: true
Status message: Too many fonts to report; some fonts omitted. Total fonts = 1555
File title: Introduction
Page count: 140
Activity of users you follow
User Activity Date