Depth separation for functions learnable by gradient descent
Depth-3 networks can express functions depth-2 cannot. Whether training can find them is a different question, and it is open.
Problem statement
Exhibit a distribution and a target function that is efficiently learnable by gradient descent on a depth-3 network with polynomially many parameters and samples, and prove that no depth-2 network of polynomial width can learn it efficiently by gradient descent.
Lean 4
No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.
Background
Expressivity separations between depths are classical: Telgarsky, Eldan–Shamir and others exhibit functions requiring exponential width at depth 2 but polynomial size at depth 3. Those results say nothing about learnability, because they do not address what gradient descent finds.
"Depth helps" is the founding empirical claim of the field. A learnability separation would be the first rigorous version of it that accounts for the optimiser, rather than only for what the architecture can represent.
Known partial results
- Expressivity separations: Telgarsky (2016), Eldan and Shamir (2016), Daniely (2017).
- Statistical-query and correlational-SQ lower bounds give learnability hardness for some target classes, but the matching depth-3 upper bound under gradient training is usually missing.
- Results on learning single- and multi-index models with gradient descent characterise sample complexity via the information exponent, and are the closest existing analogue.
Recorded progress
Add yours →Nothing recorded yet. A pointer to a paper the entry is missing counts.
Machine attempts
0 recordedAttempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.
No machine attempts recorded.
Sign in to run an attempt. New accounts start with enough credits for ten.
Discussion
0 notesNotes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.
No notes yet.
Sign in to add a note.