English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  On Fast Approximate Submodular Minimization

Jegelka, S., Lin, H., & Bilmes, J. (2012). On Fast Approximate Submodular Minimization. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, & K. Weinberger (Eds.), Advances in Neural Information Processing Systems 24 (pp. 460-468). Red Hook, NY, USA: Curran.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0013-B880-6 Version Permalink: https://hdl.handle.net/21.11116/0000-0001-1965-2
Genre: Conference Paper

Files

show Files

Locators

show
hide
Locator:
https://papers.nips.cc/paper/4348-on-fast-approximate-submodular-minimization.pdf (Publisher version)
Description:
-
OA-Status:

Creators

show
hide
 Creators:
Jegelka, S1, Author           
Lin, H, Author
Bilmes, J, Author           
Affiliations:
1Dept. Empirical Inference, Max Planck Institute for Intelligent Systems, Max Planck Society, DE, ou_1497647              

Content

show
hide
Free keywords: -
 Abstract: We are motivated by an application to extract a representative subset of machine learning training data and by the poor empirical performance we observe of the popular minimum norm algorithm. In fact, for our application, minimum norm can have a running time of about O(n7) (O(n5) oracle calls). We therefore propose a fast approximate method to minimize arbitrary submodular functions. For a large sub-class of submodular functions, the algorithm is exact. Other submodular functions are iteratively approximated by tight submodular upper bounds, and then repeatedly optimized. We show theoretical properties, and empirical results suggest significant speedups over minimum norm while retaining higher accuracies.

Details

show
hide
Language(s):
 Dates: 2012-01
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: JegelkaLB2011
 Degree: -

Event

show
hide
Title: Twenty-Fifth Annual Conference on Neural Information Processing Systems (NIPS 2011)
Place of Event: Granada, Spain
Start-/End Date: -

Legal Case

show

Project information

show

Source 1

show
hide
Title: Advances in Neural Information Processing Systems 24
Source Genre: Proceedings
 Creator(s):
Shawe-Taylor, J, Editor
Zemel, RS, Editor
Bartlett, P, Editor
Pereira, F, Editor
Weinberger, KQ, Editor
Affiliations:
-
Publ. Info: Red Hook, NY, USA : Curran
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 460 - 468 Identifier: ISBN: 978-1-618-39599-3