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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A proximal distance algorithm for likelihood-based sparse covariance estimation

引用

BIOMETRIKA 2022年第4期109卷 1047-1066页

作者： Xu, Jason Lange, Kenneth Duke Univ Dept Stat Sci Box 90251 Durham NC 27708 USA Univ Calif Los Angeles Dept Computat Med Box 708822 Los Angeles CA 90095 USA

This paper addresses the task of estimating a covariance matrix under a patternless sparsity assumption. In contrast to existing approaches based on thresholding or shrinkage penalties, we propose a likelihood-based method that regularizes the distance from the covariance estimate to a symmetric sparsity set. This formulation avoids unwanted shrinkage induced by more common norm penalties, and enables optimization of the resulting nonconvex objective by solving a sequence of smooth, unconstrained subproblems. These subproblems are generated and solved via the proximal distance version of the majorization-minimization principle. The resulting algorithm executes rapidly, gracefully handles settings where the number of parameters exceeds the number of cases, yields a positive-definite solution, and enjoys desirable convergence properties. Empirically, we demonstrate that our approach outperforms competing methods across several metrics, for a suite of simulated experiments. Its merits are illustrated on international migration data and a case study on flow cytometry. Our findings suggest that the marginal and conditional dependency networks for the cell signalling data are more similar than previously concluded.

关键词： Distance-to-set penalty Majorization-minimization Penalized likelihood proximal algorithm Sequential unconstrained minimization Sparse estimation

来源：评论

学校读者我要写书评

暂无评论

ProMeSCT: A proximal Metric algorithm for Spectral CT

引用

IEEE TRANSACTIONS ON RADIATION AND PLASMA MEDICAL SCIENCES 2021年第4期5卷 548-558页

作者： Tairi, Souhil Anthoine, Sandrine Boursier, Yannick Dupont, Mathieu Morel, Christian Aix Marseille Univ CNRS IN2P3 CPPM F-13009 Marseille France Aix Marseille Univ CNRS Cent Marseille 12M F-13009 Marseille France

The acquisition of a set of spectral photon-counting computed tomography (spectral PC-CT) measurements aims at uncovering both the spatial and energetic characteristics of the imaged body, which widens the potential of tomography compared to classical computed tomography (CT). In the preclinical context, the use of polychromatic beams induces spectral mixing and, as a consequence, the reconstruction procedure requires specific algorithmic tools more complex than the standard ones used in CT. In this article, we propose a one-step inversion method to simultaneously separate and reconstruct the physical materials of an object observed in the context of spectral PC-CT. To do so, we carefully consider the underlying polychromatic model of the X-ray beam and combine it with a priori on the materials of the object to reconstruct. The simultaneous separation and reconstruction of materials is done by minimizing the resulting nonconvex ill-posed inverse problem. The dimensionality of the data and object materials worsens the computational complexity of the problem. We propose an efficient optimization algorithm based on a proximal forward-backward algorithm that is accelerated by a metric, which is specifically designed for spectral PC-CT. The efficiency of our method called ProMeSCT is demonstrated on results obtained on 3-D synthetic data with a simple regularization that encompasses the positivity of the quantities of interest.

关键词： One-step inversion photon-counting (PC) computed tomography (CT) proximal algorithm spectral CT

来源：评论

学校读者我要写书评

暂无评论

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 proximal MINIMIZATION algorithm FOR STRUCTURED NONCONVEX AND NONSMOOTH PROBLEMS

引用

SIAM JOURNAL ON OPTIMIZATION 2019年第2期29卷 1300-1328页

作者： Bot, Radu Ioan Csetnek, Erno Robert Dang-Khoa Nguyen Univ Vienna Fac Math Oskar Morgenstern Pl 1 A-1090 Vienna Austria

We propose a proximal algorithm for minimizing objective functions consisting of three summands: the composition of a nonsmooth function with a linear operator, another nonsmooth function (with each of the nonsmooth summands depending on an independent block variable), and a smooth function which couples the two block variables. The algorithm is a full splitting method, which means that the nonsmooth functions are processed via their proximal operators, the smooth function via gradient steps, and the linear operator via matrix times vector multiplication. We provide sufficient conditions for the boundedness of the generated sequence and prove that any cluster point of the latter is a KKT point of the minimization problem. In the setting of the Kurdyka-Lojasiewicz property, we show global convergence and derive convergence rates for the iterates in terms of the Lojasiewicz exponent.

关键词： structured nonconvex and nonsmooth optimization proximal algorithm full splitting scheme Kurdyka-Lojasiewicz property limiting subdifferential

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：