新算法将计算时间缩短数个数量级
成千上万的优化问题（从所有可行解中寻找最优解）如分配资金到股票以最小化回报风险、分配员工到办公室以最大化工作流和员工统计，严重依赖顺序算法。
这些算法的基本工作模式自1970年代初建立以来未曾改变（增强）。它们按“n”个步骤顺序求解特定问题。
步骤数取决于问题规模（为算法提供特定输入值）。这种方法通常导致计算瓶颈。随着算法推进，每次迭代的相对收益越来越小。
如果算法能跳跃几步，而不是走数千小步求解问题，会怎样？如果我们能让当今广泛使用的算法呈指数级加速？我们谈论的是帮助我们发现新药、避免拥堵的算法。
为实现这一目标，哈佛大学研究人员提出一种新型算法，称为“突破”，它通过大幅减少求解问题所需的迭代次数，呈指数级加速计算。
它在信息提取、拍卖设计、机器视觉、计算生物学、网络分析等多个领域的广泛问题上加速计算。
据开发者称，它能在几秒内完成以前需数天或数周的大规模计算。这为大规模并行化方法打开大门，使大规模实用摘要过程成为可能。
工作原理
顺序算法通过一次一步缩小可行解数量。而新算法并行采样不同方向，淘汰不相关方向，选择最有利（高价值）方向逼近解。它选择性丢弃未来迭代中将被忽略的值。
突破算法使用自适应采样，需要O(log n)顺序步骤，达到任意接近1/3的近似。启用并行化时，算法以指数级速度达到子模块化最大化的常数因子近似，快于任何现有方法。
例如，若任务是推荐类似《星球大战》的电影，传统算法每步添加一部具有相似属性（动作、冒险、奇幻）的电影。
新算法随机采样一组电影，剪枝与《星球大战》完全不匹配的。这给出多样化的电影集合（显然不想要10部超人电影）且类似《星球大战》。
算法继续在每步添加多样电影，直到有足够推荐项。在每步做出有价值决策的关键在于自适应采样过程。
测试与应用
研究人员在包含6000用户对4000部电影的100万评分的大型数据集上测试自适应采样算法。它成功为个人推荐个性化、多样化电影，速度比传统算法快20倍。
他们还将此算法应用于出租车调度问题——选择最佳位置用有限出租车服务最多客户。对于200万出租车行程，算法比最先进方法快6倍。
它在社交媒体分析或基因数据聚类等大规模数据集上能产生更好结果。此外，算法可用于开发多疾病临床试验、医学成像传感器阵列、药物相互作用检测。
如今，从数百万图像/视频中寻找有效子集训练深度学习网络已成挑战。此研究可帮助快速提取有价值子集，对大规模数据摘要问题有重大影响。
工业技术