检索结果-内蒙古大学图书馆

A proximal algorithm with backtracked extrapolation for a class of structured fractional programming

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS 2022年 56卷 98-122页

作者： Li, Qia Shen, Lixin Zhang, Na Zhou, Junpeng Sun Yat Sen Univ Sch Comp Sci & Engn Guangdong Prov Key Lab Computat Sci Guangzhou 510275 Peoples R China Syracuse Univ Dept Math Syracuse NY 13244 USA South China Agr Univ Coll Math & Informat Dept Appl Math Guangzhou 510642 Peoples R China Sun Yat Sen Univ Sch Comp Sci & Engn Guangzhou 510275 Peoples R China

In this paper, we consider a class of structured fractional minimization problems where the numerator part of the objective is the sum of a convex function and a Lipschitz differentiable (possibly) nonconvex function, while the denominator part is a convex function. By exploiting the structure of the problem, we propose a first-order algorithm, namely, a proximal-gradient-subgradient algorithm with backtracked extrapolation (PGSA_BE) for solving this type of optimization problem. It is worth pointing out that there are a few differences between our backtracked extrapolation and other popular extrapolations used in convex and nonconvex optimization. One of such differences is as follows: if the new iterate obtained from the extrapolated iteration satisfies a backtracking condition, then this new iterate will be replaced by the one generated from the non-extrapolated iteration. We show that any accumulation point of the sequence generated by PGSA_BE is a critical point of the problem regarded. In addition, by assuming that some auxiliary functions satisfy the Kurdyka-Lojasiewicz property, we are able to establish global convergence of the entire sequence, in the case where the denominator is locally Lipschitz differentiable, or its conjugate satisfies the calmness condition. Finally, we present some preliminary numerical results to illustrate the efficiency of PGSA_BE. (c) 2021 Elsevier Inc. All rights reserved.

关键词： Fractional programming proximal algorithm Backtracked extrapolation Sparse recovery

来源：评论

学校读者我要写书评

暂无评论

A Second-Order proximal algorithm for Consensus Optimization

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2021年第4期66卷 1864-1871页

作者： Wu, Xuyang Qu, Zhihai Lu, Jie ShanghaiTech Univ Sch Informat Sci & Technol Shanghai 201210 Peoples R China

We develop a distributed second-order proximal algorithm, referred to as SoPro, to address in-network consensus optimization. The proposed SoPro algorithm converges linearly to the exact optimal solution, provided that the global cost function is locally restricted strongly convex. This relaxes the standard global strong convexity condition required by the existing distributed optimization algorithms to establish linear convergence. In addition, we demonstrate that SoPro is computation- and communication-efficient in comparison with the state-of-the-art distributed second-order methods. Finally, extensive simulations illustrate the competitive convergence performance of SoPro.

关键词： Convergence Cost function Lagrangian functions Couplings Machine learning algorithms Machine learning Consensus optimization distributed optimization proximal algorithm second-order method

来源：评论

学校读者我要写书评

暂无评论

Sparse nonnegative tensor decomposition using proximal algorithm and inexact block coordinate descent scheme

引用

NEURAL COMPUTING & APPLICATIONS 2021年第24期33卷 17369-17387页

作者： Wang, Deqing Chang, Zheng Cong, Fengyu Dalian Univ Technol Fac Elect Informat & Elect Engn Sch Biomed Engn Dalian 116024 Peoples R China Univ Jyvaskyla Fac Informat Technol Jyvaskyla 40100 Finland Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Peoples R China Dalian Univ Technol Fac Elect Informat & Elect Engn Sch Artificial Intelligence Dalian 116024 Peoples R China Dalian Univ Technol Key Lab Integrated Circuit & Biomed Elect Syst Dalian 116024 Peoples R China

Nonnegative tensor decomposition is a versatile tool for multiway data analysis, by which the extracted components are nonnegative and usually sparse. Nevertheless, the sparsity is only a side effect and cannot be explicitly controlled without additional regularization. In this paper, we investigated the nonnegative CANDECOMP/PARAFAC (NCP) decomposition with the sparse regularization item using l(1)-norm (sparse NCP). When high sparsity is imposed, the factor matrices will contain more zero components and will not be of full column rank. Thus, the sparse NCP is prone to rank deficiency, and the algorithms of sparse NCP may not converge. In this paper, we proposed a novel model of sparse NCP with the proximal algorithm. The subproblems in the new model are strongly convex in the block coordinate descent (BCD) framework. Therefore, the new sparse NCP provides a full column rank condition and guarantees to converge to a stationary point. In addition, we proposed an inexact BCD scheme for sparse NCP, where each subproblem is updated multiple times to speed up the computation. In order to prove the effectiveness and efficiency of the sparse NCP with the proximal algorithm, we employed two optimization algorithms to solve the model, including inexact alternating nonnegative quadratic programming and inexact hierarchical alternating least squares. We evaluated the proposed sparse NCP methods by experiments on synthetic, real-world, small-scale, and large-scale tensor data. The experimental results demonstrate that our proposed algorithms can efficiently impose sparsity on factor matrices, extract meaningful sparse components, and outperform state-of-the-art methods.

