2025

1. Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors

   Kapilan Balagopalan, Yinan Li, Yao Zhao, Tuan Ngo Nguyen, and Kwang-Sung Jun

   In arxiv

   [Abstract] [Paper]

   The best-arm identification (BAI) problem is one of the most fundamental problems in interactive machine learning, which has two flavors: the fixed-budget setting (FB) and the fixed-confidence setting (FC). For K-armed bandits with the unique best arm, the optimal sample complexities for both settings have been settled down, and they match up to logarithmic factors. This prompts an interesting research question about the generic, potentially structured BAI problems: Is FB harder than FC or the other way around? In this paper, we show that FB is no harder than FC up to logarithmic factors. We do this constructively: we propose a novel algorithm called FC2FB (fixed confidence to fixed budget), which is a meta algorithm that takes in an FC algorithm A and turn it into an FB algorithm. We prove that this FC2FB enjoys a sample complexity that matches, up to logarithmic factors, that of the sample complexity of A. This means that the optimal FC sample complexity is an upper bound of the optimal FB sample complexity up to logarithmic factors. Our result not only reveals a fundamental relationship between FB and FC, but also has a significant implication: FC2FB, combined with existing state-of-the-art FC algorithms, leads to improved sample complexity for a number of FB problems.

2. HAVER: Instance-Dependent Error Bounds for Maximum Mean Estimation and Applications to Q-Learning and Monte Carlo Tree Search

   Tuan Ngo Nguyen, Jay Barrett, and Kwang-Sung Jun

   In Proceedings of the AISTAT 2025

   [Abstract] [Paper]

   We study the problem of estimating the value of the largest mean among distributions via samples from them (rather than estimating which distribution has the largest mean), which arises from various machine learning tasks including Q-learning and Monte Carlo tree search. While there have been a few proposed algorithms, their performance analyses have been limited to their biases rather than a precise error metric. In this paper, we propose a novel algorithm called HAVER (Head AVERaging) and analyze its mean squared error. Our analysis reveals that HAVER has a compelling performance in two respects. First, HAVER estimates the maximum mean as well as the oracle who knows the identity of the best distribution and reports its sample mean. Second, perhaps surprisingly, HAVER exhibits even better rates than this oracle when there are many distributions near the best one. Both of these improvements are the first of their kind in the literature, and we also prove that the naive algorithm that reports the largest empirical mean does not achieve these bounds. Finally, we confirm our theoretical findings via numerical experiments including bandits and Q-learning scenarios where HAVER outperforms baseline methods.

3. Fixing the Loose Brake: Exponential Tail Bounds for Stopping Time in Best Arm Identification

   Kapilan Balagopalan*, Tuan Ngo Nguyen*, Yao Zhao*, and Kwang-Sung Jun

   In Proceedings of the ICML 2025

   [Abstract] [Paper]

   The best arm identification problem requires identifying the best alternative (i.e., arm) in active experimentation using the smallest number of experiments (i.e., arm pulls), which is crucial for cost-efficient and timely decision-making processes. In the fixed confidence setting, an algorithm must stop data-dependently and return the estimated best arm with a correctness guarantee. Since this stopping time is random, we desire its distribution to have light tails. Unfortunately, many existing studies focus on high probability or in expectation bounds on the stopping time, which allow heavy tails and, for high probability bounds, even not stopping at all. We first prove that this never-stopping event can indeed happen for some popular algorithms. Motivated by this, we propose algorithms that provably enjoy an exponential-tailed stopping time, which improves upon the polynomial tail bound reported by Kalyanakrishnan et al. (2012). The first algorithm is based on a fixed budget algorithm called Sequential Halving along with a doubling trick. The second algorithm is a meta algorithm that takes in any fixed confidence algorithm with a high probability stopping guarantee and turns it into one that enjoys an exponential-tailed stopping time. Our results imply that there is much more to be desired for contemporary fixed confidence algorithms.

2021

1. Crosslingual Transfer Learning for Relation and Event Extraction via Word Category and Class Alignments

   Minh Van Nguyen, Tuan Ngo Nguyen, Bonan Min, and Thien Huu Nguyen

   In Proceedings of the EMNLP 2021

   [Abstract] [Paper]

   Previous work on crosslingual Relation and Event Extraction (REE) suffers from the monolingual bias issue due to the training of models on only the source language data. An approach to overcome this issue is to use unlabeled data in the target language to aid the alignment of crosslingual representations, i.e., via fooling a language discriminator. However, as this approach does not condition on class information, a target language example of a class could be incorrectly aligned to a source language example of a different class. To address this issue, we propose a novel crosslingual alignment method that leverages class information of REE tasks for representation learning. In particular, we propose to learn two versions of representation vectors for each class in an REE task based on either source or target language examples. Representation vectors for corresponding classes will then be aligned to achieve class-aware alignment for crosslingual representations. In addition, we propose to further align representation vectors for language universal word categories (i.e., parts of speech and dependency relations). As such, a novel filtering mechanism is presented to facilitate the learning of word category representations from contextualized representations on input texts based on adversarial learning. We conduct extensive crosslingual experiments with English, Chinese, and Arabic over REE tasks. The results demonstrate the benefits of the proposed method that significantly advances the state-of-the-art performance in these settings.

