Lower Bounds for BMRM and Faster Rates for Training SVMs

Details Lower Bounds for BMRM and Faster Rates for Training SVMs Lower Bounds for BMRM and Faster Rates for Training SVMs

2009-09-07

arxiv.org/abs/0909.1334v2

Computer Science

Learning

21 pages, 49 figures

Scientific paper

Regularized risk minimization with the binary hinge loss and its variants lies at the heart of many machine learning problems. Bundle methods for regularized risk minimization (BMRM) and the closely related SVMStruct are considered the best general purpose solvers to tackle this problem. It was recently shown that BMRM requires $O(1/\epsilon)$ iterations to converge to an $\epsilon$ accurate solution. In the first part of the paper we use the Hadamard matrix to construct a regularized risk minimization problem and show that these rates cannot be improved. We then show how one can exploit the structure of the objective function to devise an algorithm for the binary hinge loss which converges to an $\epsilon$ accurate solution in $O(1/\sqrt{\epsilon})$ iterations.

Affiliated with

Also associated with

No associations

Rating

Lower Bounds for BMRM and Faster Rates for Training SVMs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lower Bounds for BMRM and Faster Rates for Training SVMs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Bounds for BMRM and Faster Rates for Training SVMs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-107399