Search

This paper considers the problem of supervised learning with linear methods when both features and labels can be corrupted, either in the form of heavy tailed data and/or corrupted rows. We introduce a combination of coordinate gradient descent as a learning algorithm together with robust estimators of the partial derivatives. This leads to robust statistical learning methods that have a numerical complexity nearly identical to non-robust ones based on empirical risk minimization. The main idea is simple: while robust learning with gradient descent requires the computational cost of robustly estimating the whole gradient to update all parameters, a parameter can be updated immediately using a robust estimator of a single partial derivative in coordinate gradient descent. We prove upper bounds on the generalization error of the algorithms derived from this idea, that control both the optimization and statistical errors with and without a strong convexity assumption of the risk. Finally, we propose an efficient implementation of this approach in a new Python library called linlearn, and demonstrate through extensive numerical experiments that our approach introduces a new interesting compromise between robustness, statistical performance and numerical efficiency for this problem. [ABSTRACT FROM AUTHOR]

Coordinate descent algorithms are popular in machine learning and large-scale data analysis problems due to their low computational cost iterative schemes and their improved performances. In this work, we define a monotone accelerated coordinate gradient descent-type method for problems consisting of minimizing f + g , where f is quadratic and g is nonsmooth and non-separable and has a low-complexity proximal mapping. The algorithm is enabled by employing the forward–backward envelope, a composite envelope that possess an exact smooth reformulation of f + g . We prove the algorithm achieves a convergence rate of O (1 / k 1.5) in terms of the original objective function, improving current coordinate descent-type algorithms. In addition, we describe an adaptive variant of the algorithm that backtracks the spectral information and coordinate Lipschitz constants of the problem. We numerically examine our algorithms on various settings, including two-dimensional total-variation-based image inpainting problems, showing a clear advantage in performance over current coordinate descent-type methods. [ABSTRACT FROM AUTHOR]

A novel trust region method for solving linearly constrained nonlinear programs is presented. The proposed technique is amenable to a distributed implementation, as its salient ingredient is an alternating projected gradient sweep in place of the Cauchy point computation. It is proven that the algorithm yields a sequence that globally converges to a critical point. As a result of some changes to the standard trust region method, namely a proximal regularisation of the trust region subproblem, it is shown that the local convergence rate is linear with an arbitrarily small ratio. Thus, convergence is locally almost superlinear, under standard regularity assumptions. The proposed method is successfully applied to compute local solutions to alternating current optimal power flow problems in transmission and distribution networks. Moreover, the new mechanism for computing a Cauchy point compares favourably against the standard projected search, as for its activity detection properties. [ABSTRACT FROM AUTHOR]

We propose an ℓ1-penalized algorithm for fitting high-dimensional generalized linear mixed models (GLMMs). GLMMs can be viewed as an extension of generalized linear models for clustered observations. Our Lasso-type approach for GLMMs should be mainly used as variable screening method to reduce the number of variables below the sample size. We then suggest a refitting by maximum likelihood based on the selected variables only. This is an effective correction to overcome problems stemming from the variable screening procedure that are more severe with GLMMs than for generalized linear models. We illustrate the performance of our algorithm on simulated as well as on real data examples. Supplementary materials are available online and the algorithm is implemented in the R packageglmmixedlasso. [ABSTRACT FROM PUBLISHER]

In this paper, we strengthen the edge-based semidefinite programming relaxation (ESDP) recently proposed by Wang, Zheng, Boyd, and Ye (SIAM J. Optim. 19:655-673, ) by adding lower bound constraints. We show that, when distances are exact, zero individual trace is necessary and sufficient for a sensor to be correctly positioned by an interior solution. To extend this characterization of accurately positioned sensors to the noisy case, we propose a noise-aware version of ESDP ( ρ-ESDP) and show that, for small noise, a small individual trace is equivalent to the sensor being accurately positioned by a certain analytic center solution. We then propose a postprocessing heuristic based on ρ-ESDP and a distributed algorithm to solve it. Our computational results show that, when applied to a solution obtained by solving ρ-ESDP proposed of Pong and Tseng (Math. Program. doi:), this heuristics usually improves the RMSD by at least 10%. Furthermore, it provides a certificate for identifying accurately positioned sensors in the refined solution, which is not common for existing refinement heuristics. [ABSTRACT FROM AUTHOR]