2. Hierarchical Graph Convolutional Networks for Jointly Resolving Cross-Document Coreference of Entity and Event Mentions

   Duy Phung, Tuan Ngo Nguyen, and Thien Huu Nguyen

   In Proceedings of the NAACL-HLT TextGraphs Workshop 2021

   [Abstract] [Paper]

   This paper studies the problem of cross-document event coreference resolution (CDECR) that seeks to determine if event mentions across multiple documents refer to the same real-world events. Prior work has demonstrated the benefits of the predicate-argument information and document context for resolving the coreference of event mentions. However, such information has not been captured effectively in prior work for CDECR. To address these limitations, we propose a novel deep learning model for CDECR that introduces hierarchical graph convolutional neural networks (GCN) to jointly resolve entity and event mentions. As such, sentence-level GCNs enable the encoding of important context words for event mentions and their arguments while the document-level GCN leverages the interaction structures of event mentions and arguments to compute document representations to perform CDECR. Extensive experiments are conducted to demonstrate the effectiveness of the proposed model.

2020

1. Event Detection: Gate Diversity and Syntactic Importance Scoresfor Graph Convolution Neural Networks

   Viet Dac Lai, Tuan Ngo Nguyen, and Thien Huu Nguyen

   In Proceedings of the EMNLP 2020

   [Abstract] [Paper]

   Recent studies on event detection (ED) haveshown that the syntactic dependency graph canbe employed in graph convolution neural net-works (GCN) to achieve state-of-the-art per-formance. However, the computation of thehidden vectors in such graph-based models isagnostic to the trigger candidate words, po-tentially leaving irrelevant information for thetrigger candidate for event prediction. In addi-tion, the current models for ED fail to exploitthe overall contextual importance scores of thewords, which can be obtained via the depen-dency tree, to boost the performance. In thisstudy, we propose a novel gating mechanismto filter noisy information in the hidden vec-tors of the GCN models for ED based on theinformation from the trigger candidate. Wealso introduce novel mechanisms to achievethe contextual diversity for the gates and theimportance score consistency for the graphsand models in ED. The experiments show thatthe proposed model achieves state-of-the-artperformance on two ED datasets.

2. Graph Transformer Networks with Syntactic and Semantic Structures for Event Argument Extraction

   Amir Pouran Ben Veyseh, Tuan Ngo Nguyen, and Thien Huu Nguyen

   In Findings of the EMNLP 2020

   [Abstract] [Paper]

   The goal of Event Argument Extraction (EAE) is to find the role of each entity mention for a given event trigger word. It has been shown in the previous works that the syntactic structures of the sentences are helpful for the deep learning models for EAE. However, a major problem in such prior works is that they fail to exploit the semantic structures of the sentences to induce effective representations for EAE. Consequently, in this work, we propose a novel model for EAE that exploits both syntactic and semantic structures of the sentences with the Graph Transformer Networks (GTNs) to learn more effective sentence structures for EAE. In addition, we introduce a novel inductive bias based on information bottleneck to improve generalization of the EAE models. Extensive experiments are performed to demonstrate the benefits of the proposed model, leading to state-of-the-art performance for EAE on standard datasets.

3. Learning to select important context words for event detection

   Nghia Trung Ngo, Tuan Ngo Nguyen, and Thien Huu Nguyen

   In Proceedings of the PAKDD 2020

   [Abstract] [Paper]

   It is important to locate important context words in the sentences and model them appropriately to perform event detection (ED) effectively. This has been mainly achieved by some fixed word selection strategy in the previous studies for ED. In this work, we propose a novel method that learns to select relevant context words for ED based on the Gumbel-Softmax trick. The extensive experiments demonstrate the effectiveness of the proposed method, leading to the state-of-the-art performance for ED over different benchmark datasets and settings.

2019

1. On the effectiveness of the pooling methods for biomedical relation extraction with deep learning

   Tuan Ngo Nguyen, Franck Dernoncourt, and Thien Huu Nguyen

   In Proceedings of the EMNLP LOUHI Workshop 2019

   [Abstract] [Paper]

   Deep learning models have achieved state-of-the-art performances on many relation extraction datasets. A common element in these deep learning models involves the pooling mechanisms where a sequence of hidden vectors is aggregated to generate a single representation vector, serving as the features to perform prediction for RE. Unfortunately, the models in the literature tend to employ different strategies to perform pooling for RE, leading to the challenge to determine the best pooling mechanism for this problem, especially in the biomedical domain. In order to answer this question, in this work, we conduct a comprehensive study to evaluate the effectiveness of different pooling mechanisms for the deep learning models in biomedical RE. The experimental results suggest that dependency-based pooling is the best pooling strategy for RE in the biomedical domain, yielding the state-of-the-art performance on two benchmark datasets for this problem.