探讨张量秩的计算复杂性,对任意整环上的张量证明了秩问题与该整环上的多项式方程组问题的多项式时间等价性,同时得出了对称秩和矩阵补全问题的类似结论。
Nov, 2016
证明了在数值线性代数中,许多高效可计算问题的多线性(张量)形式都是 NP 难的。其中包括决定一个双线性方程组的可行性,确定一个三阶张量是否具有给定的特征值,奇异值或谱范数;逼近特征值,特征向量,奇异向量或谱范数;确定三阶张量的秩或最佳秩 - 1 逼近等问题,以及证明了将这些问题限制在对称张量中并不能缓解它们的 NP 难度。通过证明 NP 难性,进一步指出了线性 / 凸问题计算可行性和非线性 / 非凸问题计算可行性之间的边界。
Nov, 2009
通过分析低阶多项式的统计性能,我们得出了一个用户友好的下界,表示任何 D 次多项式可以达到的最佳均方误差。我们进一步研究了低阶多项式在重构估计问题的应用,提供了种植子矩阵和种植稠密子图问题的低阶最小均方误差紧致表征。
Aug, 2020
比较多元多项式函数全局优化算法,证明了使用具有半定规划的平方和松弛技术比代数方法更有效,并为实数代数几何中的广泛计算问题提供了可能性。
Mar, 2001
本研究解决了深度神经网络导函数的最优 Vapnik-Chervonenkis 维度(VC-dimension)和伪维度估计的问题,并将其应用于机器学习方法中涉及函数导数的损失函数的学习误差估计,从而填补了包括物理为基础的机器学习模型和应用程序(例如生成模型、解决偏微分方程、操作学习、网络压缩、提取、正则化等)的学习误差估计的空白。
May, 2023
本研究讨论了如何在任意锥形多项式曲线和给定线性子空间的交集中找到元素。我们提出了一种基于多项式时间的算法来解决这个问题,并将其应用于解决低秩分解问题和量子纠缠问题等相关问题。
Dec, 2022
研究了近似维度和间隔复杂度的概念,这些概念相对于确切表示给定的假设类所需的嵌入的最小维度或范数来近似表示。发现这些概念不仅足以用于使用线性预测器或核进行学习,而且与确切的变体不同,它们也是必要的。因此,它们更适合讨论线性或核方法的限制。
Mar, 2020
本文提出了一种用保守梯度模型来估计算法分化的计算成本的方法,并且较为详细地描述了其在反向传播和前向传播中的应用。主要方法是基于局部 Lipschitz 半代数或可定义基本函数的方法,可以极大地加速了反向传播过程。
Jun, 2022
本文解决了有理单纯形上的多项式函数 f 的计算复杂性问题,证明了对于任意多项式都是 NP 难的,但如果多项式仅依赖于有限个变量,则可以在多项式时间内进行积分。
Sep, 2008
提出一种基于梯度的方法,利用导向高维不确定性量化问题中重要方向,构建函数的岭近似,对于向量值函数来说。该方法最小化近似误差的上界,通过子空间 Poincare 不等式获得。在参数空间配备高斯概率测度的情况下,提供了彻底的数学分析,结果表明,使用函数的梯度可以有效地降低维度。还展示了如何选择函数定域的规范对函数的低维近似有影响。该方法推广了与标量值函数相关联的主动子空间的概念。
Jan, 2018