关键词： Tensor decomposition Nonnegative CANDECOMP PARAFAC decomposition Sparse regularization proximal algorithm Inexact block coordinate descent

来源：评论

学校读者我要写书评

暂无评论

On the convergence of the proximal algorithm for nonsmooth functions involving analytic features

引用

MATHEMATICAL PROGRAMMING 2009年第1-2期116卷 5-16页

作者： Attouch, Hedy Bolte, Jerome Univ Montpellier 2 CNRS I3M UMR 5149 F-34095 Montpellier France Univ Paris 06 Equipe Combinatoire & Optimisat UMR 7090 F-75252 Paris 05 France

We study the convergence of the proximal algorithm applied to nonsmooth functions that satisfy the Lojasiewicz inequality around their generalized critical points. Typical examples of functions complying with these conditions are continuous semialgebraic or subanalytic functions. Following Lojasiewicz's original idea, we prove that any bounded sequence generated by the proximal algorithm converges to some generalized critical point. We also obtain convergence rate results which are related to the flatness of the function by means of Lojasiewicz exponents. Apart from the sharp and elliptic cases which yield finite or geometric convergence, the decay estimates that are derived are of the type O(k(-s)), where s is an element of (0, + infinity) depends on the flatness of the function.

关键词： proximal algorithm Lujasiewicz inequality subanalytic functions

来源：评论

学校读者我要写书评

暂无评论

An accelerated proximal algorithm for regularized nonconvex and nonsmooth bi-level optimization

引用

MACHINE LEARNING 2023年第5期112卷 1433-1463页

作者： Chen, Ziyi Kailkhura, Bhavya Zhou, Yi Univ Utah Elect & Comp Dept 50 Cent Campus Dr 2110 Salt Lake City UT 84112 USA Lawrence Livermore Natl Lab 7000 East Ave Livermore CA 10587 USA

Many important machine learning applications involve regularized nonconvex bi-level optimization. However, the existing gradient-based bi-level optimization algorithms cannot handle nonconvex or nonsmooth regularizers, and they suffer from a high computation complexity in nonconvex bi-level optimization. In this work, we study a proximal gradient-type algorithm that adopts the approximate implicit differentiation (AID) scheme for nonconvex bi-level optimization with possibly nonconvex and nonsmooth regularizers. In particular, the algorithm applies the Nesterov's momentum to accelerate the computation of the implicit gradient involved in AID. We provide a comprehensive analysis of the global convergence properties of this algorithm through identifying its intrinsic potential function. In particular, we formally establish the convergence of the model parameters to a critical point of the bi-level problem, and obtain an improved computation complexity (O) over tilde(?(3.5)e(-2))over the state-of-the-art result. Moreover, we analyze the asymptotic convergence rates of this algorithm under a class of local nonconvex geometries characterized by a Lojasiewicz-type gradient inequality. Experiment on hyper-parameter optimization demonstrates the effectiveness of our algorithm.

关键词： Bilevel optimization Nesterov's momentum Nonconvex regularization proximal algorithm

来源：评论

学校读者我要写书评

暂无评论

Dual Consensus proximal algorithm for Multi-Agent Sharing Problems

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2021年 69卷 5568-5579页

作者： Alghunaim, Sulaiman A. Lyu, Qi Yan, Ming Sayed, Ali H. Kuwait Univ Dept Elect Engn Kuwait 13060 Kuwait Michigan State Univ MSU Dept Computat Math Sci & Engn E Lansing MI 48824 USA Michigan State Univ MSU Dept ofMathemat E Lansing MI 48824 USA Ecole Polytech Fed Lausanne Sch Engn CH-1015 Lausanne Switzerland

This work considers multi-agent sharing optimization problems, where each agent owns a local smooth function plus a non-smooth function, and the network seeks to minimize the sum of all local functions plus a coupling composite function (possibly non-smooth). For this non-smooth setting, centralized algorithms are known to converge linearly under certain conditions. On the other hand, decentralized algorithms have not been shown to achieve linear convergence under the same conditions. In this work, we propose a decentralized proximal primal-dual algorithm and establish its linear convergence under weaker conditions than existing decentralized works. Our result shows that decentralized algorithms match the linear rate of centralized algorithms without any extra condition. Finally, we provide numerical simulations that illustrate the theoretical findings and show the advantages of the proposed method.

关键词： Convergence Signal processing algorithms Couplings Sparse matrices Machine learning algorithms Topology Symmetric matrices Multi-agent optimization sharing problem dual consensus proximal algorithm linear convergence

来源：评论

学校读者我要写书评

暂无评论

Interior proximal algorithm for Quasiconvex Programming Problems and Variational Inequalities with Linear Constraints

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2012年第1期154卷 217-234页

