Distributionally Robust Optimization with Markovian Data

Li, Mengmeng; Sutter, Tobias; Kuhn, Daniel

Distributionally Robust Optimization with Markovian Data

Files

There are no files associated with this item.

Date

2021

Authors

Li, Mengmeng

Sutter, Tobias

Kuhn, Daniel

Link to the license

In Copyright

Collections

Informatik und Informationswissenschaft

Publication type

Contribution to a conference collection

Publication status

Published

Published in

Proceedings of the 38th International Conference on Machine Learning / Meila, Marina; Zhang, Tong (ed.). - (Proceedings of Machine Learning Research ; 139). - pp. 6493-6503. - ISSN 2640-3498

Abstract

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²) 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.

Subject (DDC)

004 Computer Science

Conference

38th International Conference on Machine Learning (Virtual), Jul 18, 2021 - Jul 24, 2021

Cite This

ISO 690

LI, Mengmeng, Tobias SUTTER, Daniel KUHN, 2021. Distributionally Robust Optimization with Markovian Data. 38th International Conference on Machine Learning (Virtual), Jul 18, 2021 - Jul 24, 2021. In: MEILA, Marina, ed., Tong ZHANG, ed.. Proceedings of the 38th International Conference on Machine Learning, pp. 6493-6503. 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>
    <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: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>

URL of original publication

https://proceedings.mlr.press/v139/li21t.html

Test date of URL

2021-12-02

Bibliography of Konstanz

Yes