We consider an online model for recommendation systems, with each user being recommended an item at each time-step and providing ’like’ or ’dislike’ feedback. A latent variable model specifies the user preferences: both users and items are clustered into types. The model captures structure in both the item and user spaces, as used by item-item and user-user collaborative filtering algorithms. We study the situation in which the type preference matrix has i.i.d. entries. Our main contribution is an algorithm that simultaneously uses both item and user structures, proved to be near-optimal via corresponding information-theoretic lower bounds. In particular, our analysis highlights the sub-optimality of using only one of item or user structure (as is done in most collaborative filtering algorithms).

We study the problem of approximately transforming a sample from a source statistical model to a sample from a target statistical model without knowing the parameters of the source model, and construct several computationally efficient such reductions between canonical statistical experiments. In particular, we provide computationally efficient procedures that approximately reduce uniform, Erlang, and Laplace location models to general target families. We illustrate our methodology by establishing nonasymptotic reductions between some canonical high-dimensional problems, spanning mixtures of experts, phase retrieval, and signal denoising. Notably, the reductions are structure-preserving and can accommodate missing data. We also point to a possible application in transforming one differentially private mechanism to another.

Consider a $d$-uniform random hypergraph on $n$ vertices in which hyperedges are included iid so that the average degree is $n^\delta$. The projection of a hypergraph is a graph on the same $n$ vertices where an edge connects two vertices if and only if they belong to some hyperedge. The goal is to reconstruct the hypergraph given its projection. An earlier work of Bresler, Guo, and Polyanskiy (COLT 2024) showed that exact recovery for $d=3$ is possible if and only if $\delta < 2/5$. This work completely resolves the question for all values of $d$ for both exact and partial recovery and for both cases of whether multiplicity information about each edge is available or not. In addition, we show that the reconstruction fidelity undergoes an all-or-nothing transition at a threshold. In particular, this resolves all conjectures from Bresler, Guo, and Polyanskiy (COLT 2024).

In this work, we show the first average-case reduction transforming the sparse Spiked Covariance Model into the sparse Spiked Wigner Model and as a consequence obtain the first computational equivalence result between two well-studied high-dimensional statistics models. Our approach leverages a new perturbation equivariance property for Gram-Schmidt orthogonalization, enabling removal of dependence in the noise while preserving the signal.

The meta-task of obtaining and aligning representations through contrastive pretraining is steadily gaining importance since its introduction in CLIP and ALIGN. In this paper we theoretically explain the advantages of synchronizing with trainable inverse temperature and bias under the sigmoid loss, as implemented in the recent SigLIP and SigLIP2 models of Google DeepMind. Temperature and bias can drive the loss function to zero for a rich class of configurations that we call $(\mathsf{m}, \mathsf{br})$ -Constellations. $(\mathsf{m}, \mathsf{br})$ -Constellations are a novel combinatorial object related to spherical codes and are parametrized by a margin $\mathsf{m}$ and relative bias $\mathsf{br}$. We use our characterization of constellations to theoretically justify the success of SigLIP on retrieval, to explain the modality gap present in SigLIP, and to identify the necessary dimension for producing high-quality representations. Finally, we propose a reparameterization of the sigmoid loss with explicit relative bias, which improves training dynamics in experiments with synthetic data.

Abstract. We consider the problem of counting [Formula: see text]-cliques in [Formula: see text]-uniform Erdős–Rényi hypergraphs [Formula: see text] with edge density [Formula: see text] and show that its fine-grained average-case complexity can be based on its worst-case complexity. We prove the following: (1) Dense Erdős–Rényi graphs and hypergraphs: Counting [Formula: see text]-cliques on [Formula: see text] with [Formula: see text] and [Formula: see text] constant matches its worst-case complexity up to a [Formula: see text] factor. Assuming randomized ETH, it takes [Formula: see text] time to count [Formula: see text]-cliques in [Formula: see text] if [Formula: see text] and [Formula: see text] are constant. (2) Sparse Erdős–Rényi graphs and hypergraphs: When [Formula: see text], we give several algorithms exploiting the sparsity of [Formula: see text] that are faster than the best known worst-case algorithms. Complementing this, based on a fine-grained worst-case assumption, our reduction implies a different average-case phase diagram for each fixed [Formula: see text] depicting a tradeoff between a runtime lower bound and [Formula: see text]. Surprisingly, in the hypergraph case ([Formula: see text]), these lower bounds are tight against our algorithms exactly when [Formula: see text] is above the Erdős–Rényi [Formula: see text]-clique percolation threshold. Our reduction yields the first known average-case hardness result on Erdős–Rényi hypergraphs based on worst-case hardness conjectures. We also give a variant of our worst-case to average-case reduction for computing the parity of the [Formula: see text]-clique count that requires a milder assumption on the error probability of the blackbox solving the problem on [Formula: see text].

We study the problem of approximately transforming a sample from a source statistical model to a sample from a target statistical model without knowing the parameters of the source model, and construct several computationally efficient such reductions between canonical statistical experiments. In particular, we provide computationally efficient procedures that approximately reduce uniform, Erlang, and Laplace location models to general target families. We illustrate our methodology by establishing nonasymptotic reductions between some canonical high-dimensional problems, spanning mixtures of experts, phase retrieval, and signal denoising. Notably, the reductions are structure-preserving and can accommodate missing data. We also point to a possible application in transforming one differentially private mechanism to another.

