
Lower Bounds on Metropolized Sampling Methods for WellConditioned Distributions
We give lower bounds on the performance of two of the most popular sampl...
read it

Numerical Composition of Differential Privacy
We give a fast algorithm to optimally compose privacy guarantees of diff...
read it

Private Nonsmooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps
We study the differentially private Empirical Risk Minimization (ERM) an...
read it

Fast and Memory Efficient Differentially PrivateSGD via JL Projections
Differentially PrivateSGD (DPSGD) of Abadi et al. (2016) and its varia...
read it

Minimum Cost Flows, MDPs, and ℓ_1Regression in Nearly Linear Time for Dense Instances
In this paper we provide new randomized algorithms with improved runtime...
read it

A NearlyLinear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
Arising from structural graph theory, treewidth has become a focus of st...
read it

Structured Logconcave Sampling with a Restricted Gaussian Oracle
We give algorithms for sampling several structured logconcave families t...
read it

A Faster Interior Point Method for Semidefinite Programming
Semidefinite programs (SDPs) are a fundamental class of optimization pro...
read it

Bipartite Matching in Nearlylinear Time on Moderately Dense Graphs
We present an Õ(m+n^1.5)time randomized algorithm for maximum cardinali...
read it

Reducing Isotropy and Volume to KLS: An O(n^3ψ^2) Volume Algorithm
We show that the the volume of a convex body in ℝ^n in the general membe...
read it

Composite Logconcave Sampling with a Restricted Gaussian Oracle
We consider sampling from composite densities on ℝ^d of the form dπ(x) ∝...
read it

Network size and weights size for memorization with twolayers neural networks
In 1988, Eric B. Baum showed that twolayers neural networks with thresh...
read it

An Improved Cutting Plane Method for Convex Optimization, ConvexConcave Games and its Applications
Given a separation oracle for a convex set K ⊂R^n that is contained in a...
read it

Acceleration with a Ball Optimization Oracle
Consider an oracle which takes a point x and returns the minimizer of a ...
read it

Positive Semidefinite Programming: Mixed, Parallel, and WidthIndependent
We give the first approximation algorithm for mixed packing and covering...
read it

Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
We show that the gradient norm ∇ f(x) for x ∼(f(x)), where f is strongl...
read it

Solving Tall Dense Linear Programs in Nearly Linear Time
In this paper we provide an Õ(nd+d^3) time randomized algorithm for solv...
read it

Faster Matroid Intersection
In this paper we consider the classic matroid intersection problem: give...
read it

Strong SelfConcordance and Sampling
Motivated by the Dikin walk, we develop aspects of an interiorpoint the...
read it

Computing Circle Packing Representations of Planar Graphs
The Circle Packing Theorem states that every planar graph can be represe...
read it

Solving Linear Programs with Sqrt(rank) Linear System Solves
We present an algorithm that given a linear program with n variables, m ...
read it

The Randomized Midpoint Method for LogConcave Sampling
Sampling from logconcave distributions is a well researched problem tha...
read it

Complexity of Highly Parallel NonSmooth Convex Optimization
A landmark result of nonsmooth convex optimization is that gradient des...
read it

A nearoptimal algorithm for approximating the John Ellipsoid
We develop a simple and efficient algorithm for approximating the John E...
read it

Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
Many convex problems in machine learning and computer science share the ...
read it

An O(m/ε^3.5)Cost Algorithm for Semidefinite Programs with Diagonal Constraints
We study semidefinite programs with diagonal constraints. This problem c...
read it

Algorithmic Theory of ODEs and Sampling from Wellconditioned Logconcave Densities
Sampling logconcave functions arising in statistics and machine learning...
read it

Adversarial Examples from Cryptographic PseudoRandom Generators
In our recent work (Bubeck, Price, Razenshteyn, arXiv:1805.10204) we arg...
read it

Chasing Nested Convex Bodies Nearly Optimally
The convex body chasing problem, introduced by Friedman and Linial, is a...
read it

Competitively Chasing Convex Bodies
Let F be a family of sets in some metric space. In the Fchasing problem...
read it

Solving Linear Programs in the Current Matrix Multiplication Time
This paper shows how to solve linear programs of the form _Ax=b,x≥0 c^ x...
read it

Metrical task systems on trees via mirror descent and unfair gluing
We consider metrical task systems on tree metrics, and present an O(dept...
read it

The KannanLovászSimonovits Conjecture
The KannanLovászSimonovits conjecture says that the Cheeger constant o...
read it

A NearlyLinear Bound for Chasing Nested Convex Bodies
Friedman and Linial introduced the convex body chasing problem to explor...
read it

Leverage Score Sampling for Faster Accelerated Regression and ERM
Given a matrix A∈R^n× d and a vector b ∈R^d, we show how to compute an ϵ...
read it

An homotopy method for ℓ_p regression provably beyond selfconcordance and in inputsparsity time
We consider the problem of linear regression where the ℓ_2^n norm loss (...
read it

kserver via multiscale entropic regularization
We present an O(( k)^2)competitive randomized algorithm for the kserve...
read it

Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation
We give the first rigorous proof of the convergence of Riemannian Hamilt...
read it

Efficient Convex Optimization with Membership Oracles
We consider the problem of minimizing a convex function over a convex se...
read it

Optimal algorithms for smooth and strongly convex distributed optimization in networks
In this paper, we determine the optimal convergence rates for strongly c...
read it

Kernelbased methods for bandit convex optimization
We consider the adversarial convex bandit problem and we build the first...
read it

Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
Let ϕ(G) be the minimum conductance of an undirected graph G, and let 0=...
read it
Yin Tat Lee
is this you? claim profile