第三届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom，IJTCS-FAW）由北京大学讲席教授邓小铁于2020年牵头发起，第三届于2022年8月15日-19日线上线下交互举行。大会由中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）、中国工业与应用数学学会（CSIAM）联合主办，香港城市大学（CityU）承办，北京大学前沿计算研究中心、北京大学人工智能研究院协办。

　　

　　8月18日，本科生分论坛由北京大学本科毕业生李翰禹、香港城市大学李闽溟教授主持。小编为大家带来论坛精彩回顾。

 

 

精彩回顾

　　

Element Distinctness, Birthday Paradox, and 1-out Pseudorandom Graphs

武弘勋，清华大学

 

 

　　输入 n 个取值在0到 m 之间的整数，m≤poly(n)  ，判定其中是否存在两个数相等的计算问题称为元素互异问题（Element Distinctness）。元素互异问题的一个常见算法是对所有元素进行排序，然后比较相邻元素，需要花费 O(nlogn) 的时间和 O(n) 的空间。然而，如果要求仅能使用 S=O(polylogn) 的工作区域，则高效算法不再适用。O(n²) 的枚举法似乎成为了唯一的选择。

　　

　　1988年，Yao et.al 进一步证明了在比较模型（仅允许询问任意两个元素的大小关系）下，该问题的时间复杂度为 \Omega\left(n^{2-o(1)}\right)。然而，在更加一般的 RAM 模型（允许使用随机 oracle 及对数据进行算术运算）下， 武弘勋的最近合作工作证明了存在一个忽略对数因子复杂度为 O\left(n^{1.5}\right) 的算法。他们发现如果能够构建一个种子长度为 O(polylogn) 的哈希函数族来模拟一个 m 个元素之间的有向图，则常用于碰撞寻找的 Pollard-rho 算法很适合用来发现重复元素。关于 Pollard-rho 算法的著名结论生日悖论表明，Pollard-rho 算法从一点出发查询到一个碰撞的期望长度至多为 O\left(n^{0.5}\right)，而任意两个顶点从随机起点被经过的概率至少为 O(1/n) 。这表明，如果能够构造一个恰当的满足 Pollard-rho 条件的哈希函数族，则运行 n 次 Pollard 算法大约消耗 O\left(n^{1.5}\right)  时间，但任意两个顶点都几乎必然被经过，由此我们获得了一个 O\left(n^{1.5}\right) 的随机算法。

　　

　　具体而言，武弘勋和合作者证明了存在一个 O\left(\log n^{3} \log \log n\right) 的哈希函数族可以满足生日悖论的要求，从而解决了这个问题。他们的技术是迭代限制方法，即叠加 O(logn) 层独立的随机函数来构造目标图，以保证其仍然满足生日悖论要求的相互独立性。

　　

　　最后，武弘勋提出了该算法在各个问题上的应用及若干开放问题。这些问题中一部分已经被解决，但是作者指出目前的方法在寻找两组数的碰撞的问题中有本质上的困难，可能需要一些更新的思想来解决这个问题。

　　

Nash Convergence of Mean-Based Learning Algorithms in First Price Auctions

胡欣妍，北京大学

 

 

　　一价拍卖（First Price Auction）常用于在线的广告拍卖中。由于拍卖中信息的不完全性，竞拍者往往使用某些在线学习算法进行出价，这使得动态分析拍卖过程更加困难。然而，胡欣妍的合作工作证明了在某些情况下，如果所有竞拍者均使用基于均值的学习算法，则重复一价拍卖博弈最终能够收敛到纳什均衡。

　　

　　这篇文章的基础假设为：一价拍卖进行无限轮，每次拍卖的物品相同，n 个竞拍者各自具有一个固定估值 v_{i}，每轮每个竞拍者需要给出一个出价 b_{i}^{t}，出价和估值的取值均为一个上界为 V 的非负整数。

　　

