We study streaming data with categorical features where the vocabulary of categorical feature values is changing and can even grow unboundedly over time. Feature hashing is commonly used as a pre-processing step to map these categorical values into a feature space of fixed size before learning their embeddings. While these methods have been developed and evaluated for offline or batch settings, in this paper we consider online settings. We show that deterministic embeddings are sensitive to the arrival order of categories and suffer from forgetting in online learning, leading to performance deterioration. To mitigate this issue, we propose a probabilistic hash embedding (PHE) model that treats hash embeddings as stochastic and applies Bayesian online learning to learn incrementally from data. Based on the structure of PHE, we derive a scalable inference algorithm to learn model parameters and infer/update the posteriors of hash embeddings and other latent variables. Our algorithm (i) can handle an evolving vocabulary of categorical items, (ii) is adaptive to new items without forgetting old items, (iii) is implementable with a bounded set of parameters that does not grow with the number of distinct observed values on the stream, and (iv) is invariant to the item arrival order. Experiments in classification, sequence modeling, and recommendation systems in online learning setups demonstrate the superior performance of PHE while maintaining high memory efficiency (consumes as low as 2→4% memory of a one-hot embedding table).

Mintong Kang, Vinayshekhar Bannihatti Kumar, Shamik Roy, Abhishek Kumar, Sopan Khosla, Balakrishnan Murali Narayanaswamy, Rashmi Gangadharaiah. Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing. 2025.

Can we efficiently choose the best Anomaly Detection (AD) algorithm for a data-stream without requiring anomaly labels? Streaming anomaly detection is hard. SOTA AD algorithms are sensitive to their hyperparameters and no single method works well on all datasets. The best algorithm/hyper-parameter combination for a given data-stream can change over time with data drift. 'What is an anomaly?' is often application, context and dataset dependent. We propose SEAD (Streaming Ensemble of Anomaly Detectors), the first model selection algorithm for streaming, unsupervised AD. All prior AD model selection algorithms are either supervised, or only work in the offline setting when all data from the test set is available upfront. We show that SEAD is {\em(i)} unsupervised, i.e., requires no true anomaly labels, {\em(ii)} efficiently implementable in a streaming setting, {\em (iii)} agnostic to the choice of the base algorithms among which it chooses from, and {\em (iv)} adaptive to non-stationarity in the data-stream. Experiments on 14 non-trivial public datasets and an internal dataset corroborate our claims.

Text-to-SQL systems translate natural language (NL) questions into SQL queries, enabling non-technical users to interact with structured data. While large language models (LLMs) have shown promising results on the text-to-SQL task, they often produce semantically incorrect yet syntactically valid queries, with limited insight into their reliability. We propose SQLens, an end-to-end framework for fine-grained detection and correction of semantic errors in LLM-generated SQL. SQLens integrates error signals from both the underlying database and the LLM to identify potential semantic errors within SQL clauses. It further leverages these signals to guide query correction. Empirical results on two public benchmarks show that SQLens outperforms the best LLM-based self-evaluation method by 25.78% in F1 for error detection, and improves execution accuracy of out-of-the-box text-to-SQL systems by up to 20%.

Query scheduling is a critical task that directly impacts query performance in database management systems (DBMS). Deeply integrated schedulers, which require changes to DBMS internals, are usually customized for a specific engine and can take months to implement. In contrast, non-intrusive schedulers make coarse-grained decisions, such as controlling query admission and re-ordering query execution, without requiring modifications to DBMS internals. They require much less engineering effort and can be applied across a wide range of DBMS engines, offering immediate benefits to end users. However, most existing non-intrusive scheduling systems rely on simplified cost models and heuristics that cannot accurately model query interactions under concurrency and different system states, possibly leading to suboptimal scheduling decisions. This work introduces IconqSched , a new, principled non-intrusive scheduler that optimizes the execution order and timing of queries to enhance total end-to-end runtime as experienced by the user — query queuing time plus system runtime. Unlike previous approaches, IconqSched features a novel predictor, Iconq , which treats the DBMS as a black box and accurately estimates the system runtime of concurrently executed queries under different system states. Using these predictions, IconqSched is able to capture system runtime variations across different query mixes and system loads. It then employs a greedy scheduling algorithm to effectively determine which queries to submit and when to submit them. We compare IconqSched to other schedulers in terms of end-to-end runtime using realistic workload traces. On Postgres, IconqSched reduces end-to-end runtime by up to 16.5% on average and 33.6% in the tail. Similarly, on Redshift, it reduces end-to-end runtime by up to 14.4% on average and 22.9% in the tail.

