Apr, 2017

关于经验风险最小化的细粒度复杂度：核方法和神经网络

PDF
TL;DR本文研究机器学习中的经验风险最小化方法在核支持向量机、核岭回归和神经网络训练等问题上的计算复杂性，并基于复杂理论假设如强指数时间假设，证明了这些问题的条件难度结果。同时，对于许多非凸学习任务中的主要计算负担 —— 经验损失的梯度计算，也给出了类似的难度结果。
empirical risk minimizationsupervised learningcomputational complexitykernel svmsneural network
发现论文，激发创造
  • 深度人工神经网络中经验风险最小化对一般化误差的分析：在数值求解 Black-Scholes 偏微分方程中克服维数灾难

    探讨深度神经网络假设类上基于经验风险最小化 (ERM) 的新分类和回归算法在高维偏微分方程数值解中克服维数灾难的条件，并说明在多项式时间内只需合适数量的样本即可获得解。

    Sep, 2018

  • 通过二阶方法实现联邦经验风险最小化

    本文提出一种内点法（IPM），用于在联合学习设置下解决一般的经验风险最小化（ERM）问题，展示了每次迭代 IPM 的通信复杂度具有 O（d ^ {3/2}）的上限。

    May, 2023

  • 高维岭回归经验风险最小化的基本限制

    本文首次表征凸形 ERM 在高维广义线性模型推断中的基本统计精度界限，推导出任意损失函数和正则化参数值的紧凑下界，并精确评价了损失函数和正则化参数值的优化调整。

    Jun, 2020

  • 正则化经验风险最小化的分布式块对角逼近方法

    本文提出了一种通过求解对偶问题的分布式经验风险最小化训练框架，可以用于各种机器学习问题，具有全局线性收敛和更快的实证性能。

    Sep, 2017

  • 重新审视差分隐私的经验风险最小化问题：更快且更广泛

    本文研究不同设置下差分隐私经验风险最小化问题，提出了比以前更少的梯度复杂度的算法，并从凸损失函数推广到满足 Polyak-Lojasiewicz 条件的非凸函数，给出比传统算法更紧的上界。

    Feb, 2018

  • 关于平滑数据的经验风险最小化性能

    经验风险最小化算法（ERM）在已知数据集且平滑的情况下，能够实现次线性误差，并且具有统计复杂性的概念。

    Feb, 2024

  • 论经验风险最小化的方差、可接受性和稳定性

    本文研究了 Empirical Risk Minimization 在最小化最大化次优误差率下的偏差和方差分解问题，证明了在偏差方面，ERB 存在明显缺陷。同时，文中探讨了 ERM 的可接受性定理，并扩展到固定设计和随机设计的各种模型中。最后，提出了 ERM 的稳定性，以及一定条件下 ERM 的近似极小化不足的情况。

    May, 2023

  • 统计学习的风险界限

    本文提出一个通用的定理给出经验风险最小化器 (ERM) 风险的上界，并且通过采用一些方便的加权经验过程的浓度不等式扩展 Tsybakov 针对 ERM 风险下边缘条件的分析，以便处理一些测量分类器类 “大小” 的方式，特别地，当分类规则属于某个 VC 类且满足边缘条件时，我们推导出 ERM 的新风险上界，并讨论这些上界在极小化意义下的最优性。

    Feb, 2007

  • 关于具有网络数据的 ERM 原则

    研究网络数据在机器学习中的应用，通过一种通用的风险边界得到一个优化问题，使用带权重的 ERM 可以求解这个优化问题，再通过一种新的全多项式时间近似方案来在非凸情况下解决这个问题。

    Nov, 2017

  • 严格鞍点问题的经验风险最小化的快速速率

    本文研究非凸风险最小化的样本复杂性，并探索了在此上下文中最小化此类功能的有效算法，结果表明这些算法不仅具有统计稳定性，而且具有良好的泛化能力。

    Jan, 2017