Feb, 2021

通过鲁棒均匀收敛研究最小绝对偏差回归的查询复杂度

PDF
TL;DR本文提出了一个新框架来分析回归问题中的重要抽样方法，证明了最小绝对偏差回归的查询复杂度为 $\Theta (d/\epsilon^2)$，并拓展了技术来展示任何 $ \ell_p$ 损失（$p\in (1,2)$）的查询复杂度的第一个下界以及引入了鲁棒均匀收敛的概念，建立了统计学习理论和随机优化中方差降低技术之间的新联系。
regressionimportance samplingleast absolute deviationquery complexityuniform convergence
发现论文，激发创造
  • 关于鲁棒线性回归的高效算法及下界

    研究了高维线性回归在对抗性污染下的稳健模型问题，并针对从高斯分布生成的未被修正的样本的基本情况给出了几乎最紧的上界和计算下界。

    May, 2018

  • 近线性时间内的最优鲁棒线性回归

    研究了高维稳健线性回归问题，在受到对抗性破坏的情况下提出了估计方法，包括样本复杂度，恢复保证，运行时间等关键指标，并利用近期算法发展的加速算法和高斯舍入技术等方法来优化估计器的运行时间和统计样本复杂性。

    Jul, 2020

  • 普通最小二乘回归的更快、更好、更坚强的收敛速率

    提出一种基于平均加速正则梯度下降的算法，通过细化初值和 Hessian 矩阵的假设，最优地优化回归问题，并证明其在偏差与方差之间具有最优性、大数据时初始化影响可达到 O（1/n2）以及对于维度 d 的依赖程度为 O（d/n）。

    Feb, 2016

  • 鲁棒线性最小二乘回归

    针对在普通最小二乘法回归中预测的偏差问题，我们提出了一个更好的估算方法 —— 基于截断误差差值的极小 - 极大框架，其期望和差距都为 d/n。

    Oct, 2010

  • 在存在异常值的情况下，鲁棒性经验风险最小化性能的渐近特征

    本文研究高维度的鲁棒线性回归，包括离群值和使用标准损失函数的经验风险最小化（ERMs）方法。结果显示，在相似数据集上，经过最优正则化的 ERM 在大样本复杂性极限下是渐近一致的，但在评估误差方面，由于规范标定的失配，估计器的一致性要求完美计算最优规范的预估值或存在未受离群值污染的交叉验证集。不同的损失函数在最优性能的使用情况下提供了有关使用情况的见解。

    May, 2023

  • 简化 Tight L2 回归的标签复杂度

    提出一种多项式算法，其中通过删除数据点和减少步骤，可以实现与最优解的期望 $(1+d/n)$ 接近度，从而达到在减少标签复杂度的情况下，实现紧密近似。

    May, 2023

  • 最小二乘回归加权平均投影随机梯度下降算法

    探讨使用随机梯度下降的加权迭代平均算法，对确定的不可知参数进行最小二乘回归，分析了其收敛速度和误差，并提出了一种新的算法，取得了更好的性能表现。

    Jun, 2016

  • 基于 Lewis 加权子采样的 L1 回归

    考虑了只观察到少量标签时，寻找 l1 回归的近似解的问题。我们表明，根据其 Lewis 权重对 X 进行采样并输出经验最小化器可在概率 1-δ 下成功地进行，其中 m>O（1/ε²dlog (d/εδ)）。我们还给出了相应的下界。

    May, 2021

  • 高效稀疏最小绝对偏差回归与差分隐私

    本文提出了一种用于稀疏鲁棒回归问题的快速隐私保护学习解决方案，其中学习损失包括鲁棒最小绝对值损失和 $l_1$ 稀疏惩罚项。为了快速解决给定隐私预算下的非光滑损失，我们开发了一种名为 FRAPPE 的算法，通过将稀疏 LAD 问题重新表述为带惩罚的最小二乘估计问题，并采用三阶段噪声注入来保证 $(\epsilon,\delta)$- 差分隐私。实验证明，与现有隐私保护回归算法相比，我们的算法在隐私和统计准确性的权衡上取得了更好的性能。

    Jan, 2024

  • 稳定性和偏差优化风险界的收敛速度为 $O (1/n)$

    研究证明，通过满足所谓的 Bernstein 条件，可以避免高概率广义化界限中的采样误差项，从而实现高概率过量风险边界，我们进而讨论了一些强凸和 Lipschitz 损失的方法。我们展示了任何经验风险最小化方法的 $O (log n/n)$ 高概率过量风险边界，从而解决了 Shalev-Shwartz，Shamir，Srebro 和 Sridharan（2009）的问题。

    Mar, 2021