---
_id: '1859'
abstract:
- lang: eng
  text: "Structural support vector machines (SSVMs) are amongst the best performing
    models for structured computer vision tasks, such as semantic image segmentation
    or human pose estimation. Training SSVMs, however, is computationally costly,
    because it requires repeated calls to a structured prediction subroutine (called
    \\emph{max-oracle}), which has to solve an optimization problem itself, e.g. a
    graph cut.\r\nIn this work, we introduce a new algorithm for SSVM training that
    is more efficient than earlier techniques when the max-oracle is computationally
    expensive, as it is frequently the case in computer vision tasks. The main idea
    is to (i) combine the recent stochastic Block-Coordinate Frank-Wolfe algorithm
    with efficient hyperplane caching, and (ii) use an automatic selection rule for
    deciding whether to call the exact max-oracle or to rely on an approximate one
    based on the cached hyperplanes.\r\nWe show experimentally that this strategy
    leads to faster convergence to the optimum with respect to the number of requires
    oracle calls, and that this translates into faster convergence with respect to
    the total runtime when the max-oracle is slow compared to the other steps of the
    algorithm. "
author:
- first_name: Neel
  full_name: Shah, Neel
  id: 31ABAF80-F248-11E8-B48F-1D18A9856A87
  last_name: Shah
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
- first_name: Christoph
  full_name: Lampert, Christoph
  id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
  last_name: Lampert
  orcid: 0000-0001-8622-7887
citation:
  ama: 'Shah N, Kolmogorov V, Lampert C. A multi-plane block-coordinate Frank-Wolfe
    algorithm for training structural SVMs with a costly max-oracle. In: IEEE; 2015:2737-2745.
    doi:<a href="https://doi.org/10.1109/CVPR.2015.7298890">10.1109/CVPR.2015.7298890</a>'
  apa: 'Shah, N., Kolmogorov, V., &#38; Lampert, C. (2015). A multi-plane block-coordinate
    Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle (pp.
    2737–2745). Presented at the CVPR: Computer Vision and Pattern Recognition, Boston,
    MA, USA: IEEE. <a href="https://doi.org/10.1109/CVPR.2015.7298890">https://doi.org/10.1109/CVPR.2015.7298890</a>'
  chicago: Shah, Neel, Vladimir Kolmogorov, and Christoph Lampert. “A Multi-Plane
    Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly
    Max-Oracle,” 2737–45. IEEE, 2015. <a href="https://doi.org/10.1109/CVPR.2015.7298890">https://doi.org/10.1109/CVPR.2015.7298890</a>.
  ieee: 'N. Shah, V. Kolmogorov, and C. Lampert, “A multi-plane block-coordinate Frank-Wolfe
    algorithm for training structural SVMs with a costly max-oracle,” presented at
    the CVPR: Computer Vision and Pattern Recognition, Boston, MA, USA, 2015, pp.
    2737–2745.'
  ista: 'Shah N, Kolmogorov V, Lampert C. 2015. A multi-plane block-coordinate Frank-Wolfe
    algorithm for training structural SVMs with a costly max-oracle. CVPR: Computer
    Vision and Pattern Recognition, 2737–2745.'
  mla: Shah, Neel, et al. <i>A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm
    for Training Structural SVMs with a Costly Max-Oracle</i>. IEEE, 2015, pp. 2737–45,
    doi:<a href="https://doi.org/10.1109/CVPR.2015.7298890">10.1109/CVPR.2015.7298890</a>.
  short: N. Shah, V. Kolmogorov, C. Lampert, in:, IEEE, 2015, pp. 2737–2745.
conference:
  end_date: 2015-06-12
  location: Boston, MA, USA
  name: 'CVPR: Computer Vision and Pattern Recognition'
  start_date: 2015-06-07
date_created: 2018-12-11T11:54:24Z
date_published: 2015-06-01T00:00:00Z
date_updated: 2021-01-12T06:53:40Z
day: '01'
department:
- _id: VlKo
- _id: ChLa
doi: 10.1109/CVPR.2015.7298890
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1408.6804
month: '06'
oa: 1
oa_version: Preprint
page: 2737 - 2745
project:
- _id: 2532554C-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '308036'
  name: Lifelong Learning of Visual Scene Understanding
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '616160'
  name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_status: published
publisher: IEEE
publist_id: '5240'
quality_controlled: '1'
scopus_import: 1
status: public
title: A multi-plane block-coordinate Frank-Wolfe algorithm for training structural
  SVMs with a costly max-oracle
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...