---
_id: '14448'
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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
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'
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.'
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.'
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.'
short: V. Kolmogorov, in:, Proceedings of the IEEE Computer Society Conference on
Computer Vision and Pattern Recognition, IEEE, 2023, pp. 11980–11989.
conference:
end_date: 2023-06-24
location: Vancouver, Canada
name: 'CVPR: Conference on Computer Vision and Pattern Recognition'
start_date: 2023-06-17
date_created: 2023-10-22T22:01:16Z
date_published: 2023-08-22T00:00:00Z
date_updated: 2023-10-31T12:01:24Z
day: '22'
department:
- _id: VlKo
doi: 10.1109/CVPR52729.2023.01153
external_id:
arxiv:
- '2010.09567'
intvolume: ' 2023'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2010.09567'
month: '08'
oa: 1
oa_version: Preprint
page: 11980-11989
publication: Proceedings of the IEEE Computer Society Conference on Computer Vision
and Pattern Recognition
publication_identifier:
isbn:
- '9798350301298'
issn:
- 1063-6919
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe
directions'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2023
year: '2023'
...
---
_id: '14084'
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."
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.
alternative_title:
- LIPIcs
article_number: '72'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: David G.
full_name: Harris, David G.
last_name: Harris
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
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'
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'
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.
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.
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.
short: D.G. Harris, V. Kolmogorov, in:, 50th International Colloquium on Automata,
Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2023-07-10
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-08-21T06:49:11Z
day: '01'
ddc:
- '000'
- '510'
department:
- _id: VlKo
doi: 10.4230/LIPIcs.ICALP.2023.72
external_id:
arxiv:
- '2007.10824'
file:
- access_level: open_access
checksum: 6dee0684245bb1c524b9c955db1e933d
content_type: application/pdf
creator: dernst
date_created: 2023-08-21T06:45:16Z
date_updated: 2023-08-21T06:45:16Z
file_id: '14088'
file_name: 2023_LIPIcsICALP_Harris.pdf
file_size: 917791
relation: main_file
success: 1
file_date_updated: 2023-08-21T06:45:16Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '07'
oa: 1
oa_version: Published Version
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959772785'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Parameter estimation for Gibbs distributions
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 261
year: '2023'
...
---
_id: '10737'
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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Rustem
full_name: Takhanov, Rustem
id: 2CCAC26C-F248-11E8-B48F-1D18A9856A87
last_name: Takhanov
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
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
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.
ista: Takhanov R, Kolmogorov V. 2022. Combining pattern-based CRFs and weighted
context-free grammars. Intelligent Data Analysis. 26(1), 257–272.
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.
short: R. Takhanov, V. Kolmogorov, Intelligent Data Analysis 26 (2022) 257–272.
date_created: 2022-02-06T23:01:32Z
date_published: 2022-01-14T00:00:00Z
date_updated: 2023-08-02T14:09:41Z
day: '14'
department:
- _id: VlKo
doi: 10.3233/IDA-205623
external_id:
arxiv:
- '1404.5475'
isi:
- '000749997700015'
intvolume: ' 26'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1404.5475
month: '01'
oa: 1
oa_version: Preprint
page: 257-272
publication: Intelligent Data Analysis
publication_identifier:
eissn:
- 1571-4128
issn:
- 1088-467X
publication_status: published
publisher: IOS Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Combining pattern-based CRFs and weighted context-free grammars
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 26
year: '2022'
...
---
_id: '10045'
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"
article_number: '2109.10203'
article_processing_charge: No
arxiv: 1
author:
- first_name: Martin
full_name: Dvorak, Martin
id: 40ED02A8-C8B4-11E9-A9C0-453BE6697425
last_name: Dvorak
orcid: 0000-0001-5293-214X
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
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
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. .
ista: Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete
convexity. 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.
short: M. Dvorak, V. Kolmogorov, ArXiv (n.d.).
date_created: 2021-09-27T10:48:23Z
date_published: 2021-09-21T00:00:00Z
date_updated: 2023-05-03T10:40:16Z
day: '21'
ddc:
- '004'
department:
- _id: GradSch
- _id: VlKo
doi: 10.48550/arXiv.2109.10203
external_id:
arxiv:
- '2109.10203'
file:
- access_level: open_access
checksum: e7e83065f7bc18b9c188bf93b5ca5db6
content_type: application/pdf
creator: mdvorak
date_created: 2021-09-27T10:54:51Z
date_updated: 2021-09-27T10:54:51Z
file_id: '10046'
file_name: Generalized-0-Ext.pdf
file_size: 603672
relation: main_file
success: 1
file_date_updated: 2021-09-27T10:54:51Z
has_accepted_license: '1'
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
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2109.10203'
month: '09'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: submitted
status: public
title: Generalized minimum 0-extension problem and discrete convexity
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '10072'
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.
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."
alternative_title:
- LIPIcs
article_number: '31'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: David G.
full_name: Harris, David G.
last_name: Harris
- first_name: Fotis
full_name: Iliopoulos, Fotis
last_name: Iliopoulos
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
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'
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'
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.
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.
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.'
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.
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.
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
date_created: 2021-10-03T22:01:22Z
date_published: 2021-09-15T00:00:00Z
date_updated: 2022-03-18T10:08:25Z
day: '15'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.4230/LIPIcs.APPROX/RANDOM.2021.31
ec_funded: 1
external_id:
arxiv:
- '2008.05569'
file:
- access_level: open_access
checksum: 9d2544d53aa5b01565c6891d97a4d765
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-06T13:51:54Z
date_updated: 2021-10-06T13:51:54Z
file_id: '10098'
file_name: 2021_LIPIcs_Harris.pdf
file_size: 804472
relation: main_file
success: 1
file_date_updated: 2021-10-06T13:51:54Z
has_accepted_license: '1'
intvolume: ' 207'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques
publication_identifier:
isbn:
- 978-3-9597-7207-5
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: A new notion of commutativity for the algorithmic Lovász Local Lemma
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 207
year: '2021'
...
---
_id: '10552'
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.
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
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Thomas
full_name: Pock, Thomas
last_name: Pock
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.
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.
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.'
mla: Kolmogorov, Vladimir, and Thomas Pock. “One-Sided Frank-Wolfe Algorithms for
Saddle Problems.” 38th International Conference on Machine Learning, 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_created: 2021-12-16T12:41:20Z
date_published: 2021-07-01T00:00:00Z
date_updated: 2021-12-17T09:06:46Z
day: '01'
department:
- _id: VlKo
ec_funded: 1
external_id:
arxiv:
- '2101.12617'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2101.12617
month: '07'
oa: 1
oa_version: Preprint
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: 38th International Conference on Machine Learning
publication_status: published
quality_controlled: '1'
status: public
title: One-sided Frank-Wolfe algorithms for saddle problems
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
_id: '6725'
abstract:
- lang: eng
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."
alternative_title:
- LIPIcs
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
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'
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'
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.
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.
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.
conference:
end_date: 2019-07-12
location: Patras, Greece
name: 'ICALP 2019: International Colloquim on Automata, Languages and Programming'
start_date: 2019-07-08
date_created: 2019-07-29T12:23:29Z
date_published: 2019-07-01T00:00:00Z
date_updated: 2021-01-12T08:08:40Z
day: '01'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.4230/LIPICS.ICALP.2019.77
ec_funded: 1
external_id:
arxiv:
- '1803.02289'
file:
- access_level: open_access
checksum: f5ebee8eec6ae09e30365578ee63a492
content_type: application/pdf
creator: dernst
date_created: 2019-07-31T07:01:45Z
date_updated: 2020-07-14T12:47:38Z
file_id: '6738'
file_name: 2019_LIPICS_Kolmogorov.pdf
file_size: 575475
relation: main_file
file_date_updated: 2020-07-14T12:47:38Z
has_accepted_license: '1'
intvolume: ' 132'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 77:1-77:12
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: 46th International Colloquium on Automata, Languages and Programming
publication_identifier:
isbn:
- 978-3-95977-109-2
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Testing the complexity of a valued CSP language
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 132
year: '2019'
...
---
_id: '7412'
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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Dimitris
full_name: Achlioptas, Dimitris
last_name: Achlioptas
- first_name: Fotis
full_name: Iliopoulos, Fotis
last_name: Iliopoulos
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
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
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
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.
ista: Achlioptas D, Iliopoulos F, Kolmogorov V. 2019. A local lemma for focused
stochastical algorithms. SIAM Journal on Computing. 48(5), 1583–1602.
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.
short: D. Achlioptas, F. Iliopoulos, V. Kolmogorov, SIAM Journal on Computing 48
(2019) 1583–1602.
date_created: 2020-01-30T09:27:32Z
date_published: 2019-10-31T00:00:00Z
date_updated: 2023-09-06T15:25:29Z
day: '31'
department:
- _id: VlKo
doi: 10.1137/16m109332x
ec_funded: 1
external_id:
arxiv:
- '1809.01537'
isi:
- '000493900200005'
intvolume: ' 48'
isi: 1
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1809.01537
month: '10'
oa: 1
oa_version: Preprint
page: 1583-1602
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: SIAM
quality_controlled: '1'
scopus_import: '1'
status: public
title: A local lemma for focused stochastical algorithms
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 48
year: '2019'
...
---
_id: '7468'
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.
article_number: 11138-11147
article_processing_charge: No
arxiv: 1
author:
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
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'
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'
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.
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.'
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.
short: P. Swoboda, V. Kolmogorov, in:, Proceedings of the IEEE Computer Society
Conference on Computer Vision and Pattern Recognition, IEEE, 2019.
conference:
end_date: 2019-06-20
location: Long Beach, CA, United States
name: 'CVPR: Conference on Computer Vision and Pattern Recognition'
start_date: 2019-06-15
date_created: 2020-02-09T23:00:52Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-07T14:54:24Z
day: '01'
department:
- _id: VlKo
doi: 10.1109/CVPR.2019.01140
ec_funded: 1
external_id:
arxiv:
- '1806.05049'
isi:
- '000542649304076'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1806.05049
month: '06'
oa: 1
oa_version: Preprint
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: Proceedings of the IEEE Computer Society Conference on Computer Vision
and Pattern Recognition
publication_identifier:
isbn:
- '9781728132938'
issn:
- '10636919'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Map inference via block-coordinate Frank-Wolfe algorithm
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2019-June
year: '2019'
...
---
_id: '7639'
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.
article_number: 748-752
article_processing_charge: No
author:
- first_name: Amal
full_name: Rannen-Triki, Amal
last_name: Rannen-Triki
- first_name: Maxim
full_name: Berman, Maxim
last_name: Berman
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Matthew B.
full_name: Blaschko, Matthew B.
last_name: Blaschko
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'
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.
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.
short: A. Rannen-Triki, M. Berman, V. Kolmogorov, M.B. Blaschko, in:, Proceedings
of the 2019 International Conference on Computer Vision Workshop, IEEE, 2019.
conference:
end_date: 2019-10-28
location: Seoul, South Korea
name: 'ICCVW: International Conference on Computer Vision Workshop'
start_date: 2019-10-27
date_created: 2020-04-05T22:00:50Z
date_published: 2019-10-01T00:00:00Z
date_updated: 2023-09-08T11:19:12Z
day: '01'
department:
- _id: VlKo
doi: 10.1109/ICCVW.2019.00097
external_id:
isi:
- '000554591600090'
isi: 1
language:
- iso: eng
month: '10'
oa_version: None
publication: Proceedings of the 2019 International Conference on Computer Vision Workshop
publication_identifier:
isbn:
- '9781728150239'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Function norms for neural networks
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2019'
...
---
_id: '273'
abstract:
- lang: eng
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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Pritish
full_name: Mohapatra, Pritish
last_name: Mohapatra
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
- first_name: C V
full_name: Jawahar, C V
last_name: Jawahar
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: M Pawan
full_name: Kumar, M Pawan
last_name: Kumar
citation:
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'
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.
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.'
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.
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.
conference:
end_date: 2018-06-22
location: Salt Lake City, UT, USA
name: 'CVPR: Conference on Computer Vision and Pattern Recognition'
start_date: 2018-06-18
date_created: 2018-12-11T11:45:33Z
date_published: 2018-06-28T00:00:00Z
date_updated: 2023-09-11T13:24:43Z
day: '28'
department:
- _id: VlKo
doi: 10.1109/cvpr.2018.00389
ec_funded: 1
external_id:
arxiv:
- '1604.08269'
isi:
- '000457843603087'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1604.08269
month: '06'
oa: 1
oa_version: Preprint
page: 3693-3701
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition
publication_identifier:
isbn:
- '9781538664209'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Efficient optimization for rank-based loss functions
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...
---
_id: '18'
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].
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
ama: Kolmogorov V, Rolinek M. Superconcentrators of density 25.3. Ars Combinatoria.
2018;141(10):269-304.
apa: Kolmogorov, V., & Rolinek, M. (2018). Superconcentrators of density 25.3.
Ars Combinatoria. Charles Babbage Research Centre.
chicago: Kolmogorov, Vladimir, and Michal Rolinek. “Superconcentrators of Density
25.3.” Ars Combinatoria. Charles Babbage Research Centre, 2018.
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.
ista: Kolmogorov V, Rolinek M. 2018. Superconcentrators of density 25.3. Ars Combinatoria.
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.
short: V. Kolmogorov, M. Rolinek, Ars Combinatoria 141 (2018) 269–304.
date_created: 2018-12-11T11:44:11Z
date_published: 2018-10-01T00:00:00Z
date_updated: 2023-09-19T14:46:18Z
day: '01'
department:
- _id: VlKo
external_id:
arxiv:
- '1405.7828'
isi:
- '000446809500022'
intvolume: ' 141'
isi: 1
issue: '10'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1405.7828
month: '10'
oa: 1
oa_version: Preprint
page: 269 - 304
publication: Ars Combinatoria
publication_identifier:
issn:
- 0381-7032
publication_status: published
publisher: Charles Babbage Research Centre
publist_id: '8037'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Superconcentrators of density 25.3
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 141
year: '2018'
...
---
_id: '5975'
abstract:
- lang: eng
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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Kolmogorov V. Commutativity in the algorithmic Lovász local lemma. SIAM
Journal on Computing. 2018;47(6):2029-2056. 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
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.
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.
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.
short: V. Kolmogorov, SIAM Journal on Computing 47 (2018) 2029–2056.
date_created: 2019-02-13T12:59:33Z
date_published: 2018-11-08T00:00:00Z
date_updated: 2023-09-19T14:24:58Z
day: '08'
department:
- _id: VlKo
doi: 10.1137/16m1093306
ec_funded: 1
external_id:
arxiv:
- '1506.08547'
isi:
- '000453785100001'
intvolume: ' 47'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1506.08547
month: '11'
oa: 1
oa_version: Preprint
page: 2029-2056
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: Society for Industrial & Applied Mathematics (SIAM)
quality_controlled: '1'
related_material:
record:
- id: '1193'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Commutativity in the algorithmic Lovász local lemma
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 47
year: '2018'
...
---
_id: '6032'
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.
article_number: '22'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Alexandr
full_name: Kazda, Alexandr
id: 3B32BAA8-F248-11E8-B48F-1D18A9856A87
last_name: Kazda
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
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
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
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.
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.
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.
short: A. Kazda, V. Kolmogorov, M. Rolinek, ACM Transactions on Algorithms 15 (2018).
date_created: 2019-02-17T22:59:25Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2023-09-20T11:20:26Z
day: '01'
department:
- _id: VlKo
doi: 10.1145/3230649
ec_funded: 1
external_id:
arxiv:
- '1602.03124'
isi:
- '000468036500007'
intvolume: ' 15'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1602.03124
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: ACM Transactions on Algorithms
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
record:
- id: '1192'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Even delta-matroids and the complexity of planar boolean CSPs
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 15
year: '2018'
...
---
_id: '274'
abstract:
- lang: eng
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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
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.
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.
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.
short: V. Kolmogorov, in:, Proceedings of the 31st Conference On Learning Theory,
ML Research Press, 2017, pp. 228–249.
conference:
end_date: 2018-07-09
name: 'COLT: Annual Conference on Learning Theory '
start_date: 2018-07-06
date_created: 2018-12-11T11:45:33Z
date_published: 2017-12-27T00:00:00Z
date_updated: 2023-10-17T12:32:13Z
day: '27'
ddc:
- '510'
department:
- _id: VlKo
ec_funded: 1
external_id:
arxiv:
- '1608.04223'
file:
- access_level: open_access
checksum: 89db06a0e8083524449cb59b56bf4e5b
content_type: application/pdf
creator: dernst
date_created: 2020-05-12T09:23:27Z
date_updated: 2020-07-14T12:45:45Z
file_id: '7820'
file_name: 2018_PMLR_Kolmogorov.pdf
file_size: 408974
relation: main_file
file_date_updated: 2020-07-14T12:45:45Z
has_accepted_license: '1'
intvolume: ' 75'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 228-249
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: Proceedings of the 31st Conference On Learning Theory
publication_status: published
publisher: ML Research Press
publist_id: '7628'
quality_controlled: '1'
status: public
title: A faster approximation algorithm for the Gibbs partition function
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 75
year: '2017'
...
---
_id: '644'
abstract:
- lang: eng
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.
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Andrei
full_name: Krokhin, Andrei
last_name: Krokhin
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
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
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
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.
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.
short: V. Kolmogorov, A. Krokhin, M. Rolinek, SIAM Journal on Computing 46 (2017)
1087–1110.
date_created: 2018-12-11T11:47:40Z
date_published: 2017-06-29T00:00:00Z
date_updated: 2023-02-23T10:07:49Z
day: '29'
department:
- _id: VlKo
doi: 10.1137/16M1091836
ec_funded: 1
intvolume: ' 46'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1502.07327
month: '06'
oa: 1
oa_version: Preprint
page: 1087 - 1110
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: SIAM Journal on Computing
publication_status: published
publisher: SIAM
publist_id: '7138'
quality_controlled: '1'
related_material:
record:
- id: '1637'
relation: other
status: public
scopus_import: 1
status: public
title: The complexity of general-valued CSPs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 46
year: '2017'
...
---
_id: '1192'
abstract:
- lang: eng
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.
article_processing_charge: No
author:
- first_name: Alexandr
full_name: Kazda, Alexandr
id: 3B32BAA8-F248-11E8-B48F-1D18A9856A87
last_name: Kazda
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
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'
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'
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.
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.'
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.
short: A. Kazda, V. Kolmogorov, M. Rolinek, in:, SIAM, 2017, pp. 307–326.
conference:
end_date: 2017-01019
location: Barcelona, Spain
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2017-01-16
date_created: 2018-12-11T11:50:38Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-09-20T11:20:26Z
day: '01'
department:
- _id: VlKo
doi: 10.1137/1.9781611974782.20
ec_funded: 1
external_id:
isi:
- '000426965800020'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1602.03124
month: '01'
oa: 1
oa_version: Submitted Version
page: 307 - 326
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
isbn:
- 978-161197478-2
publication_status: published
publisher: SIAM
publist_id: '6159'
quality_controlled: '1'
related_material:
record:
- id: '6032'
relation: later_version
status: public
status: public
title: Even delta-matroids and the complexity of planar Boolean CSPs
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '1794'
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.
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.
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Rustem
full_name: Takhanov, Rustem
id: 2CCAC26C-F248-11E8-B48F-1D18A9856A87
last_name: Takhanov
citation:
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
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
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.
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.
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.
short: V. Kolmogorov, R. Takhanov, Algorithmica 76 (2016) 17–46.
date_created: 2018-12-11T11:54:02Z
date_published: 2016-09-01T00:00:00Z
date_updated: 2023-10-17T09:51:31Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/s00453-015-0017-7
ec_funded: 1
external_id:
arxiv:
- '1210.0508'
intvolume: ' 76'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1210.0508
month: '09'
oa: 1
oa_version: Preprint
page: 17 - 46
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: Algorithmica
publication_status: published
publisher: Springer
publist_id: '5316'
quality_controlled: '1'
related_material:
record:
- id: '2272'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Inference algorithms for pattern-based CRFs on sequence data
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 76
year: '2016'
...
---
_id: '1377'
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.
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Thomas
full_name: Pock, Thomas
last_name: Pock
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
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
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
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.
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.
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.
short: V. Kolmogorov, T. Pock, M. Rolinek, SIAM Journal on Imaging Sciences 9 (2016)
605–636.
date_created: 2018-12-11T11:51:40Z
date_published: 2016-05-03T00:00:00Z
date_updated: 2021-01-12T06:50:15Z
day: '03'
department:
- _id: VlKo
doi: 10.1137/15M1010257
ec_funded: 1
intvolume: ' 9'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1502.07770
month: '05'
oa: 1
oa_version: Preprint
page: 605 - 636
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: SIAM Journal on Imaging Sciences
publication_status: published
publisher: 'Society for Industrial and Applied Mathematics '
publist_id: '5834'
quality_controlled: '1'
scopus_import: 1
status: public
title: Total variation on a tree
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9
year: '2016'
...
---
_id: '1193'
abstract:
- lang: eng
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.
acknowledgement: European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant
agreement no 616160
article_number: '7782993'
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
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'
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'
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.
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.
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.'
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.
short: V. Kolmogorov, in:, Proceedings - Annual IEEE Symposium on Foundations of
Computer Science, IEEE, 2016.
conference:
end_date: 2016-09-11
location: 'New Brunswick, NJ, USA '
name: 'FOCS: Foundations of Computer Science'
start_date: 2016-09-09
date_created: 2018-12-11T11:50:38Z
date_published: 2016-12-15T00:00:00Z
date_updated: 2023-09-19T14:24:57Z
day: '15'
department:
- _id: VlKo
doi: 10.1109/FOCS.2016.88
ec_funded: 1
external_id:
arxiv:
- '1506.08547'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1506.08547v7
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: Proceedings - Annual IEEE Symposium on Foundations of Computer Science
publication_status: published
publisher: IEEE
publist_id: '6158'
quality_controlled: '1'
related_material:
record:
- id: '5975'
relation: later_version
status: public
scopus_import: 1
status: public
title: Commutativity in the algorithmic Lovasz local lemma
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2016-December
year: '2016'
...