Relative Interior Rule in Block-Coordinate Descent
| Autor: | Daniel Prusa, Tomáš Werner, Tomáš Dlask |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
021103 operations research Linear programming Computer science business.industry 0211 other engineering and technologies 02 engineering and technology Linear programming relaxation Maxima and minima Relative interior Local optimum Convex optimization 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Artificial intelligence Graphical model business Coordinate descent Convex function Descent (mathematics) |
| Zdroj: | CVPR |
| DOI: | 10.1109/cvpr42600.2020.00758 |
| Popis: | It is well-known that for general convex optimization problems, block-coordinate descent can get stuck in poor local optima. Despite that, versions of this method known as convergent message passing are very successful to approximately solve the dual LP relaxation of the MAP inference problem in graphical models. In attempt to identify the reason why these methods often achieve good local minima, we argue that if in block-coordinate descent the set of minimizers over a variable block has multiple elements, one should choose an element from the relative interior of this set. We show that this rule is not worse than any other rule for choosing block-minimizers. Based on this observation, we develop a theoretical framework for block-coordinate descent applied to general convex problems. We illustrate this theory on convergent message-passing methods. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|