Posts by Collection

articles

EPEM: Efficient Parameter Estimation for Multiple Class Monotone Missing Data Permalink

Information Sciences Journal (IF: 6.795), 2021

Thu Nguyen, Duy H. M. Nguyen, Huy Nguyen, Binh T. Nguyen, Bruce A. Wade Abstract: The problem of monotone missing data has been broadly studied during the last two decades and has many applications in different fields such as bioinformatics or statistics. Commonly used imputation techniques require multiple iterations through the data before yielding convergence. Moreover, those approaches may introduce extra noises and biases to the subsequent modeling. In this work, we derive exact formulas and propose a novel algorithm to compute the maximum likelihood estimators (MLEs) of a multiple class, monotone missing dataset when all the covariance matrices of all categories are assumed to be equal, namely EPEM. We then illustrate an application of our proposed methods in Linear Discriminant Analysis (LDA). As the computation is exact, our EPEM algorithm does not require multiple iterations through the data as other imputation approaches, thus promising to handle much less time-consuming than other methods. This effectiveness was validated by empirical results when EPEM reduced the error rates significantly and required a short computation time compared to several imputation-based approaches. We also release all codes and data of our experiments in one GitHub repository to contribute to the research community related to this problem. Read more

On Robust Optimal Transport: Computational Complexity and Barycenter Computation Permalink

35th Conference on Neural Information Processing Systems (NeurIPS), 2021

Huy Nguyen*, Khang Le*, Quang Minh Nguyen, Tung Pham, Hung Bui, Nhat Ho Abstract: We consider two robust versions of optimal transport, named Robust Semi-constrained Optimal Transport (RSOT) and Robust Unconstrained Optimal Transport (ROT), formulated by relaxing the marginal constraints with Kullback-Leibler divergence. For both problems in the discrete settings, we propose Sinkhorn-based algorithms that produce ε-approximations of RSOT and ROT in O˜(n2ε) time, where n is the number of supports of the probability distributions. Furthermore, to reduce the dependency of the complexity of the Sinkhorn-based algorithms on n, we apply Nyström method to approximate the kernel matrix in both RSOT and ROT by a matrix of rank r before passing it to these Sinkhorn-based algorithms. We demonstrate that these new algorithms have O˜(nr2+nrε) runtime to obtain the RSOT and ROT ε-approximations. Finally, we consider a barycenter problem based on RSOT, named Robust Semi-Constrained Barycenter problem (RSBP), and develop a robust iterative Bregman projection algorithm, called Normalized-RobustIBP algorithm, to solve the RSBP in the discrete settings of probability distributions. We show that an ε-approximated solution of the RSBP can be achieved in O˜(mn2ε) time using Normalized-RobustIBP algorithm when m=2, which is better than the previous complexity O˜(mn2ε2) of IBP algorithm for approximating the Wasserstein barycenter. Extensive experiments confirm our theoretical results. Read more

On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity Permalink

25th International Conference on Artificial Intelligence and Statistics (AISTATS), 2022

Huy Nguyen*, Khang Le*, Khai Nguyen, Tung Pham, Nhat Ho Abstract: We study the multi-marginal partial optimal transport (POT) problem between m discrete (unbalanced) measures with at most n supports. We first prove that we can obtain two equivalence forms of the multimarginal POT problem in terms of the multimarginal optimal transport problem via novel extensions of cost tensor. The first equivalence form is derived under the assumptions that the total masses of each measure are sufficiently close while the second equivalence form does not require any conditions on these masses but at the price of more sophisticated extended cost tensor. Our proof techniques for obtaining these equivalence forms rely on novel procedures of moving mass in graph theory to push transportation plan into appropriate regions. Finally, based on the equivalence forms, we develop optimization algorithm, named ApproxMPOT algorithm, that builds upon the Sinkhorn algorithm for solving the entropic regularized multimarginal optimal transport. We demonstrate that the ApproxMPOT algorithm can approximate the optimal value of multimarginal POT problem with a computational complexity upper bound of the order Oe(m3(n + 1)m/ε2) where ε > 0 stands for the desired tolerance. Read more

Entropic Gromov-Wasserstein between Gaussian Distributions Permalink

39th International Conference on Machine Learning (ICML), 2022

Huy Nguyen*, Khang Le*, Dung Le*, Dat Do, Tung Pham, Nhat Ho Abstract: We study the entropic Gromov-Wasserstein and its unbalanced version between (unbalanced) Gaussian distributions with different dimensions. When the metric is the inner product, which we refer to as inner product Gromov-Wasserstein (IGW), we demonstrate that the optimal transportation plans of entropic IGW and its unbalanced variant are (unbalanced) Gaussian distributions. Via an application of von Neumann’s trace inequality, we obtain closed-form expressions for the entropic IGW between these Gaussian distributions. Finally, we consider an entropic inner product Gromov-Wasserstein barycenter of multiple Gaussian distributions. We prove that the barycenter is Gaussian distribution when the entropic regularization parameter is small. We further derive closed-form expressions for the covariance matrix of the barycenter. Read more

