[{"quality_controlled":"1","doi":"10.1109/CVPR52729.2023.01153","publication_identifier":{"issn":["1063-6919"],"isbn":["9798350301298"]},"language":[{"iso":"eng"}],"conference":{"end_date":"2023-06-24","start_date":"2023-06-17","name":"CVPR: Conference on Computer Vision and Pattern Recognition","location":"Vancouver, Canada"},"title":"Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions","arxiv":1,"day":"22","author":[{"full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov","first_name":"Vladimir"}],"scopus_import":"1","article_processing_charge":"No","publication":"Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition","department":[{"_id":"VlKo"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IEEE","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2010.09567"}],"date_published":"2023-08-22T00:00:00Z","publication_status":"published","oa":1,"citation":{"ama":"Kolmogorov V. Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Vol 2023. IEEE; 2023:11980-11989. doi:10.1109/CVPR52729.2023.01153","apa":"Kolmogorov, V. (2023). Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Vol. 2023, pp. 11980–11989). Vancouver, Canada: IEEE. https://doi.org/10.1109/CVPR52729.2023.01153","mla":"Kolmogorov, Vladimir. “Solving Relaxations of MAP-MRF Problems: Combinatorial in-Face Frank-Wolfe Directions.” Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2023, IEEE, 2023, pp. 11980–89, doi:10.1109/CVPR52729.2023.01153.","ista":"Kolmogorov V. 2023. Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition vol. 2023, 11980–11989.","chicago":"Kolmogorov, Vladimir. “Solving Relaxations of MAP-MRF Problems: Combinatorial in-Face Frank-Wolfe Directions.” In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2023:11980–89. IEEE, 2023. https://doi.org/10.1109/CVPR52729.2023.01153.","ieee":"V. Kolmogorov, “Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vancouver, Canada, 2023, vol. 2023, pp. 11980–11989.","short":"V. Kolmogorov, in:, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, IEEE, 2023, pp. 11980–11989."},"intvolume":" 2023","status":"public","external_id":{"arxiv":["2010.09567"]},"date_created":"2023-10-22T22:01:16Z","volume":2023,"abstract":[{"lang":"eng","text":"We consider the problem of solving LP relaxations of MAP-MRF inference problems, and in particular the method proposed recently in [16], [35]. As a key computational subroutine, it uses a variant of the Frank-Wolfe (FW) method to minimize a smooth convex function over a combinatorial polytope. We propose an efficient implementation of this subroutine based on in-face Frank-Wolfe directions, introduced in [4] in a different context. More generally, we define an abstract data structure for a combinatorial subproblem that enables in-face FW directions, and describe its specialization for tree-structured MAP-MRF inference subproblems. Experimental results indicate that the resulting method is the current state-of-art LP solver for some classes of problems. Our code is available at pub.ist.ac.at/~vnk/papers/IN-FACE-FW.html."}],"date_updated":"2023-10-31T12:01:24Z","oa_version":"Preprint","month":"08","type":"conference","page":"11980-11989","_id":"14448","year":"2023"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"VlKo"}],"publication":"50th International Colloquium on Automata, Languages, and Programming","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_processing_charge":"Yes","scopus_import":"1","author":[{"full_name":"Harris, David G.","first_name":"David G.","last_name":"Harris"},{"first_name":"Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir"}],"file":[{"file_name":"2023_LIPIcsICALP_Harris.pdf","success":1,"creator":"dernst","file_size":917791,"relation":"main_file","content_type":"application/pdf","checksum":"6dee0684245bb1c524b9c955db1e933d","file_id":"14088","date_updated":"2023-08-21T06:45:16Z","access_level":"open_access","date_created":"2023-08-21T06:45:16Z"}],"day":"01","article_number":"72","arxiv":1,"title":"Parameter estimation for Gibbs distributions","conference":{"end_date":"2023-07-14","location":"Paderborn, Germany","name":"ICALP: International Colloquium on Automata, Languages, and Programming","start_date":"2023-07-10"},"language":[{"iso":"eng"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772785"]},"doi":"10.4230/LIPIcs.ICALP.2023.72","quality_controlled":"1","acknowledgement":"We thank Heng Guo for helpful explanations of algorithms for sampling connected subgraphs and matchings, Maksym Serbyn for bringing to our attention the Wang-Landau algorithm and its use in physics.","year":"2023","_id":"14084","oa_version":"Published Version","month":"07","type":"conference","abstract":[{"lang":"eng","text":"A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We will consider sampling problems which come from Gibbs distributions, which are families of probability distributions over a discrete space Ω with probability mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max] and H(ω) ∈ {0} ∪ [1, n].\r\nThe partition function is the normalization factor Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the log partition ratio is defined as q = (log Z(β_max))/Z(β_min)\r\nWe develop a number of algorithms to estimate the counts c_x using roughly Õ(q/ε²) samples for general Gibbs distributions and Õ(n²/ε²) samples for integer-valued distributions (ignoring some second-order terms and parameters), We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs and perfect matchings in a graph."}],"date_updated":"2023-08-21T06:49:11Z","volume":261,"file_date_updated":"2023-08-21T06:45:16Z","date_created":"2023-08-20T22:01:14Z","alternative_title":["LIPIcs"],"external_id":{"arxiv":["2007.10824"]},"status":"public","intvolume":" 261","citation":{"ista":"Harris DG, Kolmogorov V. 2023. Parameter estimation for Gibbs distributions. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 72.","mla":"Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” 50th International Colloquium on Automata, Languages, and Programming, vol. 261, 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.72.","apa":"Harris, D. G., & Kolmogorov, V. (2023). Parameter estimation for Gibbs distributions. In 50th International Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.72","ama":"Harris DG, Kolmogorov V. Parameter estimation for Gibbs distributions. In: 50th International Colloquium on Automata, Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.72","short":"D.G. Harris, V. Kolmogorov, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ieee":"D. G. Harris and V. Kolmogorov, “Parameter estimation for Gibbs distributions,” in 50th International Colloquium on Automata, Languages, and Programming, Paderborn, Germany, 2023, vol. 261.","chicago":"Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” In 50th International Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.72."},"publication_status":"published","oa":1,"has_accepted_license":"1","ddc":["000","510"],"date_published":"2023-07-01T00:00:00Z"},{"doi":"10.3233/IDA-205623","quality_controlled":"1","publication_identifier":{"issn":["1088-467X"],"eissn":["1571-4128"]},"isi":1,"issue":"1","language":[{"iso":"eng"}],"title":"Combining pattern-based CRFs and weighted context-free grammars","arxiv":1,"author":[{"last_name":"Takhanov","first_name":"Rustem","id":"2CCAC26C-F248-11E8-B48F-1D18A9856A87","full_name":"Takhanov, Rustem"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov"}],"day":"14","publication":"Intelligent Data Analysis","article_type":"original","scopus_import":"1","article_processing_charge":"No","publisher":"IOS Press","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","department":[{"_id":"VlKo"}],"date_published":"2022-01-14T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1404.5475","open_access":"1"}],"oa":1,"publication_status":"published","intvolume":" 26","citation":{"ama":"Takhanov R, Kolmogorov V. Combining pattern-based CRFs and weighted context-free grammars. Intelligent Data Analysis. 2022;26(1):257-272. doi:10.3233/IDA-205623","apa":"Takhanov, R., & Kolmogorov, V. (2022). Combining pattern-based CRFs and weighted context-free grammars. Intelligent Data Analysis. IOS Press. https://doi.org/10.3233/IDA-205623","mla":"Takhanov, Rustem, and Vladimir Kolmogorov. “Combining Pattern-Based CRFs and Weighted Context-Free Grammars.” Intelligent Data Analysis, vol. 26, no. 1, IOS Press, 2022, pp. 257–72, doi:10.3233/IDA-205623.","ista":"Takhanov R, Kolmogorov V. 2022. Combining pattern-based CRFs and weighted context-free grammars. Intelligent Data Analysis. 26(1), 257–272.","chicago":"Takhanov, Rustem, and Vladimir Kolmogorov. “Combining Pattern-Based CRFs and Weighted Context-Free Grammars.” Intelligent Data Analysis. IOS Press, 2022. https://doi.org/10.3233/IDA-205623.","ieee":"R. Takhanov and V. Kolmogorov, “Combining pattern-based CRFs and weighted context-free grammars,” Intelligent Data Analysis, vol. 26, no. 1. IOS Press, pp. 257–272, 2022.","short":"R. Takhanov, V. Kolmogorov, Intelligent Data Analysis 26 (2022) 257–272."},"external_id":{"isi":["000749997700015"],"arxiv":["1404.5475"]},"status":"public","volume":26,"date_created":"2022-02-06T23:01:32Z","page":"257-272","oa_version":"Preprint","type":"journal_article","month":"01","abstract":[{"lang":"eng","text":"We consider two models for the sequence labeling (tagging) problem. The first one is a Pattern-Based Conditional Random Field (PB), in which the energy of a string (chain labeling) x=x1…xn∈Dn is a sum of terms over intervals [i,j] where each term is non-zero only if the substring xi…xj equals a prespecified word w∈Λ. The second model is a Weighted Context-Free Grammar (WCFG) frequently used for natural language processing. PB and WCFG encode local and non-local interactions respectively, and thus can be viewed as complementary. We propose a Grammatical Pattern-Based CRF model (GPB) that combines the two in a natural way. We argue that it has certain advantages over existing approaches such as the Hybrid model of Benedí and Sanchez that combines N-grams and WCFGs. The focus of this paper is to analyze the complexity of inference tasks in a GPB such as computing MAP. We present a polynomial-time algorithm for general GPBs and a faster version for a special case that we call Interaction Grammars."}],"date_updated":"2023-08-02T14:09:41Z","_id":"10737","year":"2022"},{"external_id":{"arxiv":["2109.10203"]},"status":"public","citation":{"chicago":"Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2109.10203.","ieee":"M. Dvorak and V. Kolmogorov, “Generalized minimum 0-extension problem and discrete convexity,” arXiv. .","short":"M. Dvorak, V. Kolmogorov, ArXiv (n.d.).","ama":"Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete convexity. arXiv. doi:10.48550/arXiv.2109.10203","apa":"Dvorak, M., & Kolmogorov, V. (n.d.). Generalized minimum 0-extension problem and discrete convexity. arXiv. https://doi.org/10.48550/arXiv.2109.10203","mla":"Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” ArXiv, 2109.10203, doi:10.48550/arXiv.2109.10203.","ista":"Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete convexity. arXiv, 2109.10203."},"publication_status":"submitted","oa":1,"has_accepted_license":"1","ddc":["004"],"date_published":"2021-09-21T00:00:00Z","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2109.10203","open_access":"1"}],"year":"2021","_id":"10045","date_updated":"2023-05-03T10:40:16Z","abstract":[{"lang":"eng","text":"Given a fixed finite metric space (V,μ), the {\\em minimum 0-extension problem}, denoted as 0-Ext[μ], is equivalent to the following optimization problem: minimize function of the form minx∈Vn∑ifi(xi)+∑ijcijμ(xi,xj) where cij,cvi are given nonnegative costs and fi:V→R are functions given by fi(xi)=∑v∈Vcviμ(xi,v). The computational complexity of 0-Ext[μ] has been recently established by Karzanov and by Hirai: if metric μ is {\\em orientable modular} then 0-Ext[μ] can be solved in polynomial time, otherwise 0-Ext[μ] is NP-hard. To prove the tractability part, Hirai developed a theory of discrete convex functions on orientable modular graphs generalizing several known classes of functions in discrete convex analysis, such as L♮-convex functions. We consider a more general version of the problem in which unary functions fi(xi) can additionally have terms of the form cuv;iμ(xi,{u,v}) for {u,v}∈F, where set F⊆(V2) is fixed. We extend the complexity classification above by providing an explicit condition on (μ,F) for the problem to be tractable. In order to prove the tractability part, we generalize Hirai's theory and define a larger class of discrete convex functions. It covers, in particular, another well-known class of functions, namely submodular functions on an integer lattice. Finally, we improve the complexity of Hirai's algorithm for solving 0-Ext on orientable modular graphs.\r\n"}],"month":"09","oa_version":"Preprint","type":"preprint","file_date_updated":"2021-09-27T10:54:51Z","date_created":"2021-09-27T10:48:23Z","keyword":["minimum 0-extension problem","metric labeling problem","discrete metric spaces","metric extensions","computational complexity","valued constraint satisfaction problems","discrete convex analysis","L-convex functions"],"language":[{"iso":"eng"}],"doi":"10.48550/arXiv.2109.10203","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"GradSch"},{"_id":"VlKo"}],"publication":"arXiv","article_processing_charge":"No","author":[{"first_name":"Martin","last_name":"Dvorak","full_name":"Dvorak, Martin","id":"40ED02A8-C8B4-11E9-A9C0-453BE6697425","orcid":"0000-0001-5293-214X"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov"}],"file":[{"success":1,"file_name":"Generalized-0-Ext.pdf","content_type":"application/pdf","relation":"main_file","file_size":603672,"creator":"mdvorak","date_updated":"2021-09-27T10:54:51Z","file_id":"10046","checksum":"e7e83065f7bc18b9c188bf93b5ca5db6","date_created":"2021-09-27T10:54:51Z","access_level":"open_access"}],"day":"21","arxiv":1,"title":"Generalized minimum 0-extension problem and discrete convexity","article_number":"2109.10203"},{"intvolume":" 207","citation":{"ieee":"D. G. Harris, F. Iliopoulos, and V. Kolmogorov, “A new notion of commutativity for the algorithmic Lovász Local Lemma,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Virtual, 2021, vol. 207.","chicago":"Harris, David G., Fotis Iliopoulos, and Vladimir Kolmogorov. “A New Notion of Commutativity for the Algorithmic Lovász Local Lemma.” In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Vol. 207. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31.","short":"D.G. Harris, F. Iliopoulos, V. Kolmogorov, in:, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","ama":"Harris DG, Iliopoulos F, Kolmogorov V. A new notion of commutativity for the algorithmic Lovász Local Lemma. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Vol 207. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.31","mla":"Harris, David G., et al. “A New Notion of Commutativity for the Algorithmic Lovász Local Lemma.” Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, vol. 207, 31, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.APPROX/RANDOM.2021.31.","ista":"Harris DG, Iliopoulos F, Kolmogorov V. 2021. A new notion of commutativity for the algorithmic Lovász Local Lemma. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX/RANDOM: Approximation Algorithms for Combinatorial Optimization Problems/ Randomization and Computation, LIPIcs, vol. 207, 31.","apa":"Harris, D. G., Iliopoulos, F., & Kolmogorov, V. (2021). A new notion of commutativity for the algorithmic Lovász Local Lemma. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Vol. 207). Virtual: Schloss Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31"},"alternative_title":["LIPIcs"],"external_id":{"arxiv":["2008.05569"]},"status":"public","date_published":"2021-09-15T00:00:00Z","ddc":["000"],"oa":1,"publication_status":"published","has_accepted_license":"1","_id":"10072","acknowledgement":"Fotis Iliopoulos: This material is based upon work directly supported by the IAS Fund for Math and indirectly supported by the National Science Foundation Grant No. CCF-1900460. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. This work is also supported by the National Science Foundation Grant No. CCF-1815328.\r\nVladimir Kolmogorov: Supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160.","year":"2021","volume":207,"date_created":"2021-10-03T22:01:22Z","file_date_updated":"2021-10-06T13:51:54Z","oa_version":"Published Version","month":"09","type":"conference","abstract":[{"lang":"eng","text":"The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakthrough paper of Moser and Tardos and follow-up works revealed that the LLL has intimate connections with a class of stochastic local search algorithms for finding such desirable objects. In particular, it can be seen as a sufficient condition for this type of algorithms to converge fast. Besides conditions for existence of and fast convergence to desirable objects, one may naturally ask further questions regarding properties of these algorithms. For instance, \"are they parallelizable?\", \"how many solutions can they output?\", \"what is the expected \"weight\" of a solution?\", etc. These questions and more have been answered for a class of LLL-inspired algorithms called commutative. In this paper we introduce a new, very natural and more general notion of commutativity (essentially matrix commutativity) which allows us to show a number of new refined properties of LLL-inspired local search algorithms with significantly simpler proofs."}],"date_updated":"2022-03-18T10:08:25Z","conference":{"end_date":"2021-08-18","location":"Virtual","name":"APPROX/RANDOM: Approximation Algorithms for Combinatorial Optimization Problems/ Randomization and Computation","start_date":"2021-08-16"},"language":[{"iso":"eng"}],"project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"doi":"10.4230/LIPIcs.APPROX/RANDOM.2021.31","quality_controlled":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-9597-7207-5"]},"publication":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_processing_charge":"Yes","scopus_import":"1","ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","department":[{"_id":"VlKo"}],"article_number":"31","title":"A new notion of commutativity for the algorithmic Lovász Local Lemma","arxiv":1,"author":[{"last_name":"Harris","first_name":"David G.","full_name":"Harris, David G."},{"full_name":"Iliopoulos, Fotis","first_name":"Fotis","last_name":"Iliopoulos"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir"}],"file":[{"date_updated":"2021-10-06T13:51:54Z","file_id":"10098","checksum":"9d2544d53aa5b01565c6891d97a4d765","date_created":"2021-10-06T13:51:54Z","access_level":"open_access","success":1,"file_name":"2021_LIPIcs_Harris.pdf","relation":"main_file","content_type":"application/pdf","file_size":804472,"creator":"cchlebak"}],"day":"15"},{"publication_status":"published","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/2101.12617","open_access":"1"}],"quality_controlled":"1","date_published":"2021-07-01T00:00:00Z","external_id":{"arxiv":["2101.12617"]},"status":"public","project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"citation":{"ama":"Kolmogorov V, Pock T. One-sided Frank-Wolfe algorithms for saddle problems. In: 38th International Conference on Machine Learning. ; 2021.","apa":"Kolmogorov, V., & Pock, T. (2021). One-sided Frank-Wolfe algorithms for saddle problems. In 38th International Conference on Machine Learning. Virtual.","mla":"Kolmogorov, Vladimir, and Thomas Pock. “One-Sided Frank-Wolfe Algorithms for Saddle Problems.” 38th International Conference on Machine Learning, 2021.","ista":"Kolmogorov V, Pock T. 2021. One-sided Frank-Wolfe algorithms for saddle problems. 38th International Conference on Machine Learning. ICML: International Conference on Machine Learning.","chicago":"Kolmogorov, Vladimir, and Thomas Pock. “One-Sided Frank-Wolfe Algorithms for Saddle Problems.” In 38th International Conference on Machine Learning, 2021.","ieee":"V. Kolmogorov and T. Pock, “One-sided Frank-Wolfe algorithms for saddle problems,” in 38th International Conference on Machine Learning, Virtual, 2021.","short":"V. Kolmogorov, T. Pock, in:, 38th International Conference on Machine Learning, 2021."},"conference":{"end_date":"2021-07-24","location":"Virtual","name":"ICML: International Conference on Machine Learning","start_date":"2021-07-18"},"date_updated":"2021-12-17T09:06:46Z","abstract":[{"lang":"eng","text":"We study a class of convex-concave saddle-point problems of the form minxmaxy⟨Kx,y⟩+fP(x)−h∗(y) where K is a linear operator, fP is the sum of a convex function f with a Lipschitz-continuous gradient and the indicator function of a bounded convex polytope P, and h∗ is a convex (possibly nonsmooth) function. Such problem arises, for example, as a Lagrangian relaxation of various discrete optimization problems. Our main assumptions are the existence of an efficient linear minimization oracle (lmo) for fP and an efficient proximal map for h∗ which motivate the solution via a blend of proximal primal-dual algorithms and Frank-Wolfe algorithms. In case h∗ is the indicator function of a linear constraint and function f is quadratic, we show a O(1/n2) convergence rate on the dual objective, requiring O(nlogn) calls of lmo. If the problem comes from the constrained optimization problem minx∈Rd{fP(x)|Ax−b=0} then we additionally get bound O(1/n2) both on the primal gap and on the infeasibility gap. In the most general case, we show a O(1/n) convergence rate of the primal-dual gap again requiring O(nlogn) calls of lmo. To the best of our knowledge, this improves on the known convergence rates for the considered class of saddle-point problems. We show applications to labeling problems frequently appearing in machine learning and computer vision."}],"day":"01","month":"07","type":"conference","oa_version":"Preprint","author":[{"full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov"},{"full_name":"Pock, Thomas","last_name":"Pock","first_name":"Thomas"}],"date_created":"2021-12-16T12:41:20Z","arxiv":1,"title":"One-sided Frank-Wolfe algorithms for saddle problems","year":"2021","department":[{"_id":"VlKo"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","acknowledgement":"Vladimir Kolmogorov was supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160. Thomas Pock acknowledges support by an ERC grant HOMOVIS, no 640156.","article_processing_charge":"No","ec_funded":1,"publication":"38th International Conference on Machine Learning","_id":"10552"},{"_id":"6725","year":"2019","date_created":"2019-07-29T12:23:29Z","file_date_updated":"2020-07-14T12:47:38Z","volume":132,"date_updated":"2021-01-12T08:08:40Z","abstract":[{"text":"A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set Γ of cost functions, called a language. \r\nRecent breakthrough results have established a complete complexity classification of such classes with respect to language Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language Γ is known to be NP-hard. We thus study exponential algorithms for this meta-problem. We show that the tractability condition of a finite-valued language Γ can be tested in O(3‾√3|D|⋅poly(size(Γ))) time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant δ<1 there is no O(3‾√3δ|D|) algorithm, assuming that SETH holds.","lang":"eng"}],"oa_version":"Published Version","month":"07","type":"conference","page":"77:1-77:12","citation":{"apa":"Kolmogorov, V. (2019). Testing the complexity of a valued CSP language. In 46th International Colloquium on Automata, Languages and Programming (Vol. 132, p. 77:1-77:12). Patras, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2019.77","ista":"Kolmogorov V. 2019. Testing the complexity of a valued CSP language. 46th International Colloquium on Automata, Languages and Programming. ICALP 2019: International Colloquim on Automata, Languages and Programming, LIPIcs, vol. 132, 77:1-77:12.","mla":"Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” 46th International Colloquium on Automata, Languages and Programming, vol. 132, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12, doi:10.4230/LIPICS.ICALP.2019.77.","ama":"Kolmogorov V. Testing the complexity of a valued CSP language. In: 46th International Colloquium on Automata, Languages and Programming. Vol 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:77:1-77:12. doi:10.4230/LIPICS.ICALP.2019.77","short":"V. Kolmogorov, in:, 46th International Colloquium on Automata, Languages and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12.","chicago":"Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” In 46th International Colloquium on Automata, Languages and Programming, 132:77:1-77:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.77.","ieee":"V. Kolmogorov, “Testing the complexity of a valued CSP language,” in 46th International Colloquium on Automata, Languages and Programming, Patras, Greece, 2019, vol. 132, p. 77:1-77:12."},"intvolume":" 132","external_id":{"arxiv":["1803.02289"]},"status":"public","alternative_title":["LIPIcs"],"date_published":"2019-07-01T00:00:00Z","ddc":["000"],"has_accepted_license":"1","oa":1,"publication_status":"published","ec_funded":1,"scopus_import":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"publication":"46th International Colloquium on Automata, Languages and Programming","department":[{"_id":"VlKo"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"title":"Testing the complexity of a valued CSP language","day":"01","file":[{"creator":"dernst","file_size":575475,"content_type":"application/pdf","relation":"main_file","file_name":"2019_LIPICS_Kolmogorov.pdf","access_level":"open_access","date_created":"2019-07-31T07:01:45Z","checksum":"f5ebee8eec6ae09e30365578ee63a492","file_id":"6738","date_updated":"2020-07-14T12:47:38Z"}],"author":[{"first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"language":[{"iso":"eng"}],"conference":{"name":"ICALP 2019: International Colloquim on Automata, Languages and Programming","location":"Patras, Greece","start_date":"2019-07-08","end_date":"2019-07-12"},"project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"quality_controlled":"1","doi":"10.4230/LIPICS.ICALP.2019.77","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-109-2"]}},{"arxiv":1,"title":"A local lemma for focused stochastical algorithms","day":"31","author":[{"full_name":"Achlioptas, Dimitris","first_name":"Dimitris","last_name":"Achlioptas"},{"full_name":"Iliopoulos, Fotis","first_name":"Fotis","last_name":"Iliopoulos"},{"last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir"}],"ec_funded":1,"article_processing_charge":"No","scopus_import":"1","article_type":"original","publication":"SIAM Journal on Computing","department":[{"_id":"VlKo"}],"publisher":"SIAM","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","quality_controlled":"1","doi":"10.1137/16m109332x","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"language":[{"iso":"eng"}],"issue":"5","isi":1,"project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160"}],"date_created":"2020-01-30T09:27:32Z","volume":48,"date_updated":"2023-09-06T15:25:29Z","abstract":[{"lang":"eng","text":"We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These algorithms search a state space by repeatedly selecting some constraint that is violated in the current state and moving to a random nearby state that addresses the violation, while (we hope) not introducing many new violations. An important class of focused local search algorithms with provable performance guarantees has recently arisen from algorithmizations of the Lovász local lemma (LLL), a nonconstructive tool for proving the existence of satisfying states by introducing a background measure on the state space. While powerful, the state transitions of algorithms in this class must be, in a precise sense, perfectly compatible with the background measure. In many applications this is a very restrictive requirement, and one needs to step outside the class. Here we introduce the notion of measure distortion and develop a framework for analyzing arbitrary focused stochastic local search algorithms, recovering LLL algorithmizations as the special case of no distortion. Our framework takes as input an arbitrary algorithm of such type and an arbitrary probability measure and shows how to use the measure as a yardstick of algorithmic progress, even for algorithms designed independently of the measure."}],"oa_version":"Preprint","month":"10","type":"journal_article","page":"1583-1602","_id":"7412","year":"2019","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1809.01537"}],"date_published":"2019-10-31T00:00:00Z","oa":1,"publication_status":"published","citation":{"short":"D. Achlioptas, F. Iliopoulos, V. Kolmogorov, SIAM Journal on Computing 48 (2019) 1583–1602.","chicago":"Achlioptas, Dimitris, Fotis Iliopoulos, and Vladimir Kolmogorov. “A Local Lemma for Focused Stochastical Algorithms.” SIAM Journal on Computing. SIAM, 2019. https://doi.org/10.1137/16m109332x.","ieee":"D. Achlioptas, F. Iliopoulos, and V. Kolmogorov, “A local lemma for focused stochastical algorithms,” SIAM Journal on Computing, vol. 48, no. 5. SIAM, pp. 1583–1602, 2019.","apa":"Achlioptas, D., Iliopoulos, F., & Kolmogorov, V. (2019). A local lemma for focused stochastical algorithms. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/16m109332x","mla":"Achlioptas, Dimitris, et al. “A Local Lemma for Focused Stochastical Algorithms.” SIAM Journal on Computing, vol. 48, no. 5, SIAM, 2019, pp. 1583–602, doi:10.1137/16m109332x.","ista":"Achlioptas D, Iliopoulos F, Kolmogorov V. 2019. A local lemma for focused stochastical algorithms. SIAM Journal on Computing. 48(5), 1583–1602.","ama":"Achlioptas D, Iliopoulos F, Kolmogorov V. A local lemma for focused stochastical algorithms. SIAM Journal on Computing. 2019;48(5):1583-1602. doi:10.1137/16m109332x"},"intvolume":" 48","status":"public","external_id":{"arxiv":["1809.01537"],"isi":["000493900200005"]}},{"date_published":"2019-06-01T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1806.05049","open_access":"1"}],"oa":1,"publication_status":"published","citation":{"apa":"Swoboda, P., & Kolmogorov, V. (2019). Map inference via block-coordinate Frank-Wolfe algorithm. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Vol. 2019–June). Long Beach, CA, United States: IEEE. https://doi.org/10.1109/CVPR.2019.01140","mla":"Swoboda, Paul, and Vladimir Kolmogorov. “Map Inference via Block-Coordinate Frank-Wolfe Algorithm.” Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2019–June, 11138–11147, IEEE, 2019, doi:10.1109/CVPR.2019.01140.","ista":"Swoboda P, Kolmogorov V. 2019. Map inference via block-coordinate Frank-Wolfe algorithm. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition vol. 2019–June, 11138–11147.","ama":"Swoboda P, Kolmogorov V. Map inference via block-coordinate Frank-Wolfe algorithm. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Vol 2019-June. IEEE; 2019. doi:10.1109/CVPR.2019.01140","short":"P. Swoboda, V. Kolmogorov, in:, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, IEEE, 2019.","chicago":"Swoboda, Paul, and Vladimir Kolmogorov. “Map Inference via Block-Coordinate Frank-Wolfe Algorithm.” In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol. 2019–June. IEEE, 2019. https://doi.org/10.1109/CVPR.2019.01140.","ieee":"P. Swoboda and V. Kolmogorov, “Map inference via block-coordinate Frank-Wolfe algorithm,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Long Beach, CA, United States, 2019, vol. 2019–June."},"status":"public","external_id":{"arxiv":["1806.05049"],"isi":["000542649304076"]},"volume":"2019-June","date_created":"2020-02-09T23:00:52Z","abstract":[{"lang":"eng","text":"We present a new proximal bundle method for Maximum-A-Posteriori (MAP) inference in structured energy minimization problems. The method optimizes a Lagrangean relaxation of the original energy minimization problem using a multi plane block-coordinate Frank-Wolfe method that takes advantage of the specific structure of the Lagrangean decomposition. We show empirically that our method outperforms state-of-the-art Lagrangean decomposition based algorithms on some challenging Markov Random Field, multi-label discrete tomography and graph matching problems."}],"date_updated":"2023-09-07T14:54:24Z","oa_version":"Preprint","type":"conference","month":"06","_id":"7468","year":"2019","doi":"10.1109/CVPR.2019.01140","quality_controlled":"1","publication_identifier":{"issn":["10636919"],"isbn":["9781728132938"]},"isi":1,"conference":{"end_date":"2019-06-20","start_date":"2019-06-15","name":"CVPR: Conference on Computer Vision and Pattern Recognition","location":"Long Beach, CA, United States"},"language":[{"iso":"eng"}],"project":[{"grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"arxiv":1,"title":"Map inference via block-coordinate Frank-Wolfe algorithm","article_number":"11138-11147","author":[{"last_name":"Swoboda","first_name":"Paul","full_name":"Swoboda, Paul","id":"446560C6-F248-11E8-B48F-1D18A9856A87"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov"}],"day":"01","publication":"Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition","ec_funded":1,"scopus_import":"1","article_processing_charge":"No","publisher":"IEEE","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","department":[{"_id":"VlKo"}]},{"title":"Function norms for neural networks","article_number":"748-752","date_created":"2020-04-05T22:00:50Z","author":[{"first_name":"Amal","last_name":"Rannen-Triki","full_name":"Rannen-Triki, Amal"},{"full_name":"Berman, Maxim","last_name":"Berman","first_name":"Maxim"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov"},{"first_name":"Matthew B.","last_name":"Blaschko","full_name":"Blaschko, Matthew B."}],"abstract":[{"lang":"eng","text":"Deep neural networks (DNNs) have become increasingly important due to their excellent empirical performance on a wide range of problems. However, regularization is generally achieved by indirect means, largely due to the complex set of functions defined by a network and the difficulty in measuring function complexity. There exists no method in the literature for additive regularization based on a norm of the function, as is classically considered in statistical learning theory. In this work, we study the tractability of function norms for deep neural networks with ReLU activations. We provide, to the best of our knowledge, the first proof in the literature of the NP-hardness of computing function norms of DNNs of 3 or more layers. We also highlight a fundamental difference between shallow and deep networks. In the light on these results, we propose a new regularization strategy based on approximate function norms, and show its efficiency on a segmentation task with a DNN."}],"date_updated":"2023-09-08T11:19:12Z","day":"01","type":"conference","oa_version":"None","month":"10","publication":"Proceedings of the 2019 International Conference on Computer Vision Workshop","_id":"7639","article_processing_charge":"No","scopus_import":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"IEEE","department":[{"_id":"VlKo"}],"year":"2019","doi":"10.1109/ICCVW.2019.00097","date_published":"2019-10-01T00:00:00Z","quality_controlled":"1","publication_status":"published","publication_identifier":{"isbn":["9781728150239"]},"isi":1,"conference":{"end_date":"2019-10-28","location":"Seoul, South Korea","name":"ICCVW: International Conference on Computer Vision Workshop","start_date":"2019-10-27"},"citation":{"ama":"Rannen-Triki A, Berman M, Kolmogorov V, Blaschko MB. Function norms for neural networks. In: Proceedings of the 2019 International Conference on Computer Vision Workshop. IEEE; 2019. doi:10.1109/ICCVW.2019.00097","apa":"Rannen-Triki, A., Berman, M., Kolmogorov, V., & Blaschko, M. B. (2019). Function norms for neural networks. In Proceedings of the 2019 International Conference on Computer Vision Workshop. Seoul, South Korea: IEEE. https://doi.org/10.1109/ICCVW.2019.00097","ista":"Rannen-Triki A, Berman M, Kolmogorov V, Blaschko MB. 2019. Function norms for neural networks. Proceedings of the 2019 International Conference on Computer Vision Workshop. ICCVW: International Conference on Computer Vision Workshop, 748–752.","mla":"Rannen-Triki, Amal, et al. “Function Norms for Neural Networks.” Proceedings of the 2019 International Conference on Computer Vision Workshop, 748–752, IEEE, 2019, doi:10.1109/ICCVW.2019.00097.","chicago":"Rannen-Triki, Amal, Maxim Berman, Vladimir Kolmogorov, and Matthew B. Blaschko. “Function Norms for Neural Networks.” In Proceedings of the 2019 International Conference on Computer Vision Workshop. IEEE, 2019. https://doi.org/10.1109/ICCVW.2019.00097.","ieee":"A. Rannen-Triki, M. Berman, V. Kolmogorov, and M. B. Blaschko, “Function norms for neural networks,” in Proceedings of the 2019 International Conference on Computer Vision Workshop, Seoul, South Korea, 2019.","short":"A. Rannen-Triki, M. Berman, V. Kolmogorov, M.B. Blaschko, in:, Proceedings of the 2019 International Conference on Computer Vision Workshop, IEEE, 2019."},"language":[{"iso":"eng"}],"external_id":{"isi":["000554591600090"]},"status":"public"},{"citation":{"chicago":"Mohapatra, Pritish, Michal Rolinek, C V Jawahar, Vladimir Kolmogorov, and M Pawan Kumar. “Efficient Optimization for Rank-Based Loss Functions.” In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, 3693–3701. IEEE, 2018. https://doi.org/10.1109/cvpr.2018.00389.","ieee":"P. Mohapatra, M. Rolinek, C. V. Jawahar, V. Kolmogorov, and M. P. Kumar, “Efficient optimization for rank-based loss functions,” in 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, Salt Lake City, UT, USA, 2018, pp. 3693–3701.","short":"P. Mohapatra, M. Rolinek, C.V. Jawahar, V. Kolmogorov, M.P. Kumar, in:, 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp. 3693–3701.","ama":"Mohapatra P, Rolinek M, Jawahar CV, Kolmogorov V, Kumar MP. Efficient optimization for rank-based loss functions. In: 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. IEEE; 2018:3693-3701. doi:10.1109/cvpr.2018.00389","apa":"Mohapatra, P., Rolinek, M., Jawahar, C. V., Kolmogorov, V., & Kumar, M. P. (2018). Efficient optimization for rank-based loss functions. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 3693–3701). Salt Lake City, UT, USA: IEEE. https://doi.org/10.1109/cvpr.2018.00389","mla":"Mohapatra, Pritish, et al. “Efficient Optimization for Rank-Based Loss Functions.” 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp. 3693–701, doi:10.1109/cvpr.2018.00389.","ista":"Mohapatra P, Rolinek M, Jawahar CV, Kolmogorov V, Kumar MP. 2018. Efficient optimization for rank-based loss functions. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition, 3693–3701."},"status":"public","external_id":{"arxiv":["1604.08269"],"isi":["000457843603087"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.08269"}],"date_published":"2018-06-28T00:00:00Z","publication_status":"published","oa":1,"_id":"273","year":"2018","date_created":"2018-12-11T11:45:33Z","date_updated":"2023-09-11T13:24:43Z","abstract":[{"text":"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.","lang":"eng"}],"month":"06","type":"conference","oa_version":"Preprint","page":"3693-3701","language":[{"iso":"eng"}],"isi":1,"conference":{"location":"Salt Lake City, UT, USA","name":"CVPR: Conference on Computer Vision and Pattern Recognition","start_date":"2018-06-18","end_date":"2018-06-22"},"project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"quality_controlled":"1","doi":"10.1109/cvpr.2018.00389","publication_identifier":{"isbn":["9781538664209"]},"scopus_import":"1","ec_funded":1,"article_processing_charge":"No","publication":"2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition","department":[{"_id":"VlKo"}],"publisher":"IEEE","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","title":"Efficient optimization for rank-based loss functions","arxiv":1,"day":"28","author":[{"full_name":"Mohapatra, Pritish","first_name":"Pritish","last_name":"Mohapatra"},{"full_name":"Rolinek, Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","last_name":"Rolinek","first_name":"Michal"},{"full_name":"Jawahar, C V","last_name":"Jawahar","first_name":"C V"},{"full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov","first_name":"Vladimir"},{"last_name":"Kumar","first_name":"M Pawan","full_name":"Kumar, M Pawan"}]},{"year":"2018","_id":"18","page":"269 - 304","abstract":[{"lang":"eng","text":"An N-superconcentrator is a directed, acyclic graph with N input nodes and N output nodes such that every subset of the inputs and every subset of the outputs of same cardinality can be connected by node-disjoint paths. It is known that linear-size and bounded-degree superconcentrators exist. We prove the existence of such superconcentrators with asymptotic density 25.3 (where the density is the number of edges divided by N). The previously best known densities were 28 [12] and 27.4136 [17]."}],"date_updated":"2023-09-19T14:46:18Z","month":"10","type":"journal_article","oa_version":"Preprint","volume":141,"date_created":"2018-12-11T11:44:11Z","status":"public","external_id":{"arxiv":["1405.7828"],"isi":["000446809500022"]},"intvolume":" 141","citation":{"ama":"Kolmogorov V, Rolinek M. Superconcentrators of density 25.3. Ars Combinatoria. 2018;141(10):269-304.","mla":"Kolmogorov, Vladimir, and Michal Rolinek. “Superconcentrators of Density 25.3.” Ars Combinatoria, vol. 141, no. 10, Charles Babbage Research Centre, 2018, pp. 269–304.","ista":"Kolmogorov V, Rolinek M. 2018. Superconcentrators of density 25.3. Ars Combinatoria. 141(10), 269–304.","apa":"Kolmogorov, V., & Rolinek, M. (2018). Superconcentrators of density 25.3. Ars Combinatoria. Charles Babbage Research Centre.","ieee":"V. Kolmogorov and M. Rolinek, “Superconcentrators of density 25.3,” Ars Combinatoria, vol. 141, no. 10. Charles Babbage Research Centre, pp. 269–304, 2018.","chicago":"Kolmogorov, Vladimir, and Michal Rolinek. “Superconcentrators of Density 25.3.” Ars Combinatoria. Charles Babbage Research Centre, 2018.","short":"V. Kolmogorov, M. Rolinek, Ars Combinatoria 141 (2018) 269–304."},"oa":1,"publication_status":"published","date_published":"2018-10-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1405.7828"}],"publisher":"Charles Babbage Research Centre","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","department":[{"_id":"VlKo"}],"publication":"Ars Combinatoria","article_processing_charge":"No","scopus_import":"1","author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov"},{"first_name":"Michal","last_name":"Rolinek","full_name":"Rolinek, Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87"}],"day":"01","arxiv":1,"title":"Superconcentrators of density 25.3","publist_id":"8037","isi":1,"language":[{"iso":"eng"}],"issue":"10","publication_identifier":{"issn":["0381-7032"]},"quality_controlled":"1"},{"main_file_link":[{"url":"https://arxiv.org/abs/1506.08547","open_access":"1"}],"date_published":"2018-11-08T00:00:00Z","oa":1,"publication_status":"published","citation":{"short":"V. Kolmogorov, SIAM Journal on Computing 47 (2018) 2029–2056.","ieee":"V. Kolmogorov, “Commutativity in the algorithmic Lovász local lemma,” SIAM Journal on Computing, vol. 47, no. 6. Society for Industrial & Applied Mathematics (SIAM), pp. 2029–2056, 2018.","chicago":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovász Local Lemma.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM), 2018. https://doi.org/10.1137/16m1093306.","ista":"Kolmogorov V. 2018. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. 47(6), 2029–2056.","mla":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovász Local Lemma.” SIAM Journal on Computing, vol. 47, no. 6, Society for Industrial & Applied Mathematics (SIAM), 2018, pp. 2029–56, doi:10.1137/16m1093306.","apa":"Kolmogorov, V. (2018). Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/16m1093306","ama":"Kolmogorov V. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. 2018;47(6):2029-2056. doi:10.1137/16m1093306"},"intvolume":" 47","related_material":{"record":[{"relation":"earlier_version","id":"1193","status":"public"}]},"status":"public","external_id":{"arxiv":["1506.08547"],"isi":["000453785100001"]},"date_created":"2019-02-13T12:59:33Z","volume":47,"abstract":[{"text":"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.","lang":"eng"}],"date_updated":"2023-09-19T14:24:58Z","month":"11","oa_version":"Preprint","type":"journal_article","page":"2029-2056","_id":"5975","year":"2018","quality_controlled":"1","doi":"10.1137/16m1093306","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"language":[{"iso":"eng"}],"issue":"6","isi":1,"project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"616160"}],"arxiv":1,"title":"Commutativity in the algorithmic Lovász local lemma","day":"08","author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir"}],"article_processing_charge":"No","scopus_import":"1","ec_funded":1,"publication":"SIAM Journal on Computing","department":[{"_id":"VlKo"}],"publisher":"Society for Industrial & Applied Mathematics (SIAM)","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1"},{"title":"Even delta-matroids and the complexity of planar boolean CSPs","arxiv":1,"article_number":"22","author":[{"id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","full_name":"Kazda, Alexandr","first_name":"Alexandr","last_name":"Kazda"},{"full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov"},{"full_name":"Rolinek, Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","last_name":"Rolinek","first_name":"Michal"}],"day":"01","publication":"ACM Transactions on Algorithms","article_processing_charge":"No","scopus_import":"1","ec_funded":1,"article_type":"original","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"ACM","department":[{"_id":"VlKo"}],"doi":"10.1145/3230649","quality_controlled":"1","isi":1,"language":[{"iso":"eng"}],"issue":"2","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"volume":15,"date_created":"2019-02-17T22:59:25Z","abstract":[{"lang":"eng","text":"The main result of this article 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. Using a reduction to even Δ-matroids, we then extend the tractability result to larger classes of Δ-matroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely, co-independent, compact, local, linear, and binary, with the following caveat:We represent Δ-matroids by lists of tuples, while the last two use a representation by matrices. Since an n ×n matrix can represent exponentially many tuples, our tractability result is not strictly stronger than the known algorithm for linear and binary Δ-matroids."}],"date_updated":"2023-09-20T11:20:26Z","type":"journal_article","month":"12","oa_version":"Preprint","_id":"6032","year":"2018","date_published":"2018-12-01T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1602.03124","open_access":"1"}],"publication_status":"published","oa":1,"related_material":{"record":[{"id":"1192","status":"public","relation":"earlier_version"}]},"intvolume":" 15","citation":{"apa":"Kazda, A., Kolmogorov, V., & Rolinek, M. (2018). Even delta-matroids and the complexity of planar boolean CSPs. ACM Transactions on Algorithms. ACM. https://doi.org/10.1145/3230649","mla":"Kazda, Alexandr, et al. “Even Delta-Matroids and the Complexity of Planar Boolean CSPs.” ACM Transactions on Algorithms, vol. 15, no. 2, 22, ACM, 2018, doi:10.1145/3230649.","ista":"Kazda A, Kolmogorov V, Rolinek M. 2018. Even delta-matroids and the complexity of planar boolean CSPs. ACM Transactions on Algorithms. 15(2), 22.","ama":"Kazda A, Kolmogorov V, Rolinek M. Even delta-matroids and the complexity of planar boolean CSPs. ACM Transactions on Algorithms. 2018;15(2). doi:10.1145/3230649","short":"A. Kazda, V. Kolmogorov, M. Rolinek, ACM Transactions on Algorithms 15 (2018).","chicago":"Kazda, Alexandr, Vladimir Kolmogorov, and Michal Rolinek. “Even Delta-Matroids and the Complexity of Planar Boolean CSPs.” ACM Transactions on Algorithms. ACM, 2018. https://doi.org/10.1145/3230649.","ieee":"A. Kazda, V. Kolmogorov, and M. Rolinek, “Even delta-matroids and the complexity of planar boolean CSPs,” ACM Transactions on Algorithms, vol. 15, no. 2. ACM, 2018."},"status":"public","external_id":{"isi":["000468036500007"],"arxiv":["1602.03124"]}},{"publication_status":"published","oa":1,"has_accepted_license":"1","ddc":["510"],"date_published":"2017-12-27T00:00:00Z","external_id":{"arxiv":["1608.04223"]},"status":"public","intvolume":" 75","citation":{"chicago":"Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition Function.” In Proceedings of the 31st Conference On Learning Theory, 75:228–49. ML Research Press, 2017.","ieee":"V. Kolmogorov, “A faster approximation algorithm for the Gibbs partition function,” in Proceedings of the 31st Conference On Learning Theory, 2017, vol. 75, pp. 228–249.","short":"V. Kolmogorov, in:, Proceedings of the 31st Conference On Learning Theory, ML Research Press, 2017, pp. 228–249.","ama":"Kolmogorov V. A faster approximation algorithm for the Gibbs partition function. In: Proceedings of the 31st Conference On Learning Theory. Vol 75. ML Research Press; 2017:228-249.","apa":"Kolmogorov, V. (2017). A faster approximation algorithm for the Gibbs partition function. In Proceedings of the 31st Conference On Learning Theory (Vol. 75, pp. 228–249). ML Research Press.","ista":"Kolmogorov V. 2017. A faster approximation algorithm for the Gibbs partition function. Proceedings of the 31st Conference On Learning Theory. COLT: Annual Conference on Learning Theory vol. 75, 228–249.","mla":"Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition Function.” Proceedings of the 31st Conference On Learning Theory, vol. 75, ML Research Press, 2017, pp. 228–49."},"page":"228-249","oa_version":"Published Version","month":"12","type":"conference","abstract":[{"text":"We consider the problem of estimating the partition function Z(β)=∑xexp(−β(H(x)) of a Gibbs distribution with a Hamilton H(⋅), or more precisely the logarithm of the ratio q=lnZ(0)/Z(β). It has been recently shown how to approximate q with high probability assuming the existence of an oracle that produces samples from the Gibbs distribution for a given parameter value in [0,β]. The current best known approach due to Huber [9] uses O(qlnn⋅[lnq+lnlnn+ε−2]) oracle calls on average where ε is the desired accuracy of approximation and H(⋅) is assumed to lie in {0}∪[1,n]. We improve the complexity to O(qlnn⋅ε−2) oracle calls. We also show that the same complexity can be achieved if exact oracles are replaced with approximate sampling oracles that are within O(ε2qlnn) variation distance from exact oracles. Finally, we prove a lower bound of Ω(q⋅ε−2) oracle calls under a natural model of computation.","lang":"eng"}],"date_updated":"2023-10-17T12:32:13Z","volume":75,"file_date_updated":"2020-07-14T12:45:45Z","date_created":"2018-12-11T11:45:33Z","year":"2017","_id":"274","quality_controlled":"1","project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"conference":{"end_date":"2018-07-09","name":"COLT: Annual Conference on Learning Theory ","start_date":"2018-07-06"},"language":[{"iso":"eng"}],"author":[{"first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"day":"27","file":[{"creator":"dernst","file_size":408974,"content_type":"application/pdf","relation":"main_file","file_name":"2018_PMLR_Kolmogorov.pdf","access_level":"open_access","date_created":"2020-05-12T09:23:27Z","checksum":"89db06a0e8083524449cb59b56bf4e5b","file_id":"7820","date_updated":"2020-07-14T12:45:45Z"}],"title":"A faster approximation algorithm for the Gibbs partition function","arxiv":1,"publist_id":"7628","publisher":"ML Research Press","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"VlKo"}],"publication":"Proceedings of the 31st Conference On Learning Theory","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ec_funded":1,"article_processing_charge":"No"},{"page":"1087 - 1110","abstract":[{"text":"An instance of the valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. We study, assuming that P 6= NP, how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in f0;1g corresponds to ordinary CSPs, where one deals only with the feasibility issue, and there is no optimization. This case is the subject of the algebraic CSP dichotomy conjecture predicting for which constraint languages CSPs are tractable (i.e., solvable in polynomial time) and for which they are NP-hard. The case when all allowed functions take only finite values corresponds to a finitevalued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Živný. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP (i.e., the problem of deciding whether a given instance has a feasible solution) corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs.","lang":"eng"}],"date_updated":"2023-02-23T10:07:49Z","month":"06","type":"journal_article","oa_version":"Preprint","volume":46,"date_created":"2018-12-11T11:47:40Z","year":"2017","_id":"644","oa":1,"publication_status":"published","date_published":"2017-06-29T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1502.07327","open_access":"1"}],"status":"public","intvolume":" 46","related_material":{"record":[{"id":"1637","status":"public","relation":"other"}]},"citation":{"short":"V. Kolmogorov, A. Krokhin, M. Rolinek, SIAM Journal on Computing 46 (2017) 1087–1110.","chicago":"Kolmogorov, Vladimir, Andrei Krokhin, and Michal Rolinek. “The Complexity of General-Valued CSPs.” SIAM Journal on Computing. SIAM, 2017. https://doi.org/10.1137/16M1091836.","ieee":"V. Kolmogorov, A. Krokhin, and M. Rolinek, “The complexity of general-valued CSPs,” SIAM Journal on Computing, vol. 46, no. 3. SIAM, pp. 1087–1110, 2017.","apa":"Kolmogorov, V., Krokhin, A., & Rolinek, M. (2017). The complexity of general-valued CSPs. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/16M1091836","ista":"Kolmogorov V, Krokhin A, Rolinek M. 2017. The complexity of general-valued CSPs. SIAM Journal on Computing. 46(3), 1087–1110.","mla":"Kolmogorov, Vladimir, et al. “The Complexity of General-Valued CSPs.” SIAM Journal on Computing, vol. 46, no. 3, SIAM, 2017, pp. 1087–110, doi:10.1137/16M1091836.","ama":"Kolmogorov V, Krokhin A, Rolinek M. The complexity of general-valued CSPs. SIAM Journal on Computing. 2017;46(3):1087-1110. doi:10.1137/16M1091836"},"author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov"},{"full_name":"Krokhin, Andrei","first_name":"Andrei","last_name":"Krokhin"},{"last_name":"Rolinek","first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","full_name":"Rolinek, Michal"}],"day":"29","title":"The complexity of general-valued CSPs","publist_id":"7138","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"SIAM","department":[{"_id":"VlKo"}],"publication":"SIAM Journal on Computing","scopus_import":1,"ec_funded":1,"doi":"10.1137/16M1091836","quality_controlled":"1","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"language":[{"iso":"eng"}],"issue":"3"},{"date_updated":"2023-09-20T11:20:26Z","abstract":[{"text":"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.","lang":"eng"}],"month":"01","oa_version":"Submitted Version","type":"conference","page":"307 - 326","date_created":"2018-12-11T11:50:38Z","year":"2017","_id":"1192","publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.03124"}],"date_published":"2017-01-01T00:00:00Z","external_id":{"isi":["000426965800020"]},"status":"public","citation":{"short":"A. Kazda, V. Kolmogorov, M. Rolinek, in:, SIAM, 2017, pp. 307–326.","ieee":"A. Kazda, V. Kolmogorov, and M. Rolinek, “Even delta-matroids and the complexity of planar Boolean CSPs,” presented at the SODA: Symposium on Discrete Algorithms, Barcelona, Spain, 2017, pp. 307–326.","chicago":"Kazda, Alexandr, Vladimir Kolmogorov, and Michal Rolinek. “Even Delta-Matroids and the Complexity of Planar Boolean CSPs,” 307–26. SIAM, 2017. https://doi.org/10.1137/1.9781611974782.20.","ista":"Kazda A, Kolmogorov V, Rolinek M. 2017. Even delta-matroids and the complexity of planar Boolean CSPs. SODA: Symposium on Discrete Algorithms, 307–326.","mla":"Kazda, Alexandr, et al. Even Delta-Matroids and the Complexity of Planar Boolean CSPs. SIAM, 2017, pp. 307–26, doi:10.1137/1.9781611974782.20.","apa":"Kazda, A., Kolmogorov, V., & Rolinek, M. (2017). Even delta-matroids and the complexity of planar Boolean CSPs (pp. 307–326). Presented at the SODA: Symposium on Discrete Algorithms, Barcelona, Spain: SIAM. https://doi.org/10.1137/1.9781611974782.20","ama":"Kazda A, Kolmogorov V, Rolinek M. Even delta-matroids and the complexity of planar Boolean CSPs. In: SIAM; 2017:307-326. doi:10.1137/1.9781611974782.20"},"related_material":{"record":[{"status":"public","id":"6032","relation":"later_version"}]},"day":"01","author":[{"last_name":"Kazda","first_name":"Alexandr","id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","full_name":"Kazda, Alexandr"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir"},{"first_name":"Michal","last_name":"Rolinek","full_name":"Rolinek, Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87"}],"publist_id":"6159","title":"Even delta-matroids and the complexity of planar Boolean CSPs","department":[{"_id":"VlKo"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"SIAM","article_processing_charge":"No","ec_funded":1,"publication_identifier":{"isbn":["978-161197478-2"]},"quality_controlled":"1","doi":"10.1137/1.9781611974782.20","project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160"}],"language":[{"iso":"eng"}],"isi":1,"conference":{"end_date":"2017-01019","name":"SODA: Symposium on Discrete Algorithms","location":"Barcelona, Spain","start_date":"2017-01-16"}},{"issue":"1","language":[{"iso":"eng"}],"project":[{"grant_number":"616160","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"quality_controlled":"1","doi":"10.1007/s00453-015-0017-7","scopus_import":1,"ec_funded":1,"publication":"Algorithmica","department":[{"_id":"VlKo"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Springer","publist_id":"5316","arxiv":1,"title":"Inference algorithms for pattern-based CRFs on sequence data","day":"01","author":[{"first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Takhanov, Rustem","id":"2CCAC26C-F248-11E8-B48F-1D18A9856A87","last_name":"Takhanov","first_name":"Rustem"}],"citation":{"short":"V. Kolmogorov, R. Takhanov, Algorithmica 76 (2016) 17–46.","ieee":"V. Kolmogorov and R. Takhanov, “Inference algorithms for pattern-based CRFs on sequence data,” Algorithmica, vol. 76, no. 1. Springer, pp. 17–46, 2016.","chicago":"Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica. Springer, 2016. https://doi.org/10.1007/s00453-015-0017-7.","ista":"Kolmogorov V, Takhanov R. 2016. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 76(1), 17–46.","mla":"Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica, vol. 76, no. 1, Springer, 2016, pp. 17–46, doi:10.1007/s00453-015-0017-7.","apa":"Kolmogorov, V., & Takhanov, R. (2016). Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. Springer. https://doi.org/10.1007/s00453-015-0017-7","ama":"Kolmogorov V, Takhanov R. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 2016;76(1):17-46. doi:10.1007/s00453-015-0017-7"},"related_material":{"record":[{"id":"2272","status":"public","relation":"earlier_version"}]},"intvolume":" 76","external_id":{"arxiv":["1210.0508"]},"status":"public","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1210.0508"}],"date_published":"2016-09-01T00:00:00Z","publication_status":"published","oa":1,"_id":"1794","year":"2016","acknowledgement":"This work has been partially supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 616160.","date_created":"2018-12-11T11:54:02Z","volume":76,"type":"journal_article","oa_version":"Preprint","month":"09","abstract":[{"lang":"eng","text":"We consider Conditional random fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) (Formula presented.) is the sum of terms over intervals [i, j] where each term is non-zero only if the substring (Formula presented.) equals a prespecified pattern w. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.) where L is the combined length of input patterns, (Formula presented.) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula presented.) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights."}],"date_updated":"2023-10-17T09:51:31Z","page":"17 - 46"},{"date_created":"2018-12-11T11:51:40Z","volume":9,"abstract":[{"lang":"eng","text":"We consider the problem of minimizing the continuous valued total variation subject to different unary terms on trees and propose fast direct algorithms based on dynamic programming to solve these problems. We treat both the convex and the nonconvex case and derive worst-case complexities that are equal to or better than existing methods. We show applications to total variation based two dimensional image processing and computer vision problems based on a Lagrangian decomposition approach. The resulting algorithms are very effcient, offer a high degree of parallelism, and come along with memory requirements which are only in the order of the number of image pixels."}],"date_updated":"2021-01-12T06:50:15Z","month":"05","oa_version":"Preprint","type":"journal_article","page":"605 - 636","_id":"1377","year":"2016","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1502.07770"}],"date_published":"2016-05-03T00:00:00Z","publication_status":"published","oa":1,"citation":{"ieee":"V. Kolmogorov, T. Pock, and M. Rolinek, “Total variation on a tree,” SIAM Journal on Imaging Sciences, vol. 9, no. 2. Society for Industrial and Applied Mathematics , pp. 605–636, 2016.","chicago":"Kolmogorov, Vladimir, Thomas Pock, and Michal Rolinek. “Total Variation on a Tree.” SIAM Journal on Imaging Sciences. Society for Industrial and Applied Mathematics , 2016. https://doi.org/10.1137/15M1010257.","short":"V. Kolmogorov, T. Pock, M. Rolinek, SIAM Journal on Imaging Sciences 9 (2016) 605–636.","ama":"Kolmogorov V, Pock T, Rolinek M. Total variation on a tree. SIAM Journal on Imaging Sciences. 2016;9(2):605-636. doi:10.1137/15M1010257","ista":"Kolmogorov V, Pock T, Rolinek M. 2016. Total variation on a tree. SIAM Journal on Imaging Sciences. 9(2), 605–636.","mla":"Kolmogorov, Vladimir, et al. “Total Variation on a Tree.” SIAM Journal on Imaging Sciences, vol. 9, no. 2, Society for Industrial and Applied Mathematics , 2016, pp. 605–36, doi:10.1137/15M1010257.","apa":"Kolmogorov, V., Pock, T., & Rolinek, M. (2016). Total variation on a tree. SIAM Journal on Imaging Sciences. Society for Industrial and Applied Mathematics . https://doi.org/10.1137/15M1010257"},"intvolume":" 9","status":"public","publist_id":"5834","title":"Total variation on a tree","day":"03","author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov"},{"full_name":"Pock, Thomas","first_name":"Thomas","last_name":"Pock"},{"first_name":"Michal","last_name":"Rolinek","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","full_name":"Rolinek, Michal"}],"ec_funded":1,"scopus_import":1,"publication":"SIAM Journal on Imaging Sciences","department":[{"_id":"VlKo"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publisher":"Society for Industrial and Applied Mathematics ","quality_controlled":"1","doi":"10.1137/15M1010257","language":[{"iso":"eng"}],"issue":"2","project":[{"grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice"}]},{"year":"2016","acknowledgement":"European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160","_id":"1193","oa_version":"Preprint","type":"conference","month":"12","abstract":[{"text":"We consider the recent formulation of the Algorithmic Lovász Local Lemma [1], [2] for finding objects that avoid "bad features", or "flaws". It extends the Moser-Tardos resampling algorithm [3] to more general discrete spaces. At each step the method picks a flaw present in the current state and "resamples" it using a "resampling oracle" provided by the user. However, it is less flexible than the Moser-Tardos method since [1], [2] require a specific flaw selection rule, whereas [3] allows an arbitrary rule (and thus can potentially be implemented more efficiently). We formulate a new "commutativity" condition, and prove that it is sufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additional assumption. We then show that existing resampling oracles for perfect matchings and permutations do satisfy this condition. Finally, we generalize the precondition in [2] (in the case of symmetric potential causality graphs). This unifies special cases that previously were treated separately.","lang":"eng"}],"date_updated":"2023-09-19T14:24:57Z","date_created":"2018-12-11T11:50:38Z","volume":"2016-December","external_id":{"arxiv":["1506.08547"]},"status":"public","citation":{"ieee":"V. Kolmogorov, “Commutativity in the algorithmic Lovasz local lemma,” in Proceedings - Annual IEEE Symposium on Foundations of Computer Science, New Brunswick, NJ, USA , 2016, vol. 2016–December.","chicago":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovasz Local Lemma.” In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, Vol. 2016–December. IEEE, 2016. https://doi.org/10.1109/FOCS.2016.88.","short":"V. Kolmogorov, in:, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2016.","ama":"Kolmogorov V. Commutativity in the algorithmic Lovasz local lemma. In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science. Vol 2016-December. IEEE; 2016. doi:10.1109/FOCS.2016.88","mla":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovasz Local Lemma.” Proceedings - Annual IEEE Symposium on Foundations of Computer Science, vol. 2016–December, 7782993, IEEE, 2016, doi:10.1109/FOCS.2016.88.","ista":"Kolmogorov V. 2016. Commutativity in the algorithmic Lovasz local lemma. Proceedings - Annual IEEE Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science vol. 2016–December, 7782993.","apa":"Kolmogorov, V. (2016). Commutativity in the algorithmic Lovasz local lemma. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science (Vol. 2016–December). New Brunswick, NJ, USA : IEEE. https://doi.org/10.1109/FOCS.2016.88"},"related_material":{"record":[{"relation":"later_version","id":"5975","status":"public"}]},"publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1506.08547v7"}],"date_published":"2016-12-15T00:00:00Z","department":[{"_id":"VlKo"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IEEE","scopus_import":1,"ec_funded":1,"article_processing_charge":"No","publication":"Proceedings - Annual IEEE Symposium on Foundations of Computer Science","day":"15","author":[{"full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov"}],"publist_id":"6158","article_number":"7782993","title":"Commutativity in the algorithmic Lovasz local lemma","arxiv":1,"project":[{"grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"language":[{"iso":"eng"}],"conference":{"start_date":"2016-09-09","location":"New Brunswick, NJ, USA ","name":"FOCS: Foundations of Computer Science","end_date":"2016-09-11"},"quality_controlled":"1","doi":"10.1109/FOCS.2016.88"}]