Local linear convergence analysis of Primal–Dual splitting methods

In this paper, we study the local linear convergence properties of a versatile class of Primal–Dual splitting methods for minimizing composite non-smooth convex optimization problems. Under the assumption that the non-smooth components of the problem are partly smooth relative to smooth manifolds, we present a unified local convergence analysis framework for these methods. More precisely, in our framework, we first show that (i) the sequences generated by Primal–Dual splitting methods identify a pair of primal and dual smooth manifolds in a finite number of iterations, and then (ii) enter a local linear convergence regime, which is characterized based on the structure of the underlying active smooth manifolds. We also show how our results for Primal–Dual splitting can be specialized to cover existing ones on Forward–Backward splitting and Douglas–Rachford splitting/ADMM (alternating direction methods of multipliers). Moreover, based on these obtained local convergence analysis result, several practical acceleration techniques are discussed. To exemplify the usefulness of the obtained result, we consider several concrete numerical experiments arising from fields including signal/image processing, inverse problems and machine learning. The demonstration not only verifies the local linear convergence behaviour of Primal–Dual splitting methods, but also the insights on how to accelerate them in practice.     

Subgroup analysis of zero-inflated Poisson regression model with applications to insurance data

Customized personal rate offering is of growing importance in the insurance industry. To achieve this, an important step is to identify subgroups of insureds from the corresponding heterogeneous claim frequency data. In this paper, a penalized Poisson regression approach for subgroup analysis in claim frequency data is proposed. Subjects are assumed to follow a zero-inflated Poisson regression model with group-specific intercepts, which capture group characteristics of claim frequency. A penalized likelihood function is derived and optimized to identify the group-specific intercepts and effects of individual covariates. To handle the challenges arising from the optimization of the penalized likelihood function, an alternating direction method of multipliers algorithm is developed and its convergence is established. Simulation studies and real applications are provided for illustrations.     

随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用

针对具有多块可分结构的非凸优化问题提出了一类新的随机Bregman交替方向乘子法,在周期更新规则下, 证明了该算法的渐进收敛性; 在随机更新的规则下, 几乎确定的渐进收敛性得以证明。数值实验结果表明, 该算法可有效训练具有离散结构的支持向量机。     

Differentially Private Precision Matrix Estimation

In this paper, we study the problem of precision matrix estimation when the dataset contains sensitive information. In the differential privacy framework, we develop a differentially private ridge estimator by perturbing the sample covariance matrix. Then we develop a differentially private graphical lasso estimator by using the alternating direction method of multipliers (ADMM) algorithm. Furthermore, we prove theoretical results showing that the differentially private ridge estimator for the precision matrix is consistent under fixed-dimension asymptotic, and establish a convergence rate of differentially private graphical lasso estimator in the Frobenius norm as both data dimension p and sample size n are allowed to grow. The empirical results that show the utility of the proposed methods are also provided.     

一类正则化参数自由的线性约束凸优化问题的预测-校正算法

我们对文章的结构做这样的安排:第二节给出本文需要的预备知识;第三节简述单个目标函数问题(1.1)的己有算法和求解可能遇到的困难,第四节给出解决问题的预测-校正方法;第五节和第六节对问题(1.2)分别陈述己有方法的固有困难和我们提出的解决方案.最后,在第七节中,我们为提出的方法给出统一的算法框架,证明这类算法的收敛性和遍历意义下的收敛速率,同时给出我们的一些结论.     

An occlusion-adaptive tracker based on sparse representation using alternating direction method of multipliers

Recently, sparse representation has been applied to visual tracking with satisfactory performance. However, partial occlusion and computational complexity are two main obstructions in developing sparse-based tracking. In this paper, a simple yet robust tracker based on patch-based sparse representation is proposed. An adaptive motion model, including adaptive sampling regions and adaptive particle numbers, is proposed to improve the sampling efficiency. A self-adjustable segmentation approach is proposed to segment the target into local patches. A patch-based observation model, which is occlusion-adaptive, is constructed by solving a set of L1-regularized least squares problems. The L1-regularized least squares problem is solved using the alternating direction method of multipliers (ADMM). Both quantitative and qualitative experiments are conducted on several challenging image sequences and the comparisons with several state-of-the-art trackers demonstrate the effectiveness and efficiency of our tracker.     

