- 基于梯度训练的差分隐私和遗忘的证明
基于凸松弛的框架可以计算形式化的保证(证书),以满足特定预测的 ε=0 隐私保证,或者不依赖于可撤销请求的数据。验证为中心的隐私与撤销保证可用于增加用户信任度,提供针对某些成员推理攻击的鲁棒性的形式化证明,确定可能容易受攻击的记录,并增强当 - ReLU 神经网络的凸松弛在多项式时间内近似全局最优
本文研究了采用权重衰减正则化的两层 ReLU 网络与其凸松弛之间的最优性差距,揭示了在随机训练数据情况下原问题与其松弛之间相对最优性差距可以通过 O (√log n) 的因子进行界定,且应用简单的算法可在多项式时间内解决原非凸问题,此外,在 - ReLU 网络在凸松弛下的表达能力
通过对常用凸松弛方法进行深入研究,我们发现:(i)更高级的松弛方法允许更多单变量函数被精确分析的 ReLU 网络表达,(ii)更精确的松弛方法能够允许指数级规模的解空间编码相同函数的 ReLU 网络,以及(iii)即使使用最精确的单神经元松 - 底秩张量恢复的一阶方法的效率研究:严格互补条件下的张量核范数
使用凸松弛方法,基于张量核范数引入的球形约束最小化来恢复低秩张量,引入张量核范数球的适当严格互补条件下获得重要结果,包括线性收敛速度、低秩解的近似线性运行时间,在非平滑目标函数中类似结果可用于 extragradient 方法,并扩展了先前 - 最优低秩矩阵完成:半定松弛和特征向量分离
通过将低秩矩阵补全问题重新表述为在投影矩阵的非凸集上的凸问题,并实施一个可证明最优的分离分支限界方案,推导出一类新的收敛松弛方法。数值实验表明,相比现有的收敛松弛方法,我们的新型收敛松弛方法将最优性差距降低了两个数量级。此外,我们展示了我们 - 多神经元松驰引导支配界分支定界的完全验证
提出一种结合多神经元松弛和分支定界 (并运用基于 GPU 的优化器) 的神经网络验证器,将先前的优势综合以解决较大和较有挑战性的网络问题,并在多个基准测试中取得最新的最佳结果。
- 通过内存高效的半定规划使验证无关网络实现认证
该论文介绍了一种新的 SDP 算法,利用迭代特征向量方法将其各种操作表达为网络正反向传播。在 MNIST 和 CIFAR-10 数据集上的两个验证矢量网络中,将 L-inf 的验证鲁棒准确性从 1%提高到 88%和从 6%提高到 40%
- AAAI高效的空间鲁棒性认证
本研究提出了一种新的凸松弛方法,用于评估计算机视觉模型对于向量场攻击的鲁棒性,该方法可以为广泛的神经网络验证工具提供证明,实验证明该方法具有较高的效率和可扩展性。
- 稀疏回归的一级凸化
本文提出了一种基于理想 (凸包) 形式的新的计算稀疏回归的强凸松弛方式,采用半定优化问题在扩展空间中求解,具有更强更通用的性能。实验表明,所提出的锥形公式的解可以在几秒钟内求解,且在统计学上的预测精度和解释性上表现更佳。
- 鲁棒主成分分析及其变体的高效优化算法
该论文回顾了现有的优化方法来解决鲁棒 PCA 及其变体。论文讨论了这些方法的优缺点和收敛性,并提出了一些面向多处理器环境下解决大规模问题的新算法框架的可能研究方向。
- PowerModels.jl:用于探索电力流公式的开源框架
本文提出了 PowerModels,这是一个开源平台,旨在比较电力流公式,并使用 Optimal Power Flow 问题的五种不同公式进行了验证和有效性演示。
- 组合惩罚:凸松弛保留了哪些结构?
通过研究支持集上的组合惩罚函数的同质和非同质凸松弛,提出了一种基于凸单调正则化器的自适应估计器,利用集函数的较低组合信封概念和新的支持识别必要条件,得出了支持恢复的新充分条件(发现其紧度不同)。
- 稀疏切割和扩散度量下的近似分层聚类
本文研究了关于层次聚类的成本函数及其 NP 难度,提出了基于逐层递归分割的启发式方法以及基于凸松弛的近似算法,并分析了两者的逼近误差和时间复杂度,讨论了在假设条件下问题的难度。
- 非凸能量松弛的子标记精确方法
本文提出了一种基于函数提升的新型空间连续凸松弛框架,旨在解决多标签问题,与之前提出的基于函数提升的方法相比,本方法基于分段凸近似,因此需要更少的标签;与最近的基于 MRF 的方法相比,本方法在一个空间连续设置中进行,并且显示较少的栅格偏差; - 基于平方和证明的张量主成分分析
研究了一个针对张量主成分分析问题的统计模型,通过基于四次幂和松弛的舍入算法,证明了随机噪声张量的种植向量可以在高概率下被回收,还证明了四次幂和松弛在一定程度下是不起作用的,研究并利用了额外的问题结构来求解我们的平方和松弛。
- 角度同步的最大似然半定松弛的紧致性
本文通过对众多相对相位的测量,给出了一种角度同步方法,提出了在噪声干扰下用 MLE 方法解决该问题的难点,探究在不知道最优条件的情况下,最大似然估计解决角度同步过程的正确性。
- 树状网络上的 AC-Feasibility 问题是 NP - 完全的
本文研究发现基于树状网络的二阶锥松弛是紧的且交流可行性问题是 NP - 难问题。
- 用于符号多项式优化的相对熵松弛
本文介绍一种通过一系列随着规模逐渐增大的相对熵优化问题计算上下界的方法,其关键在于使用相对熵函数提供的一种凸嵌参数解决某些全局非负信号量集的证明。并利用实数代数几何的表示定理,证明我们的下界序列收敛于广泛的符号式程序类的全局最优值。最后,我 - 排列问题的凸松弛
本研究使用优化问题将排序问题表示为组合 2-SUM 问题,使用谱算法和凸松弛解决噪声和半监督排序问题,在考古、Markov 链和 DNA 碎片组装等领域进行了数值实验。
- 凸聚类分裂方法
本文提出两种方法(ADMM 和 AMA)解决凸聚类问题,旨在避免局部最小值问题,提高算法效率。实验结果表明,AMA 相比 ADMM 在复杂度和准确率方面更优。