Limitations of Stochastic Selection with Pairwise Independent Priors
Ғылым және технология
A Google TechTalk, presented by Neel Patel, 2024-04-02
Google Algorithms Seminar. ABSTRACT: Motivated by the growing interest in correlation-robust stochastic optimization, we investigate stochastic selection problems beyond independence. Specifically, we consider the instructive case of pairwise-independent priors and matroid constraints. We obtain essentially-optimal bounds for contention resolution and prophet inequalities. The impetus for our work comes from the recent work of Caragiannis et al., who derived a constant-approximation for the single-choice prophet inequality with pairwise-independent priors.
For general matroids, our results are tight and largely negative. For both contention resolution and prophet inequalities, our impossibility results hold for the full linear matroid over a finite field. We explicitly construct pairwise-independent distributions which rule out an omega(1/Rank)-balanced offline CRS and an omega(1/log Rank)-competitive prophet inequality against the (usual) oblivious adversary. For both results, we employ a generic approach for constructing pairwise-independent random vectors -- one which unifies and generalizes existing pairwise-independence constructions from the literature on universal hash functions and pseudorandomness. Specifically, our approach is based on our observation that random linear maps turn linear independence into stochastic independence.
We then examine the class of matroids which satisfy the so-called partition property -- these include most common matroids encountered in optimization. We obtain positive results for both online contention resolution and prophet inequalities with pairwise-independent priors on such matroids, approximately matching the corresponding guarantees for fully independent priors. These algorithmic results hold against the almighty adversary for both problems.
ABOUT THE SPEAKER: I am Neel, a third-year CS PhD student in the USC Theory Group, where I am being advised by Shaddin Dughmi and David Kempe. I am broadly interested in Combinatorial Optimization in the presence of Uncertainty or Incentives, Algorithmic Contract Theory and Computational Economics. Recently, I have been also working on problems in designing (fast) Dynamic Algorithms for Graph Problems. I have also worked on designing AI/ML algorithms with the consideration of ethical aspects.
Before starting my Ph.D., I spent a wonderful one and a half years at the National University of Singapore as a Research Assistant working with Yair Zick and Reza Shokri. Before that, I completed my B.Stat at Indian Statistical Institute, Kolkata.
Пікірлер: 3
*Abstract* This talk explores stochastic selection problems, focusing on prophet inequalities, beyond the assumption of independence. The speaker investigates the case of pairwise-independent priors and matroid constraints, where pairs of elements have independent weights but larger groups can exhibit arbitrary correlations. The talk presents both positive and negative results. For general matroids, the results are largely negative, demonstrating limitations on achievable approximation guarantees. However, for matroids satisfying the partition property, which includes common matroids in optimization, constant-factor prophet inequalities are achievable. The talk also discusses a novel technique for constructing pairwise-independent random vectors based on random linear maps. *Talk Summary* *Introduction to Prophet Inequalities (**0:00**)* * 0:46: The speaker introduces the concept of prophet inequalities, framing it as a game between a gambler and an adversary. * 1:18: The classic prophet inequality involves a single item and multiple buyers arriving sequentially, each with a bid sampled from a known distribution. * 1:34: The gambler (seller) must decide whether to accept or reject each bid without knowing future bids, aiming to maximize their reward. * 2:55: The concept of a "prophet" is introduced, representing an entity with full knowledge of all bids and their values. * 3:08: The talk highlights the classical result that with independent bids, the best online policy for the gambler achieves at least half of the prophet's value. *Matroid Prophet Inequalities and Beyond Independence (**3:36**)* * 3:53: The discussion extends to matroid prophet inequalities, where the gambler can accept a set of elements subject to matroid constraints. * 4:30: The talk emphasizes the limitations of assuming independence among element weights, as it may not reflect real-world scenarios like market dynamics. * 8:12: Existing results on prophet inequalities under independence are mentioned, including constant-factor approximations for various matroid constraints. * 9:09: The speaker motivates the need to explore beyond independence, highlighting applications where correlations are present, such as market clearing problems and algorithmic subroutines. *Pairwise Independence and Its Implications (**11:39**)* * 11:39: The talk delves into the concept of pairwise independence, where any pair of element weights are independent, but larger groups can have arbitrary correlations. * 14:08: Pairwise independence is presented as a promising model, as it relaxes the independence assumption while maintaining some desirable properties. * 14:32: The speaker mentions a recent result demonstrating a constant-factor prophet inequality for single-choice scenarios with pairwise-independent priors. * 17:10: The central question of the work is posed: Do constant-factor prophet inequalities exist for pairwise-independent priors beyond single-choice settings? *Main Results and Hardness Construction (**17:23**)* * 17:29: Positive results are presented for matroids satisfying the partition property, showing the existence of constant-factor pairwise-independent prophet inequalities. * 19:57: A key result reveals that constant-factor pairwise-independent prophet inequalities do not exist for general matroids, specifically for the full binary matroid. * 20:14: A lower bound of 1/log(rank) is established for the full binary matroid, indicating the limitations of achieving good approximations in general settings. *Discussion and Takeaways (**50:46**)* * 50:46: The speaker addresses the question of alternative gambler strategies, highlighting that the presented hardness construction remains robust even against more sophisticated approaches. * 55:31: The construction of the hard instances is discussed, involving the careful selection of vectors and subspaces to ensure pairwise independence and the desired spanning properties. * 1:02:54: The talk concludes by emphasizing the distinction between partition matroids and general matroids under pairwise independence and suggesting potential implications for the matroid secretary conjecture. * 1:03:29: The presented technique of embedding vectors into lower-dimensional subspaces to transform linear independence into stochastic independence is highlighted as a valuable tool with potential applications beyond the scope of the current work. i used gemini 1.5 pro to summarize the transcript Token count 15,108 / 1,048,576
#confidence intervals .. #prob(abilities) pairwise(?) "#markets" #dynamics #distribution(s) #modelling #yieldfarming #investment #economics #rate(s) #valuechain #dealflows #retail #vendor #indicator(s) #instrument(s) #capitalmarkets #esg
*ELI5 Abstract* Imagine you have a bunch of toys, each with a secret price tag. You want to pick the most valuable toy, but you can only see their prices one at a time. This is like a game where you're trying to guess which toy is worth the most without knowing all the prices! The game gets trickier because the prices might be related somehow. For example, similar toys might have similar prices. This makes it harder to guess which one is the best. This talk explores how good your guesses can be in this game, even when the prices are related. It turns out that for some types of toys, you can still do pretty well, but for others, it's almost impossible to pick the best one without knowing all the prices upfront.