  We consider stochastic gradient methods under the interpolation regime where
a perfect fit can be obtained (minimum loss at each observation). While
previous work highlighted the implicit regularization of such algorithms, we
consider an explicit regularization framework as a minimum Bregman divergence
convex feasibility problem. Using convex duality, we propose randomized
Dykstra-style algorithms based on randomized dual coordinate ascent. For
non-accelerated coordinate descent, we obtain an algorithm which bears strong
similarities with (non-averaged) stochastic mirror descent on specific
functions, as it is is equivalent for quadratic objectives, and equivalent in
the early iterations for more general objectives. It comes with the benefit of
an explicit convergence theorem to a minimum norm solution. For accelerated
coordinate descent, we obtain a new algorithm that has better convergence
properties than existing stochastic gradient methods in the interpolating
regime. This leads to accelerated versions of the perceptron for generic
$\ell_p$-norm regularizers, which we illustrate in experiments.
