DC Proximal Newton for Nonconvex Optimization Problems

A Novel Swarm Exploring Varying Parameter Recurrent Neural Network for Solving Non-Convex Nonlinear Programming

Aiming at solving non-convex nonlinear programming efficiently and accurately, a swarm exploring varying parameter recurrent neural network (SE-VPRNN) method is proposed in this article. First, the local optimal solutions are searched accurately by the proposed varying parameter recurrent neural network. After each network converges to the local optimal solutions, information is exchanged through a particle swarm optimization (PSO) framework to update the velocities and positions. The neural network searches for the local optimal solutions again from the updated position until all the neural networks are searched to the same local optimal solution. For improving the global searching ability, wavelet mutation is applied to increase the diversity of particles. Computer simulations show that the proposed method can solve the non-convex nonlinear programming effectively. Compared with three existing algorithms, the proposed method has advantages in accuracy and convergence time.

Accelerated Log-Regularized Convolutional Transform Learning and Its Convergence Guarantee

Convolutional transform learning (CTL), learning filters by minimizing the data fidelity loss function in an unsupervised way, is becoming very pervasive, resulting from keeping the best of both worlds: the benefit of unsupervised learning and the success of the convolutional neural network. There have been growing interests in developing efficient CTL algorithms. However, developing a convergent and accelerated CTL algorithm with accurate representations simultaneously with proper sparsity is an open problem. This article presents a new CTL framework with a log regularizer that can not only obtain accurate representations but also yield strong sparsity. To efficiently address our nonconvex composite optimization, we propose to employ the proximal difference of the convex algorithm (PDCA) which relies on decomposing the nonconvex regularizer into the difference of two convex parts and then optimizes the convex subproblems. Furthermore, we introduce the extrapolation technology to accelerate the algorithm, leading to a fast and efficient CTL algorithm. In particular, we provide a rigorous convergence analysis for the proposed algorithm under the accelerated PDCA. The experimental results demonstrate that the proposed algorithm can converge more stably to desirable solutions with lower approximation error and simultaneously with stronger sparsity and, thus, learn filters efficiently. Meanwhile, the convergence speed is faster than the existing CTL algorithms.

Deep Network Quantization via Error Compensation

For portable devices with limited resources, it is often difficult to deploy deep networks due to the prohibitive computational overhead. Numerous approaches have been proposed to quantize weights and/or activations to speed up the inference. Loss-aware quantization has been proposed to directly formulate the impact of weight quantization on the model's final loss. However, we discover that, under certain circumstances, such a method may not converge and end up oscillating. To tackle this issue, we introduce a novel loss-aware quantization algorithm to efficiently compress deep networks with low bit-width model weights. We provide a more accurate estimation of gradients by leveraging the Taylor expansion to compensate for the quantization error, which leads to better convergence behavior. Our theoretical analysis indicates that the gradient mismatch issue can be fixed by the newly introduced quantization error compensation term. Experimental results for both linear models and convolutional networks verify the effectiveness of our proposed method.

Stochastic DCA for minimizing a large sum of DC functions with application to multi-class logistic regression

We consider the large sum of DC (Difference of Convex) functions minimization problem which appear in several different areas, especially in stochastic optimization and machine learning. Two DCA (DC Algorithm) based algorithms are proposed: stochastic DCA and inexact stochastic DCA. We prove that the convergence of both algorithms to a critical point is guaranteed with probability one. Furthermore, we develop our stochastic DCA for solving an important problem in multi-task learning, namely group variables selection in multi class logistic regression. The corresponding stochastic DCA is very inexpensive, all computations are explicit. Numerical experiments on several benchmark datasets and synthetic datasets illustrate the efficiency of our algorithms and their superiority over existing methods, with respect to classification accuracy, sparsity of solution as well as running time.

Hybrid reconstruction method for multispectral bioluminescence tomography with log-sum regularization

Bioluminescence tomography (BLT) has important applications in the in vivo visualization of a pathological process for preclinical studies. However, the reconstruction of BLT is severely ill-posed. To recover the bioluminescence source stably and efficiently, we use a log-sum regularization term in the objective function and utilize a hybrid optimization algorithm for solving the nonconvex regularized problems (HONOR). The hybrid optimization scheme of HONOR merges second-order information and first-order information to reconstruction by choosing either the quasi-Newton (QN) or gradient descent step at each iteration. The QN step uses the limited-memory Broyden-Fletcher-Goldfarb-Shanno algorithm (L-BFGS) to acquire second-order information. Simulations and in vivo experiments based on multispectral measurements demonstrated the remarkable performance of the proposed hybrid method in the sparse reconstruction of BLT.

