Meet the Fellows Welcome Event
2021-09-08..2021-09-09
Berkeley, United States
[Meet the Fellows Welcome Event, Meet the Fellows Welcome Event Fall 2024]
who it's for
machine learning researchers, theoretical computer scientists, statisticians and applied probabilists, quantum information researchers, algorithm designers, economists and mechanism designers, causal inference researchers
topics
profile maximum likelihood for discrete properties; privacy-preserving auction design; information-theoretic fairness measures; minimax policy learning under confounding; sample-efficient reinforcement learning algorithms; stein variational gradient descent analysis; normalizing flows for distribution approximation; quantum algorithms for mean estimation; post-quantum succinct arguments; spectral bounds for local Hamiltonians; optimal transport algorithms for inverse problems
| title | author | length |
|---|---|---|
| Efficient Universal Estimators For Symmetric Property Estimation | Kirankumar Shiragur | 14m |
Describes an algorithm that computes an approximate PML (profile maximum likelihood) distribution for discrete IID samples and proves it is sample-optimal for… | ||
| Mechanism Design Via Machine Learning: Overfitting, Incentives, and Privacy | Ellen Vitercik | 09m |
Research shows how to tune a parameterized auction family—most simply the second-price (Vickrey) auction with reserve rho—by optimizing empirical revenue on a… | ||
| Fair And Reliable Machine Learning For High-Stakes Applications:approaches Using Information Theory | Sanghamitra Dutta | 14m |
Proposes a principled measure of non‑exempt disparity that combines partial information decomposition with causal models, because conditional mutual… | ||
| Information, Learning, And Incentive Design For Societal Networks | Manxi Wu | 14m |
Develops a formal framework marrying game theory, mechanism design, and control to quantify how platform signals change routing and congestion and to design… | ||
| Causal Inference And Data-Driven Decision-Making | Angela Zhou | 12m |
Presents a concrete method for learning treatment rules that is robust to unobserved confounding by optimizing worst‑case policy value over an ambiguity set… | ||
| Choosing Between Dags Can Be Hard | Richard Guo | 11m |
Two DAGs that are observationally equivalent sit on different algebraic constraints in correlation space: one is a plane enforcing marginal independence, the… | ||
| Linear Predictors in Reinforcement Learning: ... | Andrea Zanette | 11m |
Shows realizability can fail dramatically: there exist constructions giving an exponential lower bound on learnability even with exact linear Q representation… | ||
| Towards Credible and Effective Data-Driven Decision-Making | Angela Zhou | 09m |
Describes a concrete method for minimax-optimal policy learning under unobserved confounding: parameterize confounding with a sensitivity model, plug that into… | ||
| Primal--Dual Optimization and Application to Sampling | Adil Salim | 09m |
Recasts sampling as minimizing KL over probability measures, analyzes Stein Variational Gradient Descent in the infinite‑particle (population) limit using the… | ||
| Data Efficient Methods for Reinforcement Learning | Xian Carrie Wu | 11m |
Claims provable speedups for SGD with experience replay on an autoregressive Markov chain showing loss decays exponentially with an improved dependence of T… | ||
| Distribution-Free Robustness | Sitan Chen | 12m |
Provides an efficient algorithm that tolerates up to a 50% fraction of arbitrary corruptions and achieves near‑optimal clean mean squared error (up to log… | ||
| Pseudorandom Generators and Small-Space Derandomization | William Hoza | 10m |
Construction shows a concrete PRG that maps 2-bit seed -> 3-bit output: (x,y,x xor y) and therefore is pairwise independent and fools depth-2 decision trees… | ||
| Preconditioning and Locality in Algorithm Design | Jason Li | 14m |
Shows that Steiner min-cut reduces to an unbalanced case that can be solved with a polylogarithmic number of max‑flow calls: isolating every terminal takes… | ||
| Query, Communication and Discrepancy | Makrand Sinha | 10m |
Shows a concrete k-fold correlation problem that yields a constant vs almost linear separation between quantum and randomized query complexity (previous best… | ||
| Dynamic Linear Algebra | Jan van den Brand | 09m |
Describes algorithms that maintain changing matrices to update graph and optimization answers faster, with concrete bounds: a matrix multiplication time… | ||
| Let's Sample Perfectly | Siddharth Bhandari | 13m |
Uniform sampling of proper colorings of an n-vertex graph with maximum degree Δ is framed: want exact samples from the uniform distribution over colorings, not… | ||
| A Complexity-Theoretic Perspective on Fairness | Michael P. Kim | 12m |
Defines multi-calibration as calibration not just overall but on subpopulations specified by a computational class, and shows how to reduce learning such… | ||
| Quantum Simulation of Relativistic Electronic Structure Hamiltonians | Torin Stetina | 09m |
Claims an explicit construction showing relativistic electronic-structure Hamiltonians (Dirac + effective QED terms) are efficiently simulatable in polynomial… | ||
| Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier | Fermi Ma | 13m |
Proves that Kilian's original succinct-argument construction becomes post-quantum secure when paired with a post-quantum hash by giving a general… | ||
| Quantum Necromancy and the Hardness of Observing Schrodinger's Cat | Yosi Atia | 12m |
Proves that detecting coherence between orthogonal branches requires the computational ability to swap alive and dead: if a T‑gate circuit distinguishes… | ||
| Short Proof of a Spectral Chernoff Bound for Local Hamiltonians | Nilin Abrahamsen | 12m |
Claims that the spectral measure of any local Hamiltonian concentrates exponentially in the number of qubits N (not in the number of edges M), with typical… | ||
| Convex Programs, Computational Phase Transitions, and Robust Algorithms | Sam Hopkins | 09m |
Claims a polynomial-time algorithm that, under only bounded covariance (two finite moments), returns mean estimates with the same Gaussian-optimal confidence… | ||
| Understanding Statistical-to-Computational Gaps via Low-Degree Polynomials | Alex Wein | 11m |
Low-degree polynomials act as a restricted-but-strong algorithm class and predict statistical–computational gaps: the distinguishing statistic is computable by… | ||
| Sharp Threshold for the Planted Matching Problem | Dana Yang | 11m |
Establishes a sharp statistical threshold λ = 4 for exact recovery in the planted matching model, proves the minimum-weight perfect matching is… | ||
| Correlation Adjusted Debiasing (CAD): Debiasing the Lasso with Inaccurate Covariate Model | Michael Celentano | 11m |
Proposes a correlation-adjusted debiasing estimator that recovers a single coefficient beta consistently even when the covariate model gamma and outcome theta… | ||
| On Query-to-Communication Lifting for Adversary Bounds | Anurag Anshu | 14m |
Shows that Chebyshev polynomials give the optimal low-degree approximations driving several concrete advances: a provable near-linear runtime algorithm for 1D… | ||
| One-Way Functions Imply Secure Computation in a Quantum World | Andrea Coladangelo | 12m |
Claims that one-way functions (secure against quantum inverters) suffice to build information-theoretically private multiparty computation when parties use… | ||
| Quantum Algorithms for the Mean Estimation Problem | Yassine Hamoudi | 13m |
Classical and quantum-sample models both require O(σ/√N) samples for one-dimensional mean estimation, but with quantum circuit (black-box) access model the… | ||
| Distribution-Free, Risk-Controlling Prediction Sets | Stephen Bates | 13m |
Proposes distribution-free procedures that wrap any black-box model to produce risk-controlling set-valued predictions: construct a one-dimensional family… | ||
| Learning Under Requirements | Luiz Chamon | 09m |
Proposes replacing penalty-weighted adversarial training with constraint optimization that enforces robustness as a constraint, reports matching adversarial… | ||
| Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS | Lin Chen | 12m |
Claim: the reproducing-kernel Hilbert space of the rotation-invariant neural tangent kernel on the unit sphere equals that of the Laplace kernel… | ||
| Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent | Spencer Frei | 11m |
Defines proxy convexity: two auxiliary functions h and g that sandwich a nonconvex objective so first-order guarantees transfer. Proves a proxy PL inequality… | ||
| On Implicit Regularization in Deep Learning | Wei Hu | 23m |
Shows that for matrix completion parameterized as a product of d×d layers, gradient descent from near-zero consistently recovers the low-rank ground truth by… | ||
| Equilibrium Computation and the Foundations of Multi-Agent Machine Learning | Emmanouil Zampetakis | 12m |
Shows an exponential query lower bound for any first order method to find an approximate local solution of nonconvex min max problems even with Lipschitz… | ||
| A Fast Algorithm for Optimal Transport | Matt Jacobs | 09m |
An algorithm alternates gradient ascent on duals with fast computation of the c-transform and uses the known explicit c-transform gradient (McCann) so each… | ||
| Approximating Distributions Using Well-Conditioned Normalizing Flows | Holden Lee | 12m |
Claim: universal approximation of many log-concave distributions (after padding with a small Gaussian) by well-conditioned affine coupling flows with condition… | ||
| Iterative Methods and High-Dimensional Statistics | Kevin Tian | 12m |
Proposes a Hamiltonian composite sampler that expands parameter space to make composite Langevin sampling stable and matches structured targets (box… | ||
| Geometric Methods for Machine Learning and Optimization | Melanie Weber | 11m |
Hierarchical data embeds into low‑dimensional hyperbolic space because tree and hyperbolic volumes grow exponentially, so hyperbolic representations reduce… | ||
| Graphical Optimal Transport and Its Applications | Yongxin Chen | 15m |
Presents algorithms that exploit pairwise graphical structure in multi-marginal optimal transport by combining Sinkhorn with junction-tree/belief-propagation… | ||
| Quantum Information Meets Cryptography | Qipeng Liu | 16m |
Classical position verification is impossible but using BB84 states gives a provably unclonable route: one verifier sends BB84 qubits, the other sends bases… | ||
| On Implicit Regularization in Deep Learning | Wei Hu | 11m |
Argues that gradient-descent optimization imposes an implicit regularizer that prefers low-complexity solutions, shows for matrix completion that parametrizing… | ||
| Optimal Transport for Inverse Problems | Yunan Yang | 11m |
Using Wasserstein loss instead of L2 for PDE and ML inverse problems aligns transport features of model and data so gradient-based optimization avoids many… | ||
| On the Power of Preconditioning in Sparse Linear Regression | Frederic Koehler | 09m |
Proves that using the precision-matrix graph and a nested dissection preconditioner lets Lasso attain the information-theoretic Mahalanobis error rate when the… | ||
| Causal Inference With Corrupted Data: Measurement Error, Missing Values, Discretization, And... | Rahul Singh | 11m |
Census releases add differential privacy noise and plan wage discretization (rounding to 50¢), which simulations show can shrink coverage from 95% down to… | ||
| Fundamental Limits Of Learning In Data-Driven Problems | Yanjun Han | 15m |
Proves exact minimax rates for entropy estimation without a positive density lower bound and achieves them via a two-stage approximation that handles vanishing… | ||
| Algorithmic Advances For The Design And Analysis Of Randomized Control Trials | Christopher Harshaw | 13m |
Formalizes a robustness–balance trade-off for covariate balancing and constructs a randomized design that provably navigates that trade-off near-optimally… | ||
| Multi-Agent Reinforcement Learning In Stochastic Games: From Alphago To Robust Control | Kaiqing Zhang | 15m |
Shows that a simple model-based multi-agent RL plug-in estimator achieves nearly minimax sample complexity scaling with state count S, action counts a1+a2… | ||
| Learning In The Presence Of Strategic Agents: Dynamics, Equilibria, And Convergence | Eric Mazumdar | 12m |
Shows that gradient play in nonconvex general-sum continuous games often fails: many Nash equilibria are locally unstable so basins of attraction are measure… | ||
| Causal Inference For Socio-Economic & Engineering Systems | Anish Agarwal | 11m |
Work bridges econometric causal methods and ML by treating counterfactuals as tensor/matrix completion problems, using synthetic interventions to impute… | ||
| Teamwork Makes The Von Neumann Work: Two Team Zero Sum Games | Emmanouil Vlatakis | 15m |
Claim: computing an approximate Nash equilibrium in two-team zero-sum games is CLS-hard, standard first-order discretizations like gradient descent… | ||
| Nonparametric Density Estimation and Convergence of GANs under Besov IPMs | Ananya Uppal | 11m |
Generalizes nonparametric density estimation to Besov IPMs and proves new minimax convergence rates, showing certain GAN estimators are minimax optimal where… | ||
| nothing matches | ||