Optimization and Algorithm Design 2023
2023-11-27..2023-12-01
Berkeley, United States
[Semidefinite Optimization, Approximation and Applications 2014, Randomized Numerical Linear Algebra and Applications 2018, Optimization, Statistics and Uncertainty, Discrete Optimization via Continuous Relaxation, Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017), Learning, Algorithm Design and Beyond Worst-Case Analysis]
who it's for
optimization researchers, algorithm designers, machine learning researchers, numerical linear algebra engineers, distributed systems researchers, computational scientists, operations researchers
topics
geodesically convex matrix optimization; stochastic Newton distributed methods; high-dimensional SGD ODE limits; mean-field neural network analysis; theory of linear transformers; robust gradient descent for corrupted data; randomized linear algebra for IPMs; interior point methods with approximate solves; nested dissection for separable LPs; dynamic least-squares regression; fast p-norm regression algorithms; submodular function minimization and sparsification
| title | author | length |
|---|---|---|
| Exploiting geometric structure in (matrix-valued) optimization | Melanie Weber | 40m |
Provides a practical CCCP framework for matrix-valued objectives that are geodesically convex and expressible as a difference of convex functions, proving the… | ||
| A Stochastic Newton Algorithm for Distributed Convex Optimization | Brian Bullins | 35m |
A distributed stochastic Newton algorithm for homogeneous convex problems introduces a stochastic Hessian-vector product oracle and solves constrained… | ||
| Hitting the High-D(imensional) Notes: An ODE for SGD learning dynamics in high-dimensions | Courtney Paquette | 56m |
Framework shows that when samples and dimensions grow together, SGD and SGD+M trajectories become an ODE limit determined only by the data covariance spectrum… | ||
| Beyond NTK: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Time | Tengyu Ma | 55m |
Claim: gradient-flow mean-field analysis proves unmodified SGD learns single-index targets with quartic activations using polynomial width, iterations, and… | ||
| Theoretical and Practical Insights from Linear Transformers | Xiang Cheng | 33m |
One-layer linear transformers that minimize the in‑context loss provably reproduce one-step gradient descent (under Gaussian x and θ assumptions), and… | ||
| Robust Gradient Descent: Agnostically Estimating an Unknown Affine Transformation... | Santosh Vempala | 51m |
Claims a polynomial-time algorithm that, from an ε‑corrupted sample of an unknown affine transform of the d‑cube, outputs ĤA, Ĥb with total variation O(ε)… | ||
| Randomized Linear Algebra for Interior Point Methods | Petros Drineas | 27m |
Shows that predictor‑corrector IPMs retain their iteration complexity when each Newton linear system meets forward and backward error bounds (energy norm error… | ||
| IPM and Nested Dissection for Planar and Separable LPs | Sally Dong | 28m |
Combines nested dissection separator trees with a robust interior point method to get concrete solvers: planar min-cost flow in nearly-linear time (m·polylog… | ||
| Nash Social Welfare and A Tale of Mathematical Programs | Mohit Singh | 28m |
Problem is NP-hard and APX-hard; presentation lays out concrete convex and nonconvex relaxations for Nash and weighted Nash social welfare, and ties them to… | ||
| Short-Flat Decompositions and Faster Algorithms for Linear Inverse Problems | Kevin Tian | 29m |
Introduces short-flat decompositions as the structural tool that lets projected gradient methods tolerate a semi-random adversary and still recover sparse… | ||
| Fast Algorithms for Regression Problems | Deeksha Adil | 49m |
Presents a concrete algorithmic claim: p‑norm regression for p>2 gets high‑accuracy solutions by reducing to a sequence of L2 solves and converges in m^{1/3}… | ||
| The Complexity of Dynamic Least-Squares Regression | Shunhua Jiang | 01h 02m |
Settles the dynamic LSR complexity: an nd + d^3 · poly(1/ε) incremental algorithm (oblivious) that yields amortized O(d) per insertion using leverage-score… | ||
| Tight Bounds for Active lp Regression and Beyond | David P. Woodruff | 01h 00m |
Gives tight query bounds for active lp regression with concrete algorithms: sensitivity sampling followed by Lewis-weight chaining and a label-partition that… | ||
| Robust Learning of a Single Neuron via Sharpness | Jelena Diakonikolas | 32m |
Proves that, under two mild distributional conditions (anticoncentration along one good vector and 1/t^4 tail control of one-dimensional projections), running… | ||
| Instance Optimal Iterative Methods for Matrix Function Approximation | Cameron Musco | 32m |
Claim: Lanczos (Krylov) is instance-optimal for rational functions—for a degree-M/Q rational f with poles outside the spectrum, Lanczos output is within a… | ||
| Sparsifying Generalized Linear Models | Yang Liu | 56m |
Proves that sums F(x)=Σ f_i(<a_i,x>) with symmetric, monotone, mild growth f_i admit (1+ε)-approximate sparsifiers of support size about n/ε^2 times polylog… | ||
| Breaking the quadratic gap for strongly polynomial solvers to combinatorial linear programs | Bento Natura | 01h 00m |
Claims a concrete speedup: a strongly polynomial interior‑point method breaks the quadratic gap between high‑accuracy and exact solvers for combinatorial LP… | ||
| Discrepancy Minimization via Regularization | Adrian Vladu | 57m |
Introduces a concrete algorithmic framework that uses regularization to smooth the max norm, runs a continuous Newton-style update on fractional colorings, and… | ||
| Quotient Sparsification for Submodular Functions | Kent Quanrud | 29m |
Proves a single theorem that sparsifies any monotone submodular function by sampling a weighted subset of elements of size O(r log n / ε^2) and preserves the… | ||
| Recent Progress on Submodular Function Minimization | Haotian Jiang | 32m |
Recent results give concrete algorithms and bounds for submodular minimization when a minimizer has ≤ k elements: a deterministic weakly‑polynomial algorithm… | ||
| Network Unreliability in Sub-quadratic Time | Debmalya Panigrahi | 59m |
New algorithm estimates all‑terminal network unreliability in roughly m + n^{1.5} time, improving over the previous ~n^2 bound and breaking the need to… | ||
| Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver | Sorrachai Yingchareonthawornchai | 39m |
Presents a 1+ε fractional LP solver for kECSS that runs in near-linear time Õ(m/ε²) and converts to a (2+ε)-approximation for integral k-edge-connected… | ||
| nothing matches | ||