Geometric Algorithms for Learning and Data Poisoning

Geometric methods have provided many powerful tools in algorithm design and learning. In this dissertation, I will present our geometric algorithms for learning and data poisoning. In the first part of my dissertation, I introduce our approach to solve the learning line problem with ordinal constraints. Our goal is to find a mapping from a set of points into the real line, such that the number of constraints for the triple of points that encode their proximity information could be preserved as many as possible. Our algorithm computes a solution that satisfies $(1-O(\eps^{1/8}))$-fraction of all constraints, in time $O(n^7) + (1/\eps)^{O(1/\eps^{1/8})} n$. In the second part of my dissertation, I introduce our geometric algorithms for data poisoning. The key motivation of our study is to provide a systematic way of injecting nearly-optimal poisoning to data with provable worse case guarantee, so that the robustness of the clustering algorithms could be evaluated on some nearly optimal poisoned data set. I first propose our poisoning algorithms against $k$-center and $k$-means clustering. Our algorithms can achieve $\frac{1}{6}$-approximation with respect to optimal poisoning for $k$-center data poisoning problem in time $O(m n^{\lceil d/2 \rceil})$. For $k$-means data poisoning problem, we get an bi-criteria approximation algorithm for general case. The algorithm achieves $(\Omega(1/k^2),2)$-approximation with respect to optimal poisoning, that is, if the cost of optimal $m$ poisoning is $cost_k(X\cup P_\OPT)$, our algorithm compute a $2m$ poisoning, with cost at least $\Omega(1/k^2)$. Then I propose our poisoning algorithm for $k$-NN clustering. Our algorithm computes an $\eps n$-additive approximation of the optimal poisoning in $n\cdot 2^{2^{O(d+k/\eps)}}$ time.