Seminars

View all Seminars  |  Download ICal for this event

Robust Multivariate Polynomial Regression

Series: Bangalore Theory Seminars

Speaker: Vipul Arora, National University of Singapore

Date/Time: Oct 21 16:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Abstract:
We study the problem of robust multivariate polynomial regression:
let $p : reals^n to reals$ be an unknown $n$-variate polynomial of degree at most $d$ in each variable. We are given as input a set of random samples $(mathbf{x}_i, y_i) in [-1,1]^n times reals$ that are noisy versions of $(mathbf{x}_i, p(mathbf{x}_i))$. More precisely, each $mathbf{x}_i$ is sampled independently from some distribution $chi$ on $[-1,1]^n$, and for each $i$ independently, $y_i$ is arbitrary (i.e., an outlier) with probability at most $rho < 1/2$, and otherwise satisfies $|y_i - p(mathbf{x}_i)| leq sigma$. The goal is to output a polynomial $hat{p}$, of degree at most $d$ in each variable, within an $ell_infty$-distance of at most $O(sigma)$ from $p$.
Kane, Karmalkar, and Price [FOCS 17] solved this problem for $n=1$. We generalize their results to the $n$-variate setting, showing an algorithm that achieves a sample complexity of $O_n(d^n log d)$, where the hidden constant depends on $n$, if $chi$ is the $n$-dimensional Chebyshev distribution.

The sample complexity is $O_n(d^{2n} log d)$, if the samples are drawn from the uniform distribution instead. The approximation error is guaranteed to be at most $O(sigma)$, and the run-time depends on $log(1/sigma)$. In the setting where each $mathbf{x}_i$ and $y_i$ are known up to $N$ bits of precision, the run-times dependence on $N$ is linear. We also show that our sample complexities are optimal in terms of $d^n$.
Furthermore, we show that it is possible to have the run-time be independent of $1/sigma$, at the cost of a higher sample complexity.

This is a joint work with Arnab Bhattacharyya, Mathews Boban, Venkatesan Guruswami, and Esty Kelman, and appeared at ESA24.

Microsoft teams link:

Link


We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar