TY - JOUR
T1 - Generalized mirror descents with non-convex potential functions in atomic congestion games
T2 - Continuous time and discrete time
AU - Chen, Po-An
N1 - Publisher Copyright:
© 2017 Elsevier B.V.
PY - 2018/2
Y1 - 2018/2
N2 - When playing certain specific classes of no-regret algorithms such as multiplicative updates and replicator dynamics in atomic congestion games, some previous convergence analyses were done with the standard Rosenthal potential function in terms of mixed strategy profiles (i.e., probability distributions on atomic flows), which could be non-convex. In several other works, the convergence, when playing the mirror-descent algorithm (a more general family of no-regret algorithms including multiplicative updates, gradient descents, etc.), was guaranteed with a convex potential function in terms of nonatomic flows as an approximation of the Rosenthal one. The convexity of the potential function provides convenience for analysis. One may wonder if the convergence of mirror descents can still be guaranteed directly with the non-convex Rosenthal potential function. In this paper, we answer the question affirmatively for discrete-time generalized mirror descents with the smoothness property (similarly adopted in many previous works for congestion games and markets) and for continuous-time generalized mirror descents with the separability of regularization functions.
AB - When playing certain specific classes of no-regret algorithms such as multiplicative updates and replicator dynamics in atomic congestion games, some previous convergence analyses were done with the standard Rosenthal potential function in terms of mixed strategy profiles (i.e., probability distributions on atomic flows), which could be non-convex. In several other works, the convergence, when playing the mirror-descent algorithm (a more general family of no-regret algorithms including multiplicative updates, gradient descents, etc.), was guaranteed with a convex potential function in terms of nonatomic flows as an approximation of the Rosenthal one. The convexity of the potential function provides convenience for analysis. One may wonder if the convergence of mirror descents can still be guaranteed directly with the non-convex Rosenthal potential function. In this paper, we answer the question affirmatively for discrete-time generalized mirror descents with the smoothness property (similarly adopted in many previous works for congestion games and markets) and for continuous-time generalized mirror descents with the separability of regularization functions.
KW - Analysis of algorithms
KW - Congestion games
KW - Convergence
KW - Mirror descents
KW - Non-convex
UR - http://www.scopus.com/inward/record.url?scp=85032191351&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2017.10.003
DO - 10.1016/j.ipl.2017.10.003
M3 - Article
AN - SCOPUS:85032191351
SN - 0020-0190
VL - 130
SP - 36
EP - 39
JO - Information Processing Letters
JF - Information Processing Letters
ER -