PaperlayerView exact revision on arXiv

Source-linked AI summary

Ergodic Randomized Algorithms and Dynamics over Networks

Chiara Ravazzi, Paolo Frasca, Roberto Tempo, Hideaki Ishii

arXiv:1309.1349v2eess.SYcs.SY

TL;DR

Randomized network dynamics can oscillate rather than converge, even when related synchronous dynamics behave well. The paper proves an ergodicity result for average-stable randomized affine dynamics and applies it to network algorithms. Their oscillations can be averaged locally to recover the desired limit.

  • Problem

    Some randomized network algorithms oscillate persistently and fail to converge deterministically, motivating probabilistic convergence guarantees.

    Source: §I · p. 1, §III · p. 4

  • Method

    The paper proves an ergodicity result for randomized affine dynamics that are stable on average, using classical probability facts, and applies it to network algorithms.

    Source: §I · p. 1

  • Results

    The process is ergodic, and its limiting random variable has expectation equal to the synchronous convergence value.

    Source: §III · p. 4

  • Takeaways & Limitations

    Nodes can recover the desired limit by time-averaging locally, sometimes without a common clock.

    Source: §I · p. 1

Abstract

from arXiv · show

Algorithms and dynamics over networks often involve randomization, and randomization may result in oscillating dynamics which fail to converge in a deterministic sense. In this paper, we observe this undesired feature in three applications, in which the dynamics is the randomized asynchronous counterpart of a well-behaved synchronous one. These three applications are network localization, PageRank computation, and opinion dynamics. Motivated by their formal similarity, we show the following general fact, under the assumptions of independence across time and linearities of the updates: if the expected dynamics is stable and converges to the same limit of the original synchronous dynamics, then the oscillations are ergodic and the desired limit can be locally recovered via time-averaging.

I. INTRODUCTION

The paper studies randomized affine dynamics that lack equilibria but are stable on average, showing their oscillations can be ergodic and their desired limit locally recovered by time-averaging.

I. INTRODUCTION

  • Average stability yields ergodic random oscillations, allowing nodes to recover the desired limit through local time-averaging.In some cases, averaging does not require a common clock.Source: §I · p. 1
  • Time-averaging provides smoothing for randomized algorithms that do not converge deterministically.Source: §I · p. 1
  • Relative-measurement localization estimates sensor positions and also applies to clock synchronization and phase estimation in power grids.The paper proposes asynchronous pairwise gossip updates for this problem.Source: §I · p. 1
  • For PageRank, the paper establishes a general convergence result and applies it to a novel pairwise gossip algorithm [16],,.Source: §I · p. 1
  • For opinion dynamics, the proposed gossip mechanism interprets the classical model as the average evolution of randomized updates, addressing a modeling question raised in.The paper extends an observation from in connection with the Friedkin–Johnsen model.Source: §I · p. 1
  • The current framework builds on earlier conference results, adds PageRank, and is presented as applicable beyond the three examples.Source: §I · p. 2

A. Sensor localization in wireless networks

Relative localization estimates node positions from noisy differences across network edges. The paper formulates the task as least squares and establishes convergence of a gradient algorithm under a step-size condition.

A. Sensor localization in wireless networks

B. PageRank computation in Google

The PageRank computation models web pages and their links as a network, then represents the ranking recursion as affine dynamics. The recursion converges for stochastic initial vectors.

B. PageRank computation in Google

C. Opinion dynamics in social networks

The opinion model represents social influence and preconceived beliefs as affine dynamics. Its opinions converge when every agent can reach an agent with positive self-weight.

C. Opinion dynamics in social networks

III. ERGODIC RANDOMIZED DYNAMICS OVER NETWORKS

The section develops ergodicity results for randomized affine network dynamics that may oscillate instead of converging deterministically. Under stated independence and stability conditions, their time-averaged behavior recovers the synchronous limit, with applications to sensor localization, PageRank, and opinion dynamics.

Applications

  • The section applies its ergodicity results to sensor localization, PageRank computation, and opinion dynamics in social networks.The general result concerns suitable randomized versions of the network dynamics.Source: §III · pp. 4–5

Motivation and notions

  • Randomized affine dynamics can oscillate persistently and fail to converge deterministically, motivating probabilistic convergence guarantees.The section focuses on almost-sure ergodicity and notes that uniformly bounded sequences also yield mean-square convergence by dominated convergence.Source: §III · p. 4

Main result

  • Theorem 1 shows that the process converges in distribution to a random variable with a unique invariant distribution, is ergodic, and has limiting expectation x⋆.The result assumes i.i.d. matrix and input sequences with finite first moments and the stated α condition.Source: §III · p. 4

Random subsequences

  • Corollary 1 extends the analysis to random subsequences under stated independence and positive-selection-probability conditions.The corollary assumes i.i.d. process matrices and inputs with finite first moments.Source: §III · p. 5

A. Sensor localization in wireless networks (cont’d)

The sensor-localization algorithm updates a pair of nodes at a time and uses local update counts to form smoothed estimates without a shared clock. Although the raw dynamics oscillates, the smoothed estimate converges almost surely to the least-squares solution under uniform edge selection.

Algorithm

  • Each activated pair updates its raw estimates and local update counts, while the smoothed estimate is formed through time-averaging.The algorithm initializes the states at zero and selects pairs uniformly and independently across time.Source: A. Sensor localization in wireless… · p. 5

Implementation

  • Local update counts let the fully distributed algorithm average estimates without requiring nodes to share a global clock.This asynchronous feature is noted as attractive for clock-synchronization applications.Source: A. Sensor localization in wireless… · p. 5

