A Computational Framework for Multivariate Convex Regression and Its Variants

DOI10.1080/01621459.2017.1407771zbMATH Open1418.62122arXiv1509.08165OpenAlexW2963581419MaRDI QIDQ5229914FDOQ5229914

Authors: Rahul Mazumder, Arkopal Choudhury, G. Iyengar, Bodhisattva Sen 

Publication date: 19 August 2019

Published in: Journal of the American Statistical Association (Search for Journal in Brave)

Abstract: We study the nonparametric least squares estimator (LSE) of a multivariate convex regression function. The LSE, given as the solution to a quadratic program with $O(n^2)$ linear constraints ($n$ being the sample size), is difficult to compute for large problems. Exploiting problem specific structure, we propose a scalable algorithmic framework based on the augmented Lagrangian method to compute the LSE. We develop a novel approach to obtain smooth convex approximations to the fitted (piecewise affine) convex LSE and provide formal bounds on the quality of approximation. When the number of samples is not too large compared to the dimension of the predictor, we propose a regularization scheme --- Lipschitz convex regression --- where we constrain the norm of the subgradients, and study the rates of convergence of the obtained LSE. Our algorithmic framework is simple and flexible and can be easily adapted to handle variants: estimation of a non-decreasing/non-increasing convex/concave (with or without a Lipschitz bound) function. We perform numerical studies illustrating the scalability of the proposed algorithm.

Full work available at URL: https://arxiv.org/abs/1509.08165

Recommendations

• An augmented Lagrangian method with constraint generation for shape-constrained convex regression problems
• Nonparametric least squares estimation of a multivariate convex regression function
• Consistency of multidimensional convex regression
• Multivariate convex regression with adaptive partitioning
• On convergence rates of convex regression in multiple dimensions

zbMATH Keywords

augmented Lagrangian methodLipschitz convex regressionnonparametric least squares estimatorscalable quadratic programmingsmooth convex regression

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Nonparametric regression and quantile regression (62G08) Convex programming (90C25)

Cites Work

• Title not available (Why is that?)
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Smooth minimization of non-smooth functions
• Introductory lectures on convex optimization. A basic course.
• Estimating a smooth monotone regression function
• An Empirical Distribution Function for Sampling with Incomplete Information
• Monotone nonparametric regression
• The Nonparametric Approach to Demand Analysis
• Maximum Likelihood Estimates of Monotone Parameters
• Maximum Likelihood Estimation of a Multi-Dimensional Log-Concave Density
• Title not available (Why is that?)
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
• Title not available (Why is that?)
• Representation theorem for convex nonparametric least squares
• Lectures on Stochastic Programming
• The Nonparametric Approach to Production Analysis
• Nonparametric estimation of multivariate convex-transformed densities
• Nonparametic kernel regression with multiple predictors and multiple shape constraints
• A finite algorithm for finding the projection of a point onto the canonical simplex of \({\mathbb R}^ n\)
• A first-order augmented Lagrangian method for compressed sensing
• Consistency of multidimensional convex regression
• On the linear convergence of the alternating direction method of multipliers
• Title not available (Why is that?)
• Estimating a Convex Function in Nonparametric Regression
• Nonparametric least squares estimation of a multivariate convex regression function
• Multivariate convex regression with adaptive partitioning
• Consistent estimation of a convex density at the origin
• On convergence rates of convex regression in multiple dimensions
• On uniform consistent estimators for convex regression

Cited In (27)

• Convex support vector regression
• A more efficient algorithm for convex nonparametric least squares
• Consistency of multidimensional convex regression
• A dual active set algorithm for optimal sparse convex regression
• Editorial: Special issue on ``Nonparametric inference under shape constraints
• Nonparametric shape-restricted regression
• Shape constraints in economics and operations research
• Stratified incomplete local simplex tests for curvature of nonparametric multiple regression
• Title not available (Why is that?)
• Subgradient regularized multivariate convex regression at scale
• Adaptation in multivariate log-concave density estimation
• Composite difference-MAX programs for modern statistical estimation problems
• Spectrahedral Regression
• A two-level method for constructing linear regressions using optimal convex combinations
• Plugin estimation of smooth optimal transport maps
• Assessing Panamanian hospitals' performance with alternative frontier methods
• Performance enhancements for a generic conic interior point algorithm
• An augmented Lagrangian method with constraint generation for shape-constrained convex regression problems
• A penalized method for multivariate concave least squares with application to productivity analysis
• Center-outward quantiles and the measurement of multivariate risk
• Representation theorem for convex nonparametric least squares
• On convergence rates of convex regression in multiple dimensions
• Multivariate convex regression with adaptive partitioning
• A User-Friendly Computational Framework for Robust Structured Regression with the L₂ Criterion
• Semiparametric Efficiency in Convexity Constrained Single-Index Model
• Variable selection in convex quantile regression: \(\mathcal{L}_1\)-norm or \(\mathcal{L}_0\)-norm regularization?
• Generalized quantile and expectile properties for shape constrained nonparametric estimation

Uses Software

• LogConcDEAD
• ElemStatLearn

This page was built for publication: A Computational Framework for Multivariate Convex Regression and Its Variants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5229914)