Uncertainty quantification for iterative algorithms in linear models with application to early stopping

• URL: http://arxiv.org/abs/2404.17856v1
• Date: Sat, 27 Apr 2024 10:20:41 GMT
• Title: Uncertainty quantification for iterative algorithms in linear models with application to early stopping
• Authors: Pierre C. Bellec, Kai Tan,
• Abstract summary: This paper investigates the iterates $hbb1,dots,hbbT$ obtained from iterative algorithms in high-dimensional linear regression problems. The analysis and proposed estimators are applicable to Gradient Descent (GD), GD and their accelerated variants such as Fast Iterative Soft-Thresholding (FISTA)
• Score: 4.150180443030652
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper investigates the iterates $\hbb^1,\dots,\hbb^T$ obtained from iterative algorithms in high-dimensional linear regression problems, in the regime where the feature dimension $p$ is comparable with the sample size $n$, i.e., $p \asymp n$. The analysis and proposed estimators are applicable to Gradient Descent (GD), proximal GD and their accelerated variants such as Fast Iterative Soft-Thresholding (FISTA). The paper proposes novel estimators for the generalization error of the iterate $\hbb^t$ for any fixed iteration $t$ along the trajectory. These estimators are proved to be $\sqrt n$-consistent under Gaussian designs. Applications to early-stopping are provided: when the generalization error of the iterates is a U-shape function of the iteration $t$, the estimates allow to select from the data an iteration $\hat t$ that achieves the smallest generalization error along the trajectory. Additionally, we provide a technique for developing debiasing corrections and valid confidence intervals for the components of the true coefficient vector from the iterate $\hbb^t$ at any finite iteration $t$. Extensive simulations on synthetic data illustrate the theoretical results.

Related papers

• Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
  This paper aims to recover the intrinsic model parameters given the leverage scores gradient. We specifically scrutinize the inversion of the leverage score gradient, denoted as $g(x)$.
  arXiv  Detail & Related papers  (2024-08-21T01:39:42Z)
• Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
  We study sparse estimation tasks in Huber's contamination model with a focus on mean estimation, PCA, and linear regression. For each of these tasks, we give the first sample and computationally efficient robust estimators with optimal error guarantees. At the technical level, we develop a novel multidimensional filtering method in the sparse regime that may find other applications.
  arXiv  Detail & Related papers  (2024-03-15T15:51:27Z)
• Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression [44.13655983242414]
  We design the first sample near- and almost linear-time algorithms with optimal error guarantees. For robust linear regression, we give the first algorithm with sample complexity $n = tildeO(d/epsilon2)$ and almost linear runtime that approximates the target regressor within $ell$- $O(epsilon)$. This is the first sample and time algorithm achieving the optimal error guarantee, answering an open question in the literature.
  arXiv  Detail & Related papers  (2023-12-04T00:31:16Z)
• Retire: Robust Expectile Regression in High Dimensions [3.9391041278203978]
  Penalized quantile and expectile regression methods offer useful tools to detect heteroscedasticity in high-dimensional data. We propose and study (penalized) robust expectile regression (retire) We show that the proposed procedure can be efficiently solved by a semismooth Newton coordinate descent algorithm.
  arXiv  Detail & Related papers  (2022-12-11T18:03:12Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm. Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. We complement the theory with an empirical evaluation across known difficult exploration tasks.
  arXiv  Detail & Related papers  (2021-06-15T02:23:07Z)
• A Precise Performance Analysis of Support Vector Regression [105.94855998235232]
  We study the hard and soft support vector regression techniques applied to a set of $n$ linear measurements. Our results are then used to optimally tune the parameters intervening in the design of hard and soft support vector regression algorithms.
  arXiv  Detail & Related papers  (2021-05-21T14:26:28Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  We propose differentially private (DP) algorithms for bound non-dimensional optimization. We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
  arXiv  Detail & Related papers  (2020-06-24T06:01:24Z)
• Robust estimation via generalized quasi-gradients [28.292300073453877]
  We show why many recently proposed robust estimation problems are efficiently solvable. We identify the existence of "generalized quasi-gradients" We show that generalized quasi-gradients exist and construct efficient algorithms.
  arXiv  Detail & Related papers  (2020-05-28T15:14:33Z)

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.