Computational/Statistical Gaps for Learning Neural Networks

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=CRoT6gEzSSU


Duration: 59:05
476 views
11

Adam Klivans (University of Texas, Austin)
Probability, Geometry, and Computation in High Dimensions
Seminar, Dec. 1, 2020

It has been known for decades that a polynomial-size training sample suffices for learning neural networks. Most theoretical results, however, indicate that these learning tasks are computationally intractable. Where exactly is the dividing line? In this talk we consider arguably the most well-studied scenario, namely when the marginal distribution on inputs is Gaussian, and show unconditionally that gradient descent cannot learn even one-layer neural networks. We then point to a potential way forward and sketch the first fixed-parameter tractable algorithm for learning deep ReLU networks. Its running time is polynomial in the ambient dimension and exponential in only the network's parameters. This is the first nontrivial positive result for networks of depth more than two.

https://simons.berkeley.edu/events/computationalstatistical-gaps-learning-neural-networks



Other Videos By Simons Institute for the Theory of Computing


2020-12-04Stable Reinforcement Learning with Unbounded State Space
2020-12-04Multiagent Reinforcement Learning: Rollout and Policy Iteration
2020-12-04Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation
2020-12-04Nearly Minimax Optimal Reward-Free Reinforcement Learning
2020-12-03Statistical Efficiency in Offline Reinforcement Learning
2020-12-03Batch Policy Learning in Average Reward Markov Decision Processes
2020-12-03Panel Discussion
2020-12-02The Mean-Squared Error of Double Q-Learning
2020-12-02Q-learning with Uniformly Bounded Variance
2020-12-02Zap Stochastic Approximation and Implications to Q-Learning
2020-12-02Computational/Statistical Gaps for Learning Neural Networks
2020-12-02Uniform Offline Policy Evaluation (OPE) and Offline Learning in Tabular RL
2020-12-02Batch Value-function Approximation with Only Realizability
2020-12-01Reinforcement Learning using Generative Models for Continuous State and Action Space Systems
2020-12-01Monte Carlo Sampling Approach to Solving Stochastic Multistage Programs
2020-12-01Robust Learning of Stochastic Dynamical Systems
2020-12-01Confident Off-policy Evaluation and Selection through Self-Normalized Importance Weighting
2020-12-01An Equivalence between Loss Functions and Non-Uniform Sampling in Experience Replay
2020-11-30Beyond Worst-Case: Instance-Dependent Optimality in Reinforcement Learning
2020-11-30Learning Multi-Agent Collaborations With Decomposition
2020-11-30Online Learning with A Lot of Batch Data


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing