1,721,052 research outputs found
An Improved Gradient Projection-based Decomposition Technique for Support Vector Machines
No full textSupport vector machines, Quadratic programs, Decomposition techniques, Gradient projection methods, Large-scale problems,
Convergence properties of a projection method for affine variational inequality problems
No full textSee directly the article
Error analysis in equality constrained quadratic optimization problems
No full textIn questo lavoro si considera la risoluzione numerica di problemi di programmazione quadratica con vincoli lineari di uguaglianza. Quando le dimensioni e la sparsità del problema sono particolarmente elevate, un approccio efficiente consiste nel trasformare il problema originario in una successione di sottoproblemi dello stesso tipo, ma di più facile risoluzione, mediante la decomposizione della matrice della funzione obiettivo. Il comportamento del metodo iterativo derivante da quest’approccio viene esaminato in corrispondenza alla scelta di due diverse strategie per la risoluzione dei sottoproblemi. Quando la matrice della funzione obiettivo e la matrice dei vincoli sono dense e di piccole o medie dimensioni, il problema originario può essere risolto con metodi diretti di eliminazione che si basano sulla decomposizione QR della matrice dei vincoli per eliminare alcune variabili e risolvere un problema equivalente di programmazione quadratica non vincolata di dimensioni più piccole. La stabilità numerica di un metodo di questa classe, il metodo di eliminazione diretta, viene studiata mediante la tecnica dell’analisi all’indietro dell'errore
On a class of iterative methods for large-scale convex quadratic programs
No full textWe analyse the efficiency of a class of iterative methods for solving large scale convex quadratic programs. These methods, known as splitting methods and projection methods, require to solve a sequence of easy strictly convex quadratic programming subproblems obtained by splitting the matrix of the objective function. We describe in details the techniques used for generating the large and sparse test problems on which the computational behaviour of the methods is studied
On the stability of the direct elimination method for equality constrained least squares problems
No full textA backward error analysis of the direct elimination method for linear equality constrained least squares problems is presented. It is proved that the solution computed by the method is the exact solution of a perturbed problem and bounds for data perturbations are given. The numerical stability of the method is related to the way in which the constraints are used to eliminate variables and these theoretical conclusions are confirmed by a numerical example
Variable Projection Methods for Large Quadratic Programs in Training Support Vector Machines
No full textIn this paper we analyse the variable projection methods for the solution of the convex quadratic programming problem arising in training the learning techinque named Support Vector Machine. Since the Hessian matrix of the objective function is large and dense the problem is faced by decomposition techniques that require to solve a sequence of quadratic programming subproblems of smaller size. For the solution of these subproblems, we consider variable projection methods based on different steplength updating rules. In particular, we introduce a new steplength selection that implies remarkable convegence rate improvements. The effectiveness of the variable projection method combined with this steplength selection is evaluated in comparison with standard routines on well known benchmark problems
On the working set selection in gradient projection-based decomposition techniques for support vector machines
No full textThis work deals with special decomposition techniques for the large quadratic program arising in training support vector machines. These approaches split the problem into a sequence of quadratic programming (QP) subproblems which can be solved by efficient gradient projection methods recently proposed. Owing to the ability of decomposing the problem into much larger subproblems than standard decomposition packages, these techniques show promising performance and are well suited for parallelization. Here, we discuss a crucial aspect for their effectiveness: the selection of the working set; that is, the index set of the variables to be optimized at each step through the QP subproblem. We analyze the most popular working set selections and develop a new selection strategy that improves the convergence rate of the decomposition schemes based on large sized working sets. The effectiveness of the proposed strategy within the gradient projection-based decomposition techniques is shown by numerical experiments on large benchmark problems, both in serial and in parallel environments
A practical use of regularization for supervised learning with kernel methods
No full textIn several supervised learning applications, it happens that reconstruction methods have to be applied repeatedly before being able to achieve the final solution. In these situations, the availability of learning algorithms able to provide effective predictors in a very short time may lead to remarkable improvements in the overall computational requirement. Here we consider the kernel ridge regression problem and we look for predictors given by a linear combination of kernel functions plus a constant term, showing that an effective solution can be obtained very fastly by applying specific regularization algorithms directly to the linear system arising from the Empirical Risk Minimization problem
Inverse problems in machine learning: an application to brain activity interpretation
Full text linkIn a typical machine learning problem one has to build a model from a finite training set which is able to generalize the properties characterizing the examples of the training set to new examples. The model has to reflect as much as possible the set of trainingexamples but, especially in real-world problems in which the data are often corrupted by different sources of noise, it has to avoid a too strict dependence on the training examples themselves. Recent studies on the relationship between this kind of learning problem and the regularization theory for ill-posed inverse problems have given rise to new regularized learning algorithms. In this paper we recall some of these learning methods and we propose an accelerated version of the classical Landweber iterative scheme which results particularly efficient from thecomputational viewpoint. Finally, we compare the performances of these methods with the classical Support Vector Machines learning algorithm on a real-world experiment concerning brain activity interpretation through the analysis of functional magnetic resonance imaging data
- …
