Convergence and concentration properties of constant step-size SGD through Markov chains

Our framework covers both cases provided that each iteration uses new data which is independent from the past. Thanks to its simplicity and efficiency, the SGD algorithm is widely adopted as the go-to approach for stochastic optimization problems in general. Since its first appearance in the seminal work of [73] the theoretical properties of SGD have been investigated in a series of pioneering works [13, 80, 22]. A notable milestone in these theoretical developments was the discovery of Polyak-Ruppert averaging [79, 69] which allows to reduce the impact of noise and improve the convergence rate for certain cases of interest. The subject benefited from a growing attention with the advent of complex machine learning models such as neural networks and a rich literature has appeared to address the surfacing questions about SGD and its numerous variants and use cases [84, 1, 61, 9, 64]. Although the basic definition of the SGD iteration (2) is quite simple, a great number of variations are possible by playing on various aspects among which the choice of step-size is critical.