In this paper we study the random geometric graph $\mathsf{RGG}(n,\mathbb{T}^d,\mathsf{Unif},\sigma^q_p,p)$ with $L_q$ distance where each vertex is sampled uniformly from the $d$-dimensional torus and where the connection radius is chosen so that the marginal edge probability is $p$. In addition to results addressing other questions, we make progress on determining when it is possible to distinguish $\mathsf{RGG}(n,\mathbb{T}^d,\mathsf{Unif},\sigma^q_p,p)$ from the Erdős-Rényi graph $\ergraph$. Our strongest result is in the setting $q = \infty$, in which case $\mathsf{RGG}(n,\mathbb{T}^d,\mathsf{Unif},\sigma^q_p,p)$ is the \textsf{AND} of $d$ 1-dimensional random geometric graphs. We derive a formula similar to the \emph{cluster-expansion} from statistical physics, capturing the compatibility of subgraphs from each of the $d$ 1-dimensional copies, and use it to bound the signed expectations of small subgraphs. We show that counting signed 4-cycles is optimal among all low-degree tests, succeeding with high probability if and only if $d = \tilde{o}(np).$ In contrast, the signed triangle test is suboptimal and only succeeds when $d = \tilde{o}((np)^{3/4}).$ Our result stands in sharp contrast to the existing literature on random geometric graphs (mostly focused on $L_2$ geometry) where the signed triangle statistic is optimal.

The graph projection of a hypergraph is a simple graph with the same vertex set and with an edge between each pair of vertices that appear in a hyperedge. We consider the problem of reconstructing a random $d$-uniform hypergraph from its projection. Feasibility of this task depends on $d$ and the density of hyperedges in the random hypergraph. For $d=3$ we precisely determine the threshold, while for $d\ge 4$ we give bounds. All of our feasibility results are obtained by exhibiting an efficient algorithm for reconstructing the original hypergraph, while infeasibility is information-theoretic. Our results also apply to mildly inhomogeneous random hypergrahps, including hypergraph stochastic block models (HSBM). A consequence of our results is an optimal HSBM recovery algorithm, improving on Gaudio and Joshi (2023a).

The random geometric graph RGG(n,Sd−1,p) is formed by sampling n i.i.d. vectors {Vi}i = 1n uniformly on Sd−1 and placing an edge between pairs of vertices i and j for which ⟨ Vi,Vj⟩ ≥ τdp, where τdp is such that the expected density is p. We study the low-degree Fourier coefficients of the distribution RGG(n,Sd−1,p) and its Gaussian analogue. Our main conceptual contribution is a novel two-step strategy for bounding Fourier coefficients which we believe is more widely applicable to studying latent space distributions. First, we localize the dependence among edges to few fragile edges. Second, we partition the space of latent vector configurations (Sd−1)⊗ n based on the set of fragile edges and on each subset of configurations, we define a noise operator acting independently on edges not incident (in an appropriate sense) to fragile edges. We apply the resulting bounds to: 1) Settle the low-degree polynomial complexity of distinguishing spherical and Gaussian random geometric graphs from Erdos-Renyi both in the case of observing a complete set of edges and in the non-adaptively chosen mask M model recently introduced by Mardia, Verchand, and Wein; 2) Exhibit a statistical-computational gap for distinguishing RGG and a planted coloring model in a regime when RGG is distinguishable from ; 3) Reprove known bounds on the second eigenvalue of random geometric graphs.

Planted Dense Subgraph (PDS) problem is a prototypical problem with a computational-statistical gap. It also exhibits an intriguing additional phenomenon: different tasks, such as detection or recovery, appear to have different computational limits. A detection-recovery gap for PDS was substantiated in the form of a precise conjecture given by Chen and Xu (2014) (based on the parameter values for which a convexified MLE succeeds), and then shown to hold for low-degree polynomial algorithms by Schramm and Wein (2022) and for MCMC algorithms for Ben Arous et al. (2020). In this paper we demonstrate that a slight variation of the Planted Clique Hypothesis with secret leakage (introduced in Brennan and Bresler (2020)), implies a detection-recovery gap for PDS. In the same vein, we also obtain a sharp lower bound for refutation, yielding a detection-refutation gap. Our methods build on the framework of Brennan and Bresler (2020) to construct average-case reductions mapping secret leakage Planted Clique to appropriate target problems.

We aim to understand the extent to which the noise distribution in a planted signal-plus-noise problem impacts its computational complexity. To that end, we consider the planted clique and planted dense subgraph problems, but in a different ambient graph. Instead of Erdős-Rényi $G(n, p)$, which has independent edges, we take the ambient graph to be the random graph with triangles (RGT) obtained by adding triangles to $G(n, p)$. We show that the RGT can be efficiently mapped to the corresponding $G(n, p)$, and moreover, that the planted clique (or dense subgraph) is approximately preserved under this mapping. This constitutes the first average-case reduction transforming dependent noise to independent noise. Together with the easier direction of mapping the ambient graph from Erdős-Rényi to RGT, our results yield a strong equivalence between models. In order to prove our results, we develop a new general framework for reasoning about the validity of average-case reductions based on low sensitivity to perturbations.

This paper studies the problem of estimating the means $\pm\theta_{*}\in\mathbb{R}^{d}$ of a symmetric two-component Gaussian mixture $\delta_{*}\cdot N(\theta_{*},I)+(1-\delta_{*})\cdot N(-\theta_{*},I)$, where the weights $\delta_{*}$ and $1-\delta_{*}$ are unequal. Assuming that $\delta_{*}$ is known, we show that the population version of the EM algorithm globally converges if the initial estimate has non-negative inner product with the mean of the larger weight component. This can be achieved by the trivial initialization $\theta_{0}=0$. For the empirical iteration based on $n$ samples, we show that when initialized at $\theta_{0}=0$, the EM algorithm adaptively achieves the minimax error rate $\tilde{O}\Big(\min\Big\{\frac{1}{(1-2\delta_{*})}\sqrt{\frac{d}{n}},\frac{1}{\|\theta_{*}\|}\sqrt{\frac{d}{n}},\left(\frac{d}{n}\right)^{1/4}\Big\}\Big)$ in no more than $O\Big(\frac{1}{\|\theta_{*}\|(1-2\delta_{*})}\Big)$ iterations (with high probability). We also consider the EM iteration for estimating the weight $\delta_{*}$, assuming a fixed mean $\theta$ (which is possibly mismatched to $\theta_{*}$). For the empirical iteration of $n$ samples, we show that the minimax error rate $\tilde{O}\Big(\frac{1}{\|\theta_{*}\|}\sqrt{\frac{d}{n}}\Big)$ is achieved in no more than $O\Big(\frac{1}{\|\theta_{*}\|^{2}}\Big)$ iterations. These results robustify and complement recent results of Wu and Zhou (2019) obtained for the equal weights case $\delta_{*}=1/2$.

