Stochastic gradient descent for streaming linear and rectified linear systems with adversarial corruptions

• URL: http://arxiv.org/abs/2403.01204v2
• Date: Fri, 17 Jan 2025 18:15:40 GMT
• Title: Stochastic gradient descent for streaming linear and rectified linear systems with adversarial corruptions
• Authors: Halyun Jeong, Deanna Needell, Elizaveta Rebrova,
• Abstract summary: We show novel nearly linear convergence guarantees of SGD-exp to the true parameter with up to $50%$ Massart corruption rate. This is the first convergence guarantee result for robust ReLU regression in the streaming setting.
• Score: 8.756480554457985
• License:
• Abstract: We propose SGD-exp, a stochastic gradient descent approach for linear and ReLU regressions under Massart noise (adversarial semi-random corruption model) for the fully streaming setting. We show novel nearly linear convergence guarantees of SGD-exp to the true parameter with up to $50\%$ Massart corruption rate, and with any corruption rate in the case of symmetric oblivious corruptions. This is the first convergence guarantee result for robust ReLU regression in the streaming setting, and it shows the improved convergence rate over previous robust methods for $L_1$ linear regression due to a choice of an exponentially decaying step size, known for its efficiency in practice. Our analysis is based on the drift analysis of a discrete stochastic process, which could also be interesting on its own.

Related papers

• Implicit Bias and Fast Convergence Rates for Self-attention [30.08303212679308]
  Self-attention, the core mechanism of transformers, distinguishes them from traditional neural networks and drives their outstanding performance. We investigate the implicit bias of gradient descent (GD) in training a self-attention layer with fixed linear decoder in binary. We provide the first finite-time convergence rate for $W_t$ to $W_mm$, along with the rate of sparsification in the attention map.
  arXiv  Detail & Related papers  (2024-02-08T15:15:09Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  We show that Prospect, a gradient-based algorithm, enjoys linear convergence for smooth regularized losses. We also show that Prospect can converge 2-3$times$ faster than baselines such as gradient-based methods.
  arXiv  Detail & Related papers  (2023-10-21T00:03:54Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Fast Robust Kernel Regression through Sign Gradient Descent with Early Stopping [1.5229257192293204]
  Kernel ridge regression, KRR, is a generalization of linear ridge regression that is non-linear in the data, but linear in the model parameters. We introduce an equivalent formulation of the objective function of KRR, which opens up both for replacing the ridge penalty with the $ell_infty$ and $ell_1$ penalties.
  arXiv  Detail & Related papers  (2023-06-29T10:29:29Z)
• Gradient Descent Converges Linearly for Logistic Regression on Separable Data [17.60502131429094]
  We show that running gradient descent with variable learning rate guarantees loss $f(x) leq 1.1 cdot f(x*) + epsilon$ the logistic regression objective. We also apply our ideas to sparse logistic regression, where they lead to an exponential improvement of the sparsity-error tradeoff.
  arXiv  Detail & Related papers  (2023-06-26T02:15:26Z)
• Near Optimal Private and Robust Linear Regression [47.2888113094367]
  We propose a variant of the popular differentially private gradient descent (DP-SGD) algorithm with two innovations. Under label-corruption, this is the first efficient linear regression algorithm to guarantee both $(varepsilon,delta)$-DP and robustness.
  arXiv  Detail & Related papers  (2023-01-30T20:33:26Z)
• 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)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  Ordered $L_1$ (OWL) regularized regression is a new regression analysis for high-dimensional sparse learning. Proximal gradient methods are used as standard approaches to solve OWL regression. We propose the first safe screening rule for OWL regression by exploring the order of the primal solution with the unknown order structure.
  arXiv  Detail & Related papers  (2020-06-29T23:35:53Z)

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.