A Geometric Approach to Problems in Optimization and Data Science
It addresses computational and statistical challenges in machine learning, with incremental improvements across multiple domains.
The paper tackles optimization and data science problems by introducing new algorithms for approximating convex polytopes, sparsification, robust regression, and dueling optimization, and provides statistical guarantees for backdoor data poisoning attacks and graph clustering robustness.
We give new results for problems in computational and statistical machine learning using tools from high-dimensional geometry and probability. We break up our treatment into two parts. In Part I, we focus on computational considerations in optimization. Specifically, we give new algorithms for approximating convex polytopes in a stream, sparsification and robust least squares regression, and dueling optimization. In Part II, we give new statistical guarantees for data science problems. In particular, we formulate a new model in which we analyze statistical properties of backdoor data poisoning attacks, and we study the robustness of graph clustering algorithms to ``helpful'' misspecification.