　　基于均值的学习算法（Mean-Based Learning）是一类根据前 t-1 轮的信息估算各个出价的收益均值并以低概率出估值较低的出价的算法。很多著名算法，如贪婪算法，ε- 贪婪算法，MWU 算法等都是基于均值的学习算法。

　　

　　目前，收敛到纳什均衡的定义有两类，一类是时间平均（Time-Average）收敛，即竞拍者的经验分布逐渐趋于一个纳什均衡或者竞拍者在重复博弈中出现纳什均衡的概率趋于1；另一类是最终迭代（Last-Iterate）收敛，即各个竞拍者的混合策略最终会收敛的一个纳什均衡。文章对这两种定义下的收敛性均进行了分析。

　　

　　胡欣妍随后介绍了这篇文章的主要定理：假设 M 为估值同时达到最高的人数，则当 M≥2 时，博弈时间平均收敛；当 M≥3 时，博弈最终迭代收敛。否则可能不收敛。证明的主要方法是通过迭代逐次消去被占优的策略，而主要的困难在于学习算法在该定义下的随机性。

　　

　　最后，胡欣妍提出了关于收敛速度和不收敛情况的两个开放问题，并且与观众交流了出价的离散/连续性对该问题的影响。

　　

Towards Data Efficiency in Offline Reinforcement Learning

黄柏贺，北京大学

 

 

　　博弈相关的强化学习一般均使用马尔科夫决策过程作为决策的训练模型。在博弈中，我们可以恰当地定义目标函数，并且研究在不同背景下如何通过高效的学习来接近目标函数的最大期望。

　　

　　黄柏贺首先介绍了该领域的背景。在离线学习中，一个重要问题是给出关于关于ε的倒数的样本复杂度较低的算法，使得智能体的价值函数和价值函数在任意策略上的最大期望小于 ε 。算法的复杂度证明往往需要面对一些挑战，而常用的策略是对算法做一些假设。首先是分布偏移问题，即数据集上训练出的分布和接近目标函数最大期望时的分布并不相同。此时，有多种强弱不同的假设来解决这个问题，例如全策略集中性假设认为训练出的分布和任何分布都比较接近，而单策略集中性假设（Single Policy Concentrability Assumption）则仅仅认为训练出的分布和最大期望分布比较接近。其次是函数集容量问题，即算法的输出策略空间的丰富程度是未知的。此时，现实性假设（Realizability）要求达到最大期望的策略在输出空间中，而完全性假设（Completeness）则要求输出空间对 Bellman 算子是封闭的，此外还有鲁棒性假设等各种假设。

　　

　　随后，他介绍了自己的合作工作。他们给出了一个仅依靠单策略集中性假设和现实性假设的基于规范线性规划方法的算法，达到了 O\left(\varepsilon^{-6}\right) 的采样复杂性，推进了此前依赖更强假设的一个类似结果。

　　

　　最后，他展望了未来的发展。他指出，在不同假设下的算法之间还有若干复杂性的鸿沟等待填补，这将是一个很有价值的问题。

　　

On the Feasibility of Unclonable Encryption, and More

李行健，清华大学

 

 

　　在量子密码学中，不可克隆加密（unclonable cryptography）的目标是利用量子计算对消息进行加密得到密文，并使密文只能被解密一次，即不可克隆。不可克隆安全性由一个实验定义：假设有一个负责执行加密方案的挑战者，拥有密钥 k，还有三个敌手 A, B_{k}, C_{k} 。A 向挑战者发送两个消息 m_{0} 和 m_{1} ，挑战者随机选取 b∈{0,1} ，并用密钥 k 加密 m_{b} ，将密文 E n c_{k}\left(m_{b}\right) 发送给 A 。敌手 B_{k} 和 C_{k} 都知道加密所使用的密钥 k ，不过 A 只能向  B_{k} 和 C_{k} 分别单向地发送信息 \sigma_{B}, \sigma_{C} 。在收到信息之后，B_{k} 和 C_{k} 分别判断 b 是0还是1。如果多项式时间内敌手 B_{k} 和 C_{k} 同时答对的概率不超过 ½  加上一个可忽略小量，那么这个加密方案就称为不可克隆安全。任何经典计算机的加密方案都不可能满足不可克隆安全，因为只要 A 将密文复制成两份分别发送给 B_{k} 和 C_{k} ，B_{k} 和 C_{k} 就可以各自用密钥将密文解密。而量子不可克隆的性质有望帮助不可克隆安全的实现。

　　

