 NSFPAR ID:
 10219860
 Date Published:
 Journal Name:
 Advanced studies in pure mathematics
 ISSN:
 24338915
 Page Range / eLocation ID:
 149
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

We study the infinitehorizon Restless Bandit problem with the average reward criterion, under both discretetime and continuoustime settings. A fundamental goal is to design computationally efficient policies that achieve a diminishing optimality gap as the number of arms, N, grows large. Existing results on asymptotic optimality all rely on the uniform global attractor property (UGAP), a complex and challengingtoverify assumption. In this paper, we propose a general, simulationbased framework, FollowtheVirtualAdvice, that converts any singlearmed policy into a policy for the original Narmed problem. This is done by simulating the singlearmed policy on each arm and carefully steering the real state towards the simulated state. Our framework can be instantiated to produce a policy with an O(1/pN) optimality gap. In the discretetime setting, our result holds under a simpler synchronization assumption, which covers some problem instances that violate UGAP. More notably, in the continuoustime setting, we do not require any additional assumptions beyond the standard unichain condition. In both settings, our work is the first asymptotic optimality result that does not require UGAP.more » « less

Loh, PoLing ; Raginsky, Maxim (Ed.)We establish a connection between sampling and optimization on discrete domains. For a family of distributions $\mu$ defined on size $k$ subsets of a ground set of elements, that is closed under external fields, we show that rapid mixing of natural local random walks implies the existence of simple approximation algorithms to find $\max \mu(\cdot)$. More precisely, we show that if $t$step downup random walks have spectral gap at least inverse polynomially large, then $t$step local search finds $\max \mu(\cdot)$ within a factor of $k^{O(k)}$. As the main application of our result, we show that $2$step local search achieves a nearlyoptimal $k^{O(k)}$factor approximation for MAP inference on nonsymmetric $k$DPPs. This is the first nontrivial multiplicative approximation algorithm for this problem. In our main technical result, we show that an exchange inequality, a concept rooted in discrete convex analysis, can be derived from fast mixing of local random walks. We further advance the state of the art on the mixing of random walks for nonsymmetric DPPs and more generally sectorstable distributions, by obtaining the tightest possible bound on the step size needed for polynomialtime mixing of random walks. We bring the step size down by a factor of $2$ compared to prior works, and consequently get a quadratic improvement on the runtime of local search steps; this improvement is potentially of independent interest in sampling applications.more » « less

Abstract We study the stability with respect to a broad class of perturbations of gapped groundstate phases of quantum spin systems defined by frustrationfree Hamiltonians. The core result of this work is a proof using the Bravyi–Hastings–Michalakis (BHM) strategy that under a condition of local topological quantum order (LTQO), the bulk gap is stable under perturbations that decay at long distances faster than a stretched exponential. Compared to previous work, we expand the class of frustrationfree quantum spin models that can be handled to include models with more general boundary conditions, and models with discrete symmetry breaking. Detailed estimates allow us to formulate sufficient conditions for the validity of positive lower bounds for the gap that are uniform in the system size and that are explicit to some degree. We provide a survey of the BHM strategy following the approach of Michalakis and Zwolak, with alterations introduced to accommodate more general than just periodic boundary conditions and more general lattices. We express the fundamental condition known as LTQO by means of an indistinguishability radius, which we introduce. Using the uniform finitevolume results, we then proceed to study the thermodynamic limit. We first study the case of a unique limiting ground state and then also consider models with spontaneous breaking of a discrete symmetry. In the latter case, LTQO cannot hold for all local observables. However, for perturbations that preserve the symmetry, we show stability of the gap and the structure of the broken symmetry phases. We prove that the GNS Hamiltonian associated with each pure state has a nonzero spectral gap above the ground state.

Motivated by recent progress in data assimilation, we develop an algorithm to dynamically learn the parameters of a chaotic system from partial observations. Under reasonable assumptions, we supply a rigorous analytical proof that guarantees the convergence of this algorithm to the true parameter values when the system in question is the classic threedimensional Lorenz system. Such a result appears to be the first of its kind for dynamical parameter estimation of nonlinear systems. Computationally, we demonstrate the efficacy of this algorithm on the Lorenz system by recovering any proper subset of the three nondimensional parameters of the system, so long as a corresponding subset of the state is observable. We moreover probe the limitations of the algorithm by identifying dynamical regimes under which certain parameters cannot be effectively inferred having only observed certain state variables. In such cases, modifications to the algorithm are proposed that ultimately result in recovery of the parameter. Lastly, computational evidence is provided that supports the efficacy of the algorithm well beyond the hypotheses specified by the theorem, including in the presence of noisy observations, stochastic forcing, and the case where the observations are discrete and sparse in time.

Biological neural computation is inherently asynchronous due to large variations in neuronal spike timing and transmission delays. Sofar, most theoretical work on neural networks assumes the synchronous setting where neurons fire simultaneously in discrete rounds. In this work we aim at understanding the barriers of asynchronous neural computation from an algorithmic perspective. We consider an extension of the widely studied model of synchronized spiking neurons [Maass, Neural= Networks 97] to the asynchronous setting by taking into account edge and node delays. Edge Delays: We define an asynchronous model for spiking neurons in which the latency values (i.e., transmission delays) of non selfloop edges vary adversarially over time. This extends the recent work of [Hitron and Parter, ESA’19] in which the latency values are restricted to be fixed over time. Our first contribution is an impossibility result that implies that the assumption that selfloop edges have no delays (as assumed in Hitron and Parter) is indeed necessary. Interestingly, in real biological networks selfloop edges (a.k.a. autapse) are indeed free of delays, and the latter has been noted by neuroscientists to be crucial for network synchronization. To capture the computational challenges in this setting, we first consider the implementation of a single NOT gate. This simple function already captures the fundamental difficulties in the asynchronous setting. Our key technical results are space and time upper and lower bounds for the NOT function, our time bounds are tight. In the spirit of the distributed synchronizers [Awerbuch and Peleg, FOCS’90] and following [Hitron and Parter, ESA’19], we then provide a general synchronizer machinery. Our construction is very modular and it is based on efficient circuit implementation of threshold gates. The complexity of our scheme is measured by the overhead in the number of neurons and the computation time, both are shown to be polynomial in the largest latency value, and the largest incoming degree ∆ of the original network. Node Delays: We introduce the study of asynchronous communication due to variations in the response rates of the neurons in the network. In real brain networks, the round duration varies between different neurons in the network. Our key result is a simulation methodology that allows one to transform the above mentioned synchronized solution under edge delays into a synchronized under node delays while incurring a small overhead w.r.t space and time.more » « less