A delayed proximal gradient method with linear convergence rate
2014 (English)In: IEEE International Workshop on Machine Learning for Signal Processing (MLSP), IEEE conference proceedings, 2014, 1-6 p.Conference paper (Refereed)
This paper presents a new incremental gradient algorithm for minimizing the average of a large number of smooth component functions based on delayed partial gradients. Even with a constant step size, which can be chosen independently of the maximum delay bound and the number of objective function components, the expected objective value is guaranteed to converge linearly to within some ball around the optimum. We derive an explicit expression that quantifies how the convergence rate depends on objective function properties and algorithm parameters such as step-size and the maximum delay. An associated upper bound on the asymptotic error reveals the trade-off between convergence speed and residual error. Numerical examples confirm the validity of our results.
Place, publisher, year, edition, pages
IEEE conference proceedings, 2014. 1-6 p.
convergence, gradient methods, learning (artificial intelligence), algorithm parameter, asymptotic error, constant step size, convergence speed, delayed partial gradient, delayed proximal gradient method, incremental gradient algorithm, linear convergence rate, objective function component, objective function property, residual error, smooth component function, Convergence, Delays, Linear programming, Optimization, Radio frequency, Upper bound, Vectors, Incremental gradient, asynchronous parallelism, machine learning
IdentifiersURN: urn:nbn:se:kth:diva-164290DOI: 10.1109/MLSP.2014.6958872ScopusID: 2-s2.0-84912569451OAI: oai:DiVA.org:kth-164290DiVA: diva2:805303
IEEE International Workshop on Machine Learning for Signal Processing (MLSP),21-24 Sept. 2014, Reims, France
QC 201505112015-04-152015-04-152015-05-11Bibliographically approved