Hierarchical Sliced Wasserstein Distance Permalink

11th International Conference on Learning Representations (ICLR), 2023

Khai Nguyen, Tongzheng Ren, Huy Nguyen, Litu Rout, Tan Nguyen, Nhat Ho Abstract: Sliced Wasserstein (SW) distance has been widely used in different application scenarios since it can be scaled to a large number of supports without suffering from the curse of dimensionality. The value of sliced Wasserstein distance is the average of transportation cost between one-dimensional representations (projections) of original measures that are obtained by Radon Transform (RT). Despite its efficiency in the number of supports, estimating the sliced Wasserstein requires a relatively large number of projections in high-dimensional settings. Therefore, for applications where the number of supports is relatively small compared with the dimension, e.g., several deep learning applications where the mini-batch approaches are utilized, the complexities from matrix multiplication of Radon Transform become the main computational bottleneck. To address this issue, we propose to derive projections by linearly and randomly combining a smaller number of projections which are named bottleneck projections. We explain the usage of these projections by introducing Hierarchical Radon Transform (HRT) which is constructed by applying Radon Transform variants recursively. We then formulate the approach into a new metric between measures, named Hierarchical Sliced Wasserstein (HSW) distance. By proving the injectivity of HRT, we derive the metricity of HSW. Moreover, we investigate the theoretical properties of HSW including its connection to SW variants and its computational and sample complexities. Finally, we compare the computational cost and generative quality of HSW with the conventional SW on the task of deep generative modeling using various benchmark datasets including CIFAR10, CelebA, and Tiny ImageNet. Read more

Towards Convergence Rates for Parameter Estimation in Gaussian-gated Mixture of Experts Permalink

Under review, 2023

Huy Nguyen*, TrungTin Nguyen*, Khai Nguyen, Nhat Ho Abstract: Originally introduced as a neural network for ensemble learning, mixture of experts (MoE) has recently become a fundamental building block of highly successful modern deep neural networks for heterogeneous data analysis in several applications, including those in machine learning, statistics, bioinformatics, economics, and medicine. Despite its popularity in practice, a satisfactory level of understanding of the convergence behavior of Gaussian-gated MoE parameter estimation is far from complete. The underlying reason for this challenge is the inclusion of covariates in the Gaussian gating and expert networks, which leads to their intrinsically complex interactions via partial differential equations with respect to their parameters. We address these issues by designing novel Voronoi loss functions to accurately capture heterogeneity in the maximum likelihood estimator (MLE) for resolving parameter estimation in these models. Our results reveal distinct behaviors of the MLE under two settings: the first setting is when all the location parameters in the Gaussian gating are non-zeros while the second setting is when there exists at least one zero-valued location parameter. Notably, these behaviors can be characterized by the solvability of two different systems of polynomial equations. Finally, we conduct a simulation study to verify our theoretical results. Read more

Minimax Optimal Rate for Parameter Estimation in Multivariate Deviated Models Permalink

37th Conference on Neural Information Processing Systems (NeurIPS), 2023

Dat Do*, Huy Nguyen*, Khai Nguyen, Nhat Ho Abstract: Read more

Demystifying Softmax Gating Function in Gaussian Mixture of Experts Permalink

37th Conference on Neural Information Processing Systems (NeurIPS), 2023

Huy Nguyen, TrungTin Nguyen, Nhat Ho Abstract: Understanding parameter estimation of softmax gating Gaussian mixture of experts has remained a long-standing open problem in the literature. It is mainly due to three fundamental theoretical challenges associated with the softmax gating: (i) the identifiability only up to the translation of the parameters; (ii) the intrinsic interaction via partial differential equation between the softmax gating and the expert functions in Gaussian distribution; (iii) the complex dependence between the numerator and denominator of the conditional density of softmax gating Gaussian mixture of experts. We resolve these challenges by proposing novel Vononoi loss functions among parameters and establishing the convergence rates of the maximum likelihood estimator (MLE) for solving parameter estimation in these models. When the number of experts is unknown and over-specified, our findings show a connection between the rate of MLE and a solvability problem of a system of polynomial equations. Read more

Statistical Perspective of Top-K Sparse Softmax Gating Mixture of Experts Permalink

Under review, 2023