ENHANCED BLOCK-SPARSE SIGNAL RECOVERY PERFORMANCE VIA TRUNCATED e2/e1-2 MINIMIZATION

In this paper, we investigate truncated $ℓ_2/ℓ_{1−2}$ minimization and its associated alternating direction method of multipliers (ADMM) algorithm for recovering the block sparse signals. Based on the block restricted isometry property (Block-RIP), a theoretical analysis is presented to guarantee the validity of proposed method. Our theoretical results not only show a less error upper bound, but also promote the former recovery condition of truncated ℓ₁₋₂ method for sparse signal recovery. Besides, the algorithm has been compared with some state-of-the-art algorithms and numerical experiments have shown excellent performances on recovering the block sparse signals.     

Accelerating Kohn‐Sham response theory using density fitting and the auxiliary‐density‐matrix method

An extension of the formulation of the atomic‐orbital‐based response theory of Larsen et al., JCP 113, 8909 (2000) is presented. This new framework has been implemented in LSDalton and allows for the use of Kohn‐Sham density‐functional theory with approximate treatment of the Coulomb and Exchange contributions to the response equations via the popular resolution‐of‐the‐identity approximation as well as the auxiliary‐density matrix method (ADMM). We present benchmark calculations of ground‐state energies as well as the linear and quadratic response properties: vertical excitation energies, polarizabilities, and hyperpolarizabilities. The quality of these approximations in a range of basis sets is assessed against reference calculations in a large aug‐pcseg‐4 basis. Our results confirm that density fitting of the Coulomb contribution can be used without hesitation for all the studied properties. The ADMM treatment of exchange is shown to yield high accuracy for ground‐state and excitation energies, whereas for polarizabilities and hyperpolarizabilities the performance gain comes at a cost of accuracy. Excitation energies of a tetrameric model consisting of units of the P700 special pigment of photosystem I have been studied to demonstrate the applicability of the code for a large system.     

分布式L_(1/2)正则化

研究数据集被分割并存储于不同处理器时的特征提取和变量选择问题,其中处理器通过某种网络结构相互连接.提出分布式L_(1/2)正则化方法,基于ADMM算法给出分布式L_(1/2)正则化算法,证明了算法的收敛性.算法通过相邻处理器之间完成信息交互,其变量选择结果与数据集不分割时利用L_(1/2)正则化相同.实验表明,所提出的新算法有效、实用,适合于分布式存储数据处理.     

Large-Scale Structured Sparsity via Parallel Fused Lasso on Multiple GPUs

We present a massively parallel algorithm for the fused lasso, powered by a multiple number of graphics processing units (GPUs). Our method is suitable for a class of large-scale sparse regression problems on which a two-dimensional lattice structure among the coefficients is imposed. This structure is important in many statistical applications, including image-based regression in which a set of images are used to locate image regions predictive of a response variable such as human behavior. Such large datasets are increasingly common. In our study, we employ the split Bregman method and the fast Fourier transform, which jointly have a high data-level parallelism that is distinct in a two-dimensional setting. Our multi-GPU parallelization achieves remarkably improved speed. Specifically, we obtained as much as 433 times improved speed over that of the reference CPU implementation. We demonstrate the speed and scalability of the algorithm using several datasets, including 8100 samples of 512 × 512 images. Compared to the single GPU counterpart, our method also showed improved computing speed as well as high scalability. We describe the various elements of our study as well as our experience with the subtleties in selecting an existing algorithm for parallelization. It is critical that memory bandwidth be carefully considered for multi-GPU algorithms. Supplementary material for this article is available online.