XVII th Conference on Stochastic Programming

A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging

1 août 2025, 14:00

30m

F207

Invited talk Machine learning ML

Orateur

Sajad Khodadadian (Virginia Tech)

Description

Polyak averaging is a well-known technique for achieving asymptotically optimal convergence in Stochastic Approximation. In this work, we establish the first high-probability bound for general Stochastic Approximation with Polyak Averaging. We take a black-box approach, assuming access to an anytime high-probability bound for a given Stochastic Approximation, and derive tight finite-time bounds for its Polyak-averaged version. Applying our black-box framework to general contractive Stochastic Approximation, we analyze the impact of averaging under various settings.