The l(p) regularization problem with 0 < p < 1 has been widely studied for finding sparse solutions of linear inverse problems and gained successful applications in various mathematics and applied science fields...
详细信息
The l(p) regularization problem with 0 < p < 1 has been widely studied for finding sparse solutions of linear inverse problems and gained successful applications in various mathematics and applied science fields. The proximalgradient algorithm is one of the most popular algorithms for solving the l(p) regularisation problem. In the present paper, we investigate the linear convergence issue of one inexact descent method and two inexact proximal gradient algorithms (PGA). For this purpose, an optimality condition theorem is explored to provide the equivalences among a local minimum, second-order optimality condition and second-order growth property of the l(p) regularization problem. By virtue of the second-order optimality condition and second-order growth property, we establish the linear convergence properties of the inexact descent method and inexact PGAs under some simple assumptions. Both linear convergence to a local minimal value and linear convergence to a local minimum are provided. Finally, the linear convergence results of these methods are extended to the infinite-dimensional Hilbert spaces. Our results cannot be established under the framework of Kurdyka-Lojasiewicz theory.
This article studies a class of nonsmooth decentralized multiagent optimization problems where the agents aim at minimizing a sum of local strongly-convex smooth components plus a common nonsmooth term. We propose a g...
详细信息
This article studies a class of nonsmooth decentralized multiagent optimization problems where the agents aim at minimizing a sum of local strongly-convex smooth components plus a common nonsmooth term. We propose a general primal-dual algorithmic framework that unifies many existing state-of-the-art algorithms. We establish linear convergence of the proposed method to the exact minimizer in the presence of the nonsmooth term. Moreover, for the more general class of problems with agent specific nonsmooth terms, we show that linear convergence cannot be achieved (in the worst case) for the class of algorithms that uses the gradients and the proximal mappings of the smooth and nonsmooth parts, respectively. We further provide a numerical counterexample that shows how some state-of-the-art algorithms fail to converge linearly for strongly convex objectives and different local non smooth terms.
Backtracking line-search is an old yet powerful strategy for finding better step sizes to be used in proximal gradient algorithms. The main principle is to locally find a simple convex upper bound of the objective fun...
详细信息
Backtracking line-search is an old yet powerful strategy for finding better step sizes to be used in proximal gradient algorithms. The main principle is to locally find a simple convex upper bound of the objective function, which in turn controls the step size that is used. In case of inertial proximal gradient algorithms, the situation becomes much more difficult and usually leads to very restrictive rules on the extrapolation parameter. In this paper, we show that the extrapolation parameter can be controlled by also locally finding a simple concave lower bound of the objective function. This gives rise to a double convex-concave backtracking procedure which allows for an adaptive choice of both the step size and extrapolation parameters. We apply this procedure to the class of inertial Bregman proximalgradient methods, and prove that any sequence generated by these algorithms converges globally to a critical point of the function at hand. Numerical experiments on a number of challenging nonconvex problems in image processing and machine learning were conducted and show the power of combining inertial step and double backtracking strategy in achieving improved performances.
Recent technological advancements have led to the rapid generation of high-throughput biological data which can be used to address novel scientific questions in broad areas of research. These data can be thought of as...
详细信息
Recent technological advancements have led to the rapid generation of high-throughput biological data which can be used to address novel scientific questions in broad areas of research. These data can be thought of as a large matrix with covariates annotating both its rows and columns. Matrix linear models provide a convenient way for modeling such data. In many situations, sparse estimation of these models is desired. We present fast, general methods for fitting sparse matrix linear models to structured high-throughput data. We induce model sparsity using an L-1 penalty and consider the case when the response matrix and the covariate matrices are large. Due to data size, standard methods for estimation of these penalized regression models fail if the problem is converted to the corresponding univariate regression scenario. By leveraging matrix properties in the structure of our model, we develop several fast estimation algorithms (coordinate descent, FISTA and ADMM) and discuss their trade-offs. We evaluate our method's performance on simulated data, E. coli chemical genetic screening data and two Arabidopsis genetic datasets with multivariate responses. Our algorithms have been implemented in the Julia programming language and are available at https://***/senresearch/***.
We consider the nonnegative matrix factorization (NMF) problem with sparsity constraints formulated as a nonconvex composite minimization problem. We introduce four novel proximalgradient based algorithms proven glob...
详细信息
We consider the nonnegative matrix factorization (NMF) problem with sparsity constraints formulated as a nonconvex composite minimization problem. We introduce four novel proximalgradient based algorithms proven globally convergent to a critical point and which are applicable to sparsity constrained NMF models. Our approach builds on recent results allowing one to lift the classical global Lipschitz continuity requirement through the use of a non-Euclidean Bregman based distance. Since under the proposed framework we are not restricted by the gradient Lipschitz continuity assumption, we can consider new decomposition settings of the NMF problem. Two of the derived schemes are genuine non-Euclidean proximal methods that tackle nonstandard decompositions of the NMF problem. The two other schemes are novel extensions of the well-known state-of-the-art methods (the multiplicative and hierarchical alternating least squares), thus allowing one to significantly broaden the scope of these algorithms. Numerical experiments illustrate the performance of the proposed methods.
For the composite function composed of L-smooth general convex functions and non-smooth convex functions,a new accelerated distributed composite Nesterov gradient descent algorithm(Acc-DCNGD-NSC) is proposed in this...
详细信息
ISBN:
(数字)9789887581536
ISBN:
(纸本)9781665482561
For the composite function composed of L-smooth general convex functions and non-smooth convex functions,a new accelerated distributed composite Nesterov gradient descent algorithm(Acc-DCNGD-NSC) is proposed in this *** algorithm can be applied to smooth convex optimization problems and composite convex optimization *** applying Nesterov acceleration techniques and a new gradient estimation scheme to the distributed proximalgradient algorithm,Acc-DCNGD-NSC is able to converge at a sub-linear rate of O(1/t)to global optimal solution.
We focus on nonconvex and nonsmooth minimization problems with a composite objective, where the differentiable part of the objective is freed from the usual and restrictive global Lipschitz gradient continuity assumpt...
详细信息
We focus on nonconvex and nonsmooth minimization problems with a composite objective, where the differentiable part of the objective is freed from the usual and restrictive global Lipschitz gradient continuity assumption. This longstanding smoothness restriction is pervasive in first order methods, and recently was circumvented for convex composite optimization by Bauschke, Bolte, and Teboulle, through a simple framework which captures, all at once, the geometry of the function and of the feasible set. Building on this work, we tackle genuine nonconvex problems. We first complement and extend their approach to derive an extended descent lemma by introducing the notion of smooth adaptable functions. We then consider a Bregman-based proximalgradient method for the nonconvex composite model with smooth adaptable functions, which is proven to globally converge to a critical point under natural assumptions on the problem's data, and in particular for semialgebraic problems. To illustrate the potential of our general framework and results, we consider a broad class of quadratic inverse problems with sparsity constraints which arises in many fundamental applications, and we apply our approach to derive new globally convergent schemes for this class.
High dimensional mixed-effects generalized linear models extend the generalized linear models (GLMs) by adding random effects to the linear predictors of the original high dimensional GLMs. The high dimensional mixed-...
详细信息
High dimensional mixed-effects generalized linear models extend the generalized linear models (GLMs) by adding random effects to the linear predictors of the original high dimensional GLMs. The high dimensional mixed-effect logistic regression is a typical example. These models are useful in analyzing categorical or discrete data with a group structure. Inference for these models is challenging because of the intractable and generally non-convex negative log-likelihood function. In this dissertation, we propose and analyze four different algorithms to solve the high dimensional mixed-effects logistic regression model. The first two algorithms we develop are stochastic proximalgradient and second-order approximate algorithms, which are both proximalgradient-based algorithms. As the gradient of the loss function is intractable, the stochastic proximalgradient algorithm uses a Markov chain Monte Carlo technique to approximate the gradient, while the second order approximate algorithm approximates the objective function based on Taylor expansion to the second order, and solves an approximate problem. We prove the convergence of the second order approximate algorithm using the Kurdyka-Lojasiewicz (K-L) property based techniques. To analyze convergence behavior of the stochastic proximalgradient algorithm, we expand this K-L based technique to incorporate stochastic perturbations in the algorithm updates. We show that the stochastic algorithm's limiting points are the stationary points of the original objective function. We illustrate the good performance of our algorithms in several numerical examples. We also apply the two algorithms in a breast cancer data analysis. The next algorithm we consider is based on a “fixed effect approximation” of the mixed effects models. Here we treat the random effects as unknown fixed effects coefficients and estimate them without penalty. The approximation reduces the original problem to the usual high dimensional logistic regressio
Robust dictionary learning algorithms seek to learn a dictionary while being robust to the presence of outliers in the training set. Often, the elements of the training set have an underlying structure due to, for exa...
详细信息
ISBN:
(纸本)9781479984282
Robust dictionary learning algorithms seek to learn a dictionary while being robust to the presence of outliers in the training set. Often, the elements of the training set have an underlying structure due to, for example, their spatial relation or their similarity. When outliers are present as elements of the training set, they often inherit the underlying structure of the training set. This work capitalizes on such structure, encoded as an undirected graph connecting elements of the training set, and on sparsity-aware outlier modeling tools to develop robust dictionary learning algorithms. Not only do these algorithms yield a robust dictionary, but they also identify the outliers in the training set. Computationally efficient algorithms based on block coordinate descent and proximalgradient methods are developed.
Frame-based image restoration by using the balanced approach has been developed over the last decade. Many recently developed algorithms for image restoration can be viewed as an acceleration of the proximal forward-b...
详细信息
Frame-based image restoration by using the balanced approach has been developed over the last decade. Many recently developed algorithms for image restoration can be viewed as an acceleration of the proximal forward-backward splitting algorithm. Accelerated proximalgradient (APG) algorithms studied by Nesterov, Nemirovski, and others have been demonstrated to be efficient in solving various regularized convex optimization problems arising in compressed sensing, machine learning, and control. In this paper, we adapt the APG algorithm to solve the l(1)-regularized linear least squares problem in the balanced approach in frame-based image restoration. This algorithm terminates in O(1/v root epsilon) iterations with an epsilon-optimal solution, and we demonstrate that this single algorithmic framework can universally handle several image restoration problems, such as image deblurring, denoising, inpainting, and cartoon-texture decomposition. Our numerical results suggest that the APG algorithms are efficient and robust in solving large-scale image restoration problems. The algorithms we implemented are able to restore 512 x 512 images in various image restoration problems in less than 50 seconds on a modest PC. We also compare the numerical performance of our proposed algorithms applied to image restoration problems by using one frame-based system with that by using cartoon and texture systems for image deblurring, denoising, and inpainting.
暂无评论