为GPU加速的线性规划求解器提供可推广的超参调优方法
Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming
- 基于PDHG算法，建立步长与权值的样本复杂度理论
- 通过结构分析获得多项式样本复杂度，支持数据驱动调参
- 适合需高性能优化求解的工程与科研人员参考
近期研究已开发出适用于大规模线性规划的实用并行一阶方法，但其性能高度依赖超参数选择。本文针对面向现代硬件设计的先进一阶LP求解器（cu）PDLP，推导了超参数调优的泛化保证。首先，将PDHG（原-对偶混合梯度）算法的行为建模为步长和原始权重的函数，获得学习这些参数的线性样本复杂度保证。接着，对PDLP进行结构分析，该算法在PDHG基础上引入预条件、自适应步长、平均、自适应重启及平滑原始权重更新等技术。我们的分析揭示了解轨迹随超参数变化的规律，并借助数据驱动算法设计的新进展，实现了学习这些超参数的多项式样本复杂度保证。最后，通过概念验证实验展示了数据驱动调参的必要性。结果表明，该工具包可为复杂现代优化算法的求解器级实现提供有理论保障的超参数调优方法。
原文摘要 · Abstract (English)
Recent research has developed practical, parallelizable first-order methods for large scale linear programming, but performance is highly dependent on hyperparameter selection. We derive generalization guarantees for hyperparameter tuning within (cu)PDLP, a state-of-the-art first-order LP solver designed for modern hardware. First, we pin down the behavior of PDHG, the primal-dual hybrid gradient algorithm that underlies PDLP, as a function of its step size and primal weight, leading to linear sample complexity guarantees for learning those parameters. We then conduct a structural analysis of PDLP, which augments PDHG with several specialized techniques like preconditioning, adaptive step sizes, averaging, adaptive restarts, and smoothed primal weight updates. Our analysis captures the behavior of the solution trajectory as a function of the hyperparameters and leverages recent advances in data-driven algorithm design to obtain polynomial sample complexity guarantees for learning those hyperparameters. Finally, we conduct proof-of-concept experiments that demonstrate the need for data-driven PDLP parameter tuning. Our results showcase the versatility of the data-driven algorithm design toolkit for principled hyperparameter tuning within solver-grade implementations of complex modern optimization algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。