Cover Image

The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Abbe, Emmanuel, Boix-Adsera, Enric, Misiakiewicz, Theodor
Format:	Preprint
Published:	2022
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
by: Joshi, Nirmit, et al.
Published: (2024)

Prefix-free parsing for merging big BWTs
by: Diaz-Dominguez, Diego, et al.
Published: (2025)

A sufficient condition for characterizing the one-sided testable properties of families of graphs in the Random Neighbour Oracle Model
by: Awofeso, Christine, et al.
Published: (2025)

When are quarnets sufficient to reconstruct semi-directed phylogenetic networks?
by: Huber, Katharina T., et al.
Published: (2024)

Quantum property testing in sparse directed graphs
by: Apers, Simon, et al.
Published: (2024)

Simple and efficient four-cycle counting on sparse graphs
by: Burkhardt, Paul, et al.
Published: (2023)

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time
by: Kowalik, Lukasz
Published: (2024)

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
by: Bodlaender, Hans L., et al.
Published: (2025)

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
by: Bonnet, Édouard, et al.
Published: (2026)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
by: Lokshtanov, Daniel, et al.
Published: (2026)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
by: Ashvinkumar, Vikrant, et al.
Published: (2026)

Provably learning a multi-head attention layer
by: Chen, Sitan, et al.
Published: (2024)

Testing H-freeness on sparse graphs, the case of bounded expansion
by: Humeau, Samuel, et al.
Published: (2025)

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
by: Makarychev, Yury
Published: (2026)

Smallest suffixient set maintenance in near-real-time
by: Köppl, Dominik, et al.
Published: (2026)

Graph neural networks extrapolate out-of-distribution for shortest paths
by: Nerem, Robert R., et al.
Published: (2025)

A fast algorithm for All-Pairs-Shortest-Paths suitable for neural networks
by: Jing, Zeyu, et al.
Published: (2023)

The anti-lexicographic SUS-anchor: a near-optimal k=1 sampling scheme
by: Koerkamp, Groot, et al.
Published: (2026)

Optimal mass estimation in the conditional sampling model
by: Adar, Tomer, et al.
Published: (2025)

Node ranking in labeled networks
by: Arachchi, Chamalee Wickrama, et al.
Published: (2025)

Tight simulation of a distribution using conditional samples
by: Adar, Tomer
Published: (2025)

Balls-and-Bins Sampling for DP-SGD
by: Chua, Lynn, et al.
Published: (2024)

How Private are DP-SGD Implementations?
by: Chua, Lynn, et al.
Published: (2024)

A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs
by: Fox, Emily
Published: (2023)

A near-linear time approximation scheme for $(k,\ell)$-median clustering under discrete Fréchet distance
by: Driemel, Anne, et al.
Published: (2025)

Optimal FIFO grouping in public transit networks
by: Steil, Patrick
Published: (2023)

Unrolled denoising networks provably learn optimal Bayesian inference
by: Karan, Aayush, et al.
Published: (2024)

Approximating splits for decision trees quickly in sparse data streams
by: Tatti, Nikolaj
Published: (2026)

Max Weight Independent Set in sparse graphs with no long claws
by: Abrishami, Tara, et al.
Published: (2023)

Scheduling two types of jobs with minimum makespan
by: Cao, Song, et al.
Published: (2024)

Faster feasibility for dynamic flows and transshipments on temporal networks
by: Sheridan, Kristin, et al.
Published: (2024)

Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
by: Abbas, Amira, et al.
Published: (2025)

An FPRAS for two terminal reliability in directed acyclic graphs
by: Feng, Weiming, et al.
Published: (2023)

Free-order secretary for two-sided independence systems
by: Bérczi, Kristóf, et al.
Published: (2025)

Controlling tail risk in two-slope ski rental
by: Cui, Qiming, et al.
Published: (2025)

Efficient algorithm for linear diophantine equations in two variables
by: Deora, Mayank, et al.
Published: (2025)

Faster two-dimensional pattern matching with $k$ mismatches
by: Ellert, Jonas, et al.
Published: (2024)

Sampling unknown large networks restricted by low sampling rates
by: Jiao, Bo
Published: (2023)

On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule
by: Chen, Zongchen, et al.
Published: (2024)

A basic lower bound for property testing
by: Fischer, Eldar
Published: (2024)