Name
Abstract | ||
|---|---|---|
We consider (a subclass of) convex qua- dratic optimization problems and analyze decomposition algorithms that perform, at least approximately, steepest-descent ex- act line search. We show that these al- gorithms, when implemented properly, are within ǫ of optimality after O(log1/ǫ) it- erations for strictly convex cost functions, and after O(1/ǫ) iterations in the general case.1 Our analysis is general enough to cover the algorithms that are used in soft- ware packages like SVMTorch and (first or second order) LibSVM. To the best of our knowledge, this is the first paper coming up with a convergence rate for these algo- rithms without introducing unnecessarily restrictive assumptions. |
Year | Venue | DocType |
|---|---|---|
2009 | COLT | Conference |
Citations | PageRank | References |
13 | 10.60 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hans-Ulrich Simon | 1 | 567 | 104.52 |
| Nikolas List | 2 | 59 | 31.35 |