Speaker: Prof. Ademir Ribeiro
Date and time: Wednesday 25 March 2015 @ 2:00 PM
Venue: Room 218 Huxley Building
Map: https://workspace.imperial.ac.uk/campusinfo/public/sthkencampus.pdf
Title: The Complexity of Primal-Dual Fixed Point Methods for Ridge Regression
Abstract:
We study the ridge regression (L2 regularized least squares) problem and its dual, which is also a ridge regression problem. We observe that the optimality conditions can be formulated in several different but equivalent ways, in the form of a linear system involving a structured matrix depending on a single “stepsize” parameter which we introduce for regularization purposes. This leads to the idea of studying and comparing, in theory and practice, the performance of the fixed point method applied to these reformulations. We compute the optimal stepsize parameters and uncover interesting connections between the complexity bounds of the variants of the fixed point scheme we consider. These connections follow from a close link between the spectral properties of the associated matrices. For instance, some reformulations involve purely imaginary eigenvalues; some involve real eigenvalues and others have all eigenvalues on the complex circle. We show that the deterministic Quartz method—which is a special case of the randomized dual coordinate ascent method with arbitrary sampling recently developed by Qu, Richtarik and Zhang—can be cast in our framework, and achieves the best rate in theory and in numerical experiments among the fixed point methods we study. This is joint work with Peter Richtarik (Edinburgh).
Bio:
I am an Associate Professor at Department of Mathematics, Federal University of Parana, Brazil, since 1992. I got my undergraduate degree in Mathematics at Federal University of Parana in 1989. In 1993 I finished my MSc in Mathematics, at IMPA – National Institute for Pure and Applied Mathematics. I got my PhD in Optimization at Federal University of Parana in 2005.
My current research interests are applied mathematics, continuous optimization, global and local convergence of algorithms as filter and trust region methods for nonlinear programming and convex optimization, complexity of direct search methods, among others. I have been published papers in journals like Applied Mathematics and Computation, Applied Mathematical Modelling, Optimization, Computational Optimization and Applications, Mathematical Programming and SIAM Journal on Optimization. I have been given talks in some meetings like Optimization Conference (Porto 2007 and Guimarães 2014), Brazilian Workshop on Continuous Optimization (Rio de Janeiro 2009 and Florianópolis 2014) and International Symposium on Mathematical Programming (Rio de Janeiro 2006 and Berlin 2012). I have supervised 2 PhD and 6 MSc students.
In joint work with Elizabeth Wegner Karas, I also have published a book (in Portuguese), called Continuous Optimization: Theoretical and computational aspects. Cengage Learning, Sao Paulo, Brazil, 2013.