1.5k citations · 1.6k across the 23 of their papers we have counts for
29 papers
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…
Quasi-Self-Concordant Optimization with Lewis Weights
Alina Ene, Ta Duy Nguyen, Adrian Vladu
In this paper, we study the problem for a quasi-self-concordant function , where are $…
Adaptive Sparsification for Linear Programming
Étienne Objois, Adrian Vladu
We introduce a generic framework for solving linear programs (LPs) with many constraints via adaptive sparsification. Our approach provides a principled generalization…
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…
Quantized Distributed Training of Large Models with Convergence Guarantees
Ilia Markov, Adrian Vladu, Qi Guo +1
Communication-reduction techniques are a popular way to improve scalability in data-parallel training of deep neural networks (DNNs). The recent emergence of large language models…
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…
CrAM: A Compression-Aware Minimizer
Alexandra Peste, Adrian Vladu, Eldar Kurtic +2
Deep neural networks (DNNs) often have to be compressed, via pruning and/or quantization, before they can be deployed in practical settings. In this work we propose a new compressi…
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…
AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks
Alexandra Peste, Eugenia Iofinova, Adrian Vladu +1
The increasing computational requirements of deep neural networks (DNNs) have led to significant interest in obtaining DNN models that are sparse, yet accurate. Recent work has inv…
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…
Projection-Free Bandit Optimization with Privacy Guarantees
Alina Ene, Huy L. Nguyen, Adrian Vladu
We design differentially private algorithms for the bandit convex optimization problem in the projection-free setting. This setting is important whenever the decision set has a com…
Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities
Alina Ene, Huy L. Nguyen, Adrian Vladu
We provide new adaptive first-order methods for constrained convex optimization. Our main algorithms AdaACSA and AdaAGD+ are accelerated methods, which are universal in the sense t…
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…
Towards Deep Learning Models Resistant to Adversarial Attacks
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt +2
Recent work has demonstrated that deep neural networks are vulnerable to adversarial examples---inputs that are almost indistinguishable from natural data and yet classified incorr…
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…