PaperlayerView exact revision on arXiv

Source-linked AI summary

Provable Bounds for Learning Some Deep Representations

Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma

arXiv:1310.6343v1cs.LGcs.AIstat.ML

TL;DR

The paper asks whether a useful class of generative deep networks can be learned despite the hardness of general neural-network learning. It introduces sparse random multilayer threshold networks and learns them layerwise from firing correlations using global graph reconstruction. The resulting algorithms learn almost all networks in the class in polynomial time, while revealing denoising-autoencoder structure and limits on shallow representations.

  • Problem

    General neural-network learning remains hard even on random inputs, while recovering a ground-truth neural network from its output distribution lacks provable methods.

  • Method

    The paper learns sparse random multilayer generative networks layerwise by using feature correlations to reconstruct each hidden bipartite graph globally.

  • Results

    The algorithm learns almost all networks in the class in polynomial time, with statistically indistinguishable generative behavior and exact recovery for discrete weights.

  • Takeaways & Limitations

    Random deep networks can support provable layerwise recovery while exhibiting denoising-autoencoder structure and representational behavior unavailable to single-layer networks.

  • Takeaways & Limitations

    The guarantees rely on sparse hidden layers and random-like edge structure, and formal depth-based representation limits remain difficult beyond shallow cases.

Abstract

from arXiv · show

We give algorithms with provable guarantees that learn a class of deep nets in the generative model view popularized by Hinton and others. Our generative model is an $n$ node multilayer neural net that has degree at most $n^γ$ for some $γ<1$ and each edge has a random edge weight in $[-1,1]$. Our algorithm learns {\em almost all} networks in this class with polynomial running time. The sample complexity is quadratic or cubic depending upon the details of the model. The algorithm uses layerwise learning. It is based upon a novel idea of observing correlations among features and using these to infer the underlying edge structure via a global graph recovery procedure. The analysis of the algorithm reveals interesting structure of neural networks with random edge weights.

1 Introduction

The paper studies whether generative, reversible deep networks can be learned despite the apparent hardness of neural-network learning. It introduces a random sparse-network class whose structure supports provable learning and several autoencoder-like properties.

  • Motivation: Learning neural nets is difficult because multiple hidden layers use nonlinear operations, with hardness results even for random inputs and shallow threshold networks.
  • Generative viewpoint: Generative deep-net models enable layerwise and unsupervised learning by reversing the network to model the observed data distribution.
  • Model assumptions: The paper assumes sparse random connectivity and random edge weights, defining a tractable ground-truth class while retaining multilayer nonlinear computation.
  • Results: The algorithm learns almost all networks in this class efficiently, producing statistically indistinguishable generative behavior and exactly recovering discrete-weight networks.
  • Structural properties: Each adjacent-layer pair is a denoising autoencoder, reverse computation is stable to noise and dropout, and two-layer distributions cannot be represented by one layer.
  • Contribution and scope: The work extends compressed-sensing intuition to learning unknown edge structure and performs layerwise learning, while deeper representation limitations remain difficult to prove.

2 Definitions and Results

The paper formalizes sparse random multilayer threshold networks and gives polynomial-time learners based on correlations and global bipartite-graph reconstruction. Its guarantees depend on sparsity, layer density, and the weight model.

  • Definitions: The ground-truth model has ℓ binary hidden layers, an observed bottom layer, degree at most d = n^γ, random edge weights, and threshold-0 computations.
  • Definitions: The top layer is initialized as a uniformly chosen sparse 0/1 vector, then successive layers are computed by thresholding weighted sums.
  • Model variants: The model permits differing layer sizes and threshold choices, but higher thresholds make the calculations harder and the learner less efficient.
  • Model variants: The observed layer can be made dense and real-valued by removing its threshold gates, avoiding the requirement that the final observed representation be sparse.
  • Guarantees: For d = n^γ with 0 < γ ≤ 0.2, the discrete-weight model uses O(log n/ρℓ^2) samples and O(n^2ℓ) time, while the real-weight model has polynomial-time learning and O(n^3ℓ^2 log n/η^2) samples.
  • Algorithmic ideas: The learner estimates pairwise or 3-wise firing correlations, then globally reconstructs the bipartite graph from distance-2 node relationships.
  • Scope: Practical use remains uncertain because the proof requires sparse hidden layers and random-like edge structure, with empirical evaluation left for future work.