Researchers currently use a number of approaches to predict and substantiate information-computation gaps in high-dimensional statistical estimation problems. A prominent approach is to characterize the limits of restricted models of computation, which on the one hand yields strong computational lower bounds for powerful classes of algorithms and on the other hand helps guide the development of efficient algorithms. In this paper, we study two of the most popular restricted computational models, the statistical query framework and low-degree polynomials, in the context of high-dimensional hypothesis testing. Our main result is that under mild conditions on the testing problem, the two classes of algorithms are essentially equivalent in power. As corollaries, we obtain new statistical query lower bounds for sparse PCA, tensor PCA and several variants of the planted clique problem.

We consider the problem of learning a tree-structured Ising model from data, such that subsequent predictions computed using the model are accurate. Con-cretely, we aim to learn a model such that posteriors$p$(Xi| X s) for small sets of variables$S$are accurate. Since its introduction more than 50 years ago, the Chow-Liu algorithm, which efficiently computes the maximum likelihood tree, has been the benchmark algorithm for learning tree-structured graphical models. A bound on the sample complexity of the Chow-Liu algorithm with respect to the prediction-centric local total variation loss was shown in [7]. While those results demonstrated that it is possible to learn a useful model even when recovering the true underlying graph is impossible, their bound depends on the maximum strength of interactions and thus does not achieve the information-theoretic optimum. In this paper, we introduce a new algorithm that carefully combines elements of the Chow-Liu algorithm with tree metric reconstruction methods to efficiently and optimally learn tree Ising models under a prediction-centric loss. Our algorithm is robust to model misspecification and adver-sarial corruptions. In contrast, we show that the celebrated Chow- Liu algorithm can be arbitrarily suboptimal.

Let$\Phi$be a uniformly random$k$-SAT formula with$n$variables and$m$clauses. We study the algorithmic task of finding a satisfying assignment of$\Phi$. It is known that satisfying assignments exist with high probability up to clause density$m/n=2^{k} \log 2-\frac{1}{2}(\log 2+1)+o_{k}(1)$, while the best polynomial-time algorithm known, the Fix algorithm of Coja-Oghlan [1], finds a satisfying assignment at the much lower clause density$(1-o_{k}(1))2^{k}\log k/k$. This prompts the question: is it possible to efficiently find a satisfying assignment at higher clause densities? We prove that the class of low degree polynomial algorithms cannot find a satisfying assignment at clause density$(1+o_{k}(1))\kappa^{\ast}2^{k}\log k/k$for a universal constant$\kappa^{\ast}\approx 4.911$. This class encompasses Fix, message passing algorithms including Belief and Survey Propagation guided decimation (with bounded or mildly growing number of rounds), and local algorithms on the factor graph. This is the first hardness result for any class of algorithms at clause density within a constant factor of that achieved by Fix. Our proof establishes and leverages a new many-way overlap gap property tailored to random$k$-SAT.

This paper identifies a structural property of data distributions that enables deep neural networks to learn hierarchically. We define the ``staircase'' property for functions over the Boolean hypercube, which posits that high-order Fourier coefficients are reachable from lower-order Fourier coefficients along increasing chains. We prove that functions satisfying this property can be learned in polynomial time using layerwise stochastic coordinate descent on regular neural networks -- a class of network architectures and initializations that have homogeneity properties. Our analysis shows that for such staircase functions and neural networks, the gradient-based algorithm learns high-level features by greedily combining lower-level features along the depth of the network. We further back our theoretical results with experiments showing that staircase functions are learnable by more standard ResNet architectures with stochastic gradient descent. Both the theoretical and experimental results support the fact that the staircase property has a role to play in understanding the capabilities of gradient-based learning on regular networks, in contrast to general polynomial-size networks that can emulate any Statistical Query or PAC algorithm, as recently shown.

Most information storage devices write data by modifying the local state of matter, in the hope that sub-atomic local interactions stabilize the state for sufficiently long time, thereby allowing later recovery. Motivated to explore how temporal evolution of physical states in magnetic storage media affects their capacity, this work initiates the study of information retention in locally-interacting particle systems. The system dynamics follow the stochastic Ising model (SIM) over a 2-dimensional √(n) × √(n) grid. The initial spin configuration X0serves as the user-controlled input. The output configuration Xt is produced by running t steps of Glauber dynamics. Our main goal is to evaluate the information capacity In(t) := maxpx0 I(X0; Xt) when time t scales with the system's size n. While the positive (but low) temperature regime is our main interest, we start by exploring the simpler zero-temperature dynamics. We first show that at zero temperature, order of √(n) bits can be stored in the system indefinitely by coding over stable, striped configurations. While √(n) is order optimal for infinite time, backing off to tn(t) are achievable. First, via linear coding arguments imply we show that In(t) = Θ(n) for t = O(n). To go beyond the linear scale, we develop a droplet-based achievability scheme that reliably stores Ω (n/ log n) for t = O(n log n) time (log n can be replaced with any o(n) function). Moving to the positive but low temperature regime, two main results are provided. First, we show that an initial configuration drawn from the Gibbs measure cannot retain more than a single bit for t ≥ exp(Cβn1/4+c) time. On the other hand, when scaling time with the inverse temperature β, the stripe-based coding scheme (that stores for infinite time at zero temperature) is shown to retain its bits for ecβ.

