PSMGD: Periodic Stochastic Multi-Gradient Descent for Fast Multi-Objective Optimization

📄 arXiv: 2412.10961v2 📥 PDF

作者: Mingjing Xu, Peizhong Ju, Jia Liu, Haibo Yang

分类: cs.LG, cs.AI

发布日期: 2024-12-14 (更新: 2024-12-17)

备注: Accepted to AAAI 2025

💡 一句话要点

提出周期性随机多梯度下降(PSMGD)算法，加速多目标优化。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control) 支柱二：RL算法与架构 (RL & Architecture)

关键词: 多目标优化 梯度下降 随机优化 动态权重 周期性更新

📋 核心要点

  1. 现有多目标优化方法需要计算动态权重，求解额外的优化问题，导致训练时间过长。
  2. PSMGD算法周期性地计算和重复利用动态权重，显著降低了计算开销，加速优化过程。
  3. 实验表明，PSMGD在保证性能的同时，显著减少了训练时间，并具有理论上的收敛性保证。

📝 摘要（中文）

多目标优化(MOO)是许多机器学习(ML)应用的核心，这些应用涉及多个可能冲突的目标(例如，多任务学习、多目标强化学习等)。尽管MOO历史悠久，但近年来，由于许多ML问题中梯度信息的可用性，ML社区对用于MOO的梯度操作算法的开发产生了浓厚的兴趣。然而，现有的MOO梯度操作方法通常训练时间较长，这主要是因为需要通过解决额外的优化问题来计算动态权重，以确定可以同时减少所有目标的公共下降方向。为了解决这个挑战，我们提出了一种新的高效算法，称为周期性随机多梯度下降(PSMGD)，以加速MOO。PSMGD的动机是关键观察，即目标之间的动态权重在优化过程中短时间内的微小更新下表现出很小的变化。因此，我们的PSMGD算法被设计为周期性地计算这些动态权重并重复利用它们，从而有效地减少了计算负担。从理论上讲，我们证明了PSMGD可以实现强凸、一般凸和非凸函数的最新收敛速度。此外，我们引入了一种新的计算复杂度度量，称为反向传播复杂度，并证明PSMGD可以实现与目标无关的反向传播复杂度。通过大量的实验，我们验证了PSMGD可以提供与最先进的MOO算法相当或更优越的性能，同时显著减少训练时间。

🔬 方法详解

问题定义：论文旨在解决多目标优化问题中，现有梯度操作方法训练时间过长的问题。这些方法通常需要通过求解额外的优化问题来计算动态权重，以找到一个能够同时降低所有目标的公共下降方向，计算成本高昂。

核心思路：论文的核心思路是观察到在优化过程中，目标之间的动态权重在短时间内变化不大。因此，可以周期性地计算这些动态权重，并在一段时间内重复使用，从而避免频繁的权重计算，降低计算负担。

技术框架：PSMGD算法的整体框架如下： 1. 初始化模型参数。 2. 周期性地（每隔一定迭代次数）计算动态权重。 3. 在每个周期内，使用相同的动态权重，进行随机多梯度下降。 4. 更新模型参数。 5. 重复步骤2-4，直到收敛。

关键创新：PSMGD的关键创新在于周期性更新动态权重的策略。与每次迭代都重新计算权重的方法相比，PSMGD显著降低了计算复杂度，同时保持了良好的优化性能。此外，论文还提出了一个新的计算复杂度度量，即反向传播复杂度，并证明PSMGD可以实现与目标无关的反向传播复杂度。

关键设计： * 周期性更新频率：周期的选择是一个关键参数，需要根据具体问题进行调整。过短的周期会增加计算开销，过长的周期可能导致权重偏差过大。 * 动态权重计算方法：可以使用现有的梯度操作方法来计算动态权重，例如切比雪夫标量化、梯度范数归一化等。 * 步长选择：需要根据具体问题选择合适的步长，以保证算法的收敛性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，PSMGD算法在多个多目标优化任务上取得了与现有最先进算法相当甚至更优越的性能，同时显著降低了训练时间。具体而言，在某些任务上，PSMGD的训练时间可以减少高达50%。此外，实验还验证了PSMGD的收敛性，并证明了其具有与目标无关的反向传播复杂度。

🎯 应用场景

PSMGD算法可广泛应用于多目标优化的机器学习任务中，例如多任务学习、多目标强化学习、推荐系统等。通过降低训练时间，PSMGD可以加速模型开发和部署，提高资源利用率，并使得在计算资源有限的环境下进行复杂的多目标优化成为可能。该算法的理论分析和实验验证也为多目标优化算法的设计提供了新的思路。

📄 摘要（原文）

Multi-objective optimization (MOO) lies at the core of many machine learning (ML) applications that involve multiple, potentially conflicting objectives (e.g., multi-task learning, multi-objective reinforcement learning, among many others). Despite the long history of MOO, recent years have witnessed a surge in interest within the ML community in the development of gradient manipulation algorithms for MOO, thanks to the availability of gradient information in many ML problems. However, existing gradient manipulation methods for MOO often suffer from long training times, primarily due to the need for computing dynamic weights by solving an additional optimization problem to determine a common descent direction that can decrease all objectives simultaneously. To address this challenge, we propose a new and efficient algorithm called Periodic Stochastic Multi-Gradient Descent (PSMGD) to accelerate MOO. PSMGD is motivated by the key observation that dynamic weights across objectives exhibit small changes under minor updates over short intervals during the optimization process. Consequently, our PSMGD algorithm is designed to periodically compute these dynamic weights and utilizes them repeatedly, thereby effectively reducing the computational overload. Theoretically, we prove that PSMGD can achieve state-of-the-art convergence rates for strongly-convex, general convex, and non-convex functions. Additionally, we introduce a new computational complexity measure, termed backpropagation complexity, and demonstrate that PSMGD could achieve an objective-independent backpropagation complexity. Through extensive experiments, we verify that PSMGD can provide comparable or superior performance to state-of-the-art MOO algorithms while significantly reducing training time.