Recently Wang, Zheng, Boyd, and Ye (SIAM J Optim 19:655-673, 2008) proposed a further relaxation of the semidefinite programming (SDP) relaxation of the sensor network localization problem, named edge-based SDP (ESDP). In simulation, the ESDP is solved much faster by interior-point method than SDP relaxation, and the solutions found are comparable or better in approximation accuracy. We study some key properties of the ESDP relaxation, showing that, when distances are exact, zero individual trace is not only sufficient, but also necessary for a sensor to be correctly positioned by an interior solution. We also show via an example that, when distances are inexact, zero individual trace is insufficient for a sensor to be accurately positioned by an interior solution. We then propose a noise-aware robust version of ESDP relaxation for which small individual trace is necessary and sufficient for a sensor to be accurately positioned by a certain analytic center solution, assuming the noise level is sufficiently small. For this analytic center solution, the position error for each sensor is shown to be in the order of the square root of its trace. Lastly, we propose a log-barrier penalty coordinate gradient descent method to find such an analytic center solution. In simulation, this method is much faster than interior-point method for solving ESDP, and the solutions found are comparable in approximation accuracy. Moreover, the method can distribute its computation over the sensors via local communication, making it practical for positioning and tracking in real time. [ABSTRACT FROM AUTHOR]

In applications such as signal processing and statistics, many problems involve finding sparse solutions to under-determined linear systems of equations. These problems can be formulated as a structured nonsmooth optimization problems, i.e., the problem of minimizing ℓ-regularized linear least squares problems. In this paper, we propose a block coordinate gradient descent method (abbreviated as CGD) to solve the more general ℓ-regularized convex minimization problems, i.e., the problem of minimizing an ℓ-regularized convex smooth function. We establish a Q-linear convergence rate for our method when the coordinate block is chosen by a Gauss-Southwell-type rule to ensure sufficient descent. We propose efficient implementations of the CGD method and report numerical results for solving large-scale ℓ-regularized linear least squares problems arising in compressed sensing and image deconvolution as well as large-scale ℓ-regularized logistic regression problems for feature selection in data classification. Comparison with several state-of-the-art algorithms specifically designed for solving large-scale ℓ-regularized linear least squares or logistic regression problems suggests that an efficiently implemented CGD method may outperform these algorithms despite the fact that the CGD method is not specifically designed just to solve these special classes of problems. [ABSTRACT FROM AUTHOR]

Support vector machines (SVMs) training may be posed as a large quadratic program (QP) with bound constraints and a single linear equality constraint. We propose a (block) coordinate gradient descent method for solving this problem and, more generally, linearly constrained smooth optimization. Our method is closely related to decomposition methods currently popular for SVM training. We establish global convergence and, under a local error bound assumption (which is satisfied by the SVM QP), linear rate of convergence for our method when the coordinate block is chosen by a Gauss-Southwell-type rule to ensure sufficient descent. We show that, for the SVM QP with n variables, this rule can be implemented in O( n) operations using Rockafellar's notion of conformal realization. Thus, for SVM training, our method requires only O( n) operations per iteration and, in contrast to existing decomposition methods, achieves linear convergence without additional assumptions. We report our numerical experience with the method on some large SVM QP arising from two-class data classification. Our experience suggests that the method can be efficient for SVM training with nonlinear kernel. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the weighted sum of a smooth function f and a convex function P of n real variables subject to m linear equality constraints. We propose a block-coordinate gradient descent method for solving this problem, with the coordinate block chosen by a Gauss-Southwell- q rule based on sufficient predicted descent. We establish global convergence to first-order stationarity for this method and, under a local error bound assumption, linear rate of convergence. If f is convex with Lipschitz continuous gradient, then the method terminates in O( n2/ ε) iterations with an ε-optimal solution. If P is separable, then the Gauss-Southwell- q rule is implementable in O( n) operations when m=1 and in O( n2) operations when m>1. In the special case of support vector machines training, for which f is convex quadratic, P is separable, and m=1, this complexity bound is comparable to the best known bound for decomposition methods. If f is convex, then, by gradually reducing the weight on P to zero, the method can be adapted to solve the bilevel problem of minimizing P over the set of minima of f+ δ X, where X denotes the closure of the feasible set. This has application in the least 1-norm solution of maximum-likelihood estimation. [ABSTRACT FROM AUTHOR]