Home | Search | Help  
Home Page Università di Genova

Technical Report Details


Date 9-6-2009
Number DISI-TR-09-01
Title An Iterative Projection Procedure to Solve Sparsity Based Regularization
Authors Sofia Mosci, Lorenzo Rosasco, Matteo Santoro, Alessandro Verri, SIlvia Villa
Bibtex Entry @techreport{morosa09, author={Mosci, S. and Rosasco, L. and Santoro, M. and Verri, A. and Villa, S.
E-mail mosci@disi.unige.it
Link ftp://ftp.disi.unige.it/person/MosciS/PAPERS/sparse_fenchel_TR.pdf
Abstract In this paper we propose a general framework to characterize and solve the optimization problems underlying a large class of sparsity based regularization algorithms. More precisely, we study the minimization of learning functionals that are sums of a differentiable data term and a convex non differentiable penalty. These latter penalties have recently become popular since they allow to enforce various kinds of sparsity in the solution. Leveraging on the theory of Fenchel duality and subdifferential calculus, we derive explicit optimality conditions for the regularized solution and propose an extremely simple, yet general, iterative projection algorithm whose convergence to the optimal solution can be proved. The generality of the framework is illustrated, considering several examples of regularization schemes including l_1 regularization (and several variants), multiple kernel learning and multi-task learning. Finally some distinctive features of the proposed framework are studied by empirical investigation.
Back to Technical Reports