@article{5975,
abstract = {We consider the recent formulation of the algorithmic Lov ́asz Local Lemma [N. Har-vey and J. Vondr ́ak, inProceedings of FOCS, 2015, pp. 1327–1345; D. Achlioptas and F. Iliopoulos,inProceedings of SODA, 2016, pp. 2024–2038; D. Achlioptas, F. Iliopoulos, and V. Kolmogorov,ALocal Lemma for Focused Stochastic Algorithms, arXiv preprint, 2018] for finding objects that avoid“bad features,” or “flaws.” It extends the Moser–Tardos resampling algorithm [R. A. Moser andG. Tardos,J. ACM, 57 (2010), 11] to more general discrete spaces. At each step the method picks aflaw present in the current state and goes to a new state according to some prespecified probabilitydistribution (which depends on the current state and the selected flaw). However, the recent formu-lation is less flexible than the Moser–Tardos method since it requires a specific flaw selection rule,whereas the algorithm of Moser and Tardos allows an arbitrary rule (and thus can potentially beimplemented more efficiently). We formulate a new “commutativity” condition and prove that it issufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additionalassumption. We then show that existing resampling oracles for perfect matchings and permutationsdo satisfy this condition.},
author = {Kolmogorov, Vladimir},
issn = {0097-5397},
journal = {SIAM Journal on Computing},
number = {6},
pages = {2029--2056},
publisher = {Society for Industrial & Applied Mathematics (SIAM)},
title = {{Commutativity in the algorithmic Lovász local lemma}},
doi = {10.1137/16m1093306},
volume = {47},
year = {2018},
}
@inproceedings{273,
abstract = {The accuracy of information retrieval systems is often measured using complex loss functions such as the average precision (AP) or the normalized discounted cumulative gain (NDCG). Given a set of positive and negative samples, the parameters of a retrieval system can be estimated by minimizing these loss functions. However, the non-differentiability and non-decomposability of these loss functions does not allow for simple gradient based optimization algorithms. This issue is generally circumvented by either optimizing a structured hinge-loss upper bound to the loss function or by using asymptotic methods like the direct-loss minimization framework. Yet, the high computational complexity of loss-augmented inference, which is necessary for both the frameworks, prohibits its use in large training data sets. To alleviate this deficiency, we present a novel quicksort flavored algorithm for a large class of non-decomposable loss functions. We provide a complete characterization of the loss functions that are amenable to our algorithm, and show that it includes both AP and NDCG based loss functions. Furthermore, we prove that no comparison based algorithm can improve upon the computational complexity of our approach asymptotically. We demonstrate the effectiveness of our approach in the context of optimizing the structured hinge loss upper bound of AP and NDCG loss for learning models for a variety of vision tasks. We show that our approach provides significantly better results than simpler decomposable loss functions, while requiring a comparable training time.},
author = {Mohapatra, Pritish and Rolinek, Michal and Jawahar, C V and Kolmogorov, Vladimir and Kumar, M Pawan},
booktitle = {2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition},
isbn = {9781538664209},
location = {Salt Lake City, UT, USA},
pages = {3693--3701},
publisher = {IEEE},
title = {{Efficient optimization for rank-based loss functions}},
doi = {10.1109/cvpr.2018.00389},
year = {2018},
}
@misc{5573,
abstract = {Graph matching problems for large displacement optical flow of RGB-D images.},
author = {Alhaija, Hassan and Sellent, Anita and Kondermann, Daniel and Rother, Carsten},
keyword = {graph matching, quadratic assignment problem<},
publisher = {IST Austria},
title = {{Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow}},
doi = {10.15479/AT:ISTA:82},
year = {2018},
}
@inproceedings{915,
abstract = {We propose a dual decomposition and linear program relaxation of the NP-hard minimum cost multicut problem. Unlike other polyhedral relaxations of the multicut polytope, it is amenable to efficient optimization by message passing. Like other polyhedral relaxations, it can be tightened efficiently by cutting planes. We define an algorithm that alternates between message passing and efficient separation of cycle- and odd-wheel inequalities. This algorithm is more efficient than state-of-the-art algorithms based on linear programming, including algorithms written in the framework of leading commercial software, as we show in experiments with large instances of the problem from applications in computer vision, biomedical image analysis and data mining.},
author = {Swoboda, Paul and Andres, Bjoern},
isbn = {978-153860457-1},
location = {Honolulu, HA, United States},
pages = {4990--4999},
publisher = {IEEE},
title = {{A message passing algorithm for the minimum cost multicut problem}},
doi = {10.1109/CVPR.2017.530},
volume = {2017},
year = {2017},
}
@inproceedings{1192,
abstract = {The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Knowing that edge CSP is tractable for even Δ-matroid constraints allows us to extend the tractability result to a larger class of Δ-matroids that includes many classes that were known to be tractable before, namely co-independent, compact, local and binary.},
author = {Kazda, Alexandr and Kolmogorov, Vladimir and Rolinek, Michal},
isbn = {978-161197478-2},
location = {Barcelona, Spain},
pages = {307 -- 326},
publisher = {SIAM},
title = {{Even delta-matroids and the complexity of planar Boolean CSPs}},
doi = {10.1137/1.9781611974782.20},
year = {2017},
}