Paper recorded by Signals 4 on 2026-09-11 in cs.LG. Abstract reproduced from arXiv; link to the original below.
Published 2026-09-11 on arXiv · recorded by Signals 4 on 2026-09-14
Category: cs.LG · 机器学习 · first seen 2026-09-14
Deep neural networks are expressive enough to contain worst-case targets that can be evaluated in polynomial time but cannot be learned in polynomial time by gradient descent. For practical tasks they nonetheless learn well, raising the question of what non-generic structure of real-world targets enables this. Existing surrogate models cannot pose this question because they either lack hard-to-lea