针对过参数化问题，提出新方法实现复合优化的线性收敛。
Preconditioned subgradient method for composite optimization: overparameterization and fast convergence
- 引入Levenberg-Morisson-Marquardt改进子梯度法
- 在弱正则条件下实现线性收敛，速率仅由凸函数决定
- 适用于矩阵感知、张量分解等实际问题
复合优化问题涉及最小化光滑映射与凸函数的复合。此类目标出现在相位恢复、盲解卷积和协同过滤等多种数据科学与信号处理应用中。当复合损失条件良好时，子梯度法可实现局部线性收敛；但若光滑映射在某种意义上条件不佳或过参数化，即使凸函数条件良好，子梯度法仍呈现较慢的次线性收敛。为克服此限制，本文提出一种Levenberg-Morisson-Marquardt子梯度法，在温和正则条件下可实现线性收敛，且收敛速率仅取决于凸函数。我们进一步证明，若干实际问题（如平方变量形式、矩阵感知、张量分解）满足这些正则条件。数值实验验证了该方法的优势。
原文摘要 · Abstract (English)
Composite optimization problems involve minimizing the composition of a smooth map with a convex function. Such objectives arise in numerous data science and signal processing applications, including phase retrieval, blind deconvolution, and collaborative filtering. The subgradient method achieves local linear convergence when the composite loss is well-conditioned. However, if the smooth map is, in a certain sense, ill-conditioned or overparameterized, the subgradient method exhibits much slower sublinear convergence even when the convex function is well-conditioned. To overcome this limitation, we introduce a Levenberg-Morrison-Marquardt subgradient method that converges linearly under mild regularity conditions at a rate determined solely by the convex function. Further, we demonstrate that these regularity conditions hold for several problems of practical interest, including square-variable formulations, matrix sensing, and tensor factorization. Numerical experiments illustrate the benefits of our method.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。