作者： Brito, Arnaldo S. da Cruz Neto, J. X. Lopes, Jurandir O. Roberto Oliveira, P. Univ Fed Rio de Janeiro Rio De Janeiro Brazil COPPE Sistemas Univ Fed Rio de Janeiro Rio De Janeiro Brazil

In this paper, we propose two interior proximal algorithms inspired by the logarithmic-quadratic proximal method. The first method we propose is for general linearly constrained quasiconvex minimization problems. For this method, we prove global convergence when the regularization parameters go to zero. The latter assumption can be dropped when the function is assumed to be pseudoconvex. We also obtain convergence results for quasimonotone variational inequalities, which are more general than monotone ones.

关键词： Quasiconvex function proximal algorithm Quasiconvex linearly constrained problems Variational inequalities Quasimonotone operator

来源：评论

学校读者我要写书评

暂无评论

Improved dimension dependence of a proximal algorithm for sampling 36

Improved dimension dependence of a proximal algorithm for sa...

引用

36th Annual Conference on Learning Theory (COLT)

作者： Fan, Jiaojiao Yuan, Bo Chen, Yongxin Georgia Inst Technol Atlanta GA 30332 USA

We propose a sampling algorithm that achieves superior complexity bounds in all the classical settings (strongly log-concave, log-concave, Logarithmic-Sobolev inequality (LSI), Poincare inequality) as well as more general settings with semi-smooth or composite potentials. Our algorithm is based on the proximal sampler introduced in Lee et al. (2021). The performance of this proximal sampler is determined by that of the restricted Gaussian oracle (RGO), a key step in the proximal sampler. The main contribution of this work is an inexact realization of RGO based on approximate rejection sampling. To bound the inexactness of RGO, we establish a new concentration inequality for semi-smooth functions over Gaussian distributions, extending the well-known concentration inequality for Lipschitz functions. Applying our RGO implementation to the proximal sampler, we achieve state-of-the-art complexity bounds in almost all settings. For instance, for strongly log-concave distributions, our method has complexity bound (O) over tilde(kappa d(1/2)) without warm start, better than the minimax bound for MALA. For distributions satisfying the LSI, our bound is (O) over tilde((kappa) over capd(1/2)) where (kappa) over cap is the ratio between smoothness and the LSI constant, better than all existing bounds.

关键词： Sampling MCMC non-asymptotic analysis concentration inequality proximal algorithm semi-smooth functions

来源：评论

学校读者我要写书评

暂无评论

HIGHER-ORDER NONNEGATIVE CANDECOMP/PARAFAC TENSOR DECOMPOSITION USING proximal algorithm 44

HIGHER-ORDER NONNEGATIVE CANDECOMP/PARAFAC TENSOR DECOMPOSIT...

引用

44th IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Wang, Deqing Cong, Fengyu Ristaniemi, Tapani Dalian Univ Technol Sch Biomed Engn Fac Elect Informat & Elect Engn Dalian Peoples R China Univ Jyvaskyla Fac Informat Technol Jyvaskyla Finland

ISBN: (纸本)9781479981311

Tensor decomposition is a powerful tool for analyzing multiway data. Nowadays, with the fast development of multisensor technology, more and more data appear in higher-order (order >= 4) and nonnegative form. However, the decomposition of higher-order nonnegative tensor suffers from poor convergence and low speed. In this study, we propose a new nonnegative CANDECOM/PARAFAC (NCP) model using proximal algorithm. The block principal pivoting method in alternating nonnegative least squares (ANLS) framework is employed to minimize the objective function. Our method can guarantee the convergence and accelerate the computation. The results of experiments on both synthetic and real data demonstrate the efficiency and superiority of our method.

关键词： Tensor decomposition nonnegative CAN-DECOMP/PARAFAC proximal algorithm block principal pivoting alternating nonnegative least squares

来源：评论

学校读者我要写书评

暂无评论

A progression strategy of proximal algorithm applied to the digital images inpainting 9

A progression strategy of proximal algorithm applied to the ...

引用

9th International Symposium on Signal, Image, Video and Communications (ISIVC)

作者： Nazih, Marouane Minaoui, Khalid Rouijel, Awatif Mohammed V Univ Rabat Fac Sci Rabat IT Rabat Ctr Associated Unit CNRSTURAC 29 Rabat Morocco ISMAC Rabat Morocco

ISBN: (纸本)9781538681732

Digital inpainting uses spatial or frequency information to restore a damaged/deleted portion of photos. Digital Image inpainting is a new and exciting research topic in the field of multimedia computing and image processing since 2000. In order to accurately solve the problem of digital image restoration in which the objective function is nonlinear, a new optimization method different from both linear search and trust region is presented in this paper. This new method is based on the family of proximal algorithms. We customize our algorithm to solve the problem of image restoration from a noisy image with a very high missing pixel. Finally, the results proved the accurate and rapid convergence of the proposed algorithm compared to other algorithms.

关键词： Image restauration Inpainting Denoising proximal algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：