There has been a growing demand for making modern cloud-based data analytics systems cost-effective and easy to use. AI-powered intelligent resource scaling is one such effort, aiming at automating scaling decisions for serverless offerings like Amazon Redshift Serverless. The foundation of intelligent resource scaling lies in the ability to forecast query workloads and their resource consumption accurately. Although the forecasting problem has been extensively studied across various domains, there is a lack of thorough analysis of existing forecasting algorithms for large-scale, real-world cloud query workloads. This paper fills this gap by providing an in-depth analysis of forecasting algorithms for real-world cloud workloads, covering the fundamental data characteristics that distinguish query workload forecasting from prior problems and evaluating the strengths and limitations of existing algorithms in this new domain. We anticipate that our findings will provide valuable insights in informing the design of an efficient and effective solution for production use, as well as in steering the forecasting community toward more effective algorithms of high real-world impact.

Selecting appropriate thresholds for anomaly detection in online, unsupervised settings is a challenging task, especially in the presence of data distribution shifts. Addressing these challenges is critical in many practical large scale systems, such as infrastructure monitoring and network intrusion detection. This paper proposes an algorithm that connects online thresholding with constructing confidence sequences achieving (1) adaptive online threshold selection robust to distribution shifts, (2) statistical guarantees on false positive and false negative rates without any distributional assumptions, and (3) improved performance when given relevant offline data to warm-start the online algorithm, while having bounded degradation if the offline data is irrelevant. We complement our theoretical results by empirical evidence that our method outperforms commonly used baselines across synthetic and real world datasets.

The real-time estimation of time-varying parameters from high-dimensional, heavy-tailed and corrupted data-streams is a common sub-routine in systems ranging from those for network monitoring and anomaly detection to those for traffic scheduling in data-centers. For estimation tasks that can be cast as minimizing a strongly convex loss function, we prove that an appropriately tuned version of the {\ttfamily clipped Stochastic Gradient Descent} (SGD) is simultaneously {\em(i)} adaptive to drift, {\em (ii)} robust to heavy-tailed inliers and arbitrary corruptions, {\em(iii)} requires no distributional knowledge and {\em (iv)} can be implemented in an online streaming fashion. All prior estimation algorithms have only been proven to posses a subset of these practical desiderata. A observation we make is that, neither the $\mathcal{O}\left(\frac{1}{t}\right)$ learning rate for {\ttfamily clipped SGD} known to be optimal for strongly convex loss functions of a \emph{stationary} data-stream, nor the $\mathcal{O}(1)$ learning rate known to be optimal for being adaptive to drift in a \emph{noiseless} environment can be used. Instead, a learning rate of $T^{-\alpha}$ for $ \alpha < 1$ where $T$ is the stream-length is needed to balance adaptivity to potential drift and to combat noise. We develop a new inductive argument and combine it with a martingale concentration result to derive high-probability under \emph{any learning rate} on data-streams exhibiting \emph{arbitrary distribution shift} - a proof strategy that may be of independent interest. Further, using the classical doubling-trick, we relax the knowledge of the stream length $T$. Ours is the first online estimation algorithm that is provably robust to heavy-tails, corruptions and distribution shift simultaneously. We complement our theoretical results empirically on synthetic and real data.

