通过噪声、凸性和零阶优化等概念，研究在有界凸集合中的一类函数的优化问题，我们提出了一个基于质心方法的改进算法，证明其相对于最小值的差距的阶数小于 d^2/√n，且比现有文献中已知的 d^{2.5}/√n 的速度更快，并且更简化。

Jun, 2024

该论文采用压缩感知框架和随机抽样技术，证明在一定光滑程度和变化的前提下，对于定义在单位球上的连续函数 f，其任意的矩阵 A 选择和采样点的随机分布可以生成具有多项式时间复杂度的统一的逼近函数。

Aug, 2010

本文探讨了一种基于函数评估的平滑函数全局最小化方法，通过使用无穷次平方平滑函数之和联合建模函数以逼近并寻找全局最小值，在时间多项式子采样的情况下，该方法的计算复杂性为 $O (n^{3.5})$，空间复杂性为 $O (n^2)$，并可以实现与全局最优解的收敛速度为 $O (n^{-m/d + 1/2 + 3/d})$，尤其适用于具有大量导数的函数，且在维数为 $m$ 的情况下，全局最优解的收敛速度不会受到 “维度诅咒” 的影响，而仅受到最坏情况下的特定常数影响。

Dec, 2020

本文介绍了解决低秩线性系统的古典次线性时间算法。我们的算法受 HHL 量子算法解决线性系统和 Tang 去量子化推荐系统量子算法的最新突破的启发。我们提出了两种算法：提供 $A^{-1} b$ 样本的 “采样” 算法和输出 $A^{-1} b$ 条目的估计值的 “查询” 算法。我们考虑的算法的时间复杂度是次线性时间的。

Nov, 2018

算法设计为在欧几里得或单纯形域内最小化 max (f_i (x))，若每个 f_i 为 1-Lipschitz 和 1 - 光滑函数，我们的方法可以在评价复杂度中找到 ε- 近似解，并具有优化性能。

Nov, 2023

本文提出了一种在椭圆域上求解一般二次函数最大化问题的近似算法，时间复杂度为线性，能获得 ϵ- 近似解，与 Nesterov 的加速梯度下降算法和 Lanczos 方法的运行时相匹配。

Jan, 2014

本文提出基于 primal-dual coordinate 方法，并应用于解决包含线性规划、分类和回归问题的双线性鞍点问题。通过设计高效的数据结构和低方差梯度估计器，我们获得了近乎恒定的每次迭代复杂度，并且在采样复杂度上实现了改进。同时，我们应用该方法到最小圆覆盖，最大内接圆和线性回归的计算几何问题中，并获得了改善的计算复杂度。

Sep, 2020

提出了一种随机优化算法，通过块坐标下降方法和矩阵草图技术，在线性系统中实现了良好的收敛性能和快速迭代时间。

Dec, 2023

本研究对矩阵进行草图，着重探讨了矩阵的不同类型和查询所需的精度。特别地，我们尤其关注了具有特殊特性的正半定矩阵和图拉普拉斯矩阵，为其设计了更优秀的草图，并探讨了草图的实际应用。

Nov, 2015

该研究考虑了通过时间域采样来计算 $N$ 长度信号的 $k$- 稀疏傅里叶变换近似的问题，提出了一种基于随机化算法的解决方案。

Apr, 2016