Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms

We analyze two classical algorithms for solving additively composite convex optimization problems where the objective is the sum of a smooth term and a nonsmooth regularizer. The first algorithm is the proximal stochastic gradient method for a single regularizer; the second is the randomized incremental proximal method, which uses the proximal operator of a randomly selected function when the regularizer is given as the sum of many nonsmooth functions. We focus on relaxing the bounded variance assumption that is common, yet stringent, for getting last iterate convergence rates. We prove the $\widetilde{O}(1/\sqrt{T})$ rate of convergence for the last iterate of both algorithms under componentwise convexity and smoothness, which is optimal up to log terms. Our results apply directly to graph-guided regularizers that arise in multi-task and federated learning, where the regularizer decomposes as a sum over edges of a collaboration graph.

Stochastic gradient descent and its variants are widely used algorithms in machine learning for optimizing model weights. We study two classical optimization algorithms that are used for solving regularized learning problems, where regularizers are used for enforcing structure on solutions, such as structure on images. Existing theory for these algorithms typically provides guarantees for the average of the models produced along the way and requires strong assumptions that may fail for many problems. In practice, however, these algorithms usually return the final model obtained after all the updates. We prove that, under much weaker assumptions, the final output of these algorithms converges at the optimal rate, up to logarithmic factors. Our results help explain the behaviour of commonly used optimization methods and apply to a wider range of problems.