Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
2016-09-19..2016-09-23
Berkeley, United States
| title | author | length |
|---|---|---|
| Introducing Decision-Making Under Uncertainty to Medical Research:... | Don Berry | 56m |
Argues that patient-level Bayesian adaptive and multi-arm bandit designs raise real-world success rates (example: 63 expected successes vs 50 under 50/50… | ||
| Optimal A-B Testing | Vivek Farias | 48m |
Claims that optimizing allocation, not randomizing, can boost estimator efficiency from constant to order-n efficiency when covariate dimension scales with… | ||
| Stable Marriages in Metric Spaces | Balaji Prabhakar | 30m |
One-dimensional Hamming preferences produce many ties: K=1 ties persist and even K ≈ log n leaves exponentially many stable matchings; recovering uniqueness… | ||
| The Simplex and Policy-Iteration Methods are Strongly Polynomial... | Yinyu Ye | 52m |
Shows that MDPs with a fixed discount are solvable by standard LP methods with explicit iteration bounds: policy iteration finishes in O(n/(1−γ) log(1/(1−γ)))… | ||
| Interpolating Between Stochastic and Worst-case Optimization | R. Ravi | 34m |
Proposes a hybrid input model that interpolates between stochastic and adversarial arrivals via a lever epsilon that flips each request with probability… | ||
| Smarter Tools for (Citi)Bike-Sharing | David Shmoys | 36m |
City bike-share demand gets modeled as Poisson arrival/return rates per station, then time-sliced into half-hour periods and analyzed with a stochastic dynamic… | ||
| How to Predict When Estimation is Hard: Algorithms for Learning on Graphs | Sasha Rakhlin | 51m |
Claim: sequential predictors achieve the same error as the NP‑hard best graph labeling while avoiding model estimation by using improper prediction and… | ||
| From Predictions to Decisions: Limitations and Possibilities of Optimization from Samples | Yaron Singer | 48m |
Shows that coverage functions (and many submodular examples like influence maximization) are PMAC-learnable yet provably fail to yield good decisions when… | ||
| Distributed Partial Clustering | Sudipto Guha | 36m |
Distributed clustering with T outliers and an arbitrary partition across s sites achieves a one‑round constant‑factor approximation by having each site compute… | ||
| Online Vector Packing | Yossi Azar | 52m |
General online vector packing is essentially hopeless in the worst case: competitive ratio grows Θ(d) for arbitrary vectors, and an information-theoretic lower… | ||
| Clustering Using Pairwise Comparisons | R. Srikant | 33m |
Converts the sparse N × (M choose 2) pairwise matrix into an N × M net-wins matrix, applies spectral projection and then repeats clustering after a random… | ||
| Online Algorithms for Covering and Packing Problems with Convex Objectives | Niv Buchbinder | 34m |
Generalizes online primal–dual to convex objectives and proves a concrete competitive bound: for monotone convex f with monotone gradient and polynomial-like… | ||
| Kernel-Based Methods for Bandit Convex Optimization | Sebastien Bubeck | 59m |
Proposes a concrete bandit algorithm that replaces one-point gradient estimates with a kernel-based unbiased estimator built from a time-varying kernel (the… | ||
| Always Valid Inference: Continuous Monitoring of A/B Tests | Ramesh Johari | 50m |
Optimizely implements always-valid p-values computed from a MSPRT (mixture SPRT) so type I error remains bounded under arbitrary user stopping rules (fixes the… | ||
| Revisiting the Exploration-Exploitation Trade-Off in Bandit Models | Emilie Kaufmann | 32m |
Characterizes when regret and pure-exploration diverge: sampling must follow information-theoretic Wstar proportions computed by a 1‑D optimization over KL… | ||
| Distribution-Free Models of Social and Information Networks | Tim Roughgarden | 55m |
Proposes two distribution-free graph classes motivated by triadic closure and proves concrete positive results. For triangle-dense graphs (global transitivity… | ||
| Learning in Games with Best-Response Oracles | Tomer Koren | 31m |
Shows that with a best-response oracle and value queries any algorithm needs Omega(sqrt(n)) time to approximate a zero-sum n-by-n game to constant accuracy, by… | ||
| Online Optimization and Learning Under Long-Term Convex Constraints and Objectives | Nikhil Devanur | 35m |
Presents concrete algorithms that turn long-term convex constraints and concave objectives into repeated linear goals using Fenchel conjugate linearization and… | ||
| Avoiding Cascading Failures for Time-of-Use Pricing | Anna Karlin | 31m |
Set static per-slot prices from the expected LP and dual prices so the expected demand per slot is below capacity, then prove that with a small multiplicative… | ||
| Procrastination with Variable Present Bias | Nicole Immorlica | 34m |
Introduces variable present bias: each day the bias B is drawn IID (example: 1/3 chance B=1, 2/3 chance B=3). Proves a main lemma that worst-case task graphs… | ||
| Simple Pricing Schemes for Consumers with Evolving Values | Shuchi Chawla | 34m |
Considers a buyer who repeatedly uses an app whose value evolves stochastically and compares a simple pricing to the omniscient benchmark that extracts the… | ||
| A Unified Duality Theory for Bayesian Mechanism Design | Matt Weinberg | 35m |
Presents a unified LP duality framework that produces a virtual welfare upper bound for Bayesian mechanisms by constructing an explicit LP duality flow whose… | ||
| Bandits and Agents: How to Incentivize Exploration? | Aleksandrs Slivkins | ? |
Claims a black-box reduction that converts any bandit algorithm into a Bayes incentive-compatible procedure by simulating the original algorithm rarely and… | ||
| Online Ad Allocation: Robust Optimization for Repeated Auctions | Vahab Mirrokni | 40m |
Vahab Mirrokni, Google
https://simons.berkeley.edu/talks/vahab-mirrokni-2016-09-22
Optimization and Decision-Making Under Uncertainty | ||
| Competitive Algorithms from Competitive Equilibria | Kamesh Munagala | 48m |
Online non‑clairvoyant scheduling over a general packing polytope is modeled, and the rule that maximizes the product of job rates — proportional fairness — is… | ||
| Online Flow-Time Optimization | Janardhan Kulkarni | 36m |
Online flow-time on unrelated machines gets two concrete algorithms, one clairvoyant greedy that assigns each arrival to the machine minimizing the… | ||
| Online Algorithms with Recourse | Amit Kumar | 33m |
Greedy online load balancing is Θ(log m) worst case, but allowing limited recourse changes the picture: an edge‑orientation rule that flips all incoming edges… | ||
| Scheduling with Uncertain Processing Times | Marc Uetz | 35m |
Shows a 3 + Δ/2 approximation for stochastic unrelated‑machine scheduling, where Δ upper‑bounds the squared coefficient of variation of job sizes. Uses a… | ||
| Secretary Problems and Online Selection with A Priori Information | Ola Svensson | 48m |
Classic secretary generalizes to matroids and to K‑choice; geometric bucketing gives a log‑rank reduction (random sampling + run unweighted algorithm on one… | ||
| Optimal Online Algorithms via Linear Scaling | Thomas Kesselheim | 30m |
Presents a simple linear scaling recipe: at time L solve the offline problem on the L/n fraction of items with capacities scaled by L/n, ignore past decisions… | ||
| nothing matches | ||