Inference problems with conjectured statistical-computational gaps are ubiquitous throughout modern statistics, computer science, statistical physics and discrete probability. While there has been success evidencing these gaps from the failure of restricted classes of algorithms, progress towards a more traditional reduction-based approach to computational complexity in statistical inference has been limited. These average-case problems are each tied to a different natural distribution, high-dimensional structure and conjecturally hard parameter regime, leaving reductions among them technically challenging. Despite a flurry of recent success in developing such techniques, existing reductions have largely been limited to inference problems with similar structure – primarily mapping among problems representable as a sparse submatrix signal plus a noise matrix, which is similar to the common starting hardness assumption of planted clique ($\textsc{pc}$). The insight in this work is that a slight generalization of the planted clique conjecture – secret leakage planted clique ($\textsc{pc}_\rho$), wherein a small amount of information about the hidden clique is revealed – gives rise to a variety of new average-case reduction techniques, yielding a web of reductions relating statistical problems with very different structure. Based on generalizations of the planted clique conjecture to specific forms of $\textsc{pc}_\rho$, we deduce tight statistical-computational tradeoffs for a diverse range of problems including robust sparse mean estimation, mixtures of sparse linear regressions, robust sparse linear regression, tensor PCA, variants of dense $k$-block stochastic block models, negatively correlated sparse PCA, semirandom planted dense subgraph, detection in hidden partition models and a universality principle for learning sparse mixtures. This gives the first reduction-based evidence for a number of conjectured statistical-computational gaps. We introduce a number of new average-case reduction techniques that also reveal novel connections to combinatorial designs based on the incidence geometry of $\mathbb{F}_r^t$ and to random matrix theory. In particular, we show a convergence result between Wishart and inverse Wishart matrices that may be of independent interest. The specific hardness conjectures for $\textsc{pc}_\rho$ implying our statistical-computational gaps all are in correspondence with natural graph problems such as $k$-partite, bipartite and hypergraph variants of $\textsc{pc}$. Hardness in a $k$-partite hypergraph variant of $\textsc{pc}$ is the strongest of these conjectures and sufficient to establish all of our computational lower bounds. We also give evidence for our $\textsc{pc}_\rho$ hardness conjectures from the failure of low-degree polynomials and statistical query algorithms. Our work raises a number of open problems and suggests that previous technical obstacles to average-case reductions may have arisen because planted clique is not the right starting point. An expanded set of hardness assumptions, such as $\textsc{pc}_\rho$, may be a key first step towards a more complete theory of reductions among statistical problems.

We develop a \emph{corrective mechanism} for neural network approximation: the total available non-linear units are divided into multiple groups and the first group approximates the function under consideration, the second approximates the error in approximation produced by the first group and corrects it, the third group approximates the error produced by the first and second groups together and so on. This technique yields several new representation and learning results for neural networks: 1. Two-layer neural networks in the random features regime (RF) can memorize arbitrary labels for $n$ arbitrary points in $\mathbb{R}^d$ with $\tilde{O}(\tfrac{n}{\theta^4})$ ReLUs, where $\theta$ is the minimum distance between two different points. This bound can be shown to be optimal in $n$ up to logarithmic factors. 2. Two-layer neural networks with ReLUs and smoothed ReLUs can represent functions with an error of at most $\epsilon$ with $O(C(a,d)\epsilon^{-1/(a+1)})$ units for $a \in \mathbb{N}\cup\{0\}$ when the function has $\Theta(ad)$ bounded derivatives. In certain cases $d$ can be replaced with effective dimension $q \ll d$. Our results indicate that neural networks with only a single nonlinear layer are surprisingly powerful with regards to representation, and show that in contrast to what is suggested in recent work, depth is not needed in order to represent highly smooth functions. 3. Gradient Descent on the recombination weights of a two-layer random features network with ReLUs and smoothed ReLUs can learn low degree polynomials up to squared error $\epsilon$ with $\mathrm{subpoly}(1/\epsilon)$ units. Even though deep networks can approximate these polynomials with $\mathrm{polylog}(1/\epsilon)$ units, existing \emph{learning} bounds for this problem require $\mathrm{poly}(1/\epsilon)$ units. To the best of our knowledge, our results give the first sub-polynomial learning guarantees for this problem.

Graphical models are often used to facilitate efficient computation of posteriors in order to make predictions. With this objective in mind, we consider the problem of estimating the parameters of a graphical model with known structure from samples such that posteriors computed using the model are accurate. Focusing on tree-structured binary Markov random fields, our main result is a sharp characterization of the dependence on number of samples needed for all pairwise marginals (and hence posteriors of one variable given another) to be accurate: n = Θ(η-2log p) samples are necessary and sufficient to estimate model parameters such that all marginals of arbitrary order k are accurate to within √kη. The result implies that prediction error is bounded uniformly, with no dependence on the strength of interactions. We will also show that these guarantees are achievable using moment matching techniques.

