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...
share
research
∙
06/02/2023
An Empirical Study on Challenging Math Problem Solving with GPT-4
Employing Large Language Models (LLMs) to address mathematical problems ...
research
∙
05/04/2023
Automatic Prompt Optimization with "Gradient Descent" and Beam Search
Large Language Models (LLMs) have shown impressive performance as genera...
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 ...
research
∙
03/22/2023
Sparks of Artificial General Intelligence: Early experiments with GPT-4
Artificial intelligence (AI) researchers have been developing and refini...
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...
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...
research
∙
01/01/2023
ReSQueing Parallel and Private Stochastic Convex Optimization
We introduce a new tool for stochastic convex optimization (SCO): a Rewe...
research
∙
12/14/2022
Learning threshold neurons via the "edge of stability"
Existing analyses of neural network training often operate under the unr...
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...
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...
research
∙
08/24/2022
A Slightly Improved Bound for the KLS Constant
We refine the recent breakthrough technique of Klartag and Lehec to obta...
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...
research
∙
07/18/2022
Private Convex Optimization in General Norms
We propose a new framework for differentially private optimization of co...
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...
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...
research
∙
03/01/2022
Private Convex Optimization via Exponential Mechanism
In this paper, we study private optimization problems for non-smooth con...
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...
research
∙
12/01/2021
Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers
We make several advances broadly related to the maintenance of electrica...
research
∙
10/29/2021
Computing Lewis Weights to High Precision
We present an algorithm for computing approximate ℓ_p Lewis weights to h...
research
∙
10/13/2021
Differentially Private Fine-tuning of Language Models
We give simpler, sparser, and faster algorithms for differentially priva...
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...
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...
research
∙
06/05/2021
Numerical Composition of Differential Privacy
We give a fast algorithm to optimally compose privacy guarantees of diff...
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...
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...
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...
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...
research
∙
10/07/2020
Structured Logconcave Sampling with a Restricted Gaussian Oracle
We give algorithms for sampling several structured logconcave families t...
research
∙
09/21/2020
A Faster Interior Point Method for Semidefinite Programming
Semidefinite programs (SDPs) are a fundamental class of optimization pro...
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...
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...
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) ∝...
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...
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...
research
∙
03/18/2020
Acceleration with a Ball Optimization Oracle
Consider an oracle which takes a point x and returns the minimizer of a ...
research
∙
02/12/2020
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
We give the first approximation algorithm for mixed packing and covering...
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...
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...
research
∙
11/25/2019
Faster Matroid Intersection
In this paper we consider the classic matroid intersection problem: give...
research
∙
11/13/2019
Strong Self-Concordance and Sampling
Motivated by the Dikin walk, we develop aspects of an interior-point the...
research
∙
11/01/2019
Computing Circle Packing Representations of Planar Graphs
The Circle Packing Theorem states that every planar graph can be represe...
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 ...
research
∙
09/12/2019
The Randomized Midpoint Method for Log-Concave Sampling
Sampling from log-concave distributions is a well researched problem tha...
research
∙
06/25/2019
Complexity of Highly Parallel Non-Smooth Convex Optimization
A landmark result of non-smooth convex optimization is that gradient des...
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...
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 ...
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...
research
∙
12/15/2018
Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
Sampling logconcave functions arising in statistics and machine learning...
research
∙
11/15/2018