|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Faster Rates for training Max-Margin Markov Networks | | Xinhua Zhang
; Ankan Saha
; S.V.N. Vishwanathan
; | | Date: |
6 Mar 2010 | | Abstract: | Structured output prediction is an important machine learning problem both in
theory and practice, and the max-margin Markov network (mcn) is an effective
approach. All state-of-the-art algorithms for optimizing mcn objectives take
at least $O(1/epsilon)$ number of iterations to find an $epsilon$ accurate
solution. Recent results in structured optimization suggest that faster rates
are possible by exploiting the structure of the objective function. Towards
this end citet{Nesterov05} proposed an excessive gap reduction technique based
on Euclidean projections which converges in $O(1/sqrt{epsilon})$ iterations
on strongly convex functions. Unfortunately when applied to mcn s, this
approach does not admit graphical model factorization which, as in many
existing algorithms, is crucial for keeping the cost per iteration tractable.
In this paper, we present a new excessive gap reduction technique based on
Bregman projections which admits graphical model factorization naturally, and
converges in $O(1/sqrt{epsilon})$ iterations. Compared with existing
algorithms, the convergence rate of our method has better dependence on
$epsilon$ and other parameters of the problem, and can be easily kernelized. | | Source: | arXiv, 1003.1354 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER