Stochastic optimization under time drift: iterate averaging, step-decay schedules, and high probability guarantees
We consider the problem of minimizing a convex function that is evolving in time according to unknown and possibly stochastic dynamics. Such problems abound in the machine learning and signal processing literature, under the names of concept drift and stochastic tracking. We provide novel non-asymptotic convergence guarantees for stochastic algorithms with iterate averaging, focusing on bounds valid both in expectation and with high probability. Notably, we show that the tracking efficiency of the proximal stochastic gradient method depends only logarithmically on the initialization quality when equipped with a step-decay schedule.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic OptimizationvalidSimilar Papers 제목 키워드 기반
Stochastic Optimization under Distributional Drift
We consider the problem of minimizing a convex function that is evolving according to unknown and possibly stochastic dynamics, which may depend jointly on time and on the decision variable itself. Such problems abound i…
Stochastic OptimizationvalidLast-iterate convergence analysis of stochastic momentum methods for neural networks
The stochastic momentum method is a commonly used acceleration technique for solving large-scale stochastic optimization problems in artificial neural networks. Current convergence results of stochastic momentum methods …
Stochastic OptimizationHigh-dimensional Limit of SGD for Diagonal Linear Networks
Understanding the behavior of stochastic gradient methods is a central problem in modern machine learning. Recent work has highlighted diagonal linear networks as a simplified yet expressive setting for analyzing the opt…
Bounding the expected run-time of nonconvex optimization with early stopping
This work examines the convergence of stochastic gradient-based optimization algorithms that use early stopping based on a validation function. The form of early stopping we consider is that optimization terminates when …
Non-Convex Optimization via Non-Reversible Stochastic Gradient Langevin Dynamics
Stochastic Gradient Langevin Dynamics (SGLD) is a powerful algorithm for optimizing a non-convex objective, where a controlled and properly scaled Gaussian noise is added to the stochastic gradients to steer the iterates…
Stochastic Optimization