Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStatistical inference of finite-rank tensors
57
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider a general statistical inference model of finite-rank tensor products. For any interaction structure and any order of tensor products, we identify the limit free energy of the model in terms of a variational formula. Our approach consists of showing first that the limit free energy must be the viscosity solution to a certain Hamilton-Jacobi equation.
rate research
Read More
We compute the high-dimensional limit of the free energy associated with a multi-layer generalized linear model. Under certain technical assumptions, we identify the limit in terms of a variational formula. The approach is to first show that the limit is a solution to a Hamilton-Jacobi equation whose initial condition is related to the limiting free energy of a model with one fewer layer. Then, we conclude by an iteration.
We study the mean-field Ising spin glass model with external field, where the random symmetric couplings matrix is orthogonally invariant in law. For sufficiently high temperature, we prove that the replica-symmetric prediction is correct for the first-order limit of the free energy. Our analysis is an adaption of a conditional quenched equals annealed argument used by Bolthausen to analyze the high-temperature regime of the Sherrington-Kirkpatrick model. We condition on a sigma-field that is generated by the iterates of an Approximate Message Passing algorithm for solving the TAP equations in this model, whose rigorous state evolution was recently established.
We consider the phase retrieval problem of reconstructing a $n$-dimensional real or complex signal $mathbf{X}^{star}$ from $m$ (possibly noisy) observations $Y_mu = | sum_{i=1}^n Phi_{mu i} X^{star}_i/sqrt{n}|$, for a large class of correlated real and complex random sensing matrices $mathbf{Phi}$, in a high-dimensional setting where $m,ntoinfty$ while $alpha = m/n=Theta(1)$. First, we derive sharp asymptotics for the lowest possible estimation error achievable statistically and we unveil the existence of sharp phase transitions for the weak- and full-recovery thresholds as a function of the singular values of the matrix $mathbf{Phi}$. This is achieved by providing a rigorous proof of a result first obtained by the replica method from statistical mechanics. In particular, the information-theoretic transition to perfect recovery for full-rank matrices appears at $alpha=1$ (real case) and $alpha=2$ (complex case). Secondly, we analyze the performance of the best-known polynomial time algorithm for this problem -- approximate message-passing -- establishing the existence of a statistical-to-algorithmic gap depending, again, on the spectral properties of $mathbf{Phi}$. Our work provides an extensive classification of the statistical and algorithmic thresholds in high-dimensional phase retrieval for a broad class of random matrices.
In modern settings of data analysis, we may be running our algorithms on datasets that are sensitive in nature. However, classical machine learning and statistical algorithms were not designed with these risks in mind, and it has been demonstrated that they may reveal personal information. These concerns disincentivize individuals from providing their data, or even worse, encouraging intentionally providing fake data. To assuage these concerns, we import the constraint of differential privacy to the statistical inference, considered by many to be the gold standard of data privacy. This thesis aims to quantify the cost of ensuring differential privacy, i.e., understanding how much additional data is required to perform data analysis with the constraint of differential privacy. Despite the maturity of the literature on differential privacy, there is still inadequate understanding in some of the most fundamental settings. In particular, we make progress in the following problems: $bullet$ What is the sample complexity of DP hypothesis testing? $bullet$ Can we privately estimate distribution properties with a negligible cost? $bullet$ What is the fundamental limit in private distribution estimation? $bullet$ How can we design algorithms to privately estimate random graphs? $bullet$ What is the trade-off between the sample complexity and the interactivity in private hypothesis selection?
We consider the problem of estimating a vector of discrete variables $(theta_1,cdots,theta_n)$, based on noisy observations $Y_{uv}$ of the pairs $(theta_u,theta_v)$ on the edges of a graph $G=([n],E)$. This setting comprises a broad family of statistical estimation problems, including group synchronization on graphs, community detection, and low-rank matrix estimation. A large body of theoretical work has established sharp thresholds for weak and exact recovery, and sharp characterizations of the optimal reconstruction accuracy in such models, focusing however on the special case of Erdos--Renyi-type random graphs. The single most important finding of this line of work is the ubiquity of an information-computation gap. Namely, for many models of interest, a large gap is found between the optimal accuracy achievable by any statistical method, and the optimal accuracy achieved by known polynomial-time algorithms. Moreover, this gap is generally believed to be robust to small amounts of additional side information revealed about the $theta_i$s. How does the structure of the graph $G$ affect this picture? Is the information-computation gap a general phenomenon or does it only apply to specific families of graphs? We prove that the picture is dramatically different for graph sequences converging to amenable graphs (including, for instance, $d$-dimensional grids). We consider a model in which an arbitrarily small fraction of the vertex labels is revealed, and show that a linear-time local algorithm can achieve reconstruction accuracy that is arbitrarily close to the information-theoretic optimum. We contrast this to the case of random graphs. Indeed, focusing on group synchronization on random regular graphs, we prove that the information-computation gap still persists even when a small amount of side information is revealed.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