We study algorithms for online change-point detection (OCPD), where samples that are potentially heavy-tailed, are presented one at a time and a change in the underlying mean must be detected as early as possible. We present an algorithm based on clipped Stochastic Gradient Descent (SGD), that works even if we only assume that the second moment of the data generating process is bounded. We derive guarantees on worst-case, finite-sample false-positive rate (FPR) over the family of all distributions with bounded second moment. Thus, our method is the first OCPD algorithm that guarantees finite-sample FPR, even if the data is high dimensional and the underlying distributions are heavy-tailed. The technical contribution of our paper is to show that clipped-SGD can estimate the mean of a random vector and simultaneously provide confidence bounds at all confidence values. We combine this robust estimate with a union bound argument and construct a sequential change-point algorithm with finite-sample FPR guarantees. We show empirically that our algorithm works well in a variety of situations, whether the underlying data are heavy-tailed, light-tailed, high dimensional or discrete. No other algorithm achieves bounded FPR theoretically or empirically, over all settings we study simultaneously.

Technology improvements have made it easier than ever to collect diverse telemetry at high resolution from any cyber or physical system, for both monitoring and control. In the domain of monitoring, anomaly detection has become an important problem in many research areas ranging from IoT and sensor networks to devOps. These systems operate in real, noisy and non-stationary environments. A fundamental question is then, ‘How to quickly spot anomalies in a data-stream, and differentiate them from either sudden or gradual drifts in the normal behaviour?’ Although several heuristics have been proposed for detecting anomalies on streams, no known method has formalized the desiderata and rigorously proven that they can be achieved. We begin by formalizing the problem as a sequential estimation task. We propose \name, (\textbf{Fi}ne \textbf{T}une on \textbf{Ne}w and \textbf{S}imilar \textbf{S}amples), a flexible framework for detecting anomalies on data streams. We show that in the case when the data stream has a gaussian distribution, FITNESS is provably both robust and adaptive. The core of our method is to fine-tune the anomaly detection system only on recent, similar examples, before predicting an anomaly score. We prove that this is sufficient for robustness and adaptivity. We further experimentally demonstrate that \name;{is} flexible in practice, i.e., it can convert existing offline AD algorithms in to robust and adaptive online ones.

The Natural Language Understanding (NLU) component in task oriented dialog systems processes a user's request and converts it into structured information that can be consumed by downstream components such as the Dialog State Tracker (DST).This information is typically represented as a semantic frame that captures the intent and slot-labels provided by the user.We first show that such a shallow representation is insufficient for complex dialog scenarios, because it does not capture the recursive nature inherent in many domains.We propose a recursive, hierarchical frame-based representation and show how to learn it from data.We formulate the frame generation task as a template-based tree decoding task, where the decoder recursively generates a template and then fills slot values into the template.We extend local tree-based loss functions with terms that provide global supervision and show how to optimize them end-to-end.We achieve a small improvement on the widely used ATIS dataset and a much larger improvement on a more complex dataset we describe here.

We study the problem of offline learning in automated decision systems under the contextual bandits model. We are given logged historical data consisting of contexts, (randomized) actions, and (nonnegative) rewards. A common goal is to evaluate what would happen if different actions were taken in the same contexts, so as to optimize the action policies accordingly. The typical approach to this problem, inverse probability weighted estimation (IPWE), requires logged action probabilities, which may be missing in practice due to engineering complications. Even when available, small action probabilities cause large uncertainty in IPWE, rendering the corresponding results insignificant. To solve both problems, we show how one can use policy improvement (PIL) objectives, regularized by policy imitation (IML). We motivate and analyze PIL as an extension to Clipped-IPWE, by showing that both are lower-bound surrogates to the vanilla IPWE. We also formally connect IML to IPWE variance estimation and natural policy gradients. Without probability logging, our PIL-IML interpretations justify and improve, by reward-weighting, the state-of-art cross-entropy (CE) loss that predicts the action items among all action candidates available in the same contexts. With probability logging, our main theoretical contribution connects IML-underfitting to the existence of either confounding variables or model misspecification. We show the value and accuracy of our insights by simulations based on Simpson’s paradox, standard UCI multiclass-to-bandit conversions and on the Criteo counterfactual analysis challenge dataset.

