Search

We prove that Ising models on the hypercube with general quadratic interactions satisfy a Poincaré inequality with respect to the natural Dirichlet form corresponding to Glauber dynamics, as soon as the operator norm of the interaction matrix is smaller than 1. The inequality implies a control on the mixing time of the Glauber dynamics. Our techniques rely on a localization procedure which establishes a structural result, stating that Ising measures may be decomposed into a mixture of measures with quadratic potentials of rank one, and provides a framework for proving concentration bounds for high temperature Ising models.

We study in this paper lower bounds for the generalization error of models derived from multi-layer neural networks, in the regime where the size of the layers is commensurate with the number of samples in the training data. We show that unbiased estimators have unacceptable performance for such nonlinear networks in this regime. We derive explicit generalization lower bounds for general biased estimators, in the cases of linear regression and of two-layered networks. In the linear case the bound is asymptotically tight. In the nonlinear case, we provide a comparison of our bounds with an empirical study of the stochastic gradient descent algorithm. The analysis uses elements from the theory of large random matrices., Comment: Minor correction+conference information. To appear in IEEE Trans. Inf. Th

Nakamoto invented the longest chain protocol, and claimed its security by analyzing the private double-spend attack, a race between the adversary and the honest nodes to grow a longer chain. But is it the worst attack? We answer the question in the affirmative for three classes of longest chain protocols, designed for different consensus models: 1) Nakamoto's original Proof-of-Work protocol; 2) Ouroboros and SnowWhite Proof-of-Stake protocols; 3) Chia Proof-of-Space protocol. As a consequence, exact characterization of the maximum tolerable adversary power is obtained for each protocol as a function of the average block time normalized by the network delay. The security analysis of these protocols is performed in a unified manner by a novel method of reducing all attacks to a race between the adversary and the honest nodes., Comment: 27 pages, 12 figures. A shorter version of this paper will appear in the 2020 ACM Conference on Computer and Communications Security (CCS)

The Nakamoto longest chain protocol is remarkably simple and has been proven to provide security against any adversary with less than 50% of the total hashing power. Proof-of-stake (PoS) protocols are an energy efficient alternative; however existing protocols adopting Nakamoto's longest chain design achieve provable security only by allowing long-term predictability (which have serious security implications). In this paper, we prove that a natural longest chain PoS protocol with similar predictability as Nakamoto's PoW protocol can achieve security against any adversary with less than 1/(1+e) fraction of the total stake. Moreover we propose a new family of longest chain PoS protocols that achieve security against a 50% adversary, while only requiring short-term predictability. Our proofs present a new approach to analyzing the formal security of blockchains, based on a notion of adversary-proof convergence., Comment: 65 pages, 16 figures

We investigate in this work the asymptotic behavior of isotropic diffusions in random environment that are small perturbations of Brownian motion. When the space dimension is three or more, we prove an invariance principle as well as transience. Our methods also apply to questions of homogenization in random media

We discuss regularization by noise of the spectrum of large random non-normal matrices. Under suitable conditions, we show that the regularization of a sequence of matrices that converges in *-moments to a regular element a by the addition of a polynomially vanishing Gaussian Ginibre matrix forces the empirical measure of eigenvalues to converge to the Brown measure of a., France. Agence nationale de la recherche (Project ANR-08-BLAN-0311-01)

