Robust kernel ridge regression based on M-estimation

Ridge regression (RR) and kernel ridge regression (KRR) are important tools to avoid the effects of multicollinearity. However, the predictions of RR and KRR become inappropriate for use in regression models when data are contaminated by outliers. In this paper, we propose an algorithm to obtain a nonlinear robust prediction without specifying a nonlinear model in advance. We combine M-estimation and kernel ridge regression to obtain the nonlinear prediction. Then, we compare the proposed method with some other methods.     

Scattered hermite interpolation by ridge functions

In this paper we study the problem of Hermite interpolation on scattered data using ridge functions, and give a wide class of ridge functions that may be used in practice to interpolate Hermite data.     

Robust conjugate duality for convex optimization under uncertainty with application to data classification

In this paper we present a robust conjugate duality theory for convex programming problems in the face of data uncertainty within the framework of robust optimization, extending the powerful conjugate duality technique. We first establish robust strong duality between an uncertain primal parameterized convex programming model problem and its uncertain conjugate dual by proving strong duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem under a regularity condition. This regularity condition is not only sufficient for robust duality but also necessary for it whenever robust duality holds for every linear perturbation of the objective function of the primal model problem. More importantly, we show that robust strong duality always holds for partially finite convex programming problems under scenario data uncertainty and that the optimistic counterpart of the dual is a tractable finite dimensional problem. As an application, we also derive a robust conjugate duality theorem for support vector machines which are a class of important convex optimization models for classifying two labelled data sets. The support vector machine has emerged as a powerful modelling tool for machine learning problems of data classification that arise in many areas of application in information and computer sciences.     

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

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

SAS6.11版岭回归分析程序设计及其实例分析

应用岭回归分析可以解决自变量之间存在复共线性时的回归问题。本文给出了在SAS6.1 1及以上版本中实现岭回归分析的程序 ,用具体实例说明进行岭回归的方法     

Dual‐ and triple‐mode matrix approximation and regression modelling

We propose a dual‐ and triple‐mode least squares for matrix approximation. This technique applied to the singular value decomposition produces the classical solution with a new interpretation. Applied to regression modelling, this approach corresponds to a regularized objective and yields a new solution with properties of a ridge regression. The results for regression are robust and suggest a convenient tool for the analysis and interpretation of the model coefficients. Numerical results are given for a marketing research data set. Copyright © 2003 John Wiley & Sons, Ltd.     

Linear Huber M-Estimator Under Ellipsoidal Data Uncertainty

The purpose of this note is to present a robust counterpart of the Huber estimation problem in the sense of Ben-Tal and Nemirovski when the data elements are subject to ellipsoidal uncertainty. The robust counterparts are polynomially solvable second-order cone programs with the strong duality property. We illustrate the effectiveness of the robust counterpart approach on a numerical example.     

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.     

Robust duality for generalized convex programming problems under data uncertainty

In this paper we present a robust duality theory for generalized convex programming problems in the face of data uncertainty within the framework of robust optimization. We establish robust strong duality for an uncertain nonlinear programming primal problem and its uncertain Lagrangian dual by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. A robust strong duality theorem is given whenever the Lagrangian function is convex. We provide classes of uncertain non-convex programming problems for which robust strong duality holds under a constraint qualification. In particular, we show that robust strong duality is guaranteed for non-convex quadratic programming problems with a single quadratic constraint with the spectral norm uncertainty under a generalized Slater condition. Numerical examples are given to illustrate the nature of robust duality for uncertain nonlinear programming problems. We further show that robust duality continues to hold under a weakened convexity condition.     

Geometric measures of convex sets and bounds on problem sensitivity and robustness for conic linear optimization

The effect of data perturbation and uncertainty has always been an important consideration in Optimization. It is important to know whether a given problem is very sensible to perturbations on the data or, on the contrary, is more “robust”. Problem geometry does have an impact on the sensitivity of the problem and in this paper we analyze this connection by developing bounds to the change in the optimal value of a conic linear problem in terms of some geometric measures related to the radius of inscribed and circumscribed balls to the feasible region of the problem. We also present a parametric analysis for Linear Programming which allows us to construct an estimate of safety limits for perturbations of the data. These results are developed in relation to questions in robust optimization.     

Robustness and nondegenerateness for linear complementarity problems

In this paper the main focus is on a stability concept for solutions of a linear complementarity problem. A solution of such a problem is robust if it is stable against slight perturbations of the data of the problem. Relations are investigated between the robustness, the nondegenerateness and the isolatedness of solutions. It turns out that an isolated nondegenerate solution is robust and also that a robust nondegenerate solution is isolated. Since the class of linear complementarity problems with only robust solutions or only nondegenerate solutions is not an open set, attention is paid to Garcia's classG _n of linear complementarity problems. The nondegenerate problems inG _n form an open set.     

稳健矩阵回归模型和方法研究

随着大数据时代的到来,我们面临的数据越来越复杂,其中待估系数为矩阵的模型亟待构造和求解.无论在统计还是优化领域,许多专家学者都致力于矩阵模型的统计性质分析及寻找其最优解的算法设计.当随机误差期望为0且同方差时,采用基于最小二乘的模型可以很好地解决问题.当随机误差异方差,分布为重尾分布(如双指数分布,t-分布等)或数据含有异常值时,需要考虑稳健的方法来求解问题.常用的稳健方法有最小一乘,分位数,Huber等.目前稳健方法的研究大多集中于线性回归问题,对于矩阵回归问题的研究比较缺乏.本文从最小二乘模型讲起,对矩阵回归问题进行了总结和评述,同时列出了一些文献和简要介绍了我们的近期的部分工作.最后对于稳健矩阵回归,我们提出了一些展望和设想.     

