Research map / Optimization / Implicit bias and generalization

Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks

ICLR 2024 · Optimization › Implicit bias and generalization · approach: Shallow ReLU network convergence · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a framework of perceptron modules and random sparse lifts (Erdős–Rényi-style sparsification at initialization) and proves that gradient flow on such large sparse networks PAC-converges to arbitrarily low loss as width grows, via a tangent approximation property.

Problem

Gradient-flow convergence guarantees for neural networks as the number of parameters grows, without overparameterization assumptions tied to the number of training samples.

Approach

Define architectures as lifts of a base computation graph (perceptron modules) by homomorphisms, and randomly sparsify the fully-connected lift at initialization (Bernoulli masks with degree scaling). Low out-degree plus sub-network coverage yields tangent approximation on a large ball around initialization, giving a separable Kurdyka-Łojasiewicz inequality and probable approximate correctness of

Key results

• Theorem: for random sparse lifts with Bernoulli masks m ~ Bern(lambda/n) and sufficiently large lift sizes n, with probability at least 1-delta gradient flow satisfies the convergence criterion with limit error epsilon and constant kappa.
• Quantitative bounds on the size threshold N_1 and speed kappa are given as functions of the witness network structure (appendix).

Limitations

• Convergence is shown only for sparse lifts; dense lifts are left as future work
• Results are about loss convergence in continuous time (gradient flow), not parameter convergence or discrete-time SGD
• Requires a witness network achieving low loss and a degree/size condition on the lift

Experimental setup

Builds on: Lottery Ticket Hypothesis Tensor Programs Named Tensors neural tangent kernel

Closest papers by meaning

• Pruning at Initialisation through the lens of Graphon Limit: Convergence, Expressivity, and Generalisation (ICML 2026 · similarity 0.90)
• Sparsity May Cry: Let Us Fail (Current) Sparse Neural Networks Together! (ICLR 2023 · similarity 0.90)
• Global Minimizers of $\ell^p$-Regularized Objectives Yield the Sparsest ReLU Neural Networks (NeurIPS 2025 · similarity 0.90)
• Position: A Theory of Deep Learning Must Include Compositional Sparsity (ICML 2025 · similarity 0.89)
• A Single-Step, Sharpness-Aware Minimization is All You Need to Achieve Efficient and Accurate Sparse Training (NeurIPS 2024 · similarity 0.89)
• The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysis (NeurIPS 2025 · similarity 0.89)