Nonconvergence to Unstable Points in Urn Models and Stochastic Approximations

By Robin Pemantle. 1990

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Linear Off-Policy Actor-Critic (2012, background): “Previous work, however, has illustrated that the stochasticity in practice makes convergence to an unstable equilibrium unlikely (Pemantle, 1990); therefore, we avoid restrictions on the policy function and do not include the projection in our algorithm Finally, we have the following (standard)…”
No bad local minima: Data independent training error guarantees for multilayer neural networks (2016, background): “However, SGD is only guaranteed to converge to critical points in which the gradient of the expected loss is zero [5], and, speciﬁcally, to stable local minima [25] (this is true also for regular gradient descent [22]).”
Exponentially vanishing sub-optimal local minima in multilayer neural networks (2017, background): “Under rather mild conditions (Pemantle, 1990; Bottou, 1998), SGD asymptotically converges to local minima of the loss.”
ON THE GLOBAL CONVERGENCE OF STOCHASTIC FICTITIOUS PLAY (2002, methodology): “The proofs of the parts (iii) and (iv), which rely on the analyses from Sections 2, 4.2, and 5 and on results of Pemantle (1990), Benaïm and Hirsch (1999a), and Benaïm (2000), can be found in the Appendix.”
Gradient Descent Converges to Minimizers (2016, background): “There are many well known examples when worst case initialization of gradient descent provably converge to saddle points [20, Section 1.2.3], and hardness results which showt at finding even alocal minimizer of nonconvex functions is NP-Hard in the worst case [19].”
A survey of random processes with reinforcement (2006, methodology): “) = 0. Proof:The method of proofis to construct a function F for which F(Xn) obeys the hypotheses of Theorem 2.9. This relies on known straightening results for stable manifolds and is carried out in [Pem90a] for Γ = {p} and in [BH95] for general Γ; see also [Bra98]. Inﬁnite dimensional spaces The s”
Stochastic Heavy ball (2016, methodology): “able sup k¥n 2 2} M k}. The sub-Gaussian assumption will be mainly used to obtain an upper bound of such an expectation, with the help of a coupling argument. Our proof will follow a strategy used in [Pem90] and [Ben06] where this kind of expectation has to be upper bounded. Nevertheless, the novelt”
Gradient Descent Only Converges to Minimizers (2016, methodology): “Specifically, we will use Stable-Center Manifold theorem developed in Smale (1967); Shub (1987); Hirsch et al.”
Generative Adversarial Networks: An Overview (2017, methodology): “By invoking the stable manifold theorem from non-linear systems theory, Lee et al. [52] showed that, were we to select the initial points of an optimizer at random, gradient descent would not converge to a saddle with probability one (also see [53], [25]).”
Natural actor-critic algorithms (2009, background): “In [50], with noise assumed to be sufficiently ‘omnidirectional’ in addition, it is shown that convergence to unstable fixed points will not occur; see also [28] for conditions on avoidance of unstable equilibria that lie in certain compact connected chain recurrent sets.”
When can the two-armed bandit algorithm be trusted? (2004, background): “There is a wide literature in stochastic approximation about traps and how not to fall into them (see [3, 6, 9, 14, 16, 17]).”
The Stag Hunt and the Evolution of Social Structure (2003, methodology): “For a more detailed treatment of the models discussed in this chapter and the next, see Skyrms and Pemantle (2000) and Pemantle and Skyrms (forthcoming a,b).”
A dynamic model of social network formation. (2000, background): “General results of (27) and (28) now imply that p(t) converges to the set where F vanishes.”
Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions (2016, background): “[21] establishes convergence of the Robbins-Monro stochastic approximation to local minimizers for strict saddle functions, whereas [10] establishes convergence to local minima for perturbed versions of multiplicative weights algorithm in generic potential games.”