 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.

In this paper, we consider the linear convectiondiffusion equation in one dimension with periodic boundary conditions, and analyze the stability of fully discrete methods that are defined with local discontinuous Galerkin (LDG) methods in space and several implicitexplicit (IMEX) RungeKutta methods in time. By using the forward temporal differences and backward temporal differences, respectively, we establish two general frameworks of the energymethod based stability analysis. From here, the fully discrete schemes being considered are shown to have monotonicity stability, i.e. the
$L^2$ norm of the numerical solution does not increase in time, under the time step condition$\tau \le \mathcal {F}(h/c, d/c^2)$ , with the convection coefficient$c$ , the diffusion coefficient$d$ , and the mesh size$h$ . The function$\mathcal {F}$ depends on the specific IMEX temporal method, the polynomial degree$k$ of the discrete space, and the mesh regularity parameter. Moreover, the time step condition becomes$\tau \lesssim h/c$ in the convectiondominated regime and it becomes$\tau \lesssim d/c^2$ in the diffusiondominated regime. The result is improved for a first order IMEXLDG method. To complement the theoretical analysis, numerical experiments are further carried out, leading to slightly stricter time step conditions that can be used by practitioners. Uniform stability with respect to the strength of the convection and diffusion effects can especially be relevant to guide the choice of time step sizes in practice, e.g. when the convectiondiffusion equations are convectiondominated in some subregions. 
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