Speaker:
Xue Chen(George Mason University)
Time:
- 11:00 – 12:00 (Time in Beijing)
- 15:00 – 16:00 (Time in Auckland)
- June 28, 2021 (Monday)
Venue:
B1-501, Main Building
Abstract:
We consider the problem of learning an unknown f with a sparse Fourier spectrum in the presence of outlier noise. In particular, the algorithm has access to a noisy oracle for (an unknown) f such that (i) the Fourier spectrum of f is k-sparse; (ii) at any query point x, the oracle returns y such that with probability 1−ρ, |y−f(x)|≤ϵ. However, with probability ρ, the error y−f(x) can be arbitrarily large. We study Fourier sparse functions over both the discrete cube {0,1}^n and the torus [0,1) and for both these domains, we design efficient algorithms which can tolerate any ρ<1/2 fraction of outliers. We note that the analogous problem for low-degree polynomials has recently been studied in several works~[AK03, GZ16, KKP17] and similar algorithmic guarantees are known in that setting. While our main results pertain to the case where the location of the outliers, i.e., x such that |y−f(x)|>ϵ is randomly distributed, we also study the case where the outliers are adversarially located. In particular, we show that over the torus, assuming that the Fourier transform satisfies a certain granularity condition, there is a sample efficient algorithm to tolerate ρ=Ω(1) fraction of outliers and further, that this is not possible without such a granularity condition. Our techniques combine a diverse array of tools from compressive sensing, sparse Fourier transform, chaining arguments and complex analysis. Based on Joint work with Anindya De (University of Pennsylvania).
Speaker Bio:
Dr. Xue Chen is an assistant professor in the CS department of George Mason University (USA). Previously, He obtained his PhD in the University of Texas at Austin, advised by Prof. David Zuckerman, and spent two years as a postdoc fellow in the theory group of Northwestern University. Prior to Austin, he received his bachelor’s degree from the Yao class in Tsinghua University.