Convergence

  • The smoothed estimate converges almost surely to the least-squares solution under uniform edge selection.The raw dynamics oscillates persistently rather than converging deterministically; the illustrated run uses a complete graph with 10 nodes and γ = 0.5.Source: A. Sensor localization in wireless… · pp. 5–6, Figure 1 · p. 5

Additional guarantees

  • With noise-free measurements, the raw state itself converges exponentially fast to the exact solution; the smoothed estimate also converges in mean square.The mean-square result is stated without a detailed proof.Source: A. Sensor localization in wireless… · p. 6

B. PageRank computation in Google (cont’d)

The section introduces a pairwise gossip algorithm for PageRank that activates one edge per step, then states an ergodic convergence result. The update requires a global time variable to preserve the stochasticity of the PageRank vector.

Algorithm

  • Each step samples an edge uniformly and independently and applies the vector update with design parameter r in (0, 1).Activating one edge at a time is presented as minimizing communication effort.Source: B. PageRank computation in Google… · p. 6

Implementation

  • Unlike the sensor-localization algorithm, this PageRank update requires nodes to access global time to preserve the stochasticity of x(k).The authors consider this reasonable for webpages or domain servers that typically have clocks.Source: B. PageRank computation in Google… · p. 6

Convergence

  • Theorem 3 states ergodic convergence for the PageRank dynamics, and the authors conclude almost-sure convergence under the specified parameter setting.The section also notes mean-square ergodicity under assumptions equivalent to those of Theorem 1.Source: B. PageRank computation in Google… · pp. 6–7

C. Opinion dynamics in social networks (cont’d)

The section introduces randomized communication in the Friedkin–Johnsen model and proves that its gossip opinion dynamics is ergodic under a graph condition. Time-averaged opinions converge to the same value as the synchronous dynamics.

C. Opinion dynamics in social networks (cont’d)

  • The randomized communication model yields a new class of opinion dynamics based on interactions in randomly selected pairs.At each step, the selected agent updates using its belief, the other agent’s belief, and its initial belief.Source: C. Opinion dynamics in social networks… · p. 7
  • The gossip dynamics converge to the same x⋆_opd as the synchronous opinion model.The proof rewrites the update as a special case of the paper’s general randomized process.Source: C. Opinion dynamics in social networks… · p. 7
  • Under the stated graph condition, the gossip opinions are almost surely and mean-square ergodic, and their time averages converge to x⋆_opd.The condition requires a path from every node to a node i with W_ii > 0.Source: C. Opinion dynamics in social networks… · p. 7
  • The model assumes uniformly sampled edges for simplicity, though the analysis can extend to other distributions.Source: C. Opinion dynamics in social networks… · p. 7
  • The pairwise gossip model offers a more realistic communication process than synchronous rounds and is consistent with pairwise asynchronous discussions reported in.The authors present this relationship as a new perspective on the Friedkin–Johnsen model.Source: C. Opinion dynamics in social networks… · p. 8

IV. CONCLUDING REMARKS

The conclusion presents time-averaging as a simple, unifying way to smooth oscillations in randomized network systems, while noting its slower convergence rate. It also points to further applications and alternative algorithmic approaches.

IV. CONCLUDING REMARKS

  • Decreasing-gain under-relaxation is an alternative smoothing approach, while asynchronous iteration and node memory are noted as avenues for faster algorithms.The conclusion says decreasing gains entail more complex analysis and identifies localization as an example of memory-based design.Source: §IV · p. 8
  • Time-averaging is simple to apply, requires minimal assumptions, unifies different algorithms, and offers qualitative insight into stochastic processes.Source: §IV · p. 8
  • Time-averages converge at a polynomial O(1/k) rate rather than the exponential rate of the original synchronous dynamics.The authors note that this drawback also occurs with over-relaxation approaches.Source: §IV · p. 8
  • The authors expect the framework to apply beyond the three examples, including sensor-network estimation and classification, convex optimization, and power-network optimization.Source: §IV · p. 8

APPENDIX A PROOF OF THEOREM 1

The proof studies a backward version of the random affine process, whose convergence and invariant distribution can be established from stability of the expected update matrix. It then uses the backward process and ergodic theorems to establish the forward process’s limiting behavior and time-average result.

APPENDIX A PROOF OF THEOREM 1

  • The proof uses iterated random-function techniques and defines a backward process whose distribution at each time matches that of the forward process.The backward process reverses the order of the random matrix products.Source: Appendix A · p. 9
  • The forward process converges in distribution to the same invariant distribution as the backward process.The proof uses their matching distributions and the backward-process convergence result.Source: Appendix A · pp. 9–10
  • When the expected update matrix is a convex combination of the identity and a Schur-stable matrix, the backward process converges almost surely to a finite limit with a unique invariant distribution.The lemma assumes i.i.d. updates with finite first moments.Source: Appendix A · p. 9
  • A stationary comparison process, Birkhoff’s theorem, and a vanishing difference between coupled trajectories establish the almost-sure time-average result.The proof also identifies the limiting mean with x⋆.Source: Appendix A · p. 10

APPENDIX B PROOF OF COROLLARY 1

The proof applies a Toeplitz-array argument to transfer convergence between trajectories, then uses ergodic and probability-limit results to obtain the claimed almost-sure conclusion.

APPENDIX B PROOF OF COROLLARY 1

  • The proof uses the Silverman–Toeplitz theorem after establishing that the coupled trajectories’ difference tends to zero.It then invokes Birkhoff’s theorem for a stationary ergodic process and uses independence in the final step.Source: Appendix B · p. 10

Related papers

Loading 1309.1349v2…