## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, October 28, 2014, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Hemant Tyagi

## Efficient sampling for learning SPAMs in high dimensions

We consider the problem of learning Sparse Additive Models (SPAMs), i.e. functions of the form: $f(x_1,...,x_d) = \sum_{l \in S} \phi_{l}(x_l)$; $S \subset {1,\dots,d}$, from point queries of $f$. Here $\phi_l$ and $S$ are unknown and $|S| = k \ll d$. Such models have been studied extensively in statistics, in the context of non-parametric regression. However in that setting, one typically does not have control over the points, at which the value of $f$ is observed.

Assuming $\phi_l$'s to be smooth, we propose a set of points at which to query $f$ and an efficient randomized algorithm that recovers: (i) $S$ exactly and, (ii) a uniform approximation to each $\phi_l$; for all $l \in S$. In contrast, the existing results in statistics provide error bounds for recovering $f$ in the weaker mean square sense.

If the point queries are noiseless, we show that $O(k \log d)$ queries suffice while if the point queries are corrupted with (i.i.d) Gaussian noise, we show that $O(k^3 (\log d)^2)$ queries suffice.

Joint work with Bernd Gärtner and Andreas Krause.

Information for students and suggested topics for student talks