7 papers
Convergence guarantees for stochastic algorithms solving non-unique problems in metric spaces
Nicholas Pischke, Thomas Powell
We prove a general quantitative theorem on the asymptotic behavior of stochastic quasi-Fejér monotone sequences in a broad metric context. Concretely, our result explicitly constru…
Generalized fluctuation bounds for stochastic algorithms in the presence of compactness
Morenikeji Neri, Nicholas Pischke, Thomas Powell
We provide a convergence result for sequences of random variables taking values in a metric space that satisfy a stochastic quasi-Fejér monotonicity condition, in the context of a…
An approximate zero-one law via the Dialectica interpretation
Thomas Powell, Alex Wan
Zero-one laws state that probabilistic events of a certain type must occur with probability either or , and nothing in between. We formulate a syntactic zero-one law, which…
An abstract effective convergence theorem for stochastic processes, with applications to stochastic approximation
Morenikeji Neri, Nicholas Pischke, Thomas Powell
We provide a general theorem on the asymptotic behavior of stochastic processes that conform to a relaxed supermartingale condition. The distinguishing feature of our result is tha…
Asymptotic regularity of a generalised stochastic Halpern scheme
Nicholas Pischke, Thomas Powell
We provide abstract, general and highly uniform rates of asymptotic regularity for a generalized stochastic Halpern-style iteration, which incorporates a second mapping in the styl…
A quantitative Robbins-Siegmund theorem
Morenikeji Neri, Thomas Powell
The Robbins-Siegmund theorem is one of the most important results in stochastic optimization, where it is widely used to prove the convergence of stochastic algorithms. We provide…
On quantitative convergence for stochastic processes: Crossings, fluctuations and martingales
Morenikeji Neri, Thomas Powell
We develop a general framework for extracting highly uniform bounds on local stability for stochastic processes in terms of information on fluctuations or crossings. This includes…