b'Yin Tat Lee'

research

∙ 09/11/2023

Textbooks Are All You Need II: phi-1.5 technical report

We continue the investigation into the power of smaller Transformer-base...

0 Yuanzhi Li, et al. ∙

research

∙ 06/02/2023

An Empirical Study on Challenging Math Problem Solving with GPT-4

Employing Large Language Models (LLMs) to address mathematical problems ...

0 Yiran Wu, et al. ∙

research

∙ 05/04/2023

Automatic Prompt Optimization with "Gradient Descent" and Beam Search

Large Language Models (LLMs) have shown impressive performance as genera...

0 Reid Pryzant, et al. ∙

research

∙ 04/07/2023

Convex Minimization with Integer Minima in O(n^4) Time

Given a convex function f on ℝ^n with an integer minimizer, we show how ...

0 Haotian Jiang, et al. ∙

research

∙ 03/22/2023

Sparks of Artificial General Intelligence: Early experiments with GPT-4

Artificial intelligence (AI) researchers have been developing and refini...

6 Sébastien Bubeck, et al. ∙

research

∙ 02/21/2023

kNN-Adapter: Efficient Domain Adaptation for Black-Box Language Models

Fine-tuning a language model on a new domain is standard practice for do...

14 Yangsibo Huang, et al. ∙

research

∙ 02/13/2023

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

The development of efficient sampling algorithms catering to non-Euclide...

0 Sivakanth Gopi, et al. ∙

research

∙ 01/01/2023

ReSQueing Parallel and Private Stochastic Convex Optimization

We introduce a new tool for stochastic convex optimization (SCO): a Rewe...

0 Yair Carmon, et al. ∙

research

∙ 12/14/2022

Learning threshold neurons via the "edge of stability"

Existing analyses of neural network training often operate under the unr...

0 Kwangjun Ahn, et al. ∙

research

∙ 11/21/2022

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method

The simplex method for linear programming is known to be highly efficien...

0 Sophie Huiberts, et al. ∙

research

∙ 10/13/2022

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

We study the convergence rate of discretized Riemannian Hamiltonian Mont...

0 Yunbum Kook, et al. ∙

research

∙ 08/24/2022

A Slightly Improved Bound for the KLS Constant

We refine the recent breakthrough technique of Klartag and Lehec to obta...

0 Arun Jambulapati, et al. ∙

research

∙ 08/07/2022

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

Many fundamental problems in machine learning can be formulated by the c...

0 Sally Dong, et al. ∙

research

∙ 07/18/2022

Private Convex Optimization in General Norms

We propose a new framework for differentially private optimization of co...

0 Sivakanth Gopi, et al. ∙

research

∙ 07/01/2022

When Does Differentially Private Learning Not Suffer in High Dimensions?

Large pretrained models can be privately fine-tuned to achieve performan...

0 Xuechen Li, et al. ∙

research

∙ 05/03/2022

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

We present a nearly-linear time algorithm for finding a minimum-cost flo...

0 Sally Dong, et al. ∙

research

∙ 03/01/2022

Private Convex Optimization via Exponential Mechanism

In this paper, we study private optimization problems for non-smooth con...

0 Sivakanth Gopi, et al. ∙

research

∙ 02/03/2022

Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space

We demonstrate for the first time that ill-conditioned, non-smooth, cons...

0 Yunbum Kook, et al. ∙

research

∙ 12/01/2021

Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers

We make several advances broadly related to the maintenance of electrica...

0 Jan van den Brand, et al. ∙

research

∙ 10/29/2021

Computing Lewis Weights to High Precision

We present an algorithm for computing approximate ℓ_p Lewis weights to h...

0 Maryam Fazel, et al. ∙

research

∙ 10/13/2021

Differentially Private Fine-tuning of Language Models

We give simpler, sparser, and faster algorithms for differentially priva...

0 Da Yu, et al. ∙

research

∙ 08/10/2021

Tutorial on the Robust Interior Point Method

We give a short, self-contained proof of the interior point method and i...

0 Yin Tat Lee, et al. ∙

research

∙ 06/10/2021

Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions

We give lower bounds on the performance of two of the most popular sampl...

0 Yin Tat Lee, et al. ∙

research

∙ 06/05/2021

Numerical Composition of Differential Privacy

We give a fast algorithm to optimally compose privacy guarantees of diff...

0 Sivakanth Gopi, et al. ∙

research

∙ 03/29/2021

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

We study the differentially private Empirical Risk Minimization (ERM) an...

0 Janardhan Kulkarni, et al. ∙

research

∙ 02/05/2021