　　报告人首先证明了一类加密方案不可能做到不可克隆安全。接着，报告人通过 coset state 构造了基于 quantum random oracle 的不可克隆加密方案。报告人证明了 coset state 的 monogamy of entanglement 性质，并以此证明了不可克隆安全性。报告人还介绍了复制保护（copy protection）问题与不可克隆加密的联系，并给出了一个基于 random oracle 的复制保护算法。

　　

Your Transformer May Not be as Powerful as You Expect

黎善达，北京大学

 

 

　　Transformer 是目前效果最好的一种深度学习模型，被应用于自然语言处理、计算机视觉、图模型处理等领域，在许多著名的深度学习模型中被作为基础架构。

　　

　　报告人首先介绍了 transformer 的结构和工作原理。Transformer 由注意力模块和逐点前馈神经网络两部分组成。报告人指出，由于注意力模块的结果与输入序列的顺序无关，并且逐点前馈神经网络对每个位置独立地进行计算，因此整个 transformer 具有位置不敏感性，将输入序列任意排列都会得到同样的输出。但在实际任务中位置信息是必要的，例如在自然语言处理中，改变单词的先后顺序可以改变一个句子的含义。

　　

　　绝对位置编码（Absolute Positional Encoding, APE）给每个位置设置一个嵌入向量，以区分不同的位置。基于 APE 的 transformer 被证明具有通用近似（universal approximation）能力，能够任意逼近任何序列到序列的函数映射，这意味着它有足够强的表达能力。然而 APE 存在难以泛化到长序列、难以捕捉相对位置关系等缺点。

　　

　　相对位置编码（Relative  Positional Encoding, RPE）通过编码相对位置成功地避免了这些问题，得到了广泛应用。然而，报告人指出，目前基于 RPE 的 transformer 不具备通用近似能力，并构造了序列到序列的连续函数使得基于 RPE 的 transformer 无法近似。报告人分析了通用近似能力对注意力模块的性质要求，并提出了具有通用近似能力的 URPE 结构。

　　

Characterizing Parametric and Convergence Stability in Nonconvex Nonsmooth Optimization

李翰禹，北京大学

 

 

　　报告人考虑了连续函数优化中的非凸非光滑优化问题，介绍了方向可导的函数的稳定点与近似稳定点。稳定点的任意方向导数不小于0，而 δ- 近似稳定点的任意方向导数不小于 -δ。大多数典型的优化算法能够找到函数的任意精度的近似稳定点。稳定点是否对于优化过程具有稳定性将会影响优化的最终结果，因此是一个值得研究的问题。

　　

　　报告人对于函数的稳定点定义了两类稳定性概念：参数稳定性和收敛稳定性。参数稳定性指的是目标函数的数值误差是否会对一个稳定点的位置甚至存在性产生影响。报告人证明任意孤立的局部极小点都满足参数稳定性。收敛稳定性指的是当一个寻找近似稳定点的迭代优化算法经过一个稳定点附近时，最终得到的近似稳定点是否一定能任意接近这个稳定点。报告人证明，如果目标函数能表示成最大值函数与解析映射的有限次复合，那么一个稳定点满足收敛稳定性当且仅当它是一个严格局部极小点。这一结论在光滑函数和凸函数的情况下都自然地成立，但对于非凸非光滑函数却是非平凡的，因为假如条件中的解析映射修改为光滑映射就会存在反例。报告人指出这一结论适用于目前几乎所有神经网络的训练过程，并介绍了有关神经网络训练稳定性的推论。