3 Each layer is a Denoising Auto-encoder

The paper proves that adjacent layers of its random network form denoising autoencoders with tied weights. The encoder reverses the decoder using adjusted thresholds and succeeds under sparse, random-graph conditions.

  • Definition: A denoising autoencoder reconstructs hidden variables from corrupted decoded outputs, and weight tying requires W′ = W^T.
  • Main result: Every successive layer pair satisfies the denoising-autoencoder definition with weight tying with high probability in both network models.
  • Single-layer guarantee: For a single layer, the result holds when ρd < 0.1, even if every output bit is independently flipped with probability 0.1.
  • Random-graph condition: For fixed sparse sets, the required unique-neighbor property holds with high probability over the random graph, though not uniformly over all sparse sets.
  • Reverse computation: The same bipartite graph serves as decoder and encoder after changing thresholds, with the encoder applying a transposed-weight computation.
  • Proof mechanism: The proof relies on the strong unique-neighbor property, which lets active higher-layer nodes retain informative lower-layer neighbors despite interference.

4 Learning a single layer network

The single-layer learner recovers hidden structure from pairwise or 3-wise correlations, then uses graph recovery and partial encoding to reconstruct the network. Under sparsity and random-graph conditions, it extends to real-valued weights and achieves polynomial-time recovery guarantees.

  • Layerwise procedure: The algorithm learns a single layer by constructing correlations, recovering positive edges, encoding hidden variables, and then recovering negative edges.It operates on samples of observed outputs and uses the recovered positive-edge structure to obtain hidden assignments.
  • Correlation recovery: Pairwise correlations distinguish related node pairs from unrelated pairs when ρ < 0.1/d^2, enabling recovery with O(log n/ρ^2) samples.Related pairs are simultaneously active with probability at least 0.9ρ, whereas unrelated pairs have probability at most (ρd)^2.
  • Hidden-layer encoding: The partial encoder recovers the hidden vector from positive edges when the support satisfies the 11/12-strong unique neighbor property, using threshold θ = 0.3d.Unique positive neighbors provide a margin separating active from inactive hidden nodes.
  • Correlation recovery: 3-wise correlations relax the sparsity requirement to ρ < 0.1/d^3/2 and allow positive-edge recovery through a 3-uniform hypergraph.Related triples occur jointly with probability at least 0.9ρ, while unrelated triples occur with probability roughly at most (ρd)^3.
  • Guarantee: For ±1 weights, the single-layer learner runs in O(n(d^3 + n)) time and uses O(log n/ρ^2) samples to recover the ground truth with high probability.The guarantee assumes a random ρn-sparse hidden assignment with ρ ≪ 1/d^3/2.
  • Real-valued weights: For real-valued weights, the first three steps still apply because their proofs use weight signs, after which weight learning becomes supervised linear classification.The edge weights can then be learned to any desired accuracy.

5 Correlations in a Multilayer Network

The multilayer analysis shows that intermediate hidden layers retain sufficiently controlled activation probabilities and correlations for the single-layer strategy to be applied repeatedly. Learning proceeds from the bottom upward by recovering one layer and peeling it off.

  • Layerwise learning: Multilayer networks are learned layerwise by modifying the one-layer algorithm at each layer.Intermediate assignments need not be independent sparse vectors, but their correlations remain low enough for the argument to continue.
  • Activation densities: The expected activation density at layer i is ρ_i = ρ_ℓ·(d/2)^(ℓ−i), based on the unique neighbor property.The analysis expects roughly a ρ_ℓ(d/2) fraction of the preceding layer to activate, with the relation propagated upward.
  • Activation densities: With high probability, each vertex in layer i activates with probability between 3ρ_i/4 and 5ρ_i/4.This bound is established inductively using randomness of the underlying graph.
  • Correlation analysis: For nodes sharing a positive common neighbor, simultaneous activation is supported by that neighbor being active while negative neighbors remain inactive.The relevant conditions occur together with probability at least ρ_2/2 under the stated parameter choices.
  • Layerwise learning: After recovering the bottom layer and encoding its hidden variables, the same reasoning is repeated after peeling it off, enabling layer-by-layer recovery.The procedure obtains values for the next hidden layer and then reconstructs the remaining graph.