Huy Nguyen, Pedram Akbarian, Fanqi Yan, Nhat Ho Abstract: Top-K sparse softmax gating mixture of experts has been widely used for scaling up massive deep-learning architectures without increasing the computational cost. Despite its popularity in real-world applications, the theoretical understanding of that gating function has remained an open problem. The main challenge comes from the structure of the top-K sparse softmax gating function, which partitions the input space into multiple regions with distinct behaviors. By focusing on a Gaussian mixture of experts, we establish theoretical results on the effects of the top-K sparse softmax gating function on both density and parameter estimations. Our results hinge upon defining novel loss functions among parameters to capture different behaviors of the input regions. When the true number of experts k∗ is known, we demonstrate that the convergence rates of density and parameter estimations are both parametric on the sample size. However, when k∗ becomes unknown and the true model is over-specified by a Gaussian mixture of k experts where k > k∗, our findings suggest that the number of experts selected from the top-K sparse softmax gating function must exceed the total cardinality of a certain number of Voronoi cells associated with the true parameters to guarantee the convergence of the density estimation. Moreover, while the density estimation rate remains parametric under this setting, the parameter estimation rates become substantially slow due to an intrinsic interaction between the softmax gating and expert functions. Read more

A General Theory for Softmax Gating Multinomial Logistic Mixture of Experts Permalink

Under review, 2023

Huy Nguyen, Pedram Akbarian, TrungTin Nguyen, Nhat Ho Abstract: Mixture-of-experts (MoE) model incorporates the power of multiple submodels via gating functions to achieve greater performance in numerous regression and classification applications. From a theoretical perspective, while there have been previous attempts to comprehend the behavior of that model under the regression settings through the convergence analysis of maximum likelihood estimation in the Gaussian MoE model, such analysis under the setting of a classification problem has remained missing in the literature. We close this gap by establishing the convergence rates of density estimation and parameter estimation in the softmax gating multinomial logistic MoE model. Notably, when part of the expert parameters vanish, these rates are shown to be slower than polynomial rates owing to an inherent interaction between the softmax gating and expert functions via partial differential equations. To address this issue, we propose using a novel class of modified softmax gating functions which transform the input value before delivering them to the gating functions. As a result, the previous interaction disappears and the parameter estimation rates are significantly improved. Read more

Fast Approximation of the Generalized Sliced-Wasserstein Distance Permalink

IEEE International Conference on Acoustics, Speech and Signal Processing, 2024

Dung Le*, Huy Nguyen*, Khai Nguyen*, Trang Nguyen*, Nhat Ho Abstract: Generalized sliced Wasserstein distance is a variant of sliced Wasserstein distance that exploits the power of non-linear projection through a given defining function to better capture the complex structures of the probability distributions. Similar to sliced Wasserstein distance, generalized sliced Wasserstein is defined as an expectation over random projections which can be approximated by the Monte Carlo method. However, the complexity of that approximation can be expensive in high-dimensional settings. To that end, we propose to form deterministic and fast approximations of the generalized sliced Wasserstein distance by using the concentration of random projections when the defining functions are polynomial function, circular function, and neural network type function. Our approximations hinge upon an important result that one-dimensional projections of a high-dimensional random vector are approximately Gaussian. Read more

expressions

Post-Structuralism, Restructured: Re-presentations of Deleuze and Guattari’s A Thousand Plateaus

This was my final project for an Information Studies class I took back in 2006 at UT-Austin. Our assignment was to transform information from one form to another, and I chose to perform this analysis of Deleuze and Guattari’s A Thousand Plateaus. I scanned and OCRed the entire book and did a visual frequency representation of certain words. Read more

IPoXP: Internet Protocol over Xylophone Players

We introduce IP over Xylophone Players (IPoXP), a novel Internet protocol between two computers using xylophone-based Arduino interfaces. In our implementation, human operators are situated within the lowest layer of the network, transmitting data between computers by striking designated keys. We discuss how IPoXP inverts the traditional mode of human-computer interaction, with a computer using the human as an interface to communicate with another computer Read more

0 (the game)

One of the many forks of the popular game 1024 by Veewo Studio (which is conceptually similar to Threes by Asher Vollmer). Try to combine all the 0 tiles until they add up to 1. Read more

Apparent Things

A Twitter bot powered by tweets proclaiming that something ‘is apparently a thing.’ Read more

robots.txt.php

An algorithmically-generated robots.txt, which disallows all bots with one exception: the bot requesting the file is allowed full access. Read more

dystopedia

A Markov chain Twitter bot trained on titles of Wikipedia articles that have been deleted. Read more

AcademicPages

AcademicPages is a ready-to-fork GitHub Pages template for academic personal websites, based on structured data in markdown files. I created it for this website, then released it so others can make their own, which are hosted for free by GitHub. Over 500 people have! Read more

IndentationError

Published: November 06, 2019

An avant-garde poem about Python Read more

talks

A Communicative Ethnography of Argumentative Strategies in a Wikipedian Content Dispute

Exploring New Media Worlds, 2008

Minh Le

Posts by Collection

articles

expressions

talks

teaching