More Like this

1. Solving Optimization Problems with Blackwell Approachability

   https://doi.org/10.1287/moor.2023.1376  

   Grand-Clément, Julien; Kroer, Christian (January 2023, Mathematics of Operations Research)

   In this paper, we propose a new algorithm for solving convex-concave saddle-point problems using regret minimization in the repeated game framework. To do so, we introduce the Conic Blackwell Algorithm + ([Formula: see text]), a new parameter- and scale-free regret minimizer for general convex compact sets. [Formula: see text] is based on Blackwell approachability and attains [Formula: see text] regret. We show how to efficiently instantiate [Formula: see text] for many decision sets of interest, including the simplex, [Formula: see text] norm balls, and ellipsoidal confidence regions in the simplex. Based on [Formula: see text], we introduce [Formula: see text], a new parameter-free algorithm for solving convex-concave saddle-point problems achieving a [Formula: see text] ergodic convergence rate. In our simulations, we demonstrate the wide applicability of [Formula: see text] on several standard saddle-point problems from the optimization and operations research literature, including matrix games, extensive-form games, distributionally robust logistic regression, and Markov decision processes. In each setting, [Formula: see text] achieves state-of-the-art numerical performance and outperforms classical methods, without the need for any choice of step sizes or other algorithmic parameters. Funding: J. Grand-Clément is supported by the Agence Nationale de la Recherche [Grant 11-LABX-0047] and by Hi! Paris. C. Kroer is supported by the Office of Naval Research [Grant N00014-22-1-2530] and by the National Science Foundation [Grant IIS-2147361]. 

   more » « less
2. Blackwell Online Learning for Markov Decision Processes

   https://doi.org/10.1109/CISS50987.2021.9400319  

   Li, Tao; Peng, Guanze; Zhu, Quanyan (March 2021, 2021 55th Annual Conference on Information Sciences and Systems (CISS))
3. Adaptive Polling in Hierarchical Social Networks Using Blackwell Dominance

   https://doi.org/10.1109/TSIPN.2019.2918442  

   Bhatt, Sujay; Krishnamurthy, Vikram (September 2019, IEEE Transactions on Signal and Information Processing over Networks)
4. From Blackwell Dominance in Large Samples to Rényi Divergences and Back Again

   https://doi.org/10.3982/ECTA17548  

   Mu, Xiaosheng; Pomatto, Luciano; Strack, Philipp; Tamuz, Omer (January 2021, Econometrica)

   null (Ed.)

   We study repeated independent Blackwell experiments; standard examples include drawing multiple samples from a population, or performing a measurement in different locations. In the baseline setting of a binary state of nature, we compare experiments in terms of their informativeness in large samples. Addressing a question due to Blackwell (1951), we show that generically an experiment is more informative than another in large samples if and only if it has higher Rényi divergences. We apply our analysis to the problem of measuring the degree of dissimilarity between distributions by means of divergences. A useful property of Rényi divergences is their additivity with respect to product distributions. Our characterization of Blackwell dominance in large samples implies that every additive divergence that satisfies the data processing inequality is an integral of Rényi divergences. 

   more » « less
5. Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent

   Farina, G.; Kroer, C.; Sandholm, T. (January 2021, AAAI Annual Conference)

   null (Ed.)