证明了近似逻辑回归损失所需空间的下界，揭示现有压缩数据集的最优性。
The Space Complexity of Approximating Logistic Loss
- 建立逻辑回归损失近似问题的空间复杂度下界，基于数据复杂度度量μ
- 在μ为常数时，下界为d/ε²量级，表明现有压缩方法已最优
- 提出高效线性规划算法计算μ，验证了其可行性
本文针对数据矩阵X∈ℝ^{n×d}和标签y∈{−1,1}^d的逻辑回归问题，给出了近似逻辑损失至ε相对误差所需数据结构的空间复杂度下界。现有核心集构造的复杂度依赖于一个自然度量μ_𝐲(𝐗)，首次由Munteanu（2018）定义。当μ_𝐲(𝐗) = O(1)时，我们给出˜Ω(d/ε²)的空间下界，表明现有核心集在此情形下已最优（仅差低阶项）。此外，当ε为常数时，我们证明了˜Ω(d·μ_𝐲(𝐗))的一般下界，说明μ_𝐲(𝐗)的依赖关系并非可合并核心集的产物。最后，我们否定了关于μ_𝐲(𝐗)难以计算的先前猜想，提供了高效的线性规划公式，并与已有近似方法进行实验对比。
原文摘要 · Abstract (English)
We provide space complexity lower bounds for data structures that approximate logistic loss up to $ε$-relative error on a logistic regression problem with data $\mathbf{X} \in \mathbb{R}^{n \times d}$ and labels $\mathbf{y} \in \{-1,1\}^d$. The space complexity of existing coreset constructions depend on a natural complexity measure $μ_\mathbf{y}(\mathbf{X})$, first defined in (Munteanu, 2018). We give an $\tildeΩ(\frac{d}{ε^2})$ space complexity lower bound in the regime $μ_\mathbf{y}(\mathbf{X}) = O(1)$ that shows existing coresets are optimal in this regime up to lower order factors. We also prove a general $\tildeΩ(d\cdot μ_\mathbf{y}(\mathbf{X}))$ space lower bound when $ε$ is constant, showing that the dependency on $μ_\mathbf{y}(\mathbf{X})$ is not an artifact of mergeable coresets. Finally, we refute a prior conjecture that $μ_\mathbf{y}(\mathbf{X})$ is hard to compute by providing an efficient linear programming formulation, and we empirically compare our algorithm to prior approximate methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。