Restricted Boltzmann Machines (RBMs) are a common family of undirected graphical models with latent variables. An RBM is described by a bipartite graph, with all observed variables in one layer and all latent variables in the other. We consider the task of learning an RBM given samples generated according to it. The best algorithms for this task currently have time complexity $\tilde{O}(n^2)$ for ferromagnetic RBMs (i.e., with attractive potentials) but $\tilde{O}(n^d)$ for general RBMs, where $n$ is the number of observed variables and $d$ is the maximum degree of a latent variable. Let the \textit{MRF neighborhood} of an observed variable be its neighborhood in the Markov Random Field of the marginal distribution of the observed variables. In this paper, we give an algorithm for learning general RBMs with time complexity $\tilde{O}(n^{2^s+1})$, where $s$ is the maximum number of latent variables connected to the MRF neighborhood of an observed variable. This is an improvement when $s < \log_2 (d-1)$, which corresponds to RBMs with sparse latent variables. Furthermore, we give a version of this learning algorithm that recovers a model with small prediction error and whose sample complexity is independent of the minimum potential in the Markov Random Field of the observed variables. This is of interest because the sample complexity of current algorithms scales with the inverse of the minimum potential, which cannot be controlled in terms of natural properties of the RBM.

We prove dimension free representation results for neural networks with D ReLU layers under square loss for a class of functions G_D defined in the paper. These results capture the precise benefits of depth in the following sense: 1. The rates for representing the class of functions G_D via D ReLU layers is sharp up to constants, as shown by matching lower bounds. 2.G_D is a proper subset of G_{D+1} and as D grows the class of functions G_D grow to contain less smooth functions. 3. If D^{\prime} < D, then the approximation rate achieved by depth D^{\prime} networks is strictly worse than that achieved by depth D networks for the class G_D. This constitutes a fine-grained characterization of the representation power of feedforward networks of arbitrary depth D and number of neurons N, in contrast to existing representation results which either require D growing quickly with N or assume that the function being represented is highly smooth. In the latter case similar rates can be obtained with a single nonlinear layer. Our results confirm the prevailing hypothesis that deeper networks are better at representing less smooth functions, and indeed, the main technical novelty is to fully exploit the fact that deep networks can produce highly oscillatory functions with few activation functions.

We study the problem of least squares linear regression where the datapoints are dependent and are sampled from a Markov chain. We establish sharp information theoretic minimax lower bounds for this problem in terms of $\tmix$, the mixing time of the underlying Markov chain, under different noise settings. Our results establish that in general, optimization with Markovian data is strictly harder than optimization with independent data and a trivial algorithm (SGD-DD) that works with only one in every $\tmix$ samples, which are approximately independent, is minimax optimal. In fact, it is strictly better than the popular Stochastic Gradient Descent (SGD) method with constant step-size which is otherwise minimax optimal in the regression with independent data setting. Beyond a worst case analysis, we investigate whether structured datasets seen in practice such as Gaussian auto-regressive dynamics can admit more efficient optimization schemes. Surprisingly, even in this specific and natural setting, Stochastic Gradient Descent (SGD) with constant step-size is still no better than SGD-DD. Instead, we propose an algorithm based on experience replay--a popular reinforcement learning technique--that achieves a significantly better error rate. Our improved rate serves as one of the first results where an algorithm outperforms SGD-DD on an interesting Markov chain and also provides one of the first theoretical analyses to support the use of experience replay in practice.

In the past decade, sparse principal component analysis has emerged as an archetypal problem for illustrating statistical-computational tradeoffs. This trend has largely been driven by a line of research aiming to characterize the average-case complexity of sparse PCA through reductions from the planted clique ($\textsc{pc}$) conjecture. All previous reductions either fail to show tight computational lower bounds matching existing algorithms or show lower bounds for formulations of sparse PCA other than its canonical generative model, the spiked covariance model. Also, these lower bounds all quickly degrade given weak forms of the $\textsc{pc}$ conjecture. We give a reduction from $\textsc{pc}$ that yields the first full characterization of the computational barrier in the spiked covariance model, providing tight lower bounds at all sparsities $k$. We also show the surprising result that even a mild improvement in the signal strength needed by the best known polynomial-time sparse PCA algorithms would imply that the hardness threshold for $\textsc{pc}$ is $\text{polylog}(N)$, rather than on the order $N^{1/2}$ as is widely conjectured. This is the first instance of a suboptimal hardness assumption implying optimal lower bounds for another problem in unsupervised learning.

In the general submatrix detection problem, the task is to detect the presence of a small $k \times k$ submatrix with entries sampled from a distribution $\mathcal{P}$ in an $n \times n$ matrix of samples from $\mathcal{Q}$. This formulation includes a number of well-studied problems, such as biclustering when $\mathcal{P}$ and $\mathcal{Q}$ are Gaussians and the planted dense subgraph formulation of community detection when the submatrix is a principal minor and $\mathcal{P}$ and $\mathcal{Q}$ are Bernoulli random variables. These problems all seem to exhibit a universal phenomenon: there is a statistical-computational gap depending on $\mathcal{P}$ and $\mathcal{Q}$ between the minimum $k$ at which this task can be solved and the minimum $k$ at which it can be solved in polynomial time. Our main result is to tightly characterize this computational barrier as a tradeoff between $k$ and the KL divergences between $\mathcal{P}$ and $\mathcal{Q}$ through average-case reductions from the planted clique conjecture. These computational lower bounds hold given mild assumptions on $\mathcal{P}$ and $\mathcal{Q}$ arising naturally from classical binary hypothesis testing. Our results recover and generalize the planted clique lower bounds for Gaussian biclustering in Ma and Wu (2015) and Brennan et al. (2018) and for the sparse and general regimes of planted dense subgraph in Hajek et al. (2015) and Brennan et al. (2018). This yields the first universality principle for computational lower bounds obtained through average-case reductions.

