Research map / Optimization / Implicit bias and generalization

Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent

AAAI 2025 · 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 stability-based generalization and optimization bounds for non-convex pairwise SGD and minibatch SGD under sub-Weibull (heavy-tailed) gradient noise and the PL condition.

Problem

Generalization and optimization guarantees for non-convex pairwise SGD are lacking, especially when gradient noise is heavy-tailed rather than sub-Gaussian or bounded-variance.

Approach

Introduces pairwise l1 uniform model stability tools that treat each sample pair as a single sample, and uses a sub-Weibull gradient-noise assumption to remove the bounded/Lipschitz gradient requirement, jointly bounding generalization and excess risk under the PL condition.

Key results

• Pairwise uniform model stability bound O((βn)^-1 L T^{1/2} log T) for non-convex pairwise SGD under Lipschitz loss (Theorem 3).
• Under sub-Weibull gradient noise with PL condition, excess risk bound for pairwise SGD improves stability term to T^{1/4} scaling (Theorems 5-6).
• First stability-based excess risk bounds for non-convex pairwise minibatch SGD with heavy tails and PL condition (Theorem 7).

Surprising findings

• Heavy-tailed gradient noise is claimed to bring mild positive dependence on the heavy-tail parameter for generalization and optimization, consistent with prior observations that heavy tails can help generalization.

Limitations

• Dependencies on theta and T may not be tight; lower bounds are needed.
• Lipschitz-based bound (Theorem 3) relies on a Lipschitz assumption that may not hold in practice.
• No empirical experiments; results are purely theoretical.

Experimental setup

Metrics: generalization error bound stability bound excess risk bound optimization error bound

Baselines: Shen et al. 2019 Lei, Liu, and Ying 2021 Madden, Dall'Anese, and Becker 2020 Lei and Tang 2021 Li and Liu 2022

Builds on: Lei, Liu, and Ying 2021 (pairwise SGD stability) Li and Liu 2022 (sub-Weibull pointwise SGD) Shen et al. 2019 Vladimirova et al. 2020 (sub-Weibull)

Closest papers by meaning

• Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise (ICML 2026 · similarity 0.94)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent (ICML 2020 · similarity 0.94)
• Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems (NeurIPS 2026 · similarity 0.91)
• Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm (ICML 2024 · similarity 0.91)
• Emergence of heavy tails in homogenized stochastic gradient descent (NeurIPS 2024 · similarity 0.91)
• Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters (NeurIPS 2026 · similarity 0.90)