Greedy Projected Gradient-Newton Method for Sparse Logistic Regression

Sparse logistic regression (SLR), which is widely used for classification and feature selection in many fields, such as neural networks, deep learning, and bioinformatics, is the classical logistic regression model with sparsity constraints. In this paper, we perform theoretical analysis on the existence and uniqueness of the solution to the SLR, and we propose a greedy projected gradient-Newton (GPGN) method for solving the SLR. The GPGN method is a combination of the projected gradient method and the Newton method. The following characteristics show that the GPGN method achieves not only elegant theoretical results but also a remarkable numerical performance in solving the SLR: 1) the full iterative sequence generated by the GPGN method converges to a global/local minimizer of the SLR under weaker conditions; 2) the GPGN method has the properties of afinite identification for an optimal support set and local quadratic convergence; and 3) the GPGN method achieves higher accuracy and higher speed compared with a number of state-of-the-art solvers according to numerical experiments.

Spatially regularized estimation of the tissue homogeneity model parameters in DCE-MRI using proximal minimization

PURPOSE

The Tofts and the extended Tofts models are the pharmacokinetic models commonly used in dynamic contrast-enhanced MRI (DCE-MRI) perfusion analysis, although they do not provide two important biological markers, namely, the plasma flow and the permeability-surface area product. Estimates of such markers are possible using advanced pharmacokinetic models describing the vascular distribution phase, such as the tissue homogeneity model. However, the disadvantage of the advanced models lies in biased and uncertain estimates, especially when the estimates are computed voxelwise. The goal of this work is to improve the reliability of the estimates by including information from neighboring voxels.

THEORY AND METHODS

Information from the neighboring voxels is incorporated in the estimation process through spatial regularization in the form of total variation. The spatial regularization is applied on five maps of perfusion parameters estimated using the tissue homogeneity model. Since the total variation is not differentiable, two proximal techniques of convex optimization are used to solve the problem numerically.

RESULTS

The proposed algorithm helps to reduce noise in the estimated perfusion-parameter maps together with improving accuracy of the estimates. These conclusions are proved using a numerical phantom. In addition, experiments on real data show improved spatial consistency and readability of perfusion maps without considerable lowering of the quality of fit.

CONCLUSION

The reliability of the DCE-MRI perfusion analysis using the tissue homogeneity model can be improved by employing spatial regularization. The proposed utilization of modern optimization techniques implies only slightly higher computational costs compared to the standard approach without spatial regularization.

Stochastic Gradient Matching Pursuit Algorithm Based on Sparse Estimation

The stochastic gradient matching pursuit algorithm requires the sparsity of the signal as prior information. However, this prior information is unknown in practical applications, which restricts the practical applications of the algorithm to some extent. An improved method was proposed to overcome this problem. First, a pre-evaluation strategy was used to evaluate the sparsity of the signal and the estimated sparsity was used as the initial sparsity. Second, if the number of columns of the candidate atomic matrix was smaller than that of the rows, the least square solution of the signal was calculated, otherwise, the least square solution of the signal was set as zero. Finally, if the current residual was greater than the previous residual, the estimated sparsity was adjusted by the fixed step-size and stage index, otherwise we did not need to adjust the estimated sparsity. The simulation results showed that the proposed method was better than other methods in terms of the aspect of reconstruction percentage in the larger sparsity environment.

Progressive Stochastic Learning for Noisy Labels

