50 citations · 157 across the 42 of their papers we have counts for
54 papers
A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
Alina Ene, Huy L. Nguyen
We give a strongly polynomial time algorithm for submodular function minimization with overall running time time, where is the…
One-Sided Matrix Completion from Ultra-Sparse Samples
Hongyang R. Zhang, Zhenshuo Zhang, Huy L. Nguyen +1
Matrix completion is a classical problem that has received recurring interest across a wide range of fields. In this paper, we revisit this problem in an ultra-sparse sampling regi…
Sample-efficient Multiclass Calibration under Error
Konstantina Bairaktari, Huy L. Nguyen
Calibrating a multiclass predictor, that outputs a distribution over labels, is particularly challenging due to the exponential number of possible prediction values. In this work,…
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…
Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
Hilal Asi, Vitaly Feldman, Jelani Nelson +3
We study the problem of private vector mean estimation in the shuffle model of privacy where users each have a unit vector . We propose a new multi-mes…
Improved Frequency Estimation Algorithms with and without Predictions
Anders Aamand, Justin Y. Chen, Huy Lê Nguyen +2
Estimating frequencies of elements appearing in a data stream is a key task in large-scale data analysis. Popular sketching approaches to this problem (e.g., CountMin and CountSket…
Online and Streaming Algorithms for Constrained -Submodular Maximization
Fabian Spaeh, Alina Ene, Huy L. Nguyen
Constrained -submodular maximization is a general framework that captures many discrete optimization problems such as ad allocation, influence maximization, personalized recomme…
Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tails
Ta Duy Nguyen, Alina Ene, Huy L. Nguyen
In this work, we study the convergence \emph{in high probability} of clipped gradient methods when the noise distribution has heavy tails, ie., with bounded th moments, for some…
High Probability Convergence of Clipped-SGD Under Heavy-tailed Noise
Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene +1
While the convergence behaviors of stochastic gradient methods are well understood \emph{in expectation}, there still exist many gaps in the understanding of their convergence with…
Improved Space Bounds for Learning with Experts
Anders Aamand, Justin Y. Chen, Huy Lê Nguyen +1
We give improved tradeoffs between space and regret for the online learning with expert advice problem over days with experts. Given a space budget of for $δ\in (0,1)…
Identification of Negative Transfers in Multitask Learning Using Surrogate Models
Dongyue Li, Huy L. Nguyen, Hongyang R. Zhang
Multitask learning is widely used in practice to train a low-resource target task by augmenting it with multiple related source tasks. Yet, naively combining all the source tasks w…
High Probability Convergence of Stochastic Gradient Methods
Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen +2
In this work, we describe a generic approach to show convergence with high probability for both stochastic convex and non-convex optimization with sub-Gaussian noise. In previous w…
Streaming Submodular Maximization with Differential Privacy
Anamay Chaturvedi, Huy Lê Nguyen, Thy Nguyen
In this work, we study the problem of privately maximizing a submodular function in the streaming setting. Extensive work has been done on privately maximizing submodular functions…
High Probability Convergence for Accelerated Stochastic Mirror Descent
Alina Ene, Huy L. Nguyen
In this work, we describe a generic approach to show convergence with high probability for stochastic convex optimization. In previous works, either the convergence is only in expe…
Improved Learning-augmented Algorithms for k-means and k-medians Clustering
Thy Nguyen, Anamay Chaturvedi, Huy Lê Nguyen
We consider the problem of clustering in the learning-augmented setting, where we are given a data set in -dimensional Euclidean space, and a label for each data point given by…
META-STORM: Generalized Fully-Adaptive Variance Reduced SGD for Unbounded Functions
Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen +2
We study the application of variance reduction (VR) techniques to general non-convex stochastic optimization problems. In this setting, the recent work STORM [Cutkosky-Orabona '19]…
An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret
Matthew Jones, Huy Lê Nguyen, Thy Nguyen
Recently a multi-agent variant of the classical multi-armed bandit was proposed to tackle fairness issues in online learning. Inspired by a long line of work in social choice and e…
On the Convergence of AdaGrad(Norm) on : Beyond Convexity, Non-Asymptotic Rate and Acceleration
Zijian Liu, Ta Duy Nguyen, Alina Ene +1
Existing analysis of AdaGrad and other adaptive methods for smooth convex optimization is typically for functions with bounded domain diameter. In unconstrained problems, previous…
Fair Range k-center
Huy Lê Nguyen, Thy Nguyen, Matthew Jones
We study the problem of fairness in k-centers clustering on data with disjoint demographic groups. Specifically, this work proposes a variant of fairness which restricts each group…
Improved Group Robustness via Classifier Retraining on Independent Splits
Thien Hang Nguyen, Hongyang R. Zhang, Huy Le Nguyen
Deep neural networks trained by minimizing the average risk can achieve strong average performance. Still, their performance for a subgroup may degrade if the subgroup is underrepr…
Private Frequency Estimation via Projective Geometry
Vitaly Feldman, Jelani Nelson, Huy Lê Nguyen +1
In this work, we propose a new algorithm ProjectiveGeometryResponse (PGR) for locally differentially private (LDP) frequency estimation. For a universe size of and with use…
Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction
Zijian Liu, Ta Duy Nguyen, Alina Ene +1
In this paper, we study the finite-sum convex optimization problem focusing on the general convex case. Recently, the study of variance reduced (VR) methods and their accelerated v…
Locally Private -Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error
Anamay Chaturvedi, Matthew Jones, Huy L. Nguyen
Given a data set of size in -dimensional Euclidean space, the -means problem asks for a set of points (called centers) so that the sum of the -distances be…
Multi-view Audio and Music Classification
Huy Phan, Huy Le Nguyen, Oliver Y. Chén +4
We propose in this work a multi-view learning approach for audio and music classification. Considering four typical low-level representations (i.e. different views) commonly used f…