Research map / Optimization / Implicit bias and generalization

Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression

NeurIPS 2024 · Optimization › Implicit bias and generalization · approach: SGD noise and flat minima · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives consistent, observable estimators of the out-of-sample error of every iterate along GD, SGD, proximal GD and proximal SGD trajectories for high-dimensional robust regression (Huber/pseudo-Huber, optional L1), using out-of-batch samples to make SGD estimates work.

Problem

Estimating the generalization (out-of-sample) error of each iterate along the trajectory of GD/SGD and proximal variants for robust regression in the proportional regime (p ~ n) with possibly heavy-tailed noise, without sample splitting or refitting.

Approach

Extends approximate-leave-one-out style risk estimation along the iteration trajectory by unrolling derivatives of iterates with respect to design entries via the chain rule into T×T weight matrices (W, K, A), estimated from data; for SGD, out-of-batch samples are used to keep the estimated K matrix invertible.

Key results

• Proposed estimates r̃_t track the true risk curves of GD, SGD, proximal GD and proximal SGD for Huber and pseudo-Huber regression over 100 replications, with the estimated optimal stopping iteration matching the true U-shape minimum.
• Directly generalizing prior trajectory estimator (inverting K without out-of-batch samples) gives suboptimal estimates r̃^sub, especially for later iterations in SGD with batch size n/10.
• Theoretical bounds show |r̂_t - r_t| converges to 0 in probability as n,p grow with T fixed, requiring only finite first moment of noise.

Measured effects reported in the paper

Surprising findings

• Direct generalization of prior trajectory risk estimation fails (K matrix non-invertible) for SGD with small batches of about 0.1n.

Limitations

• Constant depends on T as T^T, so the bounds are vacuous for T beyond roughly log(n)/log log n.
• Gaussian feature assumption; universality not established.
• Does not cover non-smooth data-fitting losses such as least absolute deviation.

Experimental setup

Datasets: synthetic Gaussian design with Student-t(2) noise

Benchmarks: simulated linear regression (n,p)=(10000,5000) and (10000,12000)

Metrics: squared generalization error ||Sigma^{1/2}(b^t - b*)||^2 agreement between estimated and true risk curves

Baselines: Generalized cross-validation tilde r_t^sub estimator (direct generalization of prior trajectory risk estimate

Builds on: approximate leave-one-out generalized cross-validation Huber regression Lasso

Closest papers by meaning

• The Benefits of Implicit Regularization from SGD in Least Squares Problems (NeurIPS 2021 · similarity 0.90)
• Better generalization with less data using robust gradient descent (ICML 2019 · similarity 0.89)
• Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD (ICLR 2023 · similarity 0.89)
• Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent (AAAI 2025 · similarity 0.87)
• Risk Bounds of Accelerated SGD for Overparameterized Linear Regression (ICLR 2024 · similarity 0.87)
• Generalization Analysis of Stochastic Weight Averaging with General Sampling (ICML 2024 · similarity 0.87)