Before revision:  The algorithm is stochastic gradient descent, and the analysis bears similarities to results of [Gupta and Sidford, NeurIPS'18].
After revision:  The algorithm is stochastic gradient descent, and the analysis bears similarities to those of optimization algorithms for regression in the usual setting [Gupta and Sidford, NeurIPS'18].