We consider the following detection problem: given a realization of a symmetric matrix ${\mathbf{X}}$ of dimension $n$, distinguish between the hypothesis that all upper triangular variables are i.i.d. Gaussians variables with mean 0 and variance $1$ and the hypothesis where ${\mathbf{X}}$ is the sum of such matrix and an independent rank-one perturbation. This setup applies to the situation where under the alternative, there is a planted principal submatrix ${\mathbf{B}}$ of size $L$ for which all upper triangular variables are i.i.d. Gaussians with mean $1$ and variance $1$, whereas all other upper triangular elements of ${\mathbf{X}}$ not in ${\mathbf{B}}$ are i.i.d. Gaussians variables with mean 0 and variance $1$. We refer to this as the `Gaussian hidden clique problem.' When $L=(1+\epsilon)\sqrt{n}$ ($\epsilon>0$), it is possible to solve this detection problem with probability $1-o_n(1)$ by computing the spectrum of ${\mathbf{X}}$ and considering the largest eigenvalue of ${\mathbf{X}}$. We prove that this condition is tight in the following sense: when $L<(1-\epsilon)\sqrt{n}$ no algorithm that examines only the eigenvalues of ${\mathbf{X}}$ can detect the existence of a hidden Gaussian clique, with error probability vanishing as $n\to\infty$. We prove this result as an immediate consequence of a more general result on rank-one perturbations of $k$-dimensional Gaussian tensors. In this context we establish a lower bound on the critical signal-to-noise ratio below which a rank-one signal cannot be detected., Comment: 15 pages

We analyze the behavior of the Barvinok estimator of the hafnian of even dimension, symmetric matrices with nonnegative entries. We introduce a condition under which the Barvinok estimator achieves subexponential errors, and show that this condition is almost optimal. Using that hafnians count the number of perfect matchings in graphs, we conclude that Barvinok's estimator gives a polynomial-time algorithm for the approximate (up to subexponential errors) evaluation of the number of perfect matchings., Comment: Published at http://dx.doi.org/10.1214/15-AOP1036 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Consider a $d$-ary rooted tree ($d\geq3$) where each edge $e$ is assigned an i.i.d. (bounded) random variable $X(e)$ of negative mean. Assign to each vertex $v$ the sum $S(v)$ of $X(e)$ over all edges connecting $v$ to the root, and assume that the maximum $S_n^*$ of $S(v)$ over all vertices $v$ at distance $n$ from the root tends to infinity (necessarily, linearly) as $n$ tends to infinity. We analyze the Metropolis algorithm on the tree and show that under these assumptions there always exists a temperature $1/\beta$ of the algorithm so that it achieves a linear (positive) growth rate in linear time. This confirms a conjecture of Aldous [Algorithmica 22 (1998) 388-412]. The proof is obtained by establishing an Einstein relation for the Metropolis algorithm on the tree., Comment: Published in at http://dx.doi.org/10.1214/13-AAP972 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We present estimates on the small singular values of a class of matrices with independent Gaussian entries and inhomogeneous variance profile, satisfying a broad-connectedness condition. Using these estimates and concentration of measure for the spectrum of Gaussian matrices with independent entries, we prove that for a large class of graphs satisfying an appropriate expansion property, the Barvinok--Godsil-Gutman estimator for the permanent achieves sub-exponential errors with high probability., Comment: small revision, no major changes. Changed terminology to "broadly connected". Corrected error in probability estimate in statement of theorems 1.4 and 1.5

We consider the maximum of the discrete two dimensional Gaussian free field in a box, and prove the existence of a (dense) deterministic subsequence along which the maximum, centered at its mean, is tight. The method of proof relies on an argument developed by F. M. Dekking and B. Host [Probab. Theory Relat. Fields 90, No. 3, 403–426 (1991; Zbl 0734.60074)] for branching random walks with bounded increments and on comparison results specific to Gaussian fields.

We present a deterministic algorithm that given a tree T with n vertices, a starting vertex v and a slackness parameter epsilon > 0, estimates within an additive error of epsilon the cover and return time, namely, the expected time it takes a simple random walk that starts at v to visit all vertices of T and return to v. The running time of our algorithm is polynomial in n/epsilon, and hence remains polynomial in n also for epsilon = 1/n^{O(1)}. We also show how the algorithm can be extended to estimate the expected cover (without return) time on trees.

We apply the theory of random Schr\"odinger operators to the analysis of multi-users communication channels similar to the Wyner model, that are characterized by short-range intra-cell broadcasting. With $H$ the channel transfer matrix, $HH^\dagger$ is a narrow-band matrix and in many aspects is similar to a random Schr\"odinger operator. We relate the per-cell sum-rate capacity of the channel to the integrated density of states of a random Schr\"odinger operator; the latter is related to the top Lyapunov exponent of a random sequence of matrices via a version of the Thouless formula. Unlike related results in classical random matrix theory, limiting results do depend on the underlying fading distributions. We also derive several bounds on the limiting per-cell sum-rate capacity, some based on the theory of random Schr\"odinger operators, and some derived from information theoretical considerations. Finally, we get explicit results in the high-SNR regime for some particular cases., Comment: Submitted to IEEE Transactions on Information Theory

In this paper we study the spectrum of certain large random Hermitian Jacobi matrices. These matrices are known to describe certain communication setups. In particular we are interested in an uplink cellular channel which models mobile users experiencing a soft-handoff situation under joint multicell decoding. Considering rather general fading statistics we provide a closed form expression for the per-cell sum-rate of this channel in high-SNR, when an intra-cell TDMA protocol is employed. Since the matrices of interest are tridiagonal, their eigenvectors can be considered as sequences with second order linear recurrence. Therefore, the problem is reduced to the study of the exponential growth of products of two by two matrices. For the case where $K$ users are simultaneously active in each cell, we obtain a series of lower and upper bound on the high-SNR power offset of the per-cell sum-rate, which are considerably tighter than previously known bounds.

Cover title., Includes bibliographical references (leaf 6)., Research supported by the U.S. Army Research Office. DAAL03-86-K-0171 Research supported by the Office of Naval Research under an Air Force contract. F19628-90-C-0002, Sanjeev R. Kulkarni and Ofer Zeitouni.

Cover title., Includes bibliographical references., Supported by the Air Force Office of Scientific Research. AFOSR-85-0227B Supported by the National Science Foundation. MIP86-19169 Supported by the U.S. Army Research Office. DAAL03-86-K-0045 Supported by NASA Headquarters, Center for Aeronautics and Space Information Sciences. NAGW-419-S1.3, by Amir Dembo, Ofer Zeitouni.

Caption title., Includes bibliographical references., A. Dembo, Ofer Zeitouni.

Cover title., Includes bibliographical references (leaf 5)., Research supported by the MITRE Sponsored Research Program. Research supported by the Army Research Office. DAAL03-86-K-0171, J. Ramanathan, O. Zeitouni.

Caption title. "August 1988.", Includes bibliographical references., This work was partially supported by the U.S. Army Research Office under contract DAAL03-86-K-0045 This work was partially supported by the National Science Foundation under grant MIP86-19169 This work was partially supported by NASA Headquarters grant NAGW-419-S1.3 This work was partially supported by Air Force Office of Scientific Research grant AFOSR-85-0227B The work of Ofer Zeitouni was partially supported by a Weizmann postdoctoral fellowship., by Amir Dembo, Ofer Zeitouni.

Caption title., Bibliography: leaf 11., Supported, in part, by a grant from the Air Force Office of Scientific Research. AFOSR-85-0227B Supported, in part, by the Weizmann Postdoctoral Fellowship., by Ofer Zeitouni.

Caption title., Includes bibliographical references (p. 5)., Supported by the NSF. DMS92-09712 Supported by a US-ISRAEL BSF grant. Supported by the Army Research Office. ARO DAAL03-92-G-0115, Amir Dembo, Ofer Zeitouni.

Caption title. "Submitted: July 29, 1991, Revised Aug. 12, 1993.", Includes bibliographical references (p. 19-20)., Supported by the U.S. Army Research Office. DAAL03-86-K-0171 DAAL03-92-G-0320 Suppoted by National Science Foundation. IRI-9209577 Supported by the Office of Naval Research under an Air Force contract. F19628-90-C-0002, Ofer Zeitouni and Sanjeev R. Kulkarni.

Caption title., Includes bibliographical references (p. 13-14)., Supported by the Bernstein Research Fund at the Technion. Supported by the Center for Intelligent Control Systems under a U.S. Army Research Office grant. DAAL03-86-K0171, Eddy Mayer Wolf and Ofer Zeitouni.

Caption title., Bibliography: leaf [12]., Supported, in part, by a grant from the Air Force Office of Scientific Research. AFOSR-85-0227B Supported, in part, by the Weizmann Postdoctoral Fellowship., Amir Dembo, Ofer Zeitouni.

Cover title. "April 1987. Revised: November 1987.", Includes bibliographical references., Supported in part by the Army Research Office. DAAG29-84-K-0082 Supported in part by the Office of Naval Research. N00014-85-K-0607 Supported in part by the Weizmann Post-Doctoral Fellowship., by Ofer Zeitouni.

Caption title., Bibliography: p. 19., Supported, in part, by a grant from the Air Force Office of Scientific Research. AFOSR-85-0227 Supported, in part, by the Weizmann Postdoctoral Fellowship., by Ofer Zeitouni.

Caption title. "September 1988.", Includes bibliographical references., The work of the second author was partially supported by a Weizmann postdoctoral fellowship and an AFSOR grant 85-0227B, Ben-Zion Bobrovsky and Ofer Zeitouni.

Caption title., Bibliography: leaf 14., Supported, in part, by a grant from the Air Force Office of Scientific Research. AFOSR-85-0227B Supported, in part, by the Weizmann Postdoctoral Fellowship., by Bernard Delyon, Ofer Zeitouni.

Includes bibliographical references (p. 96-98)., Research supported by the Air Force Office of Scientific Research. AFOSR-89-0276B Research supported by the Army Research Office. DAAL03-86-K-171, A. Dembo, O. Zeitouni.

The problem of deciding whether the mean of an unknown distribution is in a set Alpha or in its complement based on a sequence of independent random variables drawn according to this distribution is considered. Using large deviations techniques, an algorithm is proposed which is shown to lead to an a.s. correct decision for a class of Alpha which are necessarily countable. A refined decision procedure is also presented which, given a countable decomposition of Alpha, can determine a.s. to which set of the decomposition the mean belongs. This extends and simplifies a construction by Cover., Prepared in cooperation with Technion, Haifa, Israel. Sponsored in part by Office of Naval Research (ONR), and Air Force contract F19628-90-C-0002.

Following a set up investigated by Rishel we consider an adaptive control problem with unknown parameter x as a partially observed stochastic control problem. Exploiting the finite dimensionality of the estimator, we transform it to a fully observed stochastic optimal control problem to which we then find epsilon-optimal randomized feedback policies.

The dependence of the optimal nonlinear filter on it's initial conditions is considered for continuous time linear filtering and for finite state space nonlinear filtering. Partial results are obtained in the high signal to noise ration case, together with a characterization of the Lyapunov exponent in the (easier) low SNR case.

Prepared in cooperation with Stanford University, Stanford, CA.

Investigating Hopfield's model of associative memory implementation by a neural network, led to a generalized potential system with a much superior performance as an associative memory. In particular, there are no spurious memories, and any set of desired points can be stored, with unlimited capacity (in the continuous time and real space version of the model). There are no limit cycles in this system, and the size of all basins of attraction can reach up to half the distance between the stored points, by proper choice of the design parameters. A discrete time version with its state space being the unit hypercube is also derived, and admits superior properties compared to the corresponding Hopfield network. In particular the capacity of any system of N neurons, with a fixed desired size of basins of attractions, is exponentially growing with N and is asymptotically optimal in the information theory sense. The computational complexity of this model is slightly larger than that of the Hopfield memory, but of the same order. The results are derived under an axiomatic approach which determines the desired properties and shows that the above mentioned model is the only one to achieve them., Supersedes AD-A181 933.

A relaxation model is presented based on an N dimensional Coulomb potential. The model has arbitrarily large storage capacity and, in addition, well-defined basins of attraction about stored memory states. The model is compared with the Hopfield relaxation model. Keywords: High density storage model; Hopfield model; Relaxation., Sponsored in part by contracts DAAG29-84-K-0262 and DAAG29-84-K-0082.

We investigate in this work the asymptotic behavior of isotropic diffusions in random environment that are small perturbations of Brownian motion. When the space dimension is three or more, we prove an invariance principle as well as transience. Our methods also apply to questions of homogenization in random media