Robust nonlinear optimization with conic representable uncertainty set

The robust optimization methodology is known as a popular method dealing with optimization problems with uncertain data and hard constraints. This methodology has been applied so far to various convex conic optimization problems where only their inequality constraints are subject to uncertainty. In this paper, the robust optimization methodology is applied to the general nonlinear programming (NLP) problem involving both uncertain inequality and equality constraints. The uncertainty set is defined by conic representable sets, the proposed uncertainty set is general enough to include many uncertainty sets, which have been used in literature, as special cases. The robust counterpart (RC) of the general NLP problem is approximated under this uncertainty set. It is shown that the resulting approximate RC of the general NLP problem is valid in a small neighborhood of the nominal value. Furthermore a rather general class of programming problems is posed that the robust counterparts of its problems can be derived exactly under the proposed uncertainty set. Our results show the applicability of robust optimization to a wider area of real applications and theoretical problems with more general uncertainty sets than those considered so far. The resulting robust counterparts which are traditional optimization problems make it possible to use existing algorithms of mathematical optimization to solve more complicated and general robust optimization problems.     

Robust discrete optimization and network flows

We propose an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0–1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0–1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard -approximable 0–1 discrete optimization problem, remains -approximable. Finally, we propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network. The research of the author was partially supported by the Singapore-MIT alliance.The research of the author is supported by a graduate scholarship from the National University of Singapore.Mathematics Subject Classification (2000): 90C10, 90C15     

基于泛岭估计对岭估计过度压缩的改进方法

岭估计是解决多元线性回归多重共线性问题的有效方法,是有偏的压缩估计。与普通最小二乘估计相比,岭估计可以降低参数估计的均方误差,但是却增大残差平方和,拟合效果变差。本文提出一种基于泛岭估计对岭估计过度压缩的改进方法,可以改进岭估计的拟合效果,减小岭估计残差平方和的增加幅度。     

Variable-sized uncertainty and inverse problems in robust optimization

In robust optimization, the general aim is to find a solution that performs well over a set of possible parameter outcomes, the so-called uncertainty set. In this paper, we assume that the uncertainty size is not fixed, and instead aim at finding a set of robust solutions that covers all possible uncertainty set outcomes. We refer to these problems as robust optimization with variable-sized uncertainty. We discuss how to construct smallest possible sets of min–max robust solutions and give bounds on their size.A special case of this perspective is to analyze for which uncertainty sets a nominal solution ceases to be a robust solution, which amounts to an inverse robust optimization problem. We consider this problem with a min–max regret objective and present mixed-integer linear programming formulations that can be applied to construct suitable uncertainty sets.Results on both variable-sized uncertainty and inverse problems are further supported with experimental data.     

Regularization tools and robust optimization for ill-conditioned least squares problem: A computational comparison

Least squares problems arise frequently in many disciplines such as image restorations. In these areas, for the given least squares problem, usually the coefficient matrix is ill-conditioned. Thus if the problem data are available with certain error, then after solving least squares problem with classical approaches we might end up with a meaningless solution. Tikhonov regularization, is one of the most widely used approaches to deal with such situations. In this paper, first we briefly describe these approaches, then the robust optimization framework which includes the errors in problem data is presented. Finally, our computational experiments on several ill-conditioned standard test problems using the regularization tools, a Matlab package for least squares problem, and the robust optimization framework, show that the latter approach may be the right choice.     

Robust penalty function method for an uncertain multi-time control optimization problems

This paper gives some new results on multi-time first-order PDE constrained control optimization problem in the face of data uncertainty (MCOPU). We obtain the robust sufficient optimality conditions for (MCOPU). Further, we construct an unconstrained multi-time control optimization problem (MCOPU)_? corresponding to (MCOPU) via absolute value penalty function method. Then, we show that the robust optimal solution to the constrained problem and a robust minimizer to the unconstrained problem are equivalent under suitable hypotheses. Moreover, we give some non-trivial examples to validate the results established in this paper.     

Outlier detection and robust covariance estimation using mathematical programming

The outlier detection problem and the robust covariance estimation problem are often interchangeable. Without outliers, the classical method of maximum likelihood estimation (MLE) can be used to estimate parameters of a known distribution from observational data. When outliers are present, they dominate the log likelihood function causing the MLE estimators to be pulled toward them. Many robust statistical methods have been developed to detect outliers and to produce estimators that are robust against deviation from model assumptions. However, the existing methods suffer either from computational complexity when problem size increases or from giving up desirable properties, such as affine equivariance. An alternative approach is to design a special mathematical programming model to find the optimal weights for all the observations, such that at the optimal solution, outliers are given smaller weights and can be detected. This method produces a covariance estimator that has the following properties: First, it is affine equivariant. Second, it is computationally efficient even for large problem sizes. Third, it easy to incorporate prior beliefs into the estimator by using semi-definite programming. The accuracy of this method is tested for different contamination models, including recently proposed ones. The method is not only faster than the Fast-MCD method for high dimensional data but also has reasonable accuracy for the tested cases.     

Proportion-based robust optimization and team orienteering problem with interval data

In this paper, a proportion-based robust optimization approach is developed to deal with uncertain combinatorial optimization problems. This approach assumes that a certain proportion of uncertain coefficients in each solution are allowed to change and optimizes a deterministic model so as to achieve a trade-off between optimality and feasibility when the coefficients change. We apply this approach on team orienteering problem with interval data (TOPID), a variant of vehicle routing problem, which has not yet been studied before. A branch and price algorithm is proposed to solve the robust counterpart by using two novel dominance relations. Finally, numerical study is performed. The results show the usefulness of the proposed robust optimization approach and the effectiveness of our algorithm.