TY - GEN
T1 - Towards an optimal stochastic alternating direction method of multipliers
AU - Azadi, Samaneh
AU - Sra, Suvrit
N1 - Publisher Copyright:
Copyright © (2014) by the International Machine Learning Society (IMLS) All rights reserved.
PY - 2014
Y1 - 2014
N2 - We study regularized stochastic convex optimization subject to linear equality constraints. This class of problems was recently also studied by Ouyang et al. (2013) and Suzuki (2013); both introduced similar stochastic alternating direction method of multipliers (SADMM) algorithms. However, the analysis of both papers led to suboptimal convergence rates. This paper presents two new SADMM methods: (i) the first attains the minimax optimal rate of 0(l/κ2) for nonsmooth strongly-convex stochastic problems; while (ii) the second progresses towards an optimal rate by exhibiting an 0{I/κ2) rate for the smooth part. We present several experiments with our new methods; the results indicate improved performance over competing ADMM methods.
AB - We study regularized stochastic convex optimization subject to linear equality constraints. This class of problems was recently also studied by Ouyang et al. (2013) and Suzuki (2013); both introduced similar stochastic alternating direction method of multipliers (SADMM) algorithms. However, the analysis of both papers led to suboptimal convergence rates. This paper presents two new SADMM methods: (i) the first attains the minimax optimal rate of 0(l/κ2) for nonsmooth strongly-convex stochastic problems; while (ii) the second progresses towards an optimal rate by exhibiting an 0{I/κ2) rate for the smooth part. We present several experiments with our new methods; the results indicate improved performance over competing ADMM methods.
UR - http://www.scopus.com/inward/record.url?scp=84919948575&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84919948575
T3 - 31st International Conference on Machine Learning, ICML 2014
SP - 944
EP - 959
BT - 31st International Conference on Machine Learning, ICML 2014
PB - International Machine Learning Society (IMLS)
T2 - 31st International Conference on Machine Learning, ICML 2014
Y2 - 21 June 2014 through 26 June 2014
ER -