数据科学优化挑战：高维问题分布式算法及新方法研究

欧洲计算优化杂志11（2023）100064数据科学中的优化挑战最近在数据科学和机器学习方面的突破和研究激增使优化的基本作用成为最前沿：几乎所有的机器学习模型都可以被视为优化问题的解决方案（从最小化到鞍点和平衡问题），即使机器学习技术在其他领域有其根源，优化也提供了必要的计算骨干，使其可实现。这期特刊的目的是探讨在界面上出现的挑战数据科学，优化和学习理论，特别关注能够使用不精确的问题信息处理高维问题并以分布式和高效方式利用结构的优化算法。本特刊中包含的九项同行评审的研究工作解决了一系列关于这个问题的及时的顶级问题：一阶和二阶方法的不同类型的加速机制，以提高这些算法的效率和可扩展性，利用问题结构，如鞍点问题或非线性支持向量机，提出新的一阶和二阶非凸和凸优化方法（ADMM，Newton-MR，非线性共轭梯度和信赖域方法，具有可证明的全局收敛率并应用于机器学习系统的训练）。此外，几篇论文解决了问题或算法的随机性在作者方面，该特刊代表了领先专家和有前途的早期职业研究人员的主要作品我们已经放弃了根据第一作者的姓名按字母顺序呈现论文，以创建与主题相关的集群，突出所前两篇论文将加速作为获得不同问题类的更快算法的工具https://doi.org/10.1016/j.ejco.2023.1000642192-4406/© 2023作者。由Elsevier Ltd代表欧洲运筹学协会（EURO）出版。这是CC BY许可证下的开放获取文章（creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表欧洲计算优化杂志期刊主页：www.elsevier.com/locate/ejco2数据科学中的优化挑战-特刊编辑通过高效线性代数的支持向量机的训练如下。随后的三篇论文集群解决了分布式优化设置，特定的算法开发与相关的分析和数值。最后，这期特刊以三篇论文结束，这些论文提出了不同阶的方法，用于一般非凸问题，并具有全局收敛速度和复杂性保证，然后将其应用于有限和最小化问题。为了读者Scieur 等 人 [Regularized nonlinear acceleration （ RNA ） ， Adv Neural Inf ProcessSyst，29（2016）]介绍了一种通用的向量序列外推技术，该技术可以加速固定点迭代，并且已经成功地用于加速优化问题的一阶方法，方法是将它们应用于寻找目标梯度的零在本卷题为“直接非线性加速（DNA）“的论文中就像RNA一样，正则化在DNA中也是至关重要的，并且它得到了仔细的解决;还给出了一些关于训练深度神经网络的理论保证和令人鼓舞的数值结果在“Accelerated variance-reduced methods for saddle-point problems”（EkaterinaBorodich ， Vladislav Tominin ， Yaroslav Tominin ， Dmitry Kovalev ， AlexanderGasnikov ， and Pavel Dvurechensky ） 中 所 提 出 的 计 划 享 有 秩 序 最 优 的 复 杂 性guarantees（对数因子）下，典型的光滑性假设的类（强）凸-（强）凹目标。论文它解决了这一挑战的联合建议，既近似的内核使用所谓的分层半可分离的结构，并解决由此产生的二次规划使用ADMM方法。这导致了一个成功的共生，数值实验表明，允许在随后的无矩阵线性代数有效的结构开发在“拜占庭弹性随机梯度下降（SGD）的简化收敛理论”（Lindon Roberts和EdwardSmyth）中- 拜占庭的对手由于这种恶意干扰，标准模型训练方法（如SGD）无法获得令人满意的结 果 ， 这 导 致 Blanchard 等 人 引 入 了 Byzantine 弹 性 SGD [Machine learning withadversaries ： Byzantine tolerant gradient descent ， Adv Neural Inf Process Syst ， 30（2017）]。本文重新考虑了这种初始方法，并大大简化了分析，在非凸目标的标准光滑假设下得到了一组收敛结果。数据科学中的优化挑战论文Uribe和Alexander Gasnikov）研究了实现更快算法的其他模式：分布式计算和预处理，用于解决复合经验风险最小化问题。这两个想法最近已经在Hendrikx等人[Statistically preconditioned accelerated gradientmethod for distributed optimization ，PMLR，119（2020）]中的预处理加速梯度方法（SPAG）中结合起来在这里，提出了一个不精确的SPAG的变体，其中辅助子问题仅近似地在精确的意义上解决，使得随后的方法保持（精确的）SPAG的复杂性。此外，对于一个子类的目标，线性收敛的子问题求解器，并提供了总的计算复杂性的不精确SPAG。令人鼓舞的大规模逻辑回归问题的数值实验。分 散 式 个 性 化 联 邦 学 习 ： 下 限 和 最 优 算 法for all personalization modes“（byAbdurakhmon Sadiev，Ekaterina Borodich，Aleksandr Beznosikov，Darina Dvinskikh，SaveliyChezhegov，RachaelTappenden，MartinTakánov，andAlexanderGasnikov），作者考虑了去中心化、个性化的联邦学习问题。在集中式的情况下，标准的正则化技术会带来显著的通信成本，因此它们很难在去中心化的环境中实现为了解决这个问题，作者提出了一种正则化策略，该策略已被调整到底层计算网络的结构，并且他们提出了所涉及的通信和本地计算成本的下限，以及一种达到这些界限的阶数最优方法（也经过了数值验证）。论文Royer）提出了一种新的非线性共轭梯度法，该方法通过线性收敛条件和修正的重新开始进行了精心设计，使其具有全局收敛速度和最坏情况下的复杂度界.通过与梯度下降法的比较，对后者进行了详细的讨论，作者同样提供了该算法在非线性回归问题上的新成分的有希望的数值说明论文Mahoney）重新研究了不精确的牛顿法这一研究得很好的课题，并得到了令人惊讶的作者提出了一种新的不精确的变体，解决了牛顿方向在最小二乘意义上，从而允许退化的二阶导数被采用和一个更大的类比凸目标，不变凸函数，被认为是。一个深入的分析如下，programat，ING的近似牛顿步骤的性能时，使用MINRES计算，其全局和局部收敛性能比通常的假设下温和。数字-数据科学中的4个优化挑战-特刊编辑在一些机器学习问题上，给出了Newton-MR与最先进的Newton变体的计算比较在贝拉维亚湾古廖利湾Morini和Ph. L. Toint）， 针对目标及其导数的估计受到随机噪声污染的一般非凸目标，提出了一种信赖域算法。该方法使用高次多项式局部模型，涉及这些不精确的评估问题的信息，并被证明能够找到高阶近似最小值（阶数最多的多项式模型的程度），在预期中，在适当的假设和保证的全球范围内的不精确的评估所需的数量详细讨论的噪声水平和approximates-tions和近似的临界性概念之间的相互作用，以及插图上的有限和最小化问题。我们希望读者能够享受这段旅程，通过数据科学中经常出现的崎岖，山脉，有时不确定的优化问题！竞合利益作者声明，他们没有已知的竞争性经济利益或个人关系，可能会影响本文报告的工作。Coralia Cartisa，PanayotisMertikopoulosba数学研究所，牛津大学，伍德斯托克路，牛津，OX2 6GG，联合王国bGrenoble Alpes大学，CNRS，Inria，Grenoble INP，LIG，38000 Grenoble，France电子邮件地址：cartis@maths.ox.ac.uk（C. imag.fr（P. Mertikopoulos）*通讯作者。