# Sublinear Time Algorithms for Several Geometric Optimization (With Outliers) Problems In Machine Learning

arXiv: https://arxiv.org/abs/2301.02870 · HTML: https://mlsanity.com/paper/2301.02870/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 94 references that are in the map.
- First posted on arXiv 7 Jan 2023.

## Builds on (most cited first, 13 of 13)

- [Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning](https://mlsanity.com/paper/1712.03141/) (2017)
- [Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning](https://mlsanity.com/paper/1804.00308/) (2018)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Locating a Small Cluster Privately](https://mlsanity.com/paper/1604.05590/) (2016)
- [varepsilon-Coresets for Clustering (with Outliers) in Doubling Metrics](https://mlsanity.com/paper/1804.02530/) (2018)
- [Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially](https://mlsanity.com/paper/1802.09205/) (2018)
- [k-center Clustering under Perturbation Resilience](https://mlsanity.com/paper/1505.03924/) (2015)
- [Beyond Worst-Case Analysis](https://mlsanity.com/paper/1806.09817/) (2018)
- [Approximation and Streaming Algorithms for Projective Clustering via Random Projections](https://mlsanity.com/paper/1407.2063/) (2014)
- [Approximate Cech Complexes in Low and High Dimensions](https://mlsanity.com/paper/1307.3272/) (2013)
- [Optimization Algorithms for Faster Computational Geometry](https://mlsanity.com/paper/1412.1001/) (2014)
- [A Sub-linear Time Framework for Geometric Optimization with Outliers in High Dimensions](https://mlsanity.com/paper/2004.10090/) (2020)
- [Minimizing Quadratic Functions in Constant Time](https://mlsanity.com/paper/1608.07179/) (2016)

## Abstract (arXiv)

In this paper, we study several important geometric optimization problems arising in machine learning. First, we revisit the Minimum Enclosing Ball (MEB) problem in Euclidean space ℝd. The problem has been extensively studied before, but real-world machine learning tasks often need to handle large-scale datasets so that we cannot even afford linear time algorithms. Motivated by the recent studies on em beyond worst-case analysis, we introduce the notion of stability for MEB, which is natural and easy to understand. Roughly speaking, an instance of MEB is stable, if the radius of the resulting ball cannot be significantly reduced by removing a small fraction of the input points. Under the stability assumption, we present two sampling algorithms for computing radius-approximate MEB with sample complexities independent of the number of input points n. In particular, the second algorithm has the sample complexity even independent of the dimensionality d. We also consider the general case without the stability assumption. We present a hybrid algorithm that can output either a radius-approximate MEB or a covering-approximate MEB. Our algorithm improves the running time and the number of passes for the previous sublinear MEB algorithms. Our method relies on two novel techniques, the Uniform-Adaptive Sampling method and Sandwich Lemma. Furthermore, we observe that these two techniques can be generalized to design sublinear time algorithms for a broader range of geometric optimization problems with outliers in high dimensions, including MEB with outliers, one-class and two-class linear SVMs with outliers, k-center clustering with outliers, and flat fitting with outliers. Our proposed algorithms also work fine for kernels.