Proximal Newton-type methods for minimizing composite functions
Jason D. Lee111J. Lee and Y. Sun contributed equally to this work. 222Institute for Computational and Mathematical Engineering, Stanford University, Stanford, California. Yuekai Sun111J. Lee and Y. Sun contributed equally to this work. 222Institute for Computational and Mathematical Engineering, Stanford University, Stanford, California. Michael A. Saunders333Department of Management Science and Engineering, Stanford University, Stanford, California.
Abstract
We generalize Newton-type methods for minimizing smooth functions to handle a sum of two convex functions: a smooth function and a nonsmooth function with a simple proximal mapping. We show that the resulting proximal Newton-type methods inherit the desirable convergence behavior of Newton-type methods for minimizing smooth functions, even when search directions are computed inexactly. Many popular methods tailored to problems arising in bioinformatics, signal processing, and statistical learning are special cases of proximal Newton-type methods, and our analysis yields new convergence results for some of these methods.
中文速览
针对生物信息学、信号处理和统计学习中广泛存在的"光滑函数加非光滑正则项"复合优化问题，现有的一阶方法收敛慢，而经典牛顿法又无法直接处理非光滑部分。本文提出了一类"近端牛顿型方法"（proximal Newton-type methods），核心思路是只对光滑部分建立二阶局部二次模型，再通过非光滑部分的近端映射（proximal mapping）求解每步的搜索方向，从而把牛顿法的曲率信息引入复合优化。理论分析证明，即便每步子问题只被近似求解（inexact），只要采用自适应停止准则控制求解精度，整个方法依然能全局收敛，且在最优解附近达到超线性乃至二次收敛速度，与光滑函数上牛顿法的经典结论完全吻合。这一框架统一了glmnet、QUIC、proximal quasi-Newton等众多已有方法，并为它们提供了新的收敛性保证，对大规模稀疏优化问题的算法设计具有重要的理论和实践价值。
原文 arXiv:1206.1623;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1206.1623v13