The complexity of clique problems on Erdos-Renyi random graphs has become a central topic in average-case complexity. Algorithmic phase transitions in these problems have been shown to have broad connections ranging from mixing of Markov chains and statistical physics to information-computation gaps in high-dimensional statistics. We consider the problem of counting k-cliques in s-uniform Erdos-Renyi hypergraphs G(n, c, s) with edge density c and show that its fine-grained average-case complexity can be based on its worstcase complexity. We prove the following: 1) Dense Erdos-Renyi hypergraphs: Counting k-cliques on G(n, c, s) with k and c constant matches its worst-case complexity up to a polylog(n) factor. Assuming ETH, it takes nΩ(k)time to count k-cliques in G(n, c, s) if k and c are constant. 2)Sparse Erdos-Renyi hypergraphs: When c = Θ(n-α), for each fixed α our reduction yields different average-case phase diagrams depicting a tradeoff between runtime and k. Assuming the best known worst-case algorithms are optimal, in the graph case of s = 2, we establish that the exponent in n of the optimal running time for k-clique counting in G(n, c, s) is ωk/3 - Cα(k/2) + Ok,α(1), where ω/9 ≤ C ≤ 1 and w is the matrix multiplication constant. In the hypergraph case of s ≥ 3, we show a lower bound at the exponent of k-α(k/s)+Ok,α(1) which surprisingly is s tight against algorithmic achievability exactly for the set of c above the Erdos-Renyi k-clique percolation threshold. Our reduction yields the first known average-case hardness result on Erdos-Renyi hypergraphs based on a worst-case hardness assumption. We also analyze several natural algorithms for counting k-cliques in G(n, c, s) that establish our upper bounds in the sparse case c = Θ(n-α).

Motivated by questions of data stabilization in emerging magnetic storage technologies, we study the retention of information in interacting particle systems. The interactions between particles adhere to the stochastic Ising model (SIM) on the two-dimensional (2D) √n × √n grid. The measure of interest is the information capacity In(t) =△ maxpX0I(X0; Xt), where the initial spin configuration X0is a user-controlled input and the output configuration Xtis produced by running t steps of Glauber dynamics. After the results on the zero-temperature regime reported last year, this work focuses on the positive but low temperature regime. We first show that storing more than a single bit for an exponential time is impossible when the initial configuration is drawn from the equilibrium distribution. Specifically, if X0is drawn according to the Gibbs measure, then I(X0; Xt) ≤ 1 + o(1) for t ≥ exp (cn1/4+ε). On the other hand, when scaling time with β, we propose a stripe-based coding scheme that stores order of √n bits for exp(β) time. Key to the analysis of the scheme is a new result on the survival time of a single plus-labeled stripe in a sea of minuses. Together, the 1-bit upper bound and the striped-based storage scheme constitute initial steps towards a general analysis of In(t) for β > 0.

We consider the problem of experimental design for learning causal graphs that have a tree structure. We propose an adaptive framework that determines the next intervention based on a Bayesian prior updated with the outcomes of previous experiments, focusing on the setting where observational data is cheap (assumed infinite) and interventional data is expensive. While information greedy approaches are popular in active learning, we show that in this setting they can be exponentially suboptimal (in the number of interventions required), and instead propose an algorithm that exploits graph structure in the form of a centrality measure. If infinite interventional data is available, we show that the algorithm requires a number of interventions less than or equal to a factor of 2 times the minimum achievable number. We show that the algorithm and the associated theory can be adapted to the setting where each performed intervention yields finitely many samples. Several extensions are also presented, to the case where a specified set of nodes cannot be intervened on, to the case where $K$ interventions are scheduled at once, and to the fully adaptive case where each experiment yields only one sample. In the case of finite interventional data, through simulated experiments we show that our algorithms outperform different adaptive baseline algorithms.

Graphical models are a rich language for describing high-dimensional distributions in terms of their dependence structure. While there are algorithms with provable guarantees for learning undirected graphical models in a variety of settings, there has been much less progress in the important scenario when there are latent variables. Here we study Restricted Boltzmann Machines (or RBMs), which are a popular model with wide-ranging applications in dimensionality reduction, collaborative filtering, topic modeling, feature extraction and deep learning.

Recently, research in unsupervised learning has gravitated towards exploring statistical-computational gaps induced by sparsity. A line of work initiated in Berthet and Rigollet (2013) has aimed to explain these gaps through reductions to conjecturally hard problems from complexity theory. However, the delicate nature of average-case reductions has limited the development of techniques and often led to weaker hardness results that only apply to algorithms robust to different noise distributions or that do not need to know the parameters of the problem. We introduce several new techniques to give a web of average-case reductions showing strong computational lower bounds based on the planted clique conjecture. Our new lower bounds include: Planted Independent Set: We show tight lower bounds for detecting a planted independent set of size $k$ in a sparse Erdős-Rényi graph of size $n$ with edge density $\tilde{\Theta}(n^{-\alpha})$. Planted Dense Subgraph: If $p > q$ are the edge densities inside and outside of the community, we show the first lower bounds for the general regime $q = \tilde{\Theta}(n^{-\alpha})$ and $p - q = \tilde{\Theta}(n^{-\gamma})$ where $\gamma \ge \alpha$, matching the lower bounds predicted in Chen and Xu (2016). Our lower bounds apply to a deterministic community size $k$, resolving a question raised in Hajek et al. (2015). Biclustering: We show strong lower bounds for Gaussian biclustering as a simple hypothesis testing problem to detect a uniformly at random planted flat $k \times k$ submatrix. Sparse Rank-1 Submatrix: We show that detection in the sparse spiked Wigner model is often harder than biclustering, and are able to obtain two different tight lower bounds for these problems with different reductions from planted clique. Sparse PCA: We give a reduction between rank-1 submatrix and sparse PCA to obtain tight lower bounds in the less sparse regime $k \gg \sqrt{n}$, when the spectral algorithm is optimal over the SDP. We give an alternate reduction recovering the lower bounds of Berthet and Rigollet (2013) and Gao et al. (2017) in the simple hypothesis testing variant of sparse PCA. We also observe a subtlety in the complexity of sparse PCA that arises when the planted vector is biased. Subgraph Stochastic Block Model: We introduce a model where two small communities are planted in an Erdős-Rényi graph of the same average edge density and give tight lower bounds yielding different hard regimes than planted dense subgraph. Our results demonstrate that, despite the delicate nature of average-case reductions, using natural problems as intermediates can often be beneficial, as is the case in worst-case complexity. Our main technical contribution is to introduce a set of techniques for average-case reductions that: (1) maintain the level of signal in an instance of a problem; (2) alter its planted structure; and (3) map two initial high-dimensional distributions simultaneously to two target distributions approximately under total variation. We also give algorithms matching our lower bounds and identify the information-theoretic limits of the models we consider.

