Discrepancy Minimization via Regularization

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=Rb0vhnNWLwM


Duration: 57:18
974 views
20

Adrian Vladu (IRIF)
https://simons.berkeley.edu/talks/adrian-vladu-irif-2023-11-30
Optimization and Algorithm Design

We introduce a new algorithmic framework for discrepancy minimization based on regularization. We demonstrate how varying the regularizer allows us to re-interpret several breakthrough works in algorithmic discrepancy, ranging from Spencer's theorem to Banaszczyk's bound. Using our techniques, we also show that the Beck-Fiala and Komlos conjectures are true for a new regime of pseudorandom instances.

Joint work with Lucas Pesenti (SODA 2023).



Other Videos By Simons Institute for the Theory of Computing


2024-02-01Locality I
2024-02-01Quantum LDPC Codes I
2024-02-01Recent Advances in Multiplicity Codes
2024-02-01Intro to Quantum Codes
2024-02-01Algebraic Codes/Algorithms I
2023-12-08Data Structures and Optimization for Fast Algorithms
2023-12-02Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
2023-12-01Network Unreliability in Sub-quadratic Time
2023-12-01Recent Progress on Submodular Function Minimization
2023-12-01Quotient Sparsification for Submodular Functions
2023-12-01Discrepancy Minimization via Regularization
2023-12-01Breaking the quadratic gap for strongly polynomial solvers to combinatorial linear programs
2023-11-30Sparsifying Generalized Linear Models
2023-11-30Instance Optimal Iterative Methods for Matrix Function Approximation
2023-11-29Nash Social Welfare and A Tale of Mathematical Programs
2023-11-29Robust Gradient Descent: Agnostically Estimating an Unknown Affine Transformation...
2023-11-28Hitting the High-D(imensional) Notes: An ODE for SGD learning dynamics in high-dimensions
2023-11-27Exploiting geometric structure in (matrix-valued) optimization
2023-11-21Towards Interpretable Data Science
2023-11-13Introduction and Program Highlights
2023-11-13Modern Paradigms in Generalization


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Optimization and Algorithm Design
Adrian Vladu