2024/08/14 by Amit Attia, Attia, Amit, Ofir Gaash +3
Business, Management and Accounting · Computer Science · #Advanced Queuing Theory Analysis #Cloud Computing and Resource Management #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2408.07503
openalex publication_date 2024/08/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
We consider the problem of asynchronous stochastic optimization, where an optimization algorithm makes updates based on stale stochastic gradients of the objective that are subject to an arbitrary (possibly adversarial) sequence of delays. We present a procedure which, for any given q ∈ (0,1], transforms any standard stochastic first-order method to an asynchronous method with convergence guarantee depending on the q-quantile delay of the sequence. This approach leads to convergence rates of the form O(τq/qT+σ/√(qT)) for non-convex and O(τq2/(q T)2+σ/√(qT)) for convex smooth problems, where τq is the q-quantile delay, generalizing and improving on existing results that depend on the average delay. We further show a method that automatically adapts to all quantiles simultaneously, without any prior knowledge of the delays, achieving convergence rates of the form O(infq τq/qT+σ/√(qT)) for non-convex and O(infq τq2/(q T)2+σ/√(qT)) for convex smooth problems. Our technique is based on asynchronous mini-batching with a careful batch-size selection and filtering of stale gradients.