We study the problem of testing, using only a single sample, between mean field distribu- tions (like Curie-Weiss, Erdős-Rényi) and structured Gibbs distributions (like Ising model on sparse graphs and Exponential Random Graphs). Our goal is to test without know- ing the parameter values of the underlying models: only the structure of dependencies is known. We develop a new approach that applies to both the Ising and Exponential Random Graph settings based on a general and natural statistical test. The test can dis- tinguish the hypotheses with high probability above a certain threshold in the (inverse) temperature parameter, and is optimal in that below the threshold no test can distinguish the hypotheses. The thresholds do not correspond to the presence of long-range order in the models. By aggregating information at a global scale, our test works even at very high temperatures. The proofs are based on distributional approximation and sharp concentration of quadratic forms, when restricted to Hamming spheres. The restriction to Hamming spheres is necessary, since otherwise any scalar statistic is useless without explicit knowledge of the temperature parameter. At the same time, this restriction changes the behavior of the functions under consideration, making it hard to directly apply standard methods (i.e., Stein’s method) for concentration of weakly dependent variables. Instead, we carry out an additional tensorization argument using a Markov chain that respects the symmetry of the Hamming sphere.

Most information systems store data by modifying the local state of the matter, in the hope that atomic (or subatomic) local interactions would stabilize the state for sufficiently long time, thereby allowing later recovery. In this work we initiate the study of information retention properties of locally-interacting systems. We model the time-dependent interactions between the different particles via the stochastic Ising model (SIM). The initial spin configuration X0serves as the user-controlled input. The output configuration Xtis produced by running t steps of the Glauber chain. Our main goal is to evaluate the information capacity In(t) =̂ maxpX0I(X0; Xt) when the time t scales with the size or the system n according to various rates. For the zero-temperature SIM on the two-dimensional √n×√n grid and free boundary condition, it is easy to show that In(t)=Θ(n) as long as t=O(n). In addition, we show that order of √n bits can be stored for infinite time (and even with zero error). The √n achievability is optimal when t→∞ and n is fixed. Our main result is in extending achievability to super-linear (in n) times via a coding scheme that reliably stores more than √n bits (in orders of magnitude). The analysis of the scheme decomposes the system into Ω(√n) independent Z-channels whose crossover probability is found via the (recently rigorously established) Lifshitz law of phase boundary movement. Finally, two order optimal characterizations of In(t), for all t, are given for the grid dynamics with an external magnetic field and for the dynamics on the Honeycomb lattice. It shown that In(t)=Θ(n) in both cases, suggesting their superiority over the grid without an external field for storage purposes.

Sparse Principal Component Analysis (SPCA) and Sparse Linear Regression (SLR) have a wide range of applications and have attracted a tremendous amount of attention in the last two decades as canonical examples of statistical problems in high dimension. A variety of algorithms have been proposed for both SPCA and SLR, but an explicit connection between the two had not been made. We show how to efficiently transform a black-box solver for SLR into an algorithm for SPCA: assuming the SLR solver satisfies prediction error guarantees achieved by existing efficient algorithms such as those based on the Lasso, the SPCA algorithm derived from it achieves near state of the art guarantees for testing and for support recovery for the single spiked covariance model as obtained by the current best polynomial-time algorithms. Our reduction not only highlights the inherent similarity between the two problems, but also, from a practical standpoint, allows one to obtain a collection of algorithms for SPCA directly from known algorithms for SLR. We provide experimental results on simulated data comparing our proposed framework to other algorithms for SPCA.

There is much empirical evidence that item-item collaborative filtering works well in practice. Motivated to understand this, we provide a framework to design and analyze various recommendation algorithms. The setup amounts to online binary matrix completion, where at each time a random user requests a recommendation and the algorithm chooses an entry to reveal in the user's row. The goal is to minimize regret, or equivalently to maximize the number of +1 entries revealed at any time. We analyze an item-item collaborative filtering algorithm that can achieve fundamentally better performance compared to user-user collaborative filtering. The algorithm achieves good "cold-start" performance (appropriately defined) by quickly making good recommendations to new users about whom there is little information.

graph underlying an Ising model from i.i.d. samples. Over the last fifteen years this problem has been of significant interest in the statistics, machine learning, and statistical physics communities, and much of the effort has been directed towards finding algorithms with low computational cost for various restricted classes of models. Nevertheless, for learning Ising models on general graphs with p nodes of degree at most d, it is not known whether or not it is possible to improve upon the pd computation needed to exhaustively search over all possible neighborhoods for each node.

We study vector space interference alignment for the multiple-input multiple-output interference channel with no time or frequency diversity, and no symbol extensions. We prove both necessary and sufficient conditions for alignment. In particular, we characterize the feasibility of alignment for the symmetric three-user channel where all users transmit along d dimensions, all transmitters have M antennas and all receivers have N antennas, as well as feasibility of alignment for the fully symmetric (M = N) channel with an arbitrary number of users. An implication of our results is that the total degrees of freedom available in a K-user interference channel, using only spatial diversity from the multiple antennas, is at most 2. This is in sharp contrast to the K/2 degrees of freedom shown to be possible by Cadambe and Jafar with arbitrarily large time or frequency diversity. Moving beyond the question of feasibility, we additionally discuss computation of the number of solutions using Schubert calculus in cases where there are a finite number of solutions.

