Friday, 10:30 - 10:55 h, Room: H 1028

 

Pradeep Ravikumar
Nearest neighbor based greedy coordinate descent

Coauthors: Inderjit Dhillon, Ambuj Tewari

 

Abstract:
Increasingly, optimization problems in machine learning, especially those arising from high-dimensional statistical estimation, have a large number of variables. Modern statistical estimators developed over the past decade have statistical or sample complexity that depends only weakly on the number of parameters when there is some structure to the problem, such as sparsity. A central question is whether similar advances can be made in their computational complexity as well. In this talk, we propose strategies that indicate that such advances can indeed be made. In particular, we investigate the greedy coordinate descent algorithm, and note that performing the greedy step efficiently weakens the costly dependence on the problem size provided the solution is sparse. We then propose a suite of methods that perform these greedy steps efficiently by a reduction to nearest neighbor search. We also develop a practical implementation of our algorithm that combines greedy coordinate descent with locality sensitive hashing, using which we are not only able to significantly speed up the vanilla greedy method, but also outperform cyclic descent when the problem size becomes large.

 

Talk 1 of the invited session Fri.1.H 1028
"Greedy algorithms for sparse optimization" [...]
Cluster 21
"Sparse optimization & compressed sensing" [...]

 

  Payday Loans In Virginia. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.