research
∙
07/02/2023
Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
We study a generalization of boosting to the multiclass setting. We intr...
share
research
∙
05/25/2023
Most Neural Networks Are Almost Learnable
We present a PTAS for learning random constant-depth networks. We show t...
research
∙
02/15/2023
Efficiently Learning Neural Networks: What Assumptions May Suffice?
Understanding when neural networks can be learned efficiently is a funda...
research
∙
11/17/2022
On the Sample Complexity of Two-Layer Networks: Lipschitz vs. Element-Wise Lipschitz Activation
We investigate the sample complexity of bounded two-layer neural network...
research
∙
09/26/2022
Approximate Description Length, Covering Numbers, and VC Dimension
Recently, Daniely and Granot [arXiv:1910.05697] introduced a new notion ...
research
∙
02/10/2022
Monotone Learning
The amount of training-data is one of the key factors which determines t...
research
∙
06/22/2021
Asynchronous Stochastic Optimization Robust to Arbitrary Delays
We consider stochastic optimization with delayed gradients where, at eac...
research
∙
05/20/2021
An Exact Poly-Time Membership-Queries Algorithm for Extraction a three-Layer ReLU Network
As machine learning increasingly becomes more prevalent in our everyday ...
research
∙
01/20/2021
From Local Pseudorandom Generators to Hardness of Learning
We prove hardness-of-learning results under a well-studied assumption on...
research
∙
10/28/2020
Most ReLU Networks Suffer from ℓ^2 Adversarial Perturbations
We consider ReLU networks with random weights, in which the dimension de...
research
∙
06/05/2020
Hardness of Learning Neural Networks with Natural Weights
Neural networks are nowadays highly successful despite strong hardness r...
research
∙
03/28/2020
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...
research
∙
02/18/2020
Learning Parities with Neural Networks
In recent years we see a rapidly growing line of research which shows le...
research
∙
02/09/2020
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...
research
∙
11/22/2019
Neural Networks Learning and Memorization with (almost) no Over-Parameterization
Many results in recent years established polynomial time learnability of...
research
∙
10/13/2019
Generalization Bounds for Neural Networks via Approximate Description Length
We investigate the sample complexity of networks with bounds on the magn...
research
∙
09/26/2019
The Implicit Bias of Depth: How Incremental Learning Drives Generalization
A leading hypothesis for the surprising generalization of neural network...
research
∙
07/11/2019
On the Optimality of Trees Generated by ID3
Since its inception in the 1980s, ID3 has become one of the most success...
research
∙
06/20/2019
ID3 Learns Juntas for Smoothed Product Distributions
In recent years, there are many attempts to understand popular heuristic...
research
∙
04/07/2019
Competitive ratio versus regret minimization: achieving the best of both worlds
We consider online algorithms under both the competitive ratio criteria ...
research
∙
09/24/2018
Learning without Interaction Requires Separation
One of the key resources in large-scale learning systems is the number o...
research
∙
05/07/2018
Planning and Learning with Stochastic Action Sets
In many practical uses of reinforcement learning (RL) the set of actions...
research
∙
03/08/2018
Learning with Rules
Complex classifiers may exhibit "embarassing" failures in cases that wou...
research
∙
02/27/2017
SGD Learns the Conjugate Kernel Class of the Network
We show that the standard stochastic gradient decent (SGD) algorithm is ...
research
∙
02/27/2017
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:...
research
∙
02/18/2016