Markov random fields are used to model high dimensional distributions in a number of applied areas. Much recent interest has been devoted to the reconstruction of the dependency structure from independent samples from the Markov random fields. We analyze a simple algorithm for reconstructing the underlying graph defining a Markov random field on $n$ nodes and maximum degree $d$ given observations. We show that under mild nondegeneracy conditions it reconstructs the generating graph with high probability using $\Theta(d \epsilon^{-2}\delta^{-4} \log n)$ samples, where $\epsilon,\delta$ depend on the local interactions. For most local interactions $\epsilon,\delta$ are of order $\exp(-O(d))$. Our results are optimal as a function of $n$ up to a multiplicative constant depending on $d$ and the strength of the local interactions. Our results seem to be the first results for general models that guarantee that the generating model is reconstructed. Furthermore, we provide explicit $O(n^{d+2} \epsilon^{-2}\delta^{-4} \log n)$ running-time bound. In cases where the measure on the graph has correlation decay, the running time is $O(n^2 \log n)$ for all fixed $d$. We also discuss the effect of observing noisy samples and show that as long as the noise level is low, our algorithm is effective. On the other hand, we construct an example where large noise implies nonidentifiability even for generic noise and interactions. Finally, we briefly show that in some simple cases, models with hidden nodes can also be recovered.

DNA sequencing is the basic workhorse of modern day biology and medicine. Shotgun sequencing is the dominant technique used: many randomly located short fragments called reads are extracted from the DNA sequence, and these reads are assembled to reconstruct the original sequence. A basic question is: given a sequencing technology and the statistics of the DNA sequence, what is the minimum number of reads required for reliable reconstruction? This number provides a fundamental limit to the performance of any assembly algorithm. For a simple statistical model of the DNA sequence and the read process, we show that the answer admits a critical phenomenon in the asymptotic limit of long DNA sequences: if the read length is below a threshold, reconstruction is impossible no matter how many reads are observed, and if the read length is above the threshold, having enough reads to cover the DNA sequence is sufficient to reconstruct. The threshold is computed in terms of the Renyi entropy rate of the DNA sequence. We also study the impact of noise in the read process on the performance.

DNA sequencing is the basic workhorse of modern day biology and medicine. Shotgun sequencing is the dominant technique used: many randomly located short fragments called reads are extracted from the DNA sequence, and these reads are assembled to reconstruct the original sequence. By drawing an analogy between the DNA sequencing problem and the classic communication problem, we define an information theoretic notion of sequencing capacity. This is the maximum number of DNA base pairs that can be resolved reliably per read, and provides a fundamental limit to the performance that can be achieved by any assembly algorithm. We compute the sequencing capacity explicitly for a simple statistical model of the DNA sequence and the read process.

Determining the feasibility conditions for vector space interference alignment in the K-user MIMO interference channel with constant channel coefficients has attracted much recent attention yet remains unsolved. The main result of this paper is restricted to the symmetric square case where all transmitters and receivers have N antennas, and each user desires d transmit dimensions. We prove that alignment is possible if and only if the number of antennas satisfies N ≥ d(K + 1)/2. We also show a necessary condition for feasibility of alignment with arbitrary system parameters. An algebraic geometry approach is central to the results.

Recently, Etkin, Tse, and Wang found the capacity region of the two-user Gaussian interference channel to within 1 bit/s/Hz. A natural goal is to apply this approach to the Gaussian interference channel with an arbitrary number of users. We make progress towards this goal by finding the capacity region of the many-to-one and one-to-many Gaussian interference channels to within a constant number of bits. The result makes use of a deterministic model to provide insight into the Gaussian channel. The deterministic model makes explicit the dimension of signal level. A central theme emerges: the use of lattice codes for alignment of interfering signals on the signal level.

A variety of random graph models have been developed in recent years to study a range of problems on networks, driven by the wide availability of data from many social, telecommunication, biochemical and other networks. A key model, extensively used in the sociology literature, is the exponential random graph model. This model seeks to incorporate in random graphs the notion of reciprocity, that is, the larger than expected number of triangles and other small subgraphs. Sampling from these distributions is crucial for parameter estimation hypothesis testing, and more generally for understanding basic features of the network model itself. In practice sampling is typically carried out using Markov chain Monte Carlo, in particular either the Glauber dynamics or the Metropolis-Hasting procedure.In this paper we characterize the high and low temperature regimes of the exponential random graph model. We establish that in the high temperature regime the mixing time of the Glauber dynamics is Theta(n2log n), where n is the number of vertices in the graph; in contrast, we show that in the low temperature regime the mixing is exponentially slow for any local Markov chain. Our results, moreover, give a rigorous basis for criticisms made of such models. In the high temperature regime, where sampling with MCMC is possible, we show that any finite collection of edges are asymptotically independent; thus, the model does not possess the desired reciprocity property, and is not appreciably different from the Erdos-Renyi random graph.

Bit-error probability and mutual information rate have both been used as performance criteria for space-time codes for wireless communication. We use mutual information as the performance criterion because it determines the possible rate of communication when using an outer code. In this context, linear dispersion codes, first proposed by Hassibi and Hochwald, are appealing because of the high mutual information they provide, as well as their simplicity. Because complexity increases with the number of symbols, it may be sensible in some settings to fix the number of symbols sent per data bit. In the dissertation of Y. Jiang, it was conjectured that among linear dispersion codes with independent, binary symbols, orthogonal space-time codes are optimal in the following sense: they maximize mutual information subject to an average power constraint on each symbol. We prove the conjecture for a fixed number of real symbols with arbitrary distributions