Yin Tat Lee

Xinzhi Zhang

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Private Convex Optimization in General Norms.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Learning threshold neurons via edge of stability.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping.

[BibT_eX]

[DOI]

Proceedings of the Eleventh International Conference on Learning Representations, 2023

ReSQueing Parallel and Private Stochastic Convex Optimization.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Automatic Prompt Optimization with "Gradient Descent" and Beam Search.

[BibT_eX]

[DOI]

Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023

Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Geodesic Walks in Polytopes.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

A Slightly Improved Bound for the KLS Constant.

[BibT_eX]

[DOI]

Arun Jambulapati

CoRR, 2022

Faster maxflow via improved dynamic spectral vertex sparsifiers.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Computing Lewis Weights to High Precision.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

When Does Differentially Private Learning Not Suffer in High Dimensions?

[BibT_eX]

[DOI]

Xuechen Li

Tatsunori B. Hashimoto

Huseyin A. Inan

Janardhan Kulkarni

Abhradeep Guha Thakurta

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Differentially Private Fine-tuning of Language Models.

[BibT_eX]

[DOI]

Proceedings of the Tenth International Conference on Learning Representations, 2022

The Manifold Joys of Sampling (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Private Convex Optimization via Exponential Mechanism.

[BibT_eX]

[DOI]

Sivakanth Gopi

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Universal Barrier Is n-Self-Concordant.

[BibT_eX]

[DOI]

Man-Chung Yue

Math. Oper. Res., 2021

Solving Linear Programs in the Current Matrix Multiplication Time.

[BibT_eX]

[DOI]

Michael B. Cohen

J. ACM, 2021

Kernel-based Methods for Bandit Convex Optimization.

[BibT_eX]

[DOI]

Sébastien Bubeck

Ronen Eldan

J. ACM, 2021

Tutorial on the Robust Interior Point Method.

[BibT_eX]

[DOI]

CoRR, 2021

Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps.

[BibT_eX]

[DOI]

Janardhan Kulkarni

CoRR, 2021

Reducing isotropy and volume to KLS: an o*(n3ψ2) volume algorithm.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path.

[BibT_eX]

[DOI]

Sally Dong

Guanghao Ye

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances.

[BibT_eX]

[DOI]

Jan van den Brand

Yang P. Liu

Thatchaphol Saranurak

Di Wang

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Private Non-smooth ERM and SCO in Subquadratic Steps.

[BibT_eX]

[DOI]

Janardhan Kulkarni

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Numerical Composition of Differential Privacy.

[BibT_eX]

[DOI]

Sivakanth Gopi

Lukas Wutschitz

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Fast and Memory Efficient Differentially Private-SGD via JL Projections.

[BibT_eX]

[DOI]

Uthaipon Tantipongpipat

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Structured Logconcave Sampling with a Restricted Gaussian Oracle.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Introduction to the Special Issue on SODA'18.

[BibT_eX]

[DOI]

Marcin Pilipczuk

David P. Woodruff

ACM Trans. Algorithms, 2020

Reducing Isotropy and Volume to KLS: An O(n3ψ2) Volume Algorithm.

[BibT_eX]

[DOI]

CoRR, 2020

Composite Logconcave Sampling with a Restricted Gaussian Oracle.

[BibT_eX]

[DOI]

CoRR, 2020

Network size and weights size for memorization with two-layers neural networks.

[BibT_eX]

[DOI]

CoRR, 2020

Strong self-concordance and sampling.

[BibT_eX]

[DOI]

Aditi Laddha

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

An improved cutting plane method for convex optimization, convex-concave games, and its applications.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Positive semidefinite programming: mixed, parallel, and width-independent.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Solving tall dense linear programs in nearly linear time.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Differentially Private Release of Synthetic Graphs.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Computing Circle Packing Representations of Planar Graphs.

[BibT_eX]

[DOI]

Sally Dong

Kent Quanrud

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Chasing Nested Convex Bodies Nearly Optimally.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Acceleration with a Ball Optimization Oracle.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Network size and size of the weights in memorization with two-layers neural networks.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Convex Optimization and Dynamic Data Structure (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

A Faster Interior Point Method for Semidefinite Programming.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

Di Wang

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

An $\widetilde\mathcalO(m/\varepsilon^3.5)$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints.

[BibT_eX]

[DOI]

Swati Padmanabhan

Proceedings of the Conference on Learning Theory, 2020

Leverage Score Sampling for Faster Accelerated Regression and ERM.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 2020

2019

Optimal Convergence Rates for Convex Distributed Optimization in Networks.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2019

Solving Linear Programs with Sqrt(rank) Linear System Solves.

[BibT_eX]

[DOI]

CoRR, 2019

An Õ(m/ε3.5)-Cost Algorithm for Semidefinite Programs with Diagonal Constraints.

[BibT_eX]

[DOI]

Swati Padmanabhan

CoRR, 2019

Competitively chasing convex bodies.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

A Nearly-Linear Bound for Chasing Nested Convex Bodies.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

The Randomized Midpoint Method for Log-Concave Sampling.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Complexity of Highly Parallel Non-Smooth Convex Optimization.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Adversarial examples from computational constraints.

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

Faster Matroid Intersection.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Solving Empirical Risk Minimization in the Current Matrix Multiplication Time.

[BibT_eX]

[DOI]

Qiuyi Zhang

Proceedings of the Conference on Learning Theory, 2019

Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-th Derivatives.

[BibT_eX]

[DOI]

Alexander V. Gasnikov

Pavel E. Dvurechensky

Eduard Gorbunov

Evgeniya A. Vorontsova

Proceedings of the Conference on Learning Theory, 2019

A near-optimal algorithm for approximating the John Ellipsoid.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

Near-optimal method for highly smooth convex optimization.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time.

[BibT_eX]

[DOI]

He Sun

SIAM J. Comput., 2018

Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities.

[BibT_eX]

[DOI]

CoRR, 2018

Adversarial Examples from Cryptographic Pseudo-Random Generators.

[BibT_eX]

[DOI]

CoRR, 2018

Chasing Nested Convex Bodies Nearly Optimally.

[BibT_eX]

[DOI]

CoRR, 2018

The Kannan-Lovász-Simonovits Conjecture.

[BibT_eX]

[DOI]

CoRR, 2018

Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Convergence rate of riemannian Hamiltonian Monte Carlo and faster polytope volume computation.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The Paulsen problem, continuous operator scaling, and smoothed analysis.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

A matrix expander Chernoff bound.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

k-server via multiscale entropic regularization.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

An homotopy method for lp regression provably beyond self-concordance and in input-sparsity time.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Optimal Algorithms for Non-Smooth Distributed Optimization in Networks.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Efficient Convex Optimization with Membership Oracles.

[BibT_eX]

[DOI]

Proceedings of the Conference On Learning Theory, 2018

2017

Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile.

[BibT_eX]

[DOI]

Tsz Chiu Kwok

Lap Chi Lau

SIAM J. Comput., 2017

Single Pass Spectral Sparsification in Dynamic Streams.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

An SDP-based algorithm for linear-sized spectral sparsification.

[BibT_eX]

[DOI]

He Sun

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Subquadratic submodular function minimization.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Sam Chiu-wai Wong

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks.

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Machine Learning, 2017

Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion.

[BibT_eX]

[DOI]

Santosh Srinivas Vempala

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Landmark-Matching Transformation with Large Deformation Via n-dimensional Quasi-conformal Maps.

[BibT_eX]

[DOI]

Ka Chun Lam

Lok Ming Lui

J. Sci. Comput., 2016

Sparsified Cholesky and multigrid solvers for connection laplacians.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Geometric median in nearly linear time.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver.

[BibT_eX]

[DOI]

Zeyuan Allen Zhu

Lorenzo Orecchia

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Black-box Optimization with a Politician.

[BibT_eX]

[DOI]

Sébastien Bubeck

Proceedings of the 33nd International Conference on Machine Learning, 2016

2015

Sparsified Cholesky Solvers for SDD linear systems.

[BibT_eX]

[DOI]

Richard Peng

Daniel A. Spielman

CoRR, 2015

A geometric alternative to Nesterov's accelerated gradient descent.

[BibT_eX]

[DOI]

Sébastien Bubeck

Mohit Singh

CoRR, 2015

Uniform Sampling for Matrix Approximation.

[BibT_eX]

[DOI]

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization.

[BibT_eX]

[DOI]

Sam Chiu-wai Wong

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Efficient Inverse Maintenance and Faster Algorithms for Linear Programming.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Large Deformation Registration via n-dimensional Quasi-conformal Maps.

[BibT_eX]

[DOI]

Ka Chun Lam

Lok Ming Lui

CoRR, 2014

Probabilistic Spectral Sparsification In Sublinear Time.

[BibT_eX]

[DOI]

CoRR, 2014

An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Following the Path of Least Resistance : An Õ(m sqrt(n)) Algorithm for the Minimum Cost Flow Problem.

[BibT_eX]

[DOI]

CoRR, 2013

Matching the Universal Barrier Without Paying the Costs : Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves.

[BibT_eX]

[DOI]

CoRR, 2013

A new approach to computing maximum flows using electrical flows.

[BibT_eX]

[DOI]

Satish Rao

Nikhil Srivastava

Proceedings of the Symposium on Theory of Computing Conference, 2013

Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems.

[BibT_eX]

[DOI]