提出首个针对分数型优化的交替方向乘子法，收敛更快更稳定。
ADMM for Structured Fractional Minimization
- 用ADMM分解问题，结合参数法与二次变换两种变体。
- 理论证明在1/ε³次查询内收敛到ε近似临界点。
- 适合机器学习中带非凸、非光滑项的分数优化任务。
本文研究一类结构化分数最小化问题：分子包含可微函数、简单非凸非光滑函数、凹非光滑函数及线性算子复合的凸非光滑函数；分母为弱凸或其平方根弱凸的连续函数。这类问题广泛存在于机器学习与数据科学中。现有方法多基于次梯度或平滑近端梯度法，常面临收敛慢、数值不稳定的缺陷。本文提出首个专为此类问题设计的交替方向乘子法 { t FADMM}，将原问题分解为线性近端子问题，包含两种变体：使用 Dinkelbach 参数法的 { t FADMM-D} 与使用二次变换法的 { t FADMM-Q}。通过引入新型李雅普诺夫函数，证明 { t FADMM} 在 $/mathcal{O}(1/ε^{3})$ 的预言机复杂度下收敛至 $ε$-近似临界点。在合成与真实数据集上的实验，涵盖稀疏Fisher判别分析、鲁棒夏普比率最小化与鲁棒稀疏恢复，验证了方法的有效性。
原文摘要 · Abstract (English)
This paper considers a class of structured fractional minimization problems. The numerator consists of a differentiable function, a simple nonconvex nonsmooth function, a concave nonsmooth function, and a convex nonsmooth function composed with a linear operator. The denominator is a continuous function that is either weakly convex or has a weakly convex square root. These problems are prevalent in various important applications in machine learning and data science. Existing methods, primarily based on subgradient methods and smoothing proximal gradient methods, often suffer from slow convergence and numerical stability issues. In this paper, we introduce {\sf FADMM}, the first Alternating Direction Method of Multipliers tailored for this class of problems. {\sf FADMM} decouples the original problem into linearized proximal subproblems, featuring two variants: one using Dinkelbach's parametric method ({\sf FADMM-D}) and the other using the quadratic transform method ({\sf FADMM-Q}). By introducing a novel Lyapunov function, we establish that {\sf FADMM} converges to $ε$-approximate critical points of the problem within an oracle complexity of $\mathcal{O}(1/ε^{3})$. Extensive experiments on synthetic and real-world datasets, including sparse Fisher discriminant analysis, robust Sharpe ratio minimization, and robust sparse recovery, demonstrate the effectiveness of our approach. Keywords: Fractional Minimization, Nonconvex Optimization, Proximal Linearized ADMM, Nonsmooth Optimization, Convergence Analysis
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。