Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
This paper analyzes the last-iterate convergence of clipped Stochastic Gradient Descent (SGD) for smooth convex objectives with heavy-tailed noise ($1<p\le2$), establishing a high-probability error bound of $O(LR^2\log(1/δ)/T+σR(\log(1/δ)/T)^{(p-1)/p})$ under linear learning rate decay. The analysis is extended to nonsmooth and proximal composite objectives, and robustness to $q$ adversarial gradient corruptions is shown by replacing $\log(1/δ)$ with $\log(1/δ)+q$. Corresponding lower bounds are also derived for both clean and corrupted oracle models.
Heavy-tailed noise doesn't derail clipped SGD's last-iterate convergence, achieving near-optimal rates even with adversarial gradient attacks.
In this paper, we study the last-iterate convergence of clipped stochastic gradient descent under heavy-tailed noise. We assume that the stochastic gradients are unbiased and that the noise has a bounded central $p$-th moment, where $1<p\le2$. For smooth convex objectives, a linearly decreasing learning rate gives a high-probability error bound of order $O(LR^2\log(1/δ)/T+σR(\log(1/δ)/T)^{(p-1)/p})$. We further establish last-iterate guarantees for nonsmooth composite objectives and smooth composite objectives with proximal updates. In addition, when a causal adversary replaces at most $q$ gradients, the same clipped update achieves a bound with $\log(1/δ)$ replaced by $\log(1/δ)+q$. The corresponding lower bounds for the clean and corrupted oracle models are also provided.