Review for NeurIPS paper: Finite-Sample Analysis of Contractive Stochastic Approximation Using Smooth Convex Envelopes

Summary and Contributions: This paper considers the fundamental problem of computing a fixed point of a stochastic contractive operator. Formally, this paper supposes that there is an operator H from R d to R d such that H(x) – x_* _c \leq \gamma x – x_* _c for some norm \cdot _c, some gamma \in (0, 1), and fixed _x_* and that given any point x can compute H(x) w where w is mean zero noise, the magnitude of which depends on x. The paper then considers the natural stochastic approximation (SA) algorithm x_k 1 x_k epsilon_k (H(x_k) – x_k w_k) for some sequences step sizes epsilon_k and stochastic mean-0 w_k, the norm of which depends on x_k. The paper provides general convergence bounds for this algorithm in terms of the norm in which H contracts and the bound on the noise vector w_k in terms of x_k. Formally, the paper supposes that conditioned up to iteration k, E w_k 2_n \leq A (1 x_k _n 2) for some norm and provides bounds on the convergence of the method.