Brenier Isotonic Regression

• URL: http://arxiv.org/abs/2603.10452v1
• Date: Wed, 11 Mar 2026 06:10:27 GMT
• Title: Brenier Isotonic Regression
• Abstract summary: We consider a novel multi-output regression problem where a regression function is emphcyclically monotone<n>We leverage the fact that Kantorovich's optimal transport (OT) always yields a cyclically monotone coupling as an optimal solution.<n>This perspective naturally allows us to interpret a regression function and the convex potential as a link function in generalized linear models and Brenier's potential in OT, respectively.
• Score: 8.285522583692144
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Isotonic regression (IR) is shape-constrained regression to maintain a univariate fitting curve non-decreasing, which has numerous applications including single-index models and probability calibration. When it comes to multi-output regression, the classical IR is no longer applicable because the monotonicity is not readily extendable. We consider a novel multi-output regression problem where a regression function is \emph{cyclically monotone}. Roughly speaking, a cyclically monotone function is the gradient of some convex potential. Whereas enforcing cyclic monotonicity is apparently challenging, we leverage the fact that Kantorovich's optimal transport (OT) always yields a cyclically monotone coupling as an optimal solution. This perspective naturally allows us to interpret a regression function and the convex potential as a link function in generalized linear models and Brenier's potential in OT, respectively, and hence we call this IR extension \emph{Brenier isotonic regression}. We demonstrate experiments with probability calibration and generalized linear models. In particular, IR outperforms many famous baselines in probability calibration robustly.

Related papers

• Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
  Invariant learning can fail even when the structure is statistically identifiable.<n>We show a conditional computational barrier: under a black-box samplable supervised sparse recovery primitive, there exist emphamplable multi-dimensional environments.<n>Synthetic and real datasets illustrate the predicted gaps and transitions and motivate simple diversity diagnostics.
  arXiv  Detail & Related papers  (2026-06-11T05:49:43Z)
• Expectation Maximization (EM) Converges for General Agnostic Mixtures [10.42358047828068]
  Given a set of data points, the objective is emphfit $k$ lines by minimizing a suitable loss function.<n> gradient EM converges exponentially to appropriately defined population loss minimizers with high probability.<n>This shows the effectiveness of EM type algorithm which converges to emphoptimal solution in the non-generative setup.
  arXiv  Detail & Related papers  (2026-04-07T13:09:22Z)
• Test Set Sizing for the Ridge Regression [51.56484100374058]
  We derive the ideal train/test split for the ridge regression to high accuracy in the limit that the number of training rows m becomes large.<n>This is the first time that such a split is calculated mathematically for a machine learning model in the large data limit.
  arXiv  Detail & Related papers  (2025-04-27T13:17:18Z)
• Benign overfitting in Fixed Dimension via Physics-Informed Learning with Smooth Inductive Bias [8.668428992331808]
  We develop an Sobolev norm learning curve for kernel ridge(less) regression when addressing (elliptical) linear inverse problems.<n>Our results show that the PDE operators in the inverse problem can stabilize the variance and even behave benign overfitting for fixed-dimensional problems.
  arXiv  Detail & Related papers  (2024-06-13T14:54:30Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Learning linear operators: Infinite-dimensional regression as a well-behaved non-compact inverse problem [4.503368323711748]
  We consider the problem of learning a linear operator $theta$ between two Hilbert spaces from empirical observations. We show that this goal can be reformulated as an inverse problem for $theta$ with the feature that its forward operator is generally non-compact. We prove that this inverse problem is equivalent to the known compact inverse problem associated with scalar response regression derivation.
  arXiv  Detail & Related papers  (2022-11-16T12:33:01Z)
• Dimension free ridge regression [10.434481202633458]
  We revisit ridge regression on i.i.d. data in terms of the bias and variance of ridge regression in terms of the bias and variance of an equivalent' sequence model.<n>As a new application, we obtain a completely explicit and sharp characterization of ridge regression for Hilbert covariates with regularly varying spectrum.
  arXiv  Detail & Related papers  (2022-10-16T16:01:05Z)
• $p$-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets [74.37849422071206]
  We study the $p$-generalized probit regression model, which is a generalized linear model for binary responses. We show how the maximum likelihood estimator for $p$-generalized probit regression can be approximated efficiently up to a factor of $(1+varepsilon)$ on large data.
  arXiv  Detail & Related papers  (2022-03-25T10:54:41Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Max-Linear Regression by Convex Programming [5.366354612549172]
  We formulate and analyze a scalable convex program given by anchored regression (AR) as the estimator for the max-linear regression problem. Our result shows a sufficient number of noise-free observations for exact recovery scales as $k4p$ up to a logarithmic factor.
  arXiv  Detail & Related papers  (2021-03-12T00:55:54Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  We derive the regret upper bounds on the classes of Sobolev spaces $W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$. The upper bounds are supported by the minimax regret analysis, which reveals that in the cases $beta> fracd2$ or $p=infty$ these rates are (essentially) optimal.
  arXiv  Detail & Related papers  (2021-02-06T15:05:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.