Title: On stochastic approximation under heavier tails
Authors: Philip Thompson - CREST-ENSAE (France) [presenting]
Abstract: The solution of regularized stochastic convex optimization problems is considered via the stochastic approximation methodology, i.e., by means of a first order stochastic oracle sampled from the population distribution in an online fashion. We show that by choosing a specific policy for the stepsize sequence and the mini-batch size per iteration (i.e. the sample size used to compute the empirical mean of the gradient), it is possible to obtain (near) optimal iteration and sample complexities under very mild assumptions on the stochastic oracle distribution. For instance, our non-asymptotic rates are valid for oracles with pointwise finite variance and with ``multiplicative noise'' (the standard deviation of the first order oracle is Lipschitz continuous). This includes, e.g., linear regression problems where the design matrix may have arbitrary unbounded corruptions. Moreover, the proposed iterative estimator possesses a ``variance localization'' property: the bounds depends only on the variance at solutions. We also show rates of convergence in the setting where the Lipschitz constant is unknown and propose a stochastic approximated line search which adapts the estimator to this lack of information. In this case, some iterative arguments based on empirical process and self-normalization theory are used.