Playlist: 27 videos
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
0:37:36
Julian Zimmert (Google Research)
https://simons.berkeley.edu/talks/tbd-473
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
Most of machine learning theory assumes i.i.d. (independent identically distributed) data. However, the i.i.d. assumption is rarely satisfied in practice. Online learning departs from this assumption by changing the evaluation measure from expected error on future samples to regret with respect to the best prediction strategy in hindsight, out of a limited set of strategies. The revised evaluation measure allows to go as far as to consider adversarial environments, for example spam filtering or learning in two-player games. The ability to learn in adversarial environments comes at a price though. The convergence rate of algorithms for adversarial environments are typically much slower than the convergence rate of algorithms for i.i.d. environments. A practitioner thus has to make a choice between safe algorithms for adversarial environments with slow convergence rate and fast algorithms for i.i.d environments, with the implied risk of complete failure if the model assumptions are violated. But does the practitioner have to take the risk? Can we design algorithms that adapt to the nature of the environment?
Visit talk page
https://simons.berkeley.edu/talks/tbd-473
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
Most of machine learning theory assumes i.i.d. (independent identically distributed) data. However, the i.i.d. assumption is rarely satisfied in practice. Online learning departs from this assumption by changing the evaluation measure from expected error on future samples to regret with respect to the best prediction strategy in hindsight, out of a limited set of strategies. The revised evaluation measure allows to go as far as to consider adversarial environments, for example spam filtering or learning in two-player games. The ability to learn in adversarial environments comes at a price though. The convergence rate of algorithms for adversarial environments are typically much slower than the convergence rate of algorithms for i.i.d. environments. A practitioner thus has to make a choice between safe algorithms for adversarial environments with slow convergence rate and fast algorithms for i.i.d environments, with the implied risk of complete failure if the model assumptions are violated. But does the practitioner have to take the risk? Can we design algorithms that adapt to the nature of the environment?
0:45:0
Victor Gabillon (Queensland University of Technology)
https://simons.berkeley.edu/talks/best-both-worlds-stochastic-adversarial-best-arm-identification
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
We study bandit best-arm identification with arbitrary and potentially adversarial rewards. A simple random uniform learner obtains the optimal rate of error in the adversarial scenario. However, this type of strategy is suboptimal when the rewards are sampled stochastically. Therefore, we ask: Can we design a learner that performs optimally in both the stochastic and adversarial problems while not being aware of the nature of the rewards? First, we show that designing such a learner is impossible in general. In particular, to be robust to adversarial rewards, we can only guarantee optimal rates of error on a subset of the stochastic problems. We give a lower bound that characterizes the optimal rate in stochastic problems if the strategy is constrained to be robust to adversarial rewards. Finally, we design a simple parameter-free algorithm and show that its probability of error matches (up to log factors) the lower bound in stochastic problems, and it is also robust to adversarial ones.
Visit talk page
https://simons.berkeley.edu/talks/best-both-worlds-stochastic-adversarial-best-arm-identification
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
We study bandit best-arm identification with arbitrary and potentially adversarial rewards. A simple random uniform learner obtains the optimal rate of error in the adversarial scenario. However, this type of strategy is suboptimal when the rewards are sampled stochastically. Therefore, we ask: Can we design a learner that performs optimally in both the stochastic and adversarial problems while not being aware of the nature of the rewards? First, we show that designing such a learner is impossible in general. In particular, to be robust to adversarial rewards, we can only guarantee optimal rates of error on a subset of the stochastic problems. We give a lower bound that characterizes the optimal rate in stochastic problems if the strategy is constrained to be robust to adversarial rewards. Finally, we design a simple parameter-free algorithm and show that its probability of error matches (up to log factors) the lower bound in stochastic problems, and it is also robust to adversarial ones.
0:52:11
Yossi Azar (Tel-Aviv University)
https://simons.berkeley.edu/talks/flow-time-scheduling-uncertain-processing-time
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
We consider the problem of online scheduling on a single machine to minimize unweighted and weighted flow time. The existing algorithms for these problems require exact knowledge of the processing time of each job. This assumption is crucial, as even a slight perturbation of the processing time would lead to polynomial competitive ratio. However, this assumption very rarely holds in real-life scenarios. We present a competitive algorithm (the competitive ratio is a function of the distortion) for unweighted flow time that do not require knowledge of the distortion in advance. For the weighted flow time we present competitive algorithms but, in this case, we need to know (an upper bound on) the distortion in advance. This is joint work with Stefano Leonardi and Noam Touitou based on papers appear in STOC 21 and SODA 2022.
Visit talk page
https://simons.berkeley.edu/talks/flow-time-scheduling-uncertain-processing-time
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
We consider the problem of online scheduling on a single machine to minimize unweighted and weighted flow time. The existing algorithms for these problems require exact knowledge of the processing time of each job. This assumption is crucial, as even a slight perturbation of the processing time would lead to polynomial competitive ratio. However, this assumption very rarely holds in real-life scenarios. We present a competitive algorithm (the competitive ratio is a function of the distortion) for unweighted flow time that do not require knowledge of the distortion in advance. For the weighted flow time we present competitive algorithms but, in this case, we need to know (an upper bound on) the distortion in advance. This is joint work with Stefano Leonardi and Noam Touitou based on papers appear in STOC 21 and SODA 2022.
0:44:16
Ben Moseley (Carnegie Mellon University)
https://simons.berkeley.edu/talks/tbd-475
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
This talk will discuss a model for augmenting algorithms with useful predictions to improve algorithm performance for running time. The model ensures predictions are formally learnable and robust. Learnability guarantees that predictions can be efficiently constructed from past data. Robustness formally ensures a prediction is robust to modest changes in the problem input. This talk will discuss predictions that satisfy these properties and result in improved run times for matching algorithms.
Visit talk page
https://simons.berkeley.edu/talks/tbd-475
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
This talk will discuss a model for augmenting algorithms with useful predictions to improve algorithm performance for running time. The model ensures predictions are formally learnable and robust. Learnability guarantees that predictions can be efficiently constructed from past data. Robustness formally ensures a prediction is robust to modest changes in the problem input. This talk will discuss predictions that satisfy these properties and result in improved run times for matching algorithms.
0:44:10
Ravi Kumar (Google)
https://simons.berkeley.edu/talks/tbd-474
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
In this talk we will consider the number of predictions used by a learning-augmented algorithm as a resource measure. Focusing on two problems---online learning in the regret setting and online caching in the competitive-ratio setting---we show that a sublinear number of predictions suffices to achieve non-trivial performance gains.
Visit talk page
https://simons.berkeley.edu/talks/tbd-474
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
In this talk we will consider the number of predictions used by a learning-augmented algorithm as a resource measure. Focusing on two problems---online learning in the regret setting and online caching in the competitive-ratio setting---we show that a sublinear number of predictions suffices to achieve non-trivial performance gains.
0:46:0
Haifeng Xu (University of Chicago)
https://simons.berkeley.edu/talks/tbd-476
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
Standard Markov decision process (MDP) features a single planner who observes the underlying state of a world and then acts. This talk will study a natural variant of this fundamental model, in which one agent observes the state whereas another agent acts. Such sequential interactions among different agents arise in various recommender systems such as ride-sharing platforms or content recommendations. When agents have different incentives, the state-informed agent can partially reveal information about the realized state to influence the actor at each round in order to steer their collective actions towards a desirable outcome, a problem which we coin Markov Persuasion Process (MPP) inspired by the celebrated recent literature of Bayesian persuasion. We will talk about both computational and reinforcement learning questions in MPP.
Visit talk page
https://simons.berkeley.edu/talks/tbd-476
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
Standard Markov decision process (MDP) features a single planner who observes the underlying state of a world and then acts. This talk will study a natural variant of this fundamental model, in which one agent observes the state whereas another agent acts. Such sequential interactions among different agents arise in various recommender systems such as ride-sharing platforms or content recommendations. When agents have different incentives, the state-informed agent can partially reveal information about the realized state to influence the actor at each round in order to steer their collective actions towards a desirable outcome, a problem which we coin Markov Persuasion Process (MPP) inspired by the celebrated recent literature of Bayesian persuasion. We will talk about both computational and reinforcement learning questions in MPP.
0:50:20
Arjada Bardhi (Duke University)
https://simons.berkeley.edu/talks/tbd-477
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
Two players who disagree on the relevance of the attributes of a complex project eval- uate it based on a select few. The optimal attribute sample is characterized in a general framework in which the correlation across attributes is modeled through a Gaussian process. Two sufficient statistics inform optimal sampling: (i) the resulting alignment between the players’ estimates, and (ii) the variability of the decision. We identify an intuitive property of the correlation structure—the nearest-attribute property—that is critical for the pattern of optimal sampling. Under such a property, all optimal attributes are relevant for some player: at most two are idiosyncratic and the rest are common. The fewer and more peripheral the common attributes and the stronger the attribute correlation, the more skewed and redundant the sample. We draw testable implications for attribute-based product evaluation and strategic selection of pilot sites.
Visit talk page
https://simons.berkeley.edu/talks/tbd-477
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
Two players who disagree on the relevance of the attributes of a complex project eval- uate it based on a select few. The optimal attribute sample is characterized in a general framework in which the correlation across attributes is modeled through a Gaussian process. Two sufficient statistics inform optimal sampling: (i) the resulting alignment between the players’ estimates, and (ii) the variability of the decision. We identify an intuitive property of the correlation structure—the nearest-attribute property—that is critical for the pattern of optimal sampling. Under such a property, all optimal attributes are relevant for some player: at most two are idiosyncratic and the rest are common. The fewer and more peripheral the common attributes and the stronger the attribute correlation, the more skewed and redundant the sample. We draw testable implications for attribute-based product evaluation and strategic selection of pilot sites.
0:48:36
Alex Slivkins (Microsoft Research)
https://simons.berkeley.edu/talks/incentivized-exploration
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
In a wide range of scenarios, individual decision-makers consume information revealed by the previous decisions, and produce information that may help in the future decisions. Each decision-maker would individually prefer to "exploit" (optimize the current reward), but would like the previous agents to "explore" (try out various alternatives). A social planner, by means of carefully designed information disclosure, can incentivize the agents to balance exploration and exploitation so as to maximize social welfare. We overview the current state of this problem space, and highlight some recent developments.
Visit talk page
https://simons.berkeley.edu/talks/incentivized-exploration
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
In a wide range of scenarios, individual decision-makers consume information revealed by the previous decisions, and produce information that may help in the future decisions. Each decision-maker would individually prefer to "exploit" (optimize the current reward), but would like the previous agents to "explore" (try out various alternatives). A social planner, by means of carefully designed information disclosure, can incentivize the agents to balance exploration and exploitation so as to maximize social welfare. We overview the current state of this problem space, and highlight some recent developments.
0:47:51
Marco Ottaviani (Bocconi University)
https://simons.berkeley.edu/talks/tbd-480
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
Modern statistics, building on decision theory, does not explicitly take into account incentive problems and strategic behavior in the collection and analysis of data. In this talk I overview recent game-theoretic models that explicitly incorporate conflicts of interest between researchers and decision makers. I also discuss implications for the organization and regulation of data collection and analysis. The talk is largely based on the following recent papers:
Strategic Sample Selection with A. Di Tillio and P.N. Sorensen (2021 Econometrica),
Research and Approval Process: The Organization of Persuasion with E. Henry (2019, American Economic Review), and
P-Hacking in Clinical Trials and How Incentives Shape the Distribution of Results across Phases with J. Adda and C. Decker (2000 PNAS).
Visit talk page
https://simons.berkeley.edu/talks/tbd-480
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
Modern statistics, building on decision theory, does not explicitly take into account incentive problems and strategic behavior in the collection and analysis of data. In this talk I overview recent game-theoretic models that explicitly incorporate conflicts of interest between researchers and decision makers. I also discuss implications for the organization and regulation of data collection and analysis. The talk is largely based on the following recent papers:
Strategic Sample Selection with A. Di Tillio and P.N. Sorensen (2021 Econometrica),
Research and Approval Process: The Organization of Persuasion with E. Henry (2019, American Economic Review), and
P-Hacking in Clinical Trials and How Incentives Shape the Distribution of Results across Phases with J. Adda and C. Decker (2000 PNAS).
0:50:26
Modibo Camara (Northwestern University)
https://simons.berkeley.edu/talks/tbd-479
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
We show that regulators can successfully adapt to market conditions like demand and supply, even if those conditions are unpredictable and evolve constantly. In our model of adaptive monopoly regulation, the regulator receives market data that it can use to revise policies over time. Building on the literature on learning in games, we develop new solution concepts for the firm that generalize Bayesian rationality but require no prior knowledge to satisfy. Our results culminate in a foundation for customer-first regulation, which uses taxes and data-driven subsidies to incentivize the firm to prioritize welfare over profits.
Visit talk page
https://simons.berkeley.edu/talks/tbd-479
Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
We show that regulators can successfully adapt to market conditions like demand and supply, even if those conditions are unpredictable and evolve constantly. In our model of adaptive monopoly regulation, the regulator receives market data that it can use to revise policies over time. Building on the literature on learning in games, we develop new solution concepts for the firm that generalize Bayesian rationality but require no prior knowledge to satisfy. Our results culminate in a foundation for customer-first regulation, which uses taxes and data-driven subsidies to incentivize the firm to prioritize welfare over profits.