Jul, 2015

线性反问题的尖锐时间 -- 数据折衷

PDF
TL;DR本文论述了解决线性反问题的优化问题的尖锐时间 - 数据权衡，重点研究了一个最小化普通最小二乘目标的限制条件问题，我们提出了一个统一的收敛分析方法，针对各种随机测量阵列，依据所选择的惩罚函数所对应的结构复杂度，尖锐地表征了收敛速率。结果适用于凸和非凸约束条件，并表明在这些设置中即使最小二乘目标函数不是强凸性，在这些设置中也可以达到线性收敛速率。当我们特定于高斯测量时，我们的结果表明，当测量次数仅是恢复所需信号的最小次数的 4 倍（即所谓的相位转换）时，就会出现这种线性收敛。我们还在相位转换点的上方精确地实现了一个更慢但几何的收敛速率。广泛的数值结果表明，所得到的速率与实际性能完全匹配。
least-squares objectivegradient projection algorithmlinear convergence raterandom measurement ensemblesphase transition
发现论文，激发创造
  • 广义高维线性反问题的几何推断

    该论文提出了一个几何统计分析框架，适用于泛化的不适定线性反问题模型，包括噪声压缩感知、符号向量恢复、迹回归、正交矩阵估计和噪声矩阵完成等特殊情况，提出了可行的计算凸规划方法，用于统计推断，包括估计、置信区间和假设检验。该论文建立了一个理论框架，以表征局部估计收敛速度，并提供统计推断保证，其结果基于局部锥几何和对偶性，并通过高斯宽度和 Sudakov 最小化估计量表征局部切锥的几何。

    Apr, 2014

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

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

    Feb, 2016

  • 稀疏约束下线性反问题的加速投影梯度方法

    本文探讨了使用 l1 惩罚解决几乎稀疏线性逆问题的正则化方法，并提出了一种基于投影梯度方法并使用可变阈值参数的迭代软阈值算法的替代方案。

    Jun, 2007

  • 反演问题中收敛速度与重构精度之间的权衡

    本文旨在探讨如何在迭代算法中通过低维近似来实现更快速的收敛速度，在保证误差率时，本方法可能会牺牲额外的重构误差。

    May, 2016

  • 通过积分二次约束分析优化算法：非强凸问题

    本文提出了一个统一的框架，能够证明广泛使用的迭代一阶优化算法的指数收敛和次指数收敛速率，并展示了该框架对梯度法、近端算法及其加速变体的实用性，同时开发了连续时间对应物，能够分析梯度流和 Nesterov 加速法的连续时间极限。

    May, 2017

  • 高维统计恢复问题的梯度法快速全局收敛

    对于大部分基于凸优化的统计 $M$- 估计器，我们分析了解决这些问题的渐进收敛速度，并在高维框架中工作，我们定义了适当限制的条件，并证明了这些条件适用于各种统计模型，我们的理论保证了项目的概率几何收敛速度不断提高，最高可达到模型的统计精度，这个结果比以往收敛结果更加尖锐，这适用于 $M$- 估计器和各种统计模型，展现了高维估计中统计精度和计算效率的有趣联系。

    Apr, 2011

  • 通过非凸优化破解样本复杂度壁垒的二次测量结构信号恢复

    本文针对 $m<<n$ 的欠定情况，在优化变量上施加先前的结构信息，将恢复问题形式化为非凸优化问题，并证明了在任何不变约束集下，投影梯度下降收敛于未知信号的线性速率，这为此数据贫瘠的场景提供了第一个可证实的算法，为理解约束非凸优化启发了强有力的工具，其数学结果为数据驱动的相位成像系统开辟了一种新的方向。

    Feb, 2017

  • 随机迭代贪婪算法在稀疏约束下的线性收敛

    本文提出了两种基于随机梯度下降方法的可能非凸稀疏约束优化问题的贪心变体算法，证明了在指定容差范围内的期望收敛线性到解决方案。这种普适的框架适用于诸如压缩感知中的稀疏信号恢复、低秩矩阵恢复和协方差矩阵估计等问题，提供具有可证明的收敛保证的方法，通常优于其确定性对应物。我们还分析了仅能近似计算梯度和投影的情况，并证明了这些方法对这些近似是鲁棒的。我们包括许多数字实验，这些实验与理论分析相一致，并在多个不同的设置中展示这些改进。

    Jul, 2014

  • 几乎必然受限凸优化

    我们提出了一种随机梯度框架，用于解决具有（可能）无限数量的线性包含约束条件的随机复合凸优化问题，而这些约束条件需要几乎确定。我们使用平滑和同伦技术处理约束条件，无需矩阵投影，并且通过数值实验表明，我们的算法实现了最先进的实用性能。

    Jan, 2019

  • 生活在边缘：在随机数据的凸性程序中的相变

    通过对随机凸优化问题进行第一次严格分析，本文提出了描述随机凸优化问题中相变现象的工具，以及可靠地预测转变区域位置和宽度的技术，这些技术适用于具有随机测量的正则化线性逆问题、随机不连贯模型下的分离问题以及随机仿射约束锥形程序等；该文还引入了统计维度这一概要参数来说明这一应用结果依赖于锥形几何的基础研究，并且通过展示锥形几何中一系列内固体积集中分布在其上，得到了对于随机旋转锥体和一个固定锥体共享射线的概率的准确上界。

    Mar, 2013