Publikation:

Distributionally Robust Optimization with Markovian Data

Lade...
Vorschaubild

Dateien

Li_2-tkazjz82mggz2.PDF
Li_2-tkazjz82mggz2.PDFGröße: 553.68 KBDownloads: 27

Datum

2021

Autor:innen

Li, Mengmeng
Kuhn, Daniel

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

DOI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Bookpart
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

MEILA, Marina, ed., Tong ZHANG, ed.. Proceedings of the 38th International Conference on Machine Learning. 2021, pp. 6493-6503. Proceedings of Machine Learning Research. 139. ISSN 2640-3498

Zusammenfassung

We study a stochastic program where the probability distribution of the uncertain problem parameters is unknown and only indirectly observed via finitely many correlated samples generated by an unknown Markov chain with d states. We propose a data-driven distributionally robust optimization model to estimate the problem’s objective function and optimal solution. By leveraging results from large deviations theory, we derive statistical guarantees on the quality of these estimators. The underlying worst-case expectation problem is nonconvex and involves O(d2) decision variables. Thus, it cannot be solved efficiently for large d. By exploiting the structure of this problem, we devise a customized Frank-Wolfe algorithm with convex direction-finding subproblems of size O(d). We prove that this algorithm finds a stationary point efficiently under mild conditions. The efficiency of the method is predicated on a dimensionality reduction enabled by a dual reformulation. Numerical experiments indicate that our approach has better computational and statistical properties than the state-of-the-art methods.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

38th International Conference on Machine Learning (Virtual), 18. Juli 2021 - 24. Juli 2021
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690LI, Mengmeng, Tobias SUTTER, Daniel KUHN, 2021. Distributionally Robust Optimization with Markovian Data. 38th International Conference on Machine Learning (Virtual), 18. Juli 2021 - 24. Juli 2021. In: MEILA, Marina, ed., Tong ZHANG, ed.. Proceedings of the 38th International Conference on Machine Learning. 2021, pp. 6493-6503. Proceedings of Machine Learning Research. 139. ISSN 2640-3498
BibTex
@inproceedings{Li2021Distr-55737,
  year={2021},
  title={Distributionally Robust Optimization with Markovian Data},
  url={https://proceedings.mlr.press/v139/li21t.html},
  number={139},
  issn={2640-3498},
  series={Proceedings of Machine Learning Research},
  booktitle={Proceedings of the 38th International Conference on Machine Learning},
  pages={6493--6503},
  editor={Meila, Marina and Zhang, Tong},
  author={Li, Mengmeng and Sutter, Tobias and Kuhn, Daniel}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/55737">
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/55737"/>
    <dc:creator>Sutter, Tobias</dc:creator>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/55737/1/Li_2-tkazjz82mggz2.PDF"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-12-02T12:37:11Z</dc:date>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Sutter, Tobias</dc:contributor>
    <dcterms:abstract xml:lang="eng">We study a stochastic program where the probability distribution of the uncertain problem parameters is unknown and only indirectly observed via finitely many correlated samples generated by an unknown Markov chain with d states. We propose a data-driven distributionally robust optimization model to estimate the problem’s objective function and optimal solution. By leveraging results from large deviations theory, we derive statistical guarantees on the quality of these estimators. The underlying worst-case expectation problem is nonconvex and involves O(d&lt;sup&gt;2&lt;/sup&gt;) decision variables. Thus, it cannot be solved efficiently for large d. By exploiting the structure of this problem, we devise a customized Frank-Wolfe algorithm with convex direction-finding subproblems of size O(d). We prove that this algorithm finds a stationary point efficiently under mild conditions. The efficiency of the method is predicated on a dimensionality reduction enabled by a dual reformulation. Numerical experiments indicate that our approach has better computational and statistical properties than the state-of-the-art methods.</dcterms:abstract>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:creator>Li, Mengmeng</dc:creator>
    <dcterms:issued>2021</dcterms:issued>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/55737/1/Li_2-tkazjz82mggz2.PDF"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:language>eng</dc:language>
    <dcterms:title>Distributionally Robust Optimization with Markovian Data</dcterms:title>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-12-02T12:37:11Z</dcterms:available>
    <dc:contributor>Kuhn, Daniel</dc:contributor>
    <dc:contributor>Li, Mengmeng</dc:contributor>
    <dc:creator>Kuhn, Daniel</dc:creator>
    <dc:rights>terms-of-use</dc:rights>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt

Prüfdatum der URL

2021-12-02

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen