English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Statistical estimation for optimization problems on graphs

Langovoy, M., & Sra, S. (2011). Statistical estimation for optimization problems on graphs. In NIPS Workshop on Discrete Optimization in Machine Learning (DISCML) 2011: Uncertainty, Generalization and Feedback (pp. 1-6).

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0013-B8DC-B Version Permalink: http://hdl.handle.net/21.11116/0000-0001-F253-0
Genre: Conference Paper

Files

show Files

Locators

show
hide
Locator:
https://arxiv.org/pdf/1311.7656.pdf (Any fulltext)
Description:
-

Creators

show
hide
 Creators:
Langovoy, M1, Author              
Sra, S1, Author              
Affiliations:
1Max Planck Institute for Intelligent Systems, Max Planck Society, Heisenbergstr. 3 70569 Stuttgart , DE, ou_1497638              

Content

show
hide
Free keywords: -
 Abstract: Large graphs abound in machine learning, data mining, and several related areas. A useful step towards analyzing such graphs is that of obtaining certain summary statistics — e.g., or the expected length of a shortest path between two nodes, or the expected weight of a minimum spanning tree of the graph, etc. These statistics provide insight into the structure of a graph, and they can help predict global properties of a graph. Motivated thus, we propose to study statistical properties of structured subgraphs (of a given graph), in particular, to estimate the expected objective function value of a combinatorial optimization problem over these subgraphs. The general task is very difficult, if not unsolvable; so for concreteness we describe a more specific statistical estimation problem based on spanning trees. We hope that our position paper encourages others to also study other types of graphical structures for which one can prove nontrivial statistical estimates.

Details

show
hide
Language(s):
 Dates: 2011-12
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: LangovoyS2011
 Degree: -

Event

show
hide
Title: NIPS Workshop on Discrete Optimization in Machine Learning (DISCML) 2011: Uncertainty, Generalization and Feedback
Place of Event: -
Start-/End Date: -

Legal Case

show

Project information

show

Source 1

show
hide
Title: NIPS Workshop on Discrete Optimization in Machine Learning (DISCML) 2011: Uncertainty, Generalization and Feedback
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 1 - 6 Identifier: -