提出一种新优化方法，能有效降低最坏情况下的约束违反，适用于多种科学计算场景。
Discrete Optimization of Min-Max Violation and its Applications Across Computational Sciences
- 将最坏情况约束违反最小化建模为离散优化问题，不依赖具体应用场景。
- 在语言模型量化中平均提升14%，断层成像重建误差降16%，滤波器纹波减少近50%。
- 基于GPU加速的启发式算法，适合需要强鲁棒性的工程与科研应用。
我们引入离散最小-最大违规（DMMV）作为通用优化问题，旨在通过离散变量赋值最小化最大约束违规。该无上下文数学形式适用于具有最坏情况性能要求的广泛场景。定义后，我们分析其性质以建立基础理解。为解决实际规模的DMMV实例，我们开发了一种利用其数学特性的GPU加速启发式算法。通过三个用例验证：（1）语言模型后训练量化，（2）离散断层成像，（3）有限冲激响应（FIR）滤波器设计。在无异常分离的量化中，平均性能优于现有方法14%；在均匀噪声下，断层成像重建误差降低16%，GPU加速达6倍；对于滤波器设计，相比商用整数优化求解器Gurobi，几乎实现50%纹波减少。结果表明研究无上下文的DMMV问题及其启发式算法的价值。代码已开源，供进一步研究。
原文摘要 · Abstract (English)
We introduce the Discrete Min-Max Violation (DMMV) as a general optimization problem which seeks an assignment of discrete values to variables that minimizes the largest constraint violation. This context-free mathematical formulation is applicable to a wide range of use cases that have worst-case performance requirements. After defining the DMMV problem mathematically, we explore its properties to establish a foundational understanding. To tackle DMMV instance sizes of practical relevance, we develop a GPU-accelerated heuristic that takes advantage of the mathematical properties of DMMV for speeding up the solution process. We demonstrate the versatile applicability of our heuristic by solving three optimization problems as use cases: (1) post-training quantization of language models, (2) discrete tomography, and (3) Finite Impulse Response (FIR) filter design. In quantization without outlier separation, our heuristic achieves 14% improvement on average over existing methods. In discrete tomography, it reduces reconstruction error by 16% under uniform noise and accelerates computations by a factor of 6 on GPU. For FIR filter design, it nearly achieves 50% ripple reduction compared to using the commercial integer optimization solver, Gurobi. Our comparative results point to the benefits of studying DMMV as a context-free optimization problem and the advantages that our proposed heuristic offers on three distinct problems. Our GPU-accelerated heuristic will be made open-source to further stimulate research on DMMV and its other applications. The code is available at https://anonymous.4open.science/r/AMVM-5F3E/
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。