Fast and Memory Efficient Differentially Private-SGD via JL Projections

Differentially Private-SGD (DP-SGD) of Abadi et al. (2016) and its varia...

0 Zhiqi Bu, et al. ∙

research

∙ 01/14/2021

Minimum Cost Flows, MDPs, and ℓ_1-Regression in Nearly Linear Time for Dense Instances

In this paper we provide new randomized algorithms with improved runtime...

0 Jan van den Brand, et al. ∙

research

∙ 11/10/2020

A Nearly-Linear 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...

0 Sally Dong, et al. ∙

research

∙ 10/07/2020

Structured Logconcave Sampling with a Restricted Gaussian Oracle

We give algorithms for sampling several structured logconcave families t...

0 Yin Tat Lee, et al. ∙

research

∙ 09/21/2020

A Faster Interior Point Method for Semidefinite Programming

Semidefinite programs (SDPs) are a fundamental class of optimization pro...

0 Haotian Jiang, et al. ∙

research

∙ 09/03/2020

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

We present an Õ(m+n^1.5)-time randomized algorithm for maximum cardinali...

0 Jan van den Brand, et al. ∙

research

∙ 08/05/2020

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...

0 He Jia, et al. ∙

research

∙ 06/10/2020

Composite Logconcave Sampling with a Restricted Gaussian Oracle

We consider sampling from composite densities on ℝ^d of the form dπ(x) ∝...

0 Ruoqi Shen, et al. ∙

research

∙ 06/04/2020

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

In 1988, Eric B. Baum showed that two-layers neural networks with thresh...

12 Sébastien Bubeck, et al. ∙

research

∙ 04/08/2020

An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications

Given a separation oracle for a convex set K ⊂R^n that is contained in a...

0 Haotian Jiang, et al. ∙

research

∙ 03/18/2020

Acceleration with a Ball Optimization Oracle

Consider an oracle which takes a point x and returns the minimizer of a ...

0 Yair Carmon, et al. ∙

research

∙ 02/12/2020

Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent

We give the first approximation algorithm for mixed packing and covering...

0 Arun Jambulapati, et al. ∙

research

∙ 02/10/2020

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...

0 Yin Tat Lee, et al. ∙

research

∙ 02/06/2020

Solving Tall Dense Linear Programs in Nearly Linear Time

In this paper we provide an Õ(nd+d^3) time randomized algorithm for solv...

0 Jan van den Brand, et al. ∙

research

∙ 11/25/2019

Faster Matroid Intersection

In this paper we consider the classic matroid intersection problem: give...

0 Deeparnab Chakrabarty, et al. ∙

research

∙ 11/13/2019

Strong Self-Concordance and Sampling

Motivated by the Dikin walk, we develop aspects of an interior-point the...

0 Aditi Laddha, et al. ∙

research

∙ 11/01/2019

Computing Circle Packing Representations of Planar Graphs

The Circle Packing Theorem states that every planar graph can be represe...

0 Sally Dong, et al. ∙

research

∙ 10/17/2019

Solving Linear Programs with Sqrt(rank) Linear System Solves

We present an algorithm that given a linear program with n variables, m ...

0 Yin Tat Lee, et al. ∙

research

∙ 09/12/2019

The Randomized Midpoint Method for Log-Concave Sampling

Sampling from log-concave distributions is a well researched problem tha...

0 Ruoqi Shen, et al. ∙

research

∙ 06/25/2019

Complexity of Highly Parallel Non-Smooth Convex Optimization

A landmark result of non-smooth convex optimization is that gradient des...

0 Sébastien Bubeck, et al. ∙

research

∙ 05/28/2019

A near-optimal algorithm for approximating the John Ellipsoid

We develop a simple and efficient algorithm for approximating the John E...

0 Michael B. Cohen, et al. ∙

research

∙ 05/11/2019

Solving Empirical Risk Minimization in the Current Matrix Multiplication Time

Many convex problems in machine learning and computer science share the ...

0 Yin Tat Lee, et al. ∙

research

∙ 03/05/2019

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

We study semidefinite programs with diagonal constraints. This problem c...

0 Yin Tat Lee, et al. ∙

research

∙ 12/15/2018

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

Sampling logconcave functions arising in statistics and machine learning...

0 Yin Tat Lee, et al. ∙

research

∙ 11/15/2018

Adversarial Examples from Cryptographic Pseudo-Random Generators

In our recent work (Bubeck, Price, Razenshteyn, arXiv:1805.10204) we arg...

0 Sébastien Bubeck, et al. ∙

Yin Tat Lee

Featured Co-authors