PROSE: A Theory of Optimal Stopping with Perishable Evidence for Peer Selection in Intermittently Connected Decentralised Learning

Abstract:Decentralised federated learning removes the aggregation server but makes collaboration dependent on transient peer availability. In mobile and intermittently connected systems, evaluating a promising peer consumes contact time and may cause the exchange opportunity itself to vanish, so that the evidence a learner gathers about a peer is perishable: it decays because links expire and because peer models drift while old measurements age. This paper develops a self-contained theory of optimal stopping for the resulting peer-selection problem. We formalise a receiver's within-contact decision as a finite-horizon Markov optimal-stopping problem with costly information acquisition and a future-arrival outside option, and prove that it admits an optimal policy characterised by a reservation value (Snell-envelope structure). Around this formulation we prove: (i) stage-uniform, drift-aware concentration and a maximin certification rule that is correct with high probability together with a finite-sample identification bound; (ii) a mobility-aware value of-information stopping rule and comparative statics showing that higher link hazard lowers the value of continued probing and enlarges the stopping region; (iii) a closed-form value of waiting under marked-Poisson contact arrivals, together with a search-theoretic reservation value whose comparative statics we characterise; and (iv) a myopic-optimality theorem establishing that, in sufficiently volatile (monotone) mobility regimes, the one-step confidence-safe rule is a sound surrogate for the optimal policy and never stops prematurely. We instantiate the theory as PROSE (Perishable-evidence Reservation-value Optimal Stopping for Exchange), a lightweight, fully local policy, and delineate the static contact and drift-free limits in which classical sequential decision problems are recovered. The development is entirely analytical.

22 pages, 6 figures. Theory paper; no experiments

Machine Learning (cs.LG)

I.2.6; G.3; C.2.4

arXiv:2609.23845 [cs.LG]

(or arXiv:2609.23845v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2609.23845 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.