Generalization Error Estimation for Primal--Dual Algorithms in Non-Smooth Regression

• URL: http://arxiv.org/abs/2608.13870v1
• Date: Fri, 14 Aug 2026 01:45:11 GMT
• Title: Generalization Error Estimation for Primal--Dual Algorithms in Non-Smooth Regression
• Abstract summary: We study trajectory-wise estimation of generalization error for primal--dual algorithms in non-smooth regression.<n>We develop a general framework that includes the Chambolle--Pock algorithm and related primal--dual splitting methods.
• Score: 6.462588783417218
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies trajectory-wise estimation of generalization error for primal--dual algorithms in non-smooth regression. Motivating examples include \(\ell_1\)-penalized least absolute deviations regression and square-root Lasso regression, where the data-fitting loss is non-differentiable and existing risk estimators for gradient-type optimization paths do not apply directly. We develop a general recursive framework that includes the Chambolle--Pock algorithm and related primal--dual splitting methods. We estimate risk by correcting each in-sample fitted value with a weighted combination of past dual iterates. The ideal weights are Stein derivative contractions and depend on the design covariance. We construct replacement weights from observable derivative contractions of the fitted-signal trajectory, yielding a covariance-free, data-driven correction. For high-dimensional Gaussian designs and fixed finite iteration horizon, we prove finite-sample guarantees for both estimators. For square-root ridge, we further establish a matched-Gaussian universality result beyond Gaussian designs. Numerical experiments show that the proposed estimators accurately track the out-of-sample risk along finite optimization paths.

Related papers

• A Simple Approximation to the Distribution of the Ridge Regression Estimator [1.1678783855674757]
  In finite samples, the ridge regression estimator trades off bias and variance to reduce estimation and prediction error.<n>Our approximation is based on nonstandards where $i)$ we let the estimator's regularization parameter grow proportionally to the sample size.<n>We propose two new strategies to select the regularization parameter for the ridge regression estimator.
  arXiv  Detail & Related papers  (2026-08-03T17:28:17Z)
• On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization [57.179679246370114]
  A potential limitation of existing methods is the bias inherent in most perturbation estimators unless a stepsize is proposed.<n>We propose a novel family of unbiased gradient scaling estimators that eliminate bias while maintaining favorable construction.
  arXiv  Detail & Related papers  (2025-10-22T18:25:43Z)
• Neural Optimal Transport Meets Multivariate Conformal Prediction [58.43397908730771]
  We propose a framework for conditional vectorile regression (CVQR)<n>CVQR combines neural optimal transport with quantized optimization, and apply it to predictions.
  arXiv  Detail & Related papers  (2025-09-29T19:50:19Z)
• Refined Risk Bounds for Unbounded Losses via Transductive Priors [67.12679195076387]
  We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression.<n>Our key tools are based on the exponential weights algorithm with carefully chosen transductive priors.
  arXiv  Detail & Related papers  (2024-10-29T00:01:04Z)
• Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression [4.150180443030652]
  We introduce estimators that precisely track the generalization error of the iterates along the trajectory of the iterative algorithm. The results are illustrated through several examples, including Huber regression, pseudo-Huber regression, and their penalized variants with non-smooth regularizer.
  arXiv  Detail & Related papers  (2024-10-03T16:13:42Z)
• Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectations [51.000851088730684]
  We develop novel modifications of nearest-neighbor and matching estimators which converge at the parametric $sqrt n $-rate.<n>We stress that our estimators do not involve nonparametric function estimators and in particular do not rely on sample-size dependent parameters smoothing.
  arXiv  Detail & Related papers  (2024-07-11T13:28:34Z)
• Improving Diffusion Models for Inverse Problems Using Optimal Posterior Covariance [52.093434664236014]
  Recent diffusion models provide a promising zero-shot solution to noisy linear inverse problems without retraining for specific inverse problems. Inspired by this finding, we propose to improve recent methods by using more principled covariance determined by maximum likelihood estimation.
  arXiv  Detail & Related papers  (2024-02-03T13:35:39Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective [30.524043513721168]
  We develop a general recipe for analyzing the convergence of iterative algorithms for a class of regression models. deterministicly, we accurately capture both the convergence rate of the algorithm and the eventual error floor in the finite-sample regime. We show sharp convergence rates for both higher-order algorithms based on alternating updates and first-order algorithms based on subgradient subgradients.
  arXiv  Detail & Related papers  (2021-09-20T21:48:19Z)
• On Low-rank Trace Regression under General Sampling Distribution [9.699586426043885]
  We show that cross-validated estimators satisfy near-optimal error bounds on general assumptions. We also show that the cross-validated estimator outperforms the theory-inspired approach of selecting the parameter.
  arXiv  Detail & Related papers  (2019-04-18T02:56:00Z)

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.