
-
From Local Pseudorandom Generators to Hardness of Learning
We prove hardness-of-learning results under a well-studied assumption on...
read it
-
Most ReLU Networks Suffer from ℓ^2 Adversarial Perturbations
We consider ReLU networks with random weights, in which the dimension de...
read it
-
Hardness of Learning Neural Networks with Natural Weights
Neural networks are nowadays highly successful despite strong hardness r...
read it
-
Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
We prove that a single step of gradient decent over depth two network, w...
read it
-
Learning Parities with Neural Networks
In recent years we see a rapidly growing line of research which shows le...
read it
-
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions
Recent advances in randomized incremental methods for minimizing L-smoot...
read it
-
Neural Networks Learning and Memorization with (almost) no Over-Parameterization
Many results in recent years established polynomial time learnability of...
read it
-
Generalization Bounds for Neural Networks via Approximate Description Length
We investigate the sample complexity of networks with bounds on the magn...
read it
-
The Implicit Bias of Depth: How Incremental Learning Drives Generalization
A leading hypothesis for the surprising generalization of neural network...
read it
-
On the Optimality of Trees Generated by ID3
Since its inception in the 1980s, ID3 has become one of the most success...
read it
-
ID3 Learns Juntas for Smoothed Product Distributions
In recent years, there are many attempts to understand popular heuristic...
read it
-
Competitive ratio versus regret minimization: achieving the best of both worlds
We consider online algorithms under both the competitive ratio criteria ...
read it
-
Learning without Interaction Requires Separation
One of the key resources in large-scale learning systems is the number o...
read it
-
Planning and Learning with Stochastic Action Sets
In many practical uses of reinforcement learning (RL) the set of actions...
read it
-
Learning with Rules
Complex classifiers may exhibit "embarassing" failures in cases that wou...
read it
-
SGD Learns the Conjugate Kernel Class of the Network
We show that the standard stochastic gradient decent (SGD) algorithm is ...
read it
-
Depth Separation for Neural Networks
Let f:S^d-1×S^d-1→S be a function of the form f(x,x') = g(〈x,x'〉) for g:...
read it
-
Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
We develop a general duality between neural networks and compositional k...
read it