6 Graph Recovery

Graph recovery reconstructs a hidden bipartite graph from observed pairs sharing common parents, despite the corresponding worst-case Graph Square Root problem being NP-hard. Random-graph properties make recovery efficient and reliable.

  • Problem definition: Graph Recovery receives the observed graph of shared-parent pairs and seeks the underlying bipartite graph.An observed edge means two visible nodes share at least one parent in the hidden graph.
  • 3-wise recovery: The 3-wise version requires an analogous hypergraph recovery problem for triples mutually connected through a hidden node.The paper notes that this variant is not detailed because of space limitations.
  • Random-graph conditions: The recovery analysis assumes random-graph properties controlling common causes, near-disjoint neighborhoods, unrelated correlations, and uniquely caused edge pairs.These properties hold with high probability when d^3/n ≪ 1.
  • Recovery guarantee: When the graph satisfies Properties 1–4, the recovery algorithm successfully reconstructs G1 in expected O(n^2) time.The algorithm identifies hidden vertices from sampled correlation neighborhoods and marks the corresponding observed edges.
  • Recovery mechanism: The algorithm separates a unique common cause from unrelated vertices by retaining vertices with sufficiently many neighbors inside the sampled correlation set.Vertices belonging to the cause retain at least 0.8d − 1 such connections, while outside vertices have at most d/10.

7 Learning the lowermost (real-valued) layer

The lowermost observed layer is real-valued, so the threshold-based learner is modified while retaining correlation-based graph recovery. A random weighted graph yields a denoising autoencoder and controlled higher-order correlations.

  • Real-valued bottom layer: The bottom layer cannot use the earlier threshold-gate algorithm directly because its observed values are real-valued.The same paradigm of identifying correlations and applying Graph Recovery remains applicable.
  • Denoising autoencoder: For a random weighted graph, E(y) = sgn(G^T y − 0.4d1) and D(h) = Gh form a denoising autoencoder under bounded independent noise.Each noise component may have variance at most O(d/log^2 n).
  • Correlation structure: When ρ_1d = O(1) and d = Ω(log^2 n), triple correlations separate nodes with a unique common neighbor from nodes with none.The stated bounds hold with high probability over the random weights and graph.

8 Two layers cannot be represented by one layer

A two-layer network with random ±1 weights can generate distributions that one-layer threshold networks cannot represent, even with arbitrary weights and thresholds. The separation arises from cancellations across hidden layers that cannot be captured by a single threshold function.

  • Model: A two-layer network computes h(1) = sgn(G1 sgn(G2h(3))) from a top-layer input through two random-weight graphs.The model uses random ±1 edge weights in both layers.
  • Separation result: The two-layer construction is more expressive than a one-layer network even when the latter has arbitrary weights and arbitrary threshold functions.The comparison concerns the generated output distribution over sparse top-layer inputs.
  • Separation result: For almost all choices of (G1, G2), every one-layer network disagrees with the two-layer network with probability at least Ω(ρ3^2) on random sparse inputs.The condition is ρ3d2d1 ≪1.
  • Proof idea: Cancellations among hidden-layer contributions prevent a single threshold function from representing even one output bit reliably.The proof focuses on a single output node and shows incompatible on/off patterns for four ancestor values.

9 Conclusions

