---
_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
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'
...