Motivated by robust and quantile regression problems, we investigate the stochastic gradient descent (SGD) algorithm for minimizing an objective function $f$ that is locally strongly convex with a sub--quadratic tail. This setting covers many widely used online statistical methods. We introduce a novel piecewise Lyapunov function that enables us to handle functions $f$ with only first-order differentiability, which includes a wide range of popular loss functions such as Huber loss. Leveraging our proposed Lyapunov function, we derive finite-time moment bounds under general diminishing stepsizes, as well as constant stepsizes. We further establish the weak convergence, central limit theorem and bias characterization under constant stepsize, providing the first geometrical convergence result for sub--quadratic SGD. Our results have wide applications, especially in online statistical methods. In particular, we discuss two applications of our results. 1) Online robust regression: We consider a corrupted linear model with sub--exponential covariates and heavy--tailed noise. Our analysis provides convergence rates comparable to those for corrupted models with Gaussian covariates and noise. 2) Online quantile regression: Importantly, our results relax the common assumption in prior work that the conditional density is continuous and provide a more fine-grained analysis for the moment bounds.

The paper concerns robust linear regression in the online setting, where the data follows a Gaussian linear model with corruptions. It is shown that the stochastic gradient descent on the absolute loss converges to the true parameter at a rate of order O(1/n). The paper received a universally positive evaluation from the reviewers, who acknowledged the novelty of the results, the theoretical justification of the proposed approach and the scalability of the algorithm. The main issue raised in the reviews is about quite restrictive assumptions on the data distribution (Gaussian linear model, and the centered data assumption).

We consider the robust linear regression problem in the online setting where we have access to the data in a streaming manner, one data point after the other. More specifically, for a true parameter \theta *, we consider the corrupted Gaussian linear model y \varepsilon b where the adversarial noise b can take any value with probability \eta and equals zero otherwise. We consider this adversary to be oblivious (i.e., b independent of the data) since this is the only contamination model under which consistency is possible. Current algorithms rely on having the whole data at hand in order to identify and remove the outliers. In contrast, we show in this work that stochastic gradient descent on the l1 loss converges to the true parameter vector at a \tilde{O}( 1 / (1 - \eta) 2 n) rate which is independent of the values of the contaminated measurements.