Title: Multipass Linear Sketches for Geometric LP-Type Problems Show Chinese title

Title: 多遍线性草图用于几何LP类型问题

Abstract: LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinatorial optimization problems, with many important applications in machine learning applications such as classification, bioinformatics, and noisy learning. We study LP-type problems in several streaming and distributed big data models, giving $\varepsilon$-approximation linear sketching algorithms with a focus on the high accuracy regime with low dimensionality $d$, that is, when ${d < (1/\varepsilon)^{0.999}}$. Our main result is an $O(ds)$ pass algorithm with $O(s( \sqrt{d}/\varepsilon)^{3d/s}) \cdot \mathrm{poly}(d, \log (1/\varepsilon))$ space complexity in words, for any parameter $s \in [1, d \log (1/\varepsilon)]$, to solve $\varepsilon$-approximate LP-type problems of $O(d)$ combinatorial and VC dimension. Notably, by taking $s = d \log (1/\varepsilon)$, we achieve space complexity polynomial in $d$ and polylogarithmic in $1/\varepsilon$, presenting exponential improvements in $1/\varepsilon$ over current algorithms. We complement our results by showing lower bounds of $(1/\varepsilon)^{\Omega(d)}$ for any $1$-pass algorithm solving the $(1 + \varepsilon)$-approximation MEB and linear SVM problems, further motivating our multi-pass approach. Show Chinese abstract

Abstract: LP型问题，如最小包围球（MEB）、线性支持向量机（SVM）、线性规划（LP）和半定规划（SDP）是基本的组合优化问题，在机器学习应用中有很多重要的应用，如分类、生物信息学和噪声学习。我们研究了几种流式和分布式大数据模型中的LP型问题，给出了$\varepsilon$-近似线性草图算法，重点放在高精度区域和低维性$d$，即当${d < (1/\varepsilon)^{0.999}}$时。 我们的主要结果是一个$O(ds)$通算法，具有$O(s( \sqrt{d}/\varepsilon)^{3d/s}) \cdot \mathrm{poly}(d, \log (1/\varepsilon))$单词的空间复杂度，对于任何参数$s \in [1, d \log (1/\varepsilon)]$，以解决$\varepsilon$-近似 LP类型问题的$O(d)$组合和VC维。 显然，通过取$s = d \log (1/\varepsilon)$，我们实现了在$d$上多项式空间复杂度和在$1/\varepsilon$上对数多项式空间复杂度，相对于现有算法在$1/\varepsilon$上实现了指数级改进。 我们通过证明任何解决$(1 + \varepsilon)$-近似 MEB 和线性 SVM 问题的$1$-pass 算法的$(1/\varepsilon)^{\Omega(d)}$下界，来补充我们的结果，进一步推动了我们的多轮方法。