The paper studies randomly wired multilayer neural nets as generative models and argues that rigorous analysis of this structured setting can yield provable learning results and theoretical insight. Its conclusions also identify randomness of the edge support as important for layerwise guarantees and leave empirical validation on real learned networks open.

  • Conclusions: Rigorous analysis of random neural-net subcases can provide a foundation for triggering improvements in broader machine-learning problems.The paper compares this role with rigorous analyses of message passing on trees and low-tree-width graphs.
  • Limitations and open directions: Provable layerwise learning relies on random support to control correlations among features in the same hidden layer.The paper identifies learning under weaker support assumptions as an open direction.
  • Model: The model uses hidden binary layers connected by random bipartite graphs with randomly chosen weights in [−1, 1].Edges appear independently with probability p_i, and thresholded computation occurs at hidden nodes.
  • Model: The generative process initializes a sparse top-layer assignment and propagates it downward through weighted threshold operations to an observed bottom layer.The observed layer is computed without thresholding in the main model.
  • Assumptions: The analysis assumes expected degrees much larger than log n so that key random-graph events hold with high probability.One cited consequence is concentration of hidden-node backdegrees around d ± √d log n.
  • Structural properties: The stronger unique-neighbor property is crucial for showing that each layer is a denoising autoencoder.It limits shared neighbors between nodes and sets with high probability over the random graph.

B Main Results

The paper gives polynomial-time algorithms that learn almost all networks in the random multilayer model under stated degree, density, and graph assumptions. Sample complexity and runtime depend on the model variant, with a faster algorithm available under an additional sparsity condition.

  • The algorithm learns a random deep neural network in polynomial time.
  • The model includes a real-valued final layer for fully dense outputs; without it, the last-layer density must be at most 1/poly log(n).
  • When i ≪ ρ_(i+1) holds, a faster and simpler algorithm runs in O(n^2) time.
  • The learned network's observed vectors agree with the original network on a (1 − η) fraction of the hidden variable h^(l).

C Each layer is a Denoising Auto-encoder

The paper proves that successive layers of its random neural networks form denoising autoencoders with weight tying and robustness to output noise. This structure supports layerwise learning based on correlations and graph recovery.

  • A denoising autoencoder uses encoder E and decoder D such that E(D(h)+η) = h with high probability under corrupted outputs.
  • Each layer is a denoising autoencoder with high probability, and the construction satisfies weight tying.
  • The single-layer construction uses a random support graph, random weights in [−1, 1], zero decoder bias, and encoder threshold 0.2d′.
  • If ρmd′ < 0.05n, the single-layer network remains a denoising autoencoder when each output bit flips independently with probability 0.01.
  • The encoder recovers most hidden assignments and has enough margin to remain stable when 0.01 fraction of observed-layer bits are flipped.
  • The layerwise learning algorithm uses pairwise or 3-wise correlations to infer shared neighbors before global graph recovery.

D.1.1 Warm up: 0/1 weights

In the 0/1-weight setting, correlations among observed nodes reveal shared hidden neighbors, enabling graph recovery under sparsity and random-graph conditions. Higher-order correlations extend the method to weaker sparsity requirements, and the recovered structure supports recovery of negative edges and multilayer graph learning.

  • Model: A random bipartite graph with m hidden nodes and n observed nodes, unit edge weights, and sparse hidden activations defines the single-layer learning problem.The observed vector is y = sgn(Gh), and learning G is equivalent to finding its edges.
  • Pairwise correlations: With high probability, PairwiseGraph recovers exactly the observed-node pairs that share a hidden neighbor under Psing and ρ ≪ 1/d^2.Estimating the relevant probabilities requires O(log n/ρ^2) samples by Chernoff bounds.
  • Pairwise correlations: Pairwise correlations identify observed-node pairs with a common hidden neighbor when ρ ≪ 1/d^2.Shared neighbors produce joint firing probability at least ρ, while disjoint neighborhoods have much smaller joint probability.
  • Higher-order correlations: 3-wise correlations relax the sparsity requirement to approximately ρ ≪ d^-3/2 by distinguishing triples with a common neighbor from other triples.A shared-neighbor triple fires jointly with probability at least ρ, whereas otherwise the probability is bounded by 3ρ_y^3 + 50ρ_yρ.

F.2 Graph Recovery with Higher-Order Correlations

