Convergence rate analysis of proximal iteratively reweighted l1 methods for lp regularization problems

被引：0

作者：

Wang, Hao ^{[1
]}

Zeng, Hao ^{[1
]}

Wang, Jiashan ^{[2
]}

机构：

[1] ShanghaiTech Univ, Sch Informat Sci & Technol, Shanghai, Peoples R China

[2] Univ Washington, Dept Math, Seattle, WA 98195 USA

来源：

OPTIMIZATION LETTERS | 2023年 / 17卷 / 02期

基金：

中国国家自然科学基金; 上海市自然科学基金;

关键词：

Kurdyka-Lojasiewicz property; Iteratively reweighted algorithm; l(p) regularization; Convergence rate; MINIMIZATION; ALGORITHM; NONCONVEX; SPARSITY;

D O I：

10.1007/s11590-022-01907-4

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we focus on the local convergence rate analysis of the proximal iteratively reweighted l(1) algorithms for solving l(p) regularization problems, which are widely applied for inducing sparse solutions. We show that if the KurdykaLojasiewicz property is satisfied, the algorithm converges to a unique first-order stationary point; furthermore, the algorithm has local linear convergence or local sublinear convergence. The theoretical results we derived are much stronger than the existing results for iteratively reweighted l(1) algorithms.

引用

页码：413 / 435

页数：23

共 29 条

[21] SECOND-ORDER METHODS FOR L1 REGULARIZED PROBLEMS IN MACHINE LEARNING
Hansen, Samantha
Nocedal, Jorge
2012 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2012, : 5237 - 5240
[22] Generalized Conjugate Gradient Methods for l1 Regularized Convex Quadratic Programming with Finite Convergence
Lu, Zhaosong
Chen, Xiaojun
MATHEMATICS OF OPERATIONS RESEARCH, 2018, 43 (01) : 275 - 303
[23] On the O(1/t) convergence rate of the alternating direction method with LQP regularization for solving structured variational inequality problems
Bnouhachem, Abdellah
Latif, Abdul
Ansari, Qamrul Hasan
JOURNAL OF INEQUALITIES AND APPLICATIONS, 2016,
[24] Convergence rate analysis of proximal iteratively reweighted ℓ1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _1$$\end{document} methods for ℓp\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _p$$\end{document} regularization problems
Hao Wang
Hao Zeng
Jiashan Wang
Optimization Letters, 2023, 17 (2) : 413 - 435
[25] FIRST-ORDER METHODS FOR PROBLEMS WITH O(1) FUNCTIONAL CONSTRAINTS CAN HAVE ALMOST THE SAME CONVERGENCE RATE AS FOR UNCONSTRAINED PROBLEMS
Xu, Yangyang
SIAM JOURNAL ON OPTIMIZATION, 2022, 32 (03) : 1759 - 1790
[26] Formal convergence analysis on deterministic l1-regularization based mini-batch learning for RBF networks
Liu, Zhaofeng
Leung, Chi-Sing
So, Hing Cheung
NEUROCOMPUTING, 2023, 532 : 77 - 93
[27] CONVERGENCE RATE OF O(1/k) FOR OPTIMISTIC GRADIENT AND EXTRAGRADIENT METHODS IN SMOOTH CONVEX-CONCAVE SADDLE POINT PROBLEMS
Mokhtari, Aryan
Ozdaglar, Asuman E.
Pattathil, Sarath
SIAM JOURNAL ON OPTIMIZATION, 2020, 30 (04) : 3230 - 3251
[28] Subspace Correction Methods for a Class of Nonsmooth and Nonadditive Convex Variational Problems with Mixed L1/L2 Data-Fidelity in Image Processing
Hintermueller, Michael
Langer, Andreas
SIAM JOURNAL ON IMAGING SCIENCES, 2013, 6 (04): : 2134 - 2173
[29] On the O(1/t)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(1/t)$\end{document} convergence rate of the alternating direction method with LQP regularization for solving structured variational inequality problems
Abdellah Bnouhachem
Abdul Latif
Qamrul Hasan Ansari
Journal of Inequalities and Applications, 2016 (1)

← 1 2 3 →