An Iterative Coordinate Descent Algorithm for High-Dimensional Nonconvex Penalized Quantile Regression

We propose and study a new iterative coordinate descent algorithm (QICD) for solving nonconvex penalized quantile regression in high dimension. By permitting different subsets of covariates to be relevant for modeling the response variable at different quantiles, nonconvex penalized quantile regression provides a flexible approach for modeling high-dimensional data with heterogeneity. Although its theory has been investigated recently, its computation remains highly challenging when p is large due to the nonsmoothness of the quantile loss function and the nonconvexity of the penalty function. Existing coordinate descent algorithms for penalized least-squares regression cannot be directly applied. We establish the convergence property of the proposed algorithm under some regularity conditions for a general class of nonconvex penalty functions including popular choices such as SCAD (smoothly clipped absolute deviation) and MCP (minimax concave penalty). Our Monte Carlo study confirms that QICD substantially improves the computational speed in the p ? n setting. We illustrate the application by analyzing a microarray dataset.     

高维线性回归模型中非凸惩罚岭回归

非凸惩罚函数包括SCAD惩罚和MCP惩罚, 这类惩罚函数具有无偏性、连续性和稀疏性等特点,岭回归方法能够很好的克服共线性问题. 本文将非凸惩罚函数和岭回归方法的优势结合起来(简记为 NPR),研究了自变量间存在高相关性问题时NPR估计的Oracle性质. 这里主要研究了参数个数$p_n$ 随样本量$n$ 呈指数阶增长的情况. 同时, 通过模拟研究和实例分析进一步验证了NPR 方法的表现.     

Local saddle point and a class of convexification methods for nonconvex optimization problems

A class of general transformation methods are proposed to convert a nonconvex optimization problem to another equivalent problem. It is shown that under certain assumptions the existence of a local saddle point or local convexity of the Lagrangian function of the equivalent problem (EP) can be guaranteed. Numerical experiments are given to demonstrate the main results geometrically.     

An Efficient Algorithm for Computing the HHSVM and Its Generalizations

The hybrid Huberized support vector machine (HHSVM) has proved its advantages over the ?₁ support vector machine (SVM) in terms of classification and variable selection. Similar to the ?₁ SVM, the HHSVM enjoys a piecewise linear path property and can be computed by a least-angle regression (LARS)-type piecewise linear solution path algorithm. In this article, we propose a generalized coordinate descent (GCD) algorithm for computing the solution path of the HHSVM. The GCD algorithm takes advantage of a majorization–minimization trick to make each coordinatewise update simple and efficient. Extensive numerical experiments show that the GCD algorithm is much faster than the LARS-type path algorithm. We further extend the GCD algorithm to solve a class of elastic net penalized large margin classifiers, demonstrating the generality of the GCD algorithm. We have implemented the GCD algorithm in a publicly available R package gcdnet.     

无穷维空间中非凸微分包含的生存构造及应用

本文在一般的Banach空间中研究非凸微分包含的生存问题．我们首先构造出了上述非凸微分包含的一个生存集．然后给出了所构造的生存集的两个应用．     

Efficient and Optimal Parallel Algorithms for Cholesky Decomposition

In this paper, we consider the problem of developing efficient and optimal parallel algorithms for Cholesky decomposition. We design our algorithms based on different data layouts and methods. We thereotically analyze the run-time of each algorithm. In order to determine the optimality of the algorithms designed, we derive theoretical lower bounds on running time based on initial data layout and compare them against the algorithmic run-times. To address portability, we design our algorithms and perform complexity analysis on the LogP model. Lastly, we implement our algorithms and analyze performance data. This revised version was published online in July 2006 with corrections to the Cover Date.     

Algorithms without accuracy saturation for evolution equations in Hilbert and Banach spaces

We consider the Cauchy problem for the first and the second order differential equations in Banach and Hilbert spaces with an operator coefficient depending on the parameter . We develop discretization methods with high parallelism level and without accuracy saturation; i.e., the accuracy adapts automatically to the smoothness of the solution. For analytical solutions the rate of convergence is exponential. These results can be viewed as a development of parallel approximations of the operator exponential and of the operator cosine family with a constant operator possessing exponential accuracy and based on the Sinc-quadrature approximations of the corresponding Dunford-Cauchy integral representations of solutions or the solution operators.