Higher-order correlations make graph recovery feasible in denser regimes and extend layerwise learning to multilayer networks and real-valued outputs. The guarantees remain conditional on random-graph properties, sparsity assumptions, and weaker recovery objectives for continuous weights.

  • Motivation: When d′^2 > n, pairwise-correlation recovery becomes uninformative because the inferred distance-2 graph is nearly complete.This motivates using higher-order correlations, which are rarer and preserve more structural information.
  • 3-wise graph recovery: 3-wise Graph Recovery reconstructs a random bipartite graph from triples sharing a common hidden neighbor.RecoverGraph3Wise groups vertices whose pairwise triple relations are mutually consistent, then creates hidden vertices for the recovered communities.
  • 3-wise graph recovery: Under m3d′^8/n^8 ≪ 1, the 3-wise recovery algorithm succeeds with high probability and expected running time O(m(d′^3 + n)).The guarantee follows from concentration of the required random-graph properties.
  • Multilayer learning: The multilayer algorithm learns each graph layerwise using correlations among intermediate representations, whose dependencies remain sufficiently low for the recovery argument.For one layer, recovering negative edges uses O(log n/(ρ^2d)) samples under ρ_yd ≪ 1.
  • Limitations: Continuous weights cannot generally be recovered exactly with few samples, so the decoder guarantee is approximate in the sense of correctness probability 1−η.The paper gives an example requiring exp(Ω(d)) samples to recover weights or agree with the true function on every input.
  • Real-valued outputs: For real-valued outputs, triple correlations can reveal common causes even when the output is fully dense, and the method permits ρpm = O(1).With random weights in [−1,1], the graph and weights can be learned using O(log^2 n/ρ_1^2) samples and O(log^2 n/ρ_1^2 + m(d^3+n)) time under the theorem’s conditions.

I.2 Representational power: One layer net can’t do two layers net

Two-layer random networks exploit cancellation patterns that no single-layer threshold network can reproduce on all sparse inputs. The section formalizes this separation and states graph properties used in the learning analysis.

  • Representational separation: Two-layer networks with random ±1 weights can generate distributions that single-layer networks with arbitrary weights and thresholds cannot match.The separation arises because two-layer cancellations cannot all be represented by a single threshold function.
  • Representational separation: For almost all (G1, G2), every one-layer network disagrees with the two-layer network with probability at least Ω(ρ3^2) on random sparse inputs.The bound applies when h(3) is a random ρ3n-sparse vector and ρ3d2d1 ≪ 1.
  • Representational separation: A local cancellation structure forces contradictory threshold constraints, so even one output bit cannot be well-represented by a single-layer network.The contradiction is exhibited using four input assignments whose required outputs cannot satisfy all corresponding linear inequalities.
  • Random-graph assumptions: The analysis relies on unique-neighbor, degree, and expansion properties that hold with high probability for suitable random graphs.For single-layer properties, expected degrees must satisfy d, d′ ≫ log n; an additional condition d2 ≤ n4/5 yields Psing+.

L Omitted Proofs in Section H

The omitted proofs bound correlations and variances in random networks to distinguish shared-parent triples from unrelated triples. They also justify graph recovery and adaptations for different edge-weight distributions.

  • Correlation bounds: When three observed nodes share no common neighbor, their output correlation is small; when they share a unique neighbor, it is large enough to distinguish the cases.With high probability, the respective bounds are |E[yuyvys]| ≤ ρ1/3 and |E[yuyvys]| ≥ 2ρ1/3.
  • Multilayer extension: The proofs extend the correlation analysis from uniformly sparse hidden vectors to hidden variables generated by upper network layers.This extension requires carefully bounding third-order moments and using the earlier variance arguments.
  • Correlation bounds: Most pairs and triples have small expectation, while only a very small number of pairs can be highly correlated under the random graph model.For a fixed set T of size at most 3d1, at most 10 pairs in T share a positive parent with high probability.
  • Graph recovery: The graph-recovery algorithm uses these correlation patterns to identify shared-parent structure, with special handling for ±1 and continuous weights.For [−1,1] weights, ambiguous hyperedges form only a small constant fraction; for ±1 weights, shared-neighbor multiplicity is controlled by a constant bound.
  • Graph recovery: For [−1,1] weights, graph recovery can miss about 1% of edges with very small weights, but PartialEncoder tolerates this constant-fraction error.The ±1 case does not have this missing-edge issue.
Loading 1310.6343v1…