Escaping Saddle Points in Constant Dimensional Spaces: An Agent-based Modeling Perspective
Pages 49 - 67
Abstract
We study a large family of stochastic processes that update a limited amount in each step. One family of such examples is agent-based modeling, where one agent at a time updates, so the state has small changes in each step. A key question is how this family of stochastic processes is approximated by their mean-field approximations. Prior work shows that the stochastic processes escape repelling fixed points and saddle points in polynomial time.
We provide a tight analysis of the above question. For any non-attracting hyperbolic fixed point and a sufficiently small constant ε >0, the process will be ε-far away from the fixed point in O(n log n) time with high probability. We also show that it takes time Ω(n log n) to escape such a fixed point with constant probability. This shows that our result is optimal up to a multiplicative constant.
We leverage the above result and show that such stochastic processes can reach the neighborhood of some attracting fixed point in $O(nłog n)$ time with high probability.
Finally, We show the power of our results by applying them to several settings: evolutionary game theory, opinion formation dynamics, and stochastic gradient descent in a finite-dimensional space.
References
[1]
Mohammed Amin Abdullah and Moez Draief. 2015. Global majority consensus by local majority polling on graphs of a given degree sequence. Discrete Applied Mathematics, Vol. 180 (2015), 1--10.
[2]
Andrea Baronchelli, Vittorio Loreto, Luca Dall'Asta, and Alain Barrat. 2006. Strategy, Topology, and all that. In The Evolution of Language: Proceedings of the 6th International Conference (EVOLANG6), Rome, Italy, 12--15 April 2006. World Scientific, 11.
[3]
Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. 2016. Stabilizing consensus with many opinions. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 620--635.
[4]
Eli Ben-Naim, Laurent Frachebourg, and Paul L Krapivsky. 1996. Coarsening and persistence in the voter model. Physical Review E, Vol. 53, 4 (1996), 3078.
[5]
Michel Benaim. 1999. Dynamics of stochastic approximation algorithms. In Seminaire de probabilites XXXIII. Springer, 1--68.
[6]
Michel Benaim and Jörgen W Weibull. 2003. Deterministic approximation of stochastic evolution in games. Econometrica, Vol. 71, 3 (2003), 873--903.
[7]
Florence Bénézit, Patrick Thiran, and Martin Vetterli. 2009. Interval consensus: from quantized gossip to voting. In Acoustics, Speech and Signal Processing, 2009. ICASSP 2009. IEEE International Conference on. IEEE, 3661--3664.
[8]
Itai Benjamini, Siu-On Chan, Ryan O'Donnell, Omer Tamuz, and Li-Yang Tan. 2016. Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs. Stochastic Processes and their Applications, Vol. 126, 9 (2016), 2719--2733.
[9]
Lawrence E Blume. 1993. The statistical mechanics of strategic interaction. Games and economic behavior, Vol. 5, 3 (1993), 387--424.
[10]
Vivek S Borkar. 2009. Stochastic approximation: a dynamical systems viewpoint. Vol. 48. Springer.
[11]
Claudio Castellano, Vittorio Loreto, Alain Barrat, Federico Cecconi, and Domenico Parisi. 2005. Comparison of voter and Glauber ordering dynamics on networks. Physical review E, Vol. 71, 6 (2005), 066107.
[12]
Claudio Castellano, Daniele Vilone, and Alessandro Vespignani. 2003. Incomplete ordering of the voter model on small-world networks. EPL (Europhysics Letters), Vol. 63, 1 (2003), 153.
[13]
Charles C Conley. 1978. Isolated invariant sets and the Morse index. Number 38. American Mathematical Soc.
[14]
Colin Cooper, Robert Els"asser, and Tomasz Radzik. 2014. The power of two choices in distributed voting. In International Colloquium on Automata, Languages, and Programming. Springer, 435--446.
[15]
Colin Cooper, Tomasz Radzik, Nicolás Rivera, and Takeharu Shiraga. 2016. Fast plurality consensus in regular expanders. arXiv preprint arXiv:1605.08403 (2016).
[16]
J Theodore Cox and David Griffeath. 1986. Diffusive clustering in the two dimensional voter model. The Annals of Probability (1986), 347--370.
[17]
James Cruise and Ayalvadi Ganesh. 2014. Probabilistic consensus via polling and majority rules. Queueing Systems, Vol. 78, 2 (2014), 99--120.
[18]
Guillaume Deffuant, Frédéric Amblard, Gérard Weisbuch, and Thierry Faure. 2002. How can extremism prevail? A study based on the relative agreement interaction model. Journal of artificial societies and social simulation, Vol. 5, 4 (2002).
[19]
M.H. DeGroot. 1974. Reaching a consensus. J. Amer. Statist. Assoc. (1974), 118--121.
[20]
Paul DiMaggio. 1986. Structural analysis of organizational fields: A blockmodel approach. Research in organizational behavior (1986).
[21]
Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. 2011. Stabilizing consensus with the power of two choices. In Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures. ACM, 149--158.
[22]
Richard Durrett, James P Gleeson, Alun L Lloyd, Peter J Mucha, Feng Shi, David Sivakoff, Joshua ES Socolar, and Chris Varghese. 2012. Graph fission in an evolving voter model. Proceedings of the National Academy of Sciences (2012).
[23]
Glenn Ellison. 1993. Learning, local interaction, and coordination. Econometrica: Journal of the Econometric Society (1993), 1047--1071.
[24]
Diodato Ferraioli. 2013. Logit dynamics: a model for bounded rationality. ACM SIGecom Exchanges, Vol. 12, 1 (2013), 34--37.
[25]
Jie Gao, Bo Li, Grant Schoenebeck, and Fang-Yi Yu. 2017. Engineering Agreement: The Naming Game with Asymmetric and Heterogeneous Agents. In AAAI. 537--543.
[26]
Jie Gao, Grant Schoenebeck, and Fang-Yi Yu. 2019. The Volatility of Weak Ties: Co-evolution of Selection and Influence in Social Networks. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19, Montreal, QC, Canada, May 13--17, 2019. 619--627. http://dl.acm.org/citation.cfm?id=3331748
[27]
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. 2015. Escaping from saddle points-online stochastic gradient for tensor decomposition. In Conference on Learning Theory. 797--842.
[28]
Reza Gheissari and Anna Ben Hamou. [n. d.]. AimPL: Markov chain mixing times, available at http://aimpl.org/markovmixing.
[29]
John C Harsanyi, Reinhard Selten, et al. 1988. A general theory of equilibrium selection in games. MIT Press Books, Vol. 1 (1988).
[30]
Rainer Hegselmann, Ulrich Krause, et al. 2002. Opinion dynamics and bounded confidence models, analysis, and simulation. Journal of artificial societies and social simulation, Vol. 5, 3 (2002).
[31]
Richard A Holley and Thomas M Liggett. 1975. Ergodic theorems for weakly interacting infinite systems and the voter model. The annals of probability (1975), 643--663.
[32]
Petter Holme and M E J Newman. 2006. Nonequilibrium phase transition in the coevolution of networks and opinions. Phys. Rev. E Stat. Nonlin. Soft Matter Phys., Vol. 74, 5 Pt 2 (Nov. 2006), 056108.
[33]
Roger A Horn, Roger A Horn, and Charles R Johnson. 1990. Matrix analysis .Cambridge university press.
[34]
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. 2017. How to escape saddle points efficiently. arXiv preprint arXiv:1703.00887 (2017).
[35]
Yashodhan Kanoria, Andrea Montanari, et al. 2011. Majority dynamics on trees and the dynamic cavity method. The Annals of Applied Probability, Vol. 21, 5 (2011), 1694--1748.
[36]
Michael Kearns and Jinsong Tan. 2008. Biased voting and the democratic primary problem. In International Workshop on Internet and Network Economics. Springer, 639--652.
[37]
Robert Kleinberg, Yuanzhi Li, and Yang Yuan. 2018. An alternative view: When does SGD escape local minima? arXiv preprint arXiv:1802.06175 (2018).
[38]
Paul L Krapivsky and Sidney Redner. 2003. Dynamics of majority rule in two-state interacting spin systems. Physical Review Letters, Vol. 90, 23 (2003), 238701.
[39]
Qianxiao Li, Cheng Tai, and Weinan E. 2019. Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundations. Journal of Machine Learning Research, Vol. 20 (2019), 40:1--40:47. http://jmlr.org/papers/v20/17--526.html
[40]
Thomas M Liggett. 1994. Coexistence in threshold voter models. The Annals of Probability (1994), 764--802.
[41]
Thomas M Liggett et al. 1997. Stochastic models of interacting systems. The Annals of Probability, Vol. 25, 1 (1997), 1--29.
[42]
Daniel McFadden et al. 1973. Conditional logit analysis of qualitative choice behavior. (1973).
[43]
Beno^it Merlet, Thanh Nhan Nguyen, et al. 2013. Convergence to equilibrium for discretizations of gradient-like flows on Riemannian manifolds. Differential and Integral Equations, Vol. 26, 5/6 (2013), 571--602.
[44]
Panayotis Mertikopoulos and Mathias Staudigl. 2018. On the convergence of gradient-like flows with noisy gradient input. SIAM Journal on Optimization, Vol. 28, 1 (2018), 163--197.
[45]
Andrea Montanari and Amin Saberi. 2008. Convergence to equilibrium in local interaction games and ising models. arXiv preprint arXiv:0812.0198 (2008).
[46]
Elchanan Mossel, Joe Neeman, and Omer Tamuz. 2014. Majority dynamics and aggregation of information in social networks. Autonomous Agents and Multi-Agent Systems, Vol. 28, 3 (2014), 408--429.
[47]
Elchanan Mossel and Grant Schoenebeck. 2010. Arriving at consensus in social networks. In The First Symposium on Innovations in Computer Science (ICS 2010) .
[48]
Ioannis Panageas, Piyush Srivastava, and Nisheeth K Vishnoi. 2016. Evolutionary dynamics in finite populations mix rapidly. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms. SIAM, 480--497.
[49]
Ioannis Panageas and Nisheeth K Vishnoi. 2016. Mixing time of Markov chains, dynamical systems and evolution. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
[50]
Christos Papadimitriou and Georgios Piliouras. 2019. Game Dynamics as the Meaning of a Game. ACM SIGecom Exchanges, Vol. 16, 2 (2019), 53--63.
[51]
Robin Pemantle et al. 1990. Nonconvergence to unstable points in urn models and stochastic approximations. The Annals of Probability, Vol. 18, 2 (1990), 698--712.
[52]
Robin Pemantle et al. 2007. A survey of random processes with reinforcement. Probability surveys, Vol. 4 (2007), 1--79.
[53]
Etienne Perron, Dinkar Vasudevan, and Milan Vojnovic. 2009. Using three states for binary consensus on complete graphs. In INFOCOM 2009, IEEE. IEEE, 2527--2535.
[54]
Herbert Robbins and Sutton Monro. 1951. A stochastic approximation method. The annals of mathematical statistics (1951), 400--407.
[55]
Clark Robinson. 1998. Dynamical systems: stability, symbolic dynamics, and chaos .CRC press.
[56]
William H Sandholm. 2010. Population games and evolutionary dynamics .MIT press.
[57]
Grant Schoenebeck and Fang-Yi Yu. 2018. Consensus of interacting particle systems on erdös-rényi graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1945--1964.
[58]
Frank Schweitzer and Laxmidhar Behera. 2009. Nonlinear voter models: the transition from invasion to coexistence. The European Physical Journal B-Condensed Matter and Complex Systems, Vol. 67, 3 (2009), 301--318.
[59]
John Scott. 1988. Social network analysis. Sage.
[60]
Vishal Sood and Sidney Redner. 2005. Voter model on heterogeneous graphs. Physical review letters, Vol. 94, 17 (2005), 178701.
[61]
Steven H Strogatz. 2018. Nonlinear dynamics and chaos: with applications to physics, biology, chemistry, and engineering. CRC Press.
[62]
Krzysztof Suchecki, Victor M Eguiluz, and Maxi San Miguel. 2005 a. Conservation laws for the voter model in complex networks. EPL (Europhysics Letters), Vol. 69, 2 (2005), 228.
[63]
Krzysztof Suchecki, Victor M Eguiluz, and Maxi San Miguel. 2005 b. Voter model dynamics in complex networks: Role of dimensionality, disorder, and degree distribution. Physical Review E, Vol. 72, 3 (2005), 036132.
[64]
Omer Tamuz and Ran J Tessler. 2015. Majority dynamics and the retention of information. Israel Journal of Mathematics, Vol. 206, 1 (2015), 483--507.
[65]
Harrison C White, Scott A Boorman, and Ronald L Breiger. 1976. Social structure from multiple networks. I. Blockmodels of roles and positions. American journal of sociology, Vol. 81, 4 (1976), 730--780.
[66]
Nicholas C Wormald et al. 1995. Differential equations for random processes and random graphs. The annals of applied probability, Vol. 5, 4 (1995), 1217--1235.
[67]
Ahad N. Zehmakan. 2018. Opinion Forming in Binomial Random Graph and Expanders. CoRR, Vol. abs/1805.12172 (2018). arxiv: 1805.12172 http://arxiv.org/abs/1805.12172
Index Terms
- Escaping Saddle Points in Constant Dimensional Spaces: An Agent-based Modeling Perspective
Recommendations
On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets
Given two bounded convex sets $$X\subseteq \mathbb R^m$$X⊆Rm and $$Y\subseteq \mathbb R^n,$$Y⊆Rn, specified by membership oracles, and a continuous convex---concave function $$F:X\times Y\rightarrow \mathbb R$$F:X Y R, we consider the problem of ...
Stochastic Approximations with Constant Step Size and Differential Inclusions
We consider stochastic approximation processes with constant step size whose associated deterministic system is an upper semicontinuous differential inclusion. We prove that over any finite time span, the sample paths of the stochastic process are closely ...
Optimal Stopping Games for Markov Processes
Let $X=(X_t)_{t \ge 0}$ be a strong Markov process, and let $G_1,\, G_2$, and $G_3$ be continuous functions satisfying $G_1 \le G_3 \le G_2$ and $\mathsf{E}_x\sup_t \vert G_i(X_t) \vert < \infty$ for $i=1,2,3$. Consider the optimal stopping game where ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2020
937 pages
ISBN:9781450379755
DOI:10.1145/3391403
- General Chairs:
- Péter Biró,
- Jason Hartline,
- Program Chairs:
- Michael Ostrovsky,
- Ariel Procaccia
Copyright © 2020 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 July 2020
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
EC '20
Sponsor:
EC '20: The 21st ACM Conference on Economics and Computation
July 13 - 17, 2020
Virtual Event, Hungary
Acceptance Rates
Overall Acceptance Rate 664 of 2,389 submissions, 28%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 216Total Downloads
- Downloads (Last 12 months)52
- Downloads (Last 6 weeks)17
Reflects downloads up to 21 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in