1 citations · 2 across the 5 of their papers we have counts for
5 papers
Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the efficient learnability of low-degree polynomial threshold functions (PTFs) in the presence of a constant fraction of adversarial corruptions. Our main algorithmic resu…
Online Robust Mean Estimation
Daniel M. Kane, Ilias Diakonikolas, Hanshen Xiao +1
We study the problem of high-dimensional robust mean estimation in an online setting. Specifically, we consider a scenario where sensors are measuring some common, ongoing phen…
Efficient Testable Learning of Halfspaces with Adversarial Label Noise
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We give the first polynomial-time algorithm for the testable learning of halfspaces in the presence of adversarial label noise under the Gaussian distribution. In the recently intr…
Exponential Hardness of Reinforcement Learning with Linear Function Approximation
Daniel Kane, Sihan Liu, Shachar Lovett +3
A fundamental question in reinforcement learning theory is: suppose the optimal value functions are linear in given features, can we learn them efficiently? This problem's counterp…
Near-Optimal Bounds for Testing Histogram Distributions
Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane +1
We investigate the problem of testing whether a discrete probability distribution over an ordered domain is a histogram on a specified number of bins. One of the most common tools…