- 互信息测量的形式限制
本文证明了任何互信息测量方法都有严重的统计限制，证明了从 N 个样本估计的任何分布自由、高置信度的互信息的下限均不能超过 O (ln N)。
- 高维高斯分布在相同均值下之间的总变差距离
对于具有相同均值的两个高维高斯分布，我们证明了其总变差距离的上限和下限，它们相互之间的常数因子差异很小。
- 随机梯度下降法在递减步长下期望收敛速率的紧凑维度无关下限
研究随机梯度下降法（SGD）在强凸目标函数上的收敛性，证明了 ICML 2018 和 2019 提出的降低步长的速率序列在每次迭代后的收敛速度与我们的下限相差不到 32 倍，为最优状态；该下限相较于现有工作大约高出了因子 775×d，其中 - 一般集合和度量的码率失真理论
该论文探讨了一种适用于具有一般分布的随机变量序列的率失真理论，其中包括流形和分形集合，引入了一种下界和一种广泛适用的子规整条件。
- 随机变量函数熵的界限及其应用
本文给出了当函数 f 不是一对一关系时 H (f (X)) 的紧密下界，并且当只知悉极大和极小概率之间比率的限制时，获得了概率分布熵的下界，该下界已经超越了文献中的先前结果，并且它在本文中的几种情形下有实际应用。
- 差分隐私选择的严格下界
该研究提出了一个基于 “指纹” 方法的新的隐私保护选择问题下限界估算，并通过分析实际排除了一些标准假设。
- 三角形计数的混合采样方案
研究在图流中估计三角形数量的问题，提出了一种采样算法，并给出了上下界，以及扩展算法来计数常量尺寸子图。
- Johnson-Lindenstrauss 引理的最优性
给定 $n$ 个 $d$ 维实向量，存在一个嵌入函数将这些向量映射到更低的维度 $m$，满足它保留这些向量之间的欧几里得距离并且它需要的最低维度是 $O (\epsilon^{-2} \log n)$，其中 $\epsilon$ 是距离阈值 - MM近似纳什均衡的通信复杂度
针对二人 NxN 游戏的 epsilon-Nash 均衡和 n 人二元动作游戏的 epsilon 弱近似 Nash 均衡，我们证明了通信复杂度的下限是多项式 N 和指数级 n。
- 强化学习中遗憾下界的研究
本文澄清了强化学习的遗憾下限，提出了一个对于 REGAL 论文中的定理 6 的推测，并提出了一个比 Bartlett 和 Tewari 2009 所提出的更严格的下限。
- 二项随机变量超出其均值的概率下限
本文利用二项式随机变量的平均绝对偏差和尾部条件期望的估计，提供了一个超过其均值的概率的下界。
- ICLR变分自编码框架中的去噪准则
本文研究了对输入和隐层同时进行噪声注入的变分自编码器，提出了一种改进的目标函数。当输入数据有噪声时，传统的变分自编码器的训练方法不可行，这里提出了一种可行的训练方法。实验结果表明，在 MNIST 和 Frey Face 数据集上，提出的去噪 - 关于最佳臂识别的最优样本复杂度
研究最优臂辨识问题，发现新算法和上下限优化，并提出一个新的关于最优样本复杂度的猜想。
- 度为 4 的 SOS 程序中种植团的最紧下界
针对种植团问题，研究了度为 4 的 SOS 松弛的最优解下界，并提出了对 SDP 解的改进方法以得出更紧的下界。
- 纯差分隐私与近似差分隐私之间
该研究通过指定参数 delta 来构建一个全新的下界，从而优化（epsilon，delta）差分隐私算法在高维数据库上精确回答统计查询的样本复杂度。除了新的下界之外，该研究还提出了纯粹和近似的差分隐私算法，用于回答任意统计查询，并通过对比标 - 优化有限和的下界
本文提出了优化 n 个 L-smooth、强凸函数总和的下界，并将其与先前的方法进行比较。在随机数据情况下，我们将这些复杂度结果与用于直接优化总和的最优一阶方法进行对比。研究发现需要谨慎进行准确比较，并确定新方法在机器学习场景中的帮助计算能 - 一般强化学习的样本复杂度
本文提出了一种新的泛化强化学习算法，适用于真实环境属于 N 个任意模型的情况下。该算法被证明在除 O（N log^2 N）步骤之外的大部分情况下都是最优的，并考虑了无限的情况。同时研究表明，紧致性是决定存在统一样本复杂度界限的关键标准，并为 - 二项分布超过期望概率的严格下界
本文研究二项式随机变量超过其期望值的概率的严格下界，该不等式在学习理论中的相对偏差界分析和无界损失函数的泛化界分析等方面具有重要作用。
- 分布式最小割近似
本文通过分布式算法研究了在标准同步消息传递模型下，计算近似的最小边割问题，提出了随机分层技术作为分析随机边采样的一种简单方法，并给出了两个分布式算法的时间复杂度，同时还强化了上一篇研究的下界。
- 消息传递模型下集合不相交的紧密界限
该研究使用信息复杂度工具及时间复杂度分析，证明在传递消息模型中，Sey Disjointness 问题及任务分配问题在最坏情况下的时间复杂度下界为 n*k。