1.5k citations · 1.6k across the 23 of their papers we have counts for
20 papers · 1 filter
Solving Positive Linear Programs with Differential Privacy
Alina Ene, Huy Le Nguyen, Ta Duy Nguyen +1
We study differentially private approximation algorithms for positive linear programs (LPs with nonnegative coefficients and variables), focusing on the fundamental families of pac…
Improved Regression via Iteratively Reweighted Least Squares
Alina Ene, Ta Duy Nguyen, Adrian Vladu
We introduce fast algorithms for solving regression problems using the iteratively reweighted least squares (IRLS) method. Our approach achieves state-of-the-art iterati…
Fixed-Parameter Tractable Submodular Maximization over a Matroid
Shamisa Nematollahi, Adrian Vladu, Junyao Zhao
In this paper, we design fixed-parameter tractable (FPT) algorithms for (non-monotone) submodular maximization subject to a matroid constraint, where the matroid rank is treate…
Solving Linear Programs with Differential Privacy
Alina Ene, Huy Le Nguyen, Ta Duy Nguyen +1
We study the problem of solving linear programs of the form , with differential privacy. For homogeneous LPs , we give an efficient -differentially…
Breaking the Barrier of Self-Concordant Barriers: Faster Interior Point Methods for M-Matrices
Adrian Vladu
We study two fundamental optimization problems: (1) scaling a symmetric positive definite matrix by a positive diagonal matrix so that the resulting matrix has row and column sums…
Approximating Norms of Non-Negative Matrices in Nearly-Linear Time
Étienne Objois, Adrian Vladu
We provide the first nearly-linear time algorithm for approximating -norms of non-negative matrices, for . Our algorithm returns a $(1-\var…
Interior Point Methods with a Gradient Oracle
Adrian Vladu
We provide an interior point method based on quasi-Newton iterations, which only requires first-order access to a strongly self-concordant barrier function. To achieve this, we ext…
Discrepancy Minimization via Regularization
Lucas Pesenti, Adrian Vladu
We introduce a new algorithmic framework for discrepancy minimization based on regularization. We demonstrate how varying the regularizer allows us to re-interpret several breakthr…
Faster Sparse Minimum Cost Flow by Electrical Flow Localization
Kyriakos Axiotis, Aleksander Mądry, Adrian Vladu
We give an time algorithm for minimum cost flow with capacities bounded by and costs bounded by . For sparse graphs with genera…
Decomposable Submodular Function Minimization via Maximum Flow
Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee +2
This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide impro…
Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs
Kyriakos Axiotis, Aleksander Mądry, Adrian Vladu
We present an -time algorithm for solving the minimum cost flow problem in graphs with unit capacity, where is the maximum absolute value of any edge weight…
Improved Convergence for and Regression via Iteratively Reweighted Least Squares
Alina Ene, Adrian Vladu
The iteratively reweighted least squares method (IRLS) is a popular technique used in practice for solving regression problems. Various versions of this method have been proposed,…
A Parallel Double Greedy Algorithm for Submodular Maximization
Alina Ene, Huy L. Nguyen, Adrian Vladu
We study parallel algorithms for the problem of maximizing a non-negative submodular function. Our main result is an algorithm that achieves a nearly-optimal approximation…
Submodular Maximization with Matroid and Packing Constraints in Parallel
Alina Ene, Huy L. Nguyen, Adrian Vladu
We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of…
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods
Michael B. Cohen, Aleksander Madry, Dimitris Tsipras +1
In this paper, we study matrix scaling and balancing, which are fundamental problems in scientific computing, with a long line of work on them that dates back to the 1960s. We prov…
Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs
Michael B. Cohen, Jonathan Kelner, John Peebles +4
In this paper we introduce a notion of spectral approximation for directed graphs. While there are many potential ways one might define approximation for directed graphs, most of t…
Multidimensional Binary Search for Contextual Decision-Making
Ilan Lobel, Renato Paes Leme, Adrian Vladu
We consider a multidimensional search problem that is motivated by questions in contextual decision-making, such as dynamic pricing and personalized medicine. Nature selects a stat…
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More
Michael B. Cohen, Jon Kelner, John Peebles +3
In this paper, we provide faster algorithms for computing various fundamental quantities associated with random walks on a directed graph, including the stationary distribution, pe…
Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Time
Michael B. Cohen, Aleksander Madry, Piotr Sankowski +1
In this paper, we study a set of combinatorial optimization problems on weighted graphs: the shortest path problem with negative weights, the weighted perfect bipartite matching pr…
Tight Bounds for Approximate Carathéodory and Beyond
Vahab Mirrokni, Renato Paes Leme, Adrian Vladu +1
We give a deterministic nearly-linear time algorithm for approximating any point inside a convex polytope with a sparse convex combination of the polytope's vertices. Our result pr…