Feb, 2024

学习增强跳表

HTML
PDF
TL;DR通过将机器学习建议整合到跳跃表的设计中，我们改进了传统数据结构设计，并构建了一种能够在几乎两倍内提供最优预期搜索时间的学习增强型跳跃表，即使预估的搜索查询存在误差，该方法依然能够是唯一最优的，而且如果搜索查询符合普遍存在的齐夫分布，那么我们的跳跃表的预期搜索时间只是常数，与项的总数量无关，而传统跳跃表的预期搜索时间则是对数时间。同时，通过实证研究，我们证明了我们的数据结构在合成和真实数据集上均优于传统跳跃表。
发现论文，激发创造
  • 带预测的不确定性下的排序和超图定向

    该论文研究了在不确定性条件下，利用学习增强算法处理排序和超图方向问题，并提出了针对准确和错误预测的性能保证算法，可以通过查询提高不确定性元素的精确度，从而最小化问题求解所需的查询数量。

    May, 2023

  • 带有预测的在线列表标记

    本论文研究了将预测融入 online list labeling 问题中，提出了一种新的数据结构并给出了 worst-case 和 stochastic error 两种模型的保证，以预测误差作为保证的上界，同时在实验中展示了该数据结构在实际应用中的表现。

    May, 2023

  • 关于学习索引的分布依赖子对数查询时间

    本文从理论上证明，在数据分布的温和假设下，具有与非学习方法相同空间复杂度的学习索引可以在期望的 O(loglog n) 查询时间内回答查询，从而进一步巩固了学习索引的实证成功。

    Jun, 2023

  • 从特定到通用的学习排序集字典：在实践中产生具有竞争力的数据结构增强器的理论上可靠的范式

    在机器学习和经典数据结构的交叉领域中，这项研究关注了学习数据结构，这是一个具有重要方法论意义和高实用性影响的新领域。我们提出了一种新的思路，通过对任何排序集合字典进行学习，例如平衡二叉搜索树或其他非排序布局的二分搜索，从而在时间性能上取得了令人印象深刻的提升。

    Sep, 2023

  • 基于预测的排序

    通过学习增强算法的角度探索排序问题，其中算法利用可能存在错误的预测来提高效率。我们考虑了两种不同的情境：在第一种情境中，为每个项目提供了其在已排序列表中的位置预测；在第二种情境中，我们假设存在一种“快速但不精确”的方法来比较项目，除此之外还有慢而准确的比较。对于这两种情境，我们设计了新的简单算法，仅使用O(Σi log ηi)个精确比较，其中ηi是第i个元素的适当定义的预测误差。特别是，随着预测质量的下降，比较次数从O(n)平滑地降低到O(nlogn)。我们证明在所考虑的误差度量方面，比较复杂度在理论上是最优的。与现有的自适应和非自适应排序算法进行的实验评估表明了在排序任务中应用学习增强算法的潜力。

    Nov, 2023

  • 在表格数据上对超参数优化引擎进行系统性研究

    我们在Ray Tune库中对所有可用的超参数优化（hyperopt）引擎进行了独立比较。我们引入了两种方法来归一化和聚合数据集和模型之间的统计数据，一种是基于排名的方法，另一种是将分数夹在随机搜索分数和完整网格搜索分数之间。这使得我们能够：i）对超参数优化引擎进行排名，ii）对其相对于随机搜索的改进程度进行一般化和统计学上显著的说明，iii）对应选择的引擎在超参优化特定学习算法上进行推荐。我们发现大多数引擎都能击败随机搜索，但只有三个引擎（HEBO、AX和BlendSearch）明显突出。我们还发现一些引擎似乎专注于超参优化特定的学习算法，这使得在比较研究中使用超参数优化技术变得棘手，因为超参数优化技术的选择可能对比较中的某些模型有利。

    Nov, 2023

  • 鲁棒学习增强字典

    我们提出了第一个学习增强的数据结构，用于实现拥有最佳一致性和鲁棒性的字典。我们的数据结构名为RobustSL，它是一个带有数据序列中元素访问频率预测的跳表。通过正确的预测，RobustSL可以实现最佳一致性（达到静态最优性）。同时，它保持每个操作的对数运行时间，确保了最佳的鲁棒性，即使预测是针对性生成的。因此，RobustSL具备了Lin、Luo和Woodruff（ICML 2022）以及Cao等人（arXiv 2023）最近提出的学习增强数据结构的所有优点，并提供了先前工作中缺失的鲁棒性保证。数值实验表明，RobustSL在使用合成和真实数据集时优于其他替代数据结构。

    Feb, 2024

  • 具有显式预测器的增强学习算法

    利用机器学习模型从过去和现在的数据中获得的预测，近期算法设计的先进方法已经显示出提高性能的潜力，并在预测失败时提供最坏情况保证，本文研究在线问题，着重于将学习问题与算法挑战相互整合，并设计了专为所需算法任务而量身定制的在线学习算法，通过细致设计的明确学习算法提出了优化总体性能的新算法，并证明了我们方法的潜力通过改进以前研究中建立的性能界限。

    Mar, 2024

  • 梯度下降在可行性问题的 Oracle 复杂度和内存权衡中是帕累托最优的

    在这篇文章中，我们使用具有访问分离预言机的内存受限算法提供了解决给定集合中的点的Oracle复杂性下界，其中集合包含单位d维球体并且含有已知半径ε的球体。我们证明了对于准确度ε≥e^(-d^(o(1)))的可行性问题，任何确定性算法要么使用d^(1+δ) bits的内存，要么至少需要进行1/(d^(0.01δ)ε^(2((1-δ)/(1+1.01δ))-o(1)))次预言机查询，其中δ∈[0,1]。此外，我们还证明了对于随机算法，要么使用d^(1+δ)的内存，要么至少需要进行1/(d^(2δ)ε^(2(1-4δ)-o(1)))次查询，其中δ∈[0,1/4]。由于梯度下降算法仅使用线性的内存O(dln(1/ε))，但进行Ω(1/ε^2)次查询，我们的结果表明它在Oracle复杂性/内存权衡中是帕累托最优的。此外，我们的结果表明，如果算法在d维中具有小于二次的内存，则确定性算法的Oracle复杂性总是多项式级别的1/ε。这揭示了一个明显的相变，因为对于二次的O(d^2ln(1/ε))内存，割平面方法仅需要O(dln(1/ε))的查询次数。

    Apr, 2024

  • 发现数据结构：最近邻搜索及其他

    本文提出了一种用于端到端学习数据结构的通用框架，能够适应底层数据分布，并对查询和空间复杂度进行精细控制。我们的框架通过从零开始学习数据结构，解决了最近邻搜索的问题，发现了多维数据中的有效结构，具有广泛的应用潜力。

    Nov, 2024