Influence maximization refers to the problem of selecting the most influential source set of a given size in a diffusion network. Most of the existing literature assumes the knowledge of the underlying network and the knowledge of the diffusion model of propagation to solve the influence maximization problem. However, both the real-world information networks and their diffusion models are not easy to determine in practice. In this article, an influence maximization algorithm based on the observed cascades has been proposed. A novel idea that a good subset of nodes for influence maximization should be composed of nodes that are not only active and strong or influential by themselves but also independent of each other has been proposed. Based on this premise, the problem has been cast as a quadratic integer programming problem with constraints. Furthermore, this problem has been shown to be equivalent to a particular class of Max-GP problem, namely, max-not-cut with size k (MNC), for which the state-of-the-art semidefinite programming (SDP) solution techniques exist with guaranteed performance ratios, although the original problem is NP-hard. The new SDP-based method presented in this article is tested on a number of synthetic as well as real-world data sets and has been shown to perform better than the state-of-the-art influence maximization algorithms which work with the apriori knowledge of the network and assume a particular diffusion model. The results demonstrate its practical applicability in applications using Twitter, blogosphere, and other social networks which are being increasingly used to target influential customers for viral marketing.

Demand response is a critical part of renewable integration and energy cost reduction goals across the world. Motivated by the need to reduce costs arising from electricity shortage and renewable energy fluctuations, we propose a novel multiarmed bandit mechanism for demand response (MAB-MDR) which makes monetary offers to strategic consumers who have unknown response characteristics, to incetivize reduction in demand. Our work is inspired by a novel connection we make to crowdsourcing mechanisms. The proposed mechanism incorporates realistic features of the demand response problem including time varying and quadratic cost function. The mechanism marries auctions, that allow users to report their preferences, with online algorithms, that allow distribution companies to learn user-specific parameters. We show that MAB-MDR is dominant strategy incentive compatible, individually rational, and achieves sublinear regret. Such mechanisms can be effectively deployed in smart grids using new information and control architecture innovations and lead to welcome savings in energy costs.

Technology products and software undergo large pre-release testing which is restricted to selected customers called a focus group. Acquiring feedback from these customers provides valuable information about the potential acceptance of the product in the market. Currently, these groups are formed either by manual or random selection or by out-sourcing, which incurs a substantial cost. However, automatic identification of these customers not only saves human effort in terms of money and time but can also help in obtaining useful feedback from fewer, effective representatives. This paper makes the first attempt at identifying these focus group members automatically through the analysis of online product reviews, posted by various consumers. We propose a novel probabilistic framework for focus group identification in an unsupervised setting and illustrate the efficacy of our approach on a dataset of 1.2 million reviews collected from Amazon.

Growing costs, environmental awareness and government directives have set the stage for an increase in the fraction of electricity supplied using intermittent renewable sources such as solar and wind energy. To compensate for the increased variability in supply and demand, we need algorithms for online energy resource allocation under temporal uncertainty of future consumption and availability. Recent advances in prediction algorithms offer hope that a reduction in future uncertainty, through short term predictions, will increase the worth of the renewables. Predictive information is then revealed incrementally in an online manner, leading to what we call dynamic temporal uncertainty. We demonstrate the non-triviality of this problem and provide online algorithms, both randomized and deterministic, to handle time varying uncertainty in future rewards for non-stationary MDPs in general and for energy resource allocation in particular. We derive theoretical upper and lower bounds that hold even for a finite horizon, and establish that, in the deterministic case, discounting future rewards can be used as a strategy to maximize the total (undiscounted) reward. We also corroborate the efficacy of our methodology using wind and demand traces.

In this paper, a novel iterative encoding scheme is proposed for memory systems suffering from stuck-at errors. The stuck-at errors can be efficiently managed by using side information about stuck-at memory cells during encoding, while encoding for unconstrained number of stuck-at errors is intractable due to its exponential complexity. The proposed coding scheme employs an iterative encoding algorithm using cross-entropy method, which has a polynomial time complexity. In addition, any linear block code (LBC) can be concatenated with the proposed code, to correct for both residual stuck-at errors and random (soft) errors. The proposed coding schemes are evaluated by numerical simulations using a memory channel undergoing both stuck-at and random errors. Simulation results show that the cross-entropy based coding scheme provides an improved block error rate (BLER) performance, or alternatively, a higher overall storage capacity.

