TY - JOUR
T1 - Self-Tuned Stochastic Approximation Schemes for Non-Lipschitzian Stochastic Multi-User Optimization and Nash Games
AU - Yousefian, Farzad
AU - Nedić, Angelia
AU - Shanbhag, Uday V.
N1 - Funding Information:
This work was supported by the National Science Foundation (NSF) through awards NSF CMMI 0948905 ARRA (Nedić and Shanbhag), CMMI-0742538 (Nedić), and CMMI-1246887 (Shanbhag).
Publisher Copyright:
© 2015 IEEE.
PY - 2016/7
Y1 - 2016/7
N2 - We consider multi-user optimization problems and Nash games with stochastic convex objectives, instances of which arise in decentralized control problems. The associated equilibrium conditions of both problems can be cast as Cartesian stochastic variational inequality problems with mappings that are strongly monotone but not necessarily Lipschitz continuous. Consequently, most of the currently available stochastic approximation schemes cannot address such problems. First, through a user-specific local smoothing, we derive an approximate map that is shown to be Lipschitz continuous with a prescribed constant. Second, motivated by the need for a robust scheme that can be implemented in a distributed fashion, we develop a distributed self-tuned stochastic approximation scheme (DSSA) that adapts to problem parameters. Importantly, this scheme is provably convergent in an almost-sure sense and displays the optimal rate of convergence in mean squared error, i.e., O(1/k). A locally randomized variant is also provided to ensure that the scheme can contend with stochastic non-Lipschitzian multi-user problems. We conclude with numerics derived from a stochastic Nash-Cournot game.
AB - We consider multi-user optimization problems and Nash games with stochastic convex objectives, instances of which arise in decentralized control problems. The associated equilibrium conditions of both problems can be cast as Cartesian stochastic variational inequality problems with mappings that are strongly monotone but not necessarily Lipschitz continuous. Consequently, most of the currently available stochastic approximation schemes cannot address such problems. First, through a user-specific local smoothing, we derive an approximate map that is shown to be Lipschitz continuous with a prescribed constant. Second, motivated by the need for a robust scheme that can be implemented in a distributed fashion, we develop a distributed self-tuned stochastic approximation scheme (DSSA) that adapts to problem parameters. Importantly, this scheme is provably convergent in an almost-sure sense and displays the optimal rate of convergence in mean squared error, i.e., O(1/k). A locally randomized variant is also provided to ensure that the scheme can contend with stochastic non-Lipschitzian multi-user problems. We conclude with numerics derived from a stochastic Nash-Cournot game.
UR - http://www.scopus.com/inward/record.url?scp=84977126633&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84977126633&partnerID=8YFLogxK
U2 - 10.1109/TAC.2015.2478124
DO - 10.1109/TAC.2015.2478124
M3 - Article
AN - SCOPUS:84977126633
SN - 0018-9286
VL - 61
SP - 1753
EP - 1766
JO - IEEE Transactions on Automatic Control
JF - IEEE Transactions on Automatic Control
IS - 7
M1 - 7258341
ER -