Optimization, Statistics and Uncertainty
2017-11-28..2017-12-01
Berkeley, United States
[Quantifying Uncertainty: Stochastic, Adversarial, and Beyond, Information Theory, Learning and Big Data (Simons Institute, 2015), Learning, Algorithm Design and Beyond Worst-Case Analysis, Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016), Optimization and Algorithm Design 2023, Randomized Numerical Linear Algebra and Applications 2018]
as the organisers put it
This workshop aims to explore the emerging connections between optimization, statistics and machine learning. It will discuss ties, both well-known and anticipated, between optimization and various approaches to modeling, reasoning about and coping with uncertainty. Some of the key topics that will be covered are: unsupervised machine learning, computational hardness in statistics, differential privacy and its applications in statistics and machine learning, online regret minimization, robust optimization and planted models.
who it's for
optimization researchers, machine learning researchers, statisticians, algorithm designers, theoretical computer scientists, privacy researchers, graph and network analysts
topics
Tikhonov-regularized polynomial extrapolation; Hamiltonian Monte Carlo with Hessian metric; Wasserstein distributional robustness; semidefinite-program DRO constructions; implicit regularization in nonconvex estimation; leverage-score weighted sampling for matrix completion; upper-confidence Frank-Wolfe bandit optimization; variational mean-field instability and TAP/AMP correction; differential privacy for adaptive data analysis (median-of-means, Gaussian noise); graph powering for spectral methods; empirical likelihood chi-squared upper confidence bounds
| title | author | length |
|---|---|---|
| Data Driven Optimization Models and Algorithms | Yinyu Ye | 01h 08m |
Describes tractable DRO constructions (moment, likelihood and Wasserstein distance sets) that reduce to semidefinite programs and give finite‑sample confidence… | ||
| Regularized Nonlinear Acceleration | Alex d'Aspremont | 32m |
Post-processes the last K iterates (typically 5–10) by forming increments, solving a small Tikhonov-regularized linear system, and returning a C-weighted… | ||
| Learning One-hidden-layer Neural Networks with Landscape Design | Tengyu Ma | 32m |
Designs a new population objective g that uses Hermite-polynomial coefficients to match Hermite coefficients between training activation gamma and data… | ||
| Algorithmic Stability for Interactive Data Analysis | Jonathan Ullman | 34m |
Interactive reuse of data causes severe overfitting: naive empirical answers let an adaptive procedure reach correlation about √D/√N (even perfect when D > N)… | ||
| Preventing Overfitting in Adaptive Data Analysis via Stability | Thomas Steinke | 27m |
Claims that adaptive answers can have distribution-dependent accuracy that scales with each query's variance rather than worst-case range, and gives algorithms… | ||
| The Convergence of Hamiltonian Monte Carlo | Santosh Vempala | 31m |
Proves that Hamiltonian Monte Carlo run with the Hessian manifold metric (log barrier) mixes far faster on polytopes — roughly MN^{2/3} mixing steps (with… | ||
| Distributional Robustness, Learning, and Empirical Likelihood | John Duchi | 34m |
Claims that modest distributional robustness recovers a variance penalty and gives usable certificates, implemented two concrete tools: a convex reweighting… | ||
| An Instability in Variational Methods for Learning Topic Models | Andrea Montanari | 58m |
Variational mean-field inference on low-rank generative models produces a spurious informative fixed point between the information-theoretic spectral threshold… | ||
| A Few Connections Between Optimization and Probability | Sasha Rakhlin | 33m |
Claims an iff equivalence: a martingale inequality holds for all martingale difference sequences exactly when there exists a function U satisfying domination… | ||
| Implicit Regularization in Nonconvex Statistical Estimation | Yuxin Chen | 29m |
Vanilla gradient descent on nonconvex statistical losses implicitly enforces incoherence and therefore converges much faster than worst-case theory predicts… | ||
| Low-rank Matrix Completion: Adaptive Sampling Can Help When, How? | Rachel Ward | 37m |
Low-rank matrix completion uses a first two-phase sampling pass: take uniform samples, estimate large row/column leverage scores from sampled row norms, then… | ||
| Graph Powering | Emmanuel Abbe | 01h 02m |
Proposes graph powering: form a new graph by adding edges between nodes within graph distance ≤ R, using the adjacency of walks thresholded to 0/1, then run… | ||
| On Approximation Guarantees for Greedy Low Rank Optimization | Sahand Negahban | 30m |
Greedy addition of rank‑one atoms achieves a provable multiplicative approximation: objective of the K‑rank greedy iterate is within a factor ~1 − exp(−C K/R)… | ||
| Fast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfe | Quentin Berthet | 30m |
Generalizes multi-armed bandits to convex optimization over the simplex with bandit feedback and proposes Upper-Confidence Frank-Wolfe: maintain per-coordinate… | ||
| Optimization's Untold Gift to Learning: Implicit Regularization | Nathan Srebro Bartom | 01h 01m |
Shows that plain optimization picks a particular solution from many global minima: gradient methods on underdetermined linear least squares converge to the… | ||
| The Power and Limitations of Kernel Learning | Misha Belkin | 33m |
Argues that kernel machines reproduce many modern ML phenomena but suffer from nearly exponential eigenvalue decay that makes RKHS problems extremely… | ||
| Sampling Algorithms for Combinatorial Pure Exploration | Anupam Gupta | 29m |
Takes the max-weight spanning-tree and matroid best-set problems from unknown edge means and gives sample-complexity bounds: adaptive elimination matches the… | ||
| Compositional Properties of Statistical Procedures: An Information-Theoretic View | Max Raginsky | 59m |
Argues that mutual information and KL chain rules explain linear degradation under adaptive composition but fail for deterministic estimators (mutual… | ||
| Stability and Convergence Trade-Off of Iterative Optimization Algorithms | Bin Yu | 28m |
Paper proves a quantitative trade-off between algorithmic stability and optimization convergence, using jackknife-style data perturbations, Le Cam minimax… | ||
| Accuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained... | Katrina Ligett | 30m |
Presents an accuracy-first procedure for differentially private ERM that searches epsilons by starting very private and doubling privacy while using correlated… | ||
| nothing matches | ||