Sparse measurement structures - in which each measurement only depends on a small number of the inputs-arise in models of many problems such as sensor networks, group testing and even lossless data compression. The most important question in these applications is `How many measurements are sufficient to reconstruct the input ?'. Regular structures, where each input is measured the same number of times, require fewer measurements than when arbitrary measurements are used. In this paper we conduct a general analysis of the performance of these regular measurement structures when used for lossy reconstruction of the input in the presence of measurement noise. The main contribution of our work is the generality of the result which is applicable to lossy detection with arbitrary, even non-linear measurements and with inputs and outputs in any discrete domain. The second contribution is the quantification of the effect of noise in the measurements on the reconstruction performance, which can be used to analyze the robustness of these sparse measurement structures. We show the generality and applicability of our results by analyzing the performance of pooling designs for rare allele detection.

Seminal work by Chevillat and Costello showed that for specific convolutional codes transmitted over a binary symmetric channel and decoded by sequential decoding, a measure of decoding effort decreases exponentially with the column distance function of the code. This has led to a large body of research in the design of codes with good distance profiles which are also used for transmission over Gaussian channels. In this paper we analyze the computational complexity of a stack decoder working on a specific tree code with real (as opposed to binary) symbols, transmitted over a memoryless Gaussian channel. In contrast to prior work that used random coding arguments, we use the intuition provided by the original proof to prove that decoding effort exhibits similar behavior even for a memoryless Gaussian channel. Our result is applicable to convolutional codes with antipodal signaling, sequence detection over Gaussian ISI channels and some sensor networks.

Prior work motivated the use of sequential decoding for the problem of large-scale detection in sensor networks. In this paper we develop the metric for sequential decoding from first principles, different from the Fano metric which is conventionally used in sequential decoding. The difference in the metric arises due to the dependence between codewords, which is inherent in sensing problems. We analyze the behavior of this metric and show that it has the requisite properties for use in sequential decoding, i.e., the metric is, 1) expected to increase if decoding proceeds correctly, and 2) expected to decrease if more than a certain number of decoding errors are made. Through simulations, we show that the metric behaves according to theory and results in much higher accuracies than the Fano metric. We also show that due to an empirically-observed computational cutoff rate, we can perform accurate detection in large scale sensor networks, even when the optimal Viterbi decoding is not computationally feasible.

This paper addresses the problem of robust text-independent speaker identification. A voting mechanism is proposed to combine probabilities generated using Gaussian mixture models (GMMs). This algorithm is evaluated on standard data sets and shown to improve performance. This method is found to decrease error rate by up to 68.6% relative on KING database and 34.9% relative on SPIDRE. An analysis is performed and a hypothesis is proposed as to why this algorithm does not give as good an identification rate in certain cases. A method of using voting along with the standard GMM method is described which overcomes this limitation. This second method is evaluated and found to decrease error rate by as much as 45.67% relative on the SPIDRE databases. It is found to give a substantial improvement over conventional GMMs in all the experiments performed. Both the proposed algorithms achieve increased accuracy with negligible increase in computational cost.

This paper addresses the problem of speaker based audio data segmentation. A novel method that has the advantages of both model and metric based techniques is proposed which creates a model for each speaker from the available data on the fly. This can be viewed as building a Hidden Markov Model (HMM) for the data with speakers abstracted as the hidden states. Each speaker/state is modeled with a Gaussian Mixture Model (GMM). To prevent a large number of spurious change points being detected, the use of the Generalized Likelihood Ratio (GLR) metric for grouping feature vectors is proposed. A clustering technique is described, through which a good initialization of each GMM is achieved, such that each state corresponds to a single speaker and not noise, silence or word classes, something that may happen in conventional unlabelled clustering. Finally, a refinement method, along the lines of Viterbi Training of HMMs is presented. The proposed method does not require prior knowledge of any speaker characteristics. It also does not require any tuning of threshold parameters, so it can be used with confidence over new data sets. The method assumes that the number of speakers is known apriori to be two. The method results in a decrease in the error rate by 84.75% on the files reported in the baseline system. It performs just as well even when the speaker segments are as short as 1s each, which is a large improvement over some previous methods, which require larger segments for accurate detection of speaker change points. 1.