Large-scale learning problems require a plethora of labels that can be efficiently collected from crowdsourcing services at low cost. However, labels annotated by crowdsourced workers are often noisy, which inevitably degrades the performance of large-scale optimizations including the prevalent stochastic gradient descent (SGD). Specifically, these noisy labels adversely affect updates of the primal variable in conventional SGD. To solve this challenge, we propose a robust SGD mechanism called progressive stochastic learning (POSTAL), which naturally integrates the learning regime of curriculum learning (CL) with the update process of vanilla SGD. Our inspiration comes from the progressive learning process of CL, namely learning from "easy" tasks to "complex" tasks. Through the robust learning process of CL, POSTAL aims to yield robust updates of the primal variable on an ordered label sequence, namely, from "reliable" labels to "noisy" labels. To realize POSTAL mechanism, we design a cluster of "screening losses," which sorts all labels from the reliable region to the noisy region. To sum up, POSTAL using screening losses ensures robust updates of the primal variable on reliable labels first, then on noisy labels incrementally until convergence. In theory, we derive the convergence rate of POSTAL realized by screening losses. Meanwhile, we provide the robustness analysis of representative screening losses. Experimental results on UCI1 simulated and Amazon Mechanical Turk crowdsourcing data sets show that the POSTAL using screening losses is more effective and robust than several existing baselines.1UCI is the abbreviation of University of California Irvine.

Solving Multiextremal Problems by Using Recurrent Neural Networks

In this paper, a neural network model for solving a class of multiextremal smooth nonconvex constrained optimization problems is proposed. Neural network is designed in such a way that its equilibrium points coincide with the local and global optimal solutions of the corresponding optimization problem. Based on the suitable underestimators for the Lagrangian of the problem, one give geometric criteria for an equilibrium point to be a global minimizer of multiextremal constrained optimization problem with or without bounds on the variables. Both necessary and sufficient global optimality conditions for a class of multiextremal constrained optimization problems are presented to determine a global optimal solution. By study of the resulting dynamic system, it is shown that under given assumptions, steady states of the dynamic system are stable and trajectories of the proposed model converge to the local and global optimal solutions of the problem. Numerical results are given and related graphs are depicted to illustrate the global convergence and performance of the solver for multiextremal constrained optimization problems.

Manifold optimization-based analysis dictionary learning with an ℓ1∕2-norm regularizer

Recently there has been increasing attention towards analysis dictionary learning. In analysis dictionary learning, it is an open problem to obtain the strong sparsity-promoting solutions efficiently while simultaneously avoiding the trivial solutions of the dictionary. In this paper, to obtain the strong sparsity-promoting solutions, we employ the ℓ_1∕2 norm as a regularizer. The very recent study on ℓ_1∕2 norm regularization theory in compressive sensing shows that its solutions can give sparser results than using the ℓ₁ norm. We transform a complex nonconvex optimization into a number of one-dimensional minimization problems. Then the closed-form solutions can be obtained efficiently. To avoid trivial solutions, we apply manifold optimization to update the dictionary directly on the manifold satisfying the orthonormality constraint, so that the dictionary can avoid the trivial solutions well while simultaneously capturing the intrinsic properties of the dictionary. The experiments with synthetic and real-world data verify that the proposed algorithm for analysis dictionary learning can not only obtain strong sparsity-promoting solutions efficiently, but also learn more accurate dictionary in terms of dictionary recovery and image processing than the state-of-the-art algorithms.

Greedy Methods, Randomization Approaches, and Multiarm Bandit Algorithms for Efficient Sparsity-Constrained Optimization

Several sparsity-constrained algorithms, such as orthogonal matching pursuit (OMP) or the Frank-Wolfe (FW) algorithm, with sparsity constraints work by iteratively selecting a novel atom to add to the current nonzero set of variables. This selection step is usually performed by computing the gradient and then by looking for the gradient component with maximal absolute entry. This step can be computationally expensive especially for large-scale and high-dimensional data. In this paper, we aim at accelerating these sparsity-constrained optimization algorithms by exploiting the key observation that, for these algorithms to work, one only needs the coordinate of the gradient's top entry. Hence, we introduce algorithms based on greedy methods and randomization approaches that aim at cheaply estimating the gradient and its top entry. Another of our contribution is to cast the problem of finding the best gradient entry as a best-arm identification in a multiarmed bandit problem. Owing to this novel insight, we are able to provide a bandit-based algorithm that directly estimates the top entry in a very efficient way. Theoretical observations stating that the resulting inexact FW or OMP algorithms act, with high probability, similar to their exact versions are also given. We have carried out several experiments showing that the greedy deterministic and the bandit approaches we propose can achieve an acceleration of an order of magnitude while being as efficient as the exact gradient when used in algorithms, such as OMP, FW, or CoSaMP.