快速排序、堆排序和冒泡排序，这些都是计算机中常见的排序算法。在机器学习领域，排序同样被广泛应用于数据统计和信息检索等方面。然而，当涉及到函数的微分问题时，这些排序算法面临挑战，因为它们在某些节点上是不可微的，这给反向传播带来了困难。

谷歌大脑团队近期提出了一种快速可微分排序算法，其时间复杂度为O(nlogn)，空间复杂度为O(n)。这种方法在性能上比现有的方法快了一个数量级。

在现代深度学习架构中，通常通过组合参数化的功能模块来构建模型，并通过梯度反向传播进行端到端的训练。这推动了可微分编程（Differentiable Programming）的发展。尽管取得了显著进展，但一些操作如排序和排名仍然是不可微的，限制了可以计算梯度的系统范围。

为了解决排序和排名的不可微问题，谷歌大脑团队提出了一种方法，即通过在线性规划公式中引入强凸正则化，将其转化为高效的可计算投影算子。这种方法使排序和排名操作变得可微分，并且易于形式分析。

在此基础上，为了实现快速计算和微分，关键步骤是将投影简化为保序优化（Isotonic Optimization）。随后，通过对保序优化进行微分，采用雅可比矩阵（Jacobian）进行分析。最后，结合相关理论推导出投影到排列多面体上的雅可比矩阵。

研究人员在CIFAR-10和CIFAR-100数据集上进行了实验，证明了新算法在精度上与最优传输（Optimal Transport, OT）方法相当，但在速度上明显更快。例如，在CIFAR-100数据集上训练600个周期，OT方法耗时29小时，而新算法仅需21小时至23小时。此外，新算法在处理大规模输入时表现出更好的内存效率。

机器学习工程师Brad Neuberg认为，快速可微分排序和排名算法在机器学习领域具有重要意义。谷歌的这项研究引发了广泛关注，并在Reddit和Hacker News等平台上引起了热烈讨论。有评论指出，可微分排序能够生成更多的梯度信息，加快训练速度，同时也意味着一些基于排名的目标可以通过可微分的方式进行优化，例如在网络搜索和标签分配等领域。

论文链接：https://arxiv.org/pdf/2002.08871.pdf

讨论链接： - https://news.ycombinator.com/item?id=22393790 - https://www.reddit.com/r/MachineLearning/comments/f85yp4/rfastdifferentiablesortingand_ranking/

以上内容是对原文章的改写，确保了信息的准确性和完整性，同时避免了直接引用和过度相似的表达。