arXiv:2410.01979math.OCcs.LG2024-10被引 8

新方法无需线搜索即可自适应求解双线性鞍点问题,提升效率与稳定性。

Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers

  • 通过历史迭代自适应估计算子范数,实现无需线搜索的自调节优化
  • 在双线性鞍点问题上达到最优复杂度,收敛速度不受算子范数影响
  • 适用于带约束分解结构的问题,特别适合对角占优或部分矩阵已知场景

线搜索常用于双线性鞍点问题的原始对偶方法,尤其当线性算子范数大或难以计算时。本文提出一种新型原始对偶方法——自调节原始对偶混合梯度(AC-PDHG),证明线搜索并非必要,且在双线性鞍点问题中可达到最优复杂度。该方法完全自适应于线性算子,仅利用历史迭代信息估计其范数。我们进一步将AC-PDHG扩展至线性约束问题,同时保证最优性间隙和约束违反度的收敛性。针对目标函数与约束均可分解为两部分的特殊情形,结合AC-PDHG设计思想,提出自调节交替方向乘子法(AC-ADMM),其收敛性仅依赖于约束矩阵的一部分,并完全自适应该部分,无需线搜索。最后,我们将AC-PDHG与AC-ADMM推广至含额外光滑项的双线性问题,通过引入新颖加速方案,在单预言机设置下达到最优迭代复杂度。

原文摘要 · Abstract (English)

Line search procedures are often employed in primal-dual methods for bilinear saddle point problems, especially when the norm of the linear operator is large or difficult to compute. In this paper, we demonstrate that line search is unnecessary by introducing a novel primal-dual method, the auto-conditioned primal-dual hybrid gradient (AC-PDHG) method, which achieves optimal complexity for solving bilinear saddle point problems. AC-PDHG is fully adaptive to the linear operator, using only past iterates to estimate its norm. We further tailor AC-PDHG to solve linearly constrained problems, providing convergence guarantees for both the optimality gap and constraint violation. Moreover, we explore an important class of linearly constrained problems where both the objective and constraints decompose into two parts. By incorporating the design principles of AC-PDHG into the preconditioned alternating direction method of multipliers (ADMM), we propose the auto-conditioned alternating direction method of multipliers (AC-ADMM), which guarantees convergence based solely on one part of the constraint matrix and fully adapts to it, eliminating the need for line search. Finally, we extend both AC-PDHG and AC-ADMM to solve bilinear problems with an additional smooth term. By integrating these methods with a novel acceleration scheme, we attain optimal iteration complexities under the single-oracle setting.

优化算法原始对偶方法自适应收敛性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。