Generative models have shown impressive capabilities in synthesizing high-quality outputs across various domains. However, a persistent challenge is the occurrence of "hallucinations," where the model produces outputs that are not grounded in the underlying facts. While empirical strategies have been explored to mitigate this issue, a rigorous theoretical understanding remains elusive. In this paper, we develop a theoretical framework to analyze the *learnability* of non-hallucinating generative models from a learning-theoretic perspective. Our results reveal that non-hallucinating learning is statistically *impossible* when relying solely on the training dataset, even for a hypothesis class of size two and when the entire training set is truthful. To overcome these limitations, we show that incorporating *inductive biases* aligned with the actual facts into the learning process is essential. We provide a systematic approach to achieve this by restricting the fact set to a concept class of finite VC-dimension and demonstrate its effectiveness under various learning paradigms. Although our findings are primarily conceptual, they represent a first step towards a principled approach to addressing hallucinations in learning generative models.

We study the problem of learning from expert advice in the presence of perturbed noisy losses. Unlike existing work that assumes stochastic perturbations, we consider the case where the perturbation occurs arbitrarily, subject to a budget$C$on each expert—an approach we term “nasty” experts. The learner's performance is evaluated on the underlying true losses while only observing the perturbed noisy losses. Assuming the existence of an expert that incurs zero true losses, we show that the minimax risk equals$\Theta(C\log K)$for an expert class of size$K$. Remarkably, this risk cannot be achieved by the standard Exponentially Weighted Average (EWA) algorithm with constant learning rates, for which we establish a lower bound of$\Omega(C^{2}/\log K)$. We further demonstrate a nearly matching upper bound of$\overline{O}(C^{2}+C\log K)$for the EWA algorithm. Our main proof technique is based on a novel potential-based analysis that is of independent interest. Finally, we demonstrate the effectiveness of our nasty expert model in the context of binary classification with Massart's noise, without knowing the noise upper bound.

We study agnostic online learning from continuous-time data streams, a setting that naturally arises in applications such as environmental monitoring, personalized recommendation, and high-frequency trading. Unlike classical discrete-time models, learners in this setting must interact with a continually evolving data stream while making queries and updating models only at sparse, strategically selected times. We develop a general theoretical framework for learning from both *oblivious* and *adaptive* data streams, which may be noisy and non-stationary. For oblivious streams, we present a black-box reduction to classical online learning that yields a regret bound of $T \cdot R(S)/S$ for any class with discrete-time regret $R(S)$, where $T$ is the time horizon and $S$ is the *query budget*. For adaptive streams, which can evolve in response to learner actions, we design a dynamic query strategy in conjunction with a novel importance weighting scheme that enables unbiased loss estimation. In particular, for hypothesis class $\mathcal{H}$ with a finite Littlestone dimension, we establish a tight regret bound of $\tilde{\Theta}(T \cdot \sqrt{\mathsf{Ldim}(\mathcal{H})/S})$ that holds in both settings. Our results provide the first *quantitative* characterization of agnostic learning in continuous-time online environments with limited interaction.

In online learning, a learner receives data in rounds and, at each round, predicts a label that is then compared to the true label, incurring a loss. The total loss overTrounds, when compared to the loss of the best expert from a class of experts or forecasters, is called the regret. In this paper, we focus on logarithmic loss for logistic-like experts withunbounded d-dimensional weights, a scenario that has been largely unexplored. To address the irregularities introduced by the unbounded weight norm, we introduce aregularizedversion of the average (fixed design) minimax regret by imposing asoft constrainton the weight norm. We demonstrate that the regularized minimax regret is fully characterized by a complexity measure we term the regularized Shtarkov sum. We also show how the behavior of the standard regret can be inferred from the regularized regret. Our main results provide aprecisecharacterization of the regularized Shtarkov sum and, consequently, the regularized regret with unbounded weights up to second-order asymptotics. Notably, unlike thed/2 logTregret growth known for bounded weights, our results imply that the regularized regret grows as (1/2+α/4)dlogTwhen the regularization parameter is of order Θ(T−α) for α ≤ 1/2. We achieve this using tools from analytic combinatorics, including multidimensional Fourier analysis, the saddle point method, and the Mellin transform.

We study the problem of online conditional distribution estimation with \emph{unbounded} label sets under local differential privacy. The problem may be succinctly stated as follows. Let $\mathcal{F}$ be a distribution-valued function class with an unbounded label set. Our aim is to estimate an \emph{unknown} function $f\in \mathcal{F}$ in an online fashion. More precisely, at time $t$, given a sample ${\mathbf{x}}_t$, we generate an estimate of $f({\mathbf{x}}_t)$ using only a \emph{privatized} version of the true \emph{labels} sampled from $f({\mathbf{x}}_t)$. The objective is to minimize the cumulative KL-risk of a finite horizon $T$. We show that under $(\epsilon,0)$-local differential privacy for the labels, the KL-risk equals $\tilde{\Theta}(\frac{1}{\epsilon}\sqrt{KT}),$ up to poly-logarithmic factors, where $K=|\mathcal{F}|$. This result significantly differs from the $\tilde{\Theta}(\sqrt{T\log K})$ bound derived in Wu et al., (2023a) for \emph{bounded} label sets. As a side-result, our approach recovers a nearly tight upper bound for the hypothesis selection problem of Gopi et al., (2020), which has only been established for the \emph{batch} setting.

We study the problem of oracle-efficient hybrid online learning when the features are generated by an unknown i.i.d. process and the labels are generated adversarially. Assuming access to an (offline) ERM oracle, we show that there exists a computationally efficient online predictor that achieves a regret upper bounded by $\tilde{O}(T^{\frac{3}{4}})$ for a finite-VC class, and upper bounded by $\tilde{O}(T^{\frac{p+1}{p+2}})$ for a class with $\alpha$ fat-shattering dimension $\alpha^{-p}$. This provides the first known oracle-efficient sublinear regret bounds for hybrid online learning with an unknown feature generation process. In particular, it confirms a conjecture of Lazaric and Munos (2012). We then extend our result to the scenario of shifting distributions with $K$ changes, yielding a regret of order $\tilde{O}(T^{\frac{4}{5}}K^{\frac{1}{5}})$. Finally, we establish a regret of $\tilde{O}((K^{\frac{2}{3}}(\log|\mathcal{H}|)^{\frac{1}{3}}+K)\cdot T^{\frac{4}{5}})$ for the contextual $K$-armed bandits with a finite policy set $\mathcal{H}$, i.i.d. generated contexts from an unknown distribution, and adversarially generated costs.

Developing machine learning models that account for potential faults encountered in real-world environments presents a fundamental challenge for mission-critical applications. In this paper, we introduce a novel theoretical framework grounded in learning theory for dealing with faults. In particular, we propose a framework called fault-tolerant PAC learning, aimed at identifying the most fault-tolerant models from a given hypothesis class (such as neural networks). We show that if faults occur randomly, fault-tolerant learning is equivalent to regular PAC learning. However, for adversarial faults, we show that the sample complexity of fault-tolerant PAC learning can grow linearly w.r.t. the number of perturbing functions induced by the faults, even for a hypothesis class with VC-dimension 1. We then provide a matching upper bound by restricting the number of perturbing functions. Finally, we show that the linear dependency on the number of perturbing functions can be substantially improved for deletion faults in neural networks. Our work provides a powerful formal framework and avenues for a number of future investigations on the precise characterization of fault-tolerant learning.

In online learning, a learner receives data in rounds 1$t T$and at each round predicts a label which is then compared to the true label resulting in a loss. The total loss over$T$rounds, when compared to a loss over the best expert from a class of experts, is called the regret. This paper focuses on logarithmic loss over a class of experts represented by a probability distribution$p$and parameterized by addimensional weight vector w. Unlike previous work that studied bounded weights, we assume that the norm of the weights can be unbounded. This unboundedness poses a challenging problem that leads to unexpected results. For such a class of weighted experts we analyze the (fixed design) minimax regret for the best predictor and worst label sequence. Such a minimax regret turns out to be a universal lower bound for most regrets analyzed in the literature. For bounded weights it is known that the minimax regret can grow like where$R$is an upper bound on the weight norm. In contrast, we show in this paper that for unbounded norm with$R$the minimax regret is asymptotically (d - 1) for a logistic-like expert class which we also extend to$R$We prove our findings by introducing the so called splittable label sequences that partition the weight space into regions with maximum sequence probability equal to 1. Finally, for a general class of monotone experts we present an upper bound 2d log$T$for the regret.

We study online classification with general hypothesis classes where the true labels are determined by some function within the class, but are corrupted by *unknown* stochastic noise, and the features are generated adversarially. Predictions are made using observed *noisy* labels and noiseless features, while the performance is measured via minimax risk when comparing against *true* labels. The noisy mechanism is modeled via a general noisy kernel that specifies, for any individual data point, a set of distributions from which the actual noisy label distribution is chosen. We show that minimax risk is *tightly* characterized (up to a logarithmic factor of the hypothesis class size) by the *Hellinger gap* of the noisy label distributions induced by the kernel, *independent* of other properties such as the means and variances of the noise. Our main technique is based on a novel reduction to an online comparison scheme of two hypotheses, along with a new *conditional* version of Le Cam-Birgé testing suitable for online settings. Our work provides the first comprehensive characterization of noisy online classification with guarantees that apply to the *ground truth* while addressing *general* noisy observations.

Microservices architecture has garnered extensive attention for its stability and scalability. However, in the complex and dynamic landscape of microservices systems, a incident in one service can propagate to others, resulting in significant economic losses and degraded user experiences. Therefore, the effective and precise localization of incidents in microservices systems becomes a critical concern. Previous research has leveraged runtime data (logs, metrics, call traces) and historical incident data to assist in root cause localization. However, due to the scarcity of business incidents (those causing severe impacts on business operations) and the fact that many incidents are reported by users, relevant run-time data and sufficient historical data are often unavailable, rendering previous methods impractical. In response to this challenge, we propose an online contrastive learning-based method for root cause localization of business incidents(OCRCL). We fully exploit incident tickets and the static dependency graph of services, integrating both textual semantic information and structural information from the dependency graph to discover root causes. Furthermore, we suggest that online contrastive learning can exhibit excellent performance with limited data and enable real-time model updates, making it better suited for industrial scenarios. Our approach demonstrates significant improvements over baseline methods across three real-world industrial datasets, highlighting its effectiveness in root cause localization.

We study the problem of online learning and online regret minimization when samples are drawn from a general unknown \emph{non-stationary} process. We introduce the concept of a \emph{dynamic changing process} with cost $K$, where the \emph{conditional} marginals of the process can vary arbitrarily, but that the number of different conditional marginals is bounded by $K$ over $T$ rounds. For such processes we prove a tight (upto $\sqrt{\log T}$ factor) bound $O(\sqrt{KT\cdot\vch\log T})$ for the \emph{expected worst case} regret of any finite VC-dimensional class $\mathcal{H}$ under absolute loss (i.e., the expected miss-classification loss). We then improve this bound for general mixable losses, by establishing a tight (up to $\log^3 T$ factor) regret bound $O(K\cdot\vch\log^3 T)$. We extend these results to general \emph{smooth adversary} processes with \emph{unknown} reference measure by showing a sub-linear regret bound for $1$-dimensional threshold functions under a general bounded convex loss. Our results can be viewed as a first step towards regret analysis with non-stationary samples in the \emph{distribution blind} (universal) regime. This also brings a new viewpoint that shifts the study of complexity of the hypothesis classes to the study of the complexity of processes generating data.

We study the problem of learning functional distributions in the presence of noise. A functional is a map from the space of features to *distributions* over a set of labels, and is often assumed to belong to a known class of hypotheses $\mathcal{F}$. Features are generated by a general random process and labels are sampled independently from feature-dependent distributions. In privacy sensitive applications, labels are passed through a noisy kernel. We consider *online learning*, where at each time step, a predictor attempts to predict the *actual* (label) distribution given only the features and *noisy* labels in prior steps. The performance of the predictor is measured by the expected KL-risk that compares the predicted distributions to the underlying truth. We show that the *minimax* expected KL-risk is of order $\tilde{\Theta}(\sqrt{T\log|\mathcal{F}|})$ for finite hypothesis class $\mathcal{F}$ and *any* non-trivial noise level. We then extend this result to general infinite classes via the concept of *stochastic sequential covering* and provide matching lower and upper bounds for a wide range of natural classes.

In online service systems, a majority of incidents are caused by changes, which can influence user experience and cause huge economic loss. Experiences with a real-world, large-scale online service system show that more than half of the change-induced incidents are reported by users. Identifying root-cause changes for these incidents is challenging due to the inherent gap between user-perceived functional-level incident information and component-level change details. Inadequate causal knowledge also brings challenges. In this paper, we propose a novel causal knowledge mining based approach aiming at root-cause change identification for user-reported incidents named Raccoon. To bridge the gap between incidents and changes, it utilizes the fault tree and software product line to represent incidents and changes at the user-perceived functional level. They are also used as the backbone of causal knowledge. To overcome the lack of causal knowledge, Raccoon adopts efficient knowledge extraction and inference methods. Moreover, Raccoon provides recommendations at the software product line and change granularity to meet diverse demands of incident triage and root-cause change identification scenarios in incident management. We evaluate Raccoon on a real-world dataset collected in a large-scale online service system. The result shows that Raccoon significantly outperforms the state-of-the-art baseline approaches, which proves its effectiveness.

In online service systems, software changes cause a majority of incidents (i.e., unplanned interruptions and outages). Managing change-induced incidents efficiently is crucial for ensuring the reliability and availability of online service systems. Understanding the incidents can help improve change-induced incident management. The task is challenging because the life cycle of change-induced incidents is complicated due to diverse change deployment and incident resolution procedures. Detailed records of the incidents and changes, together with a comprehensive analysis, are needed to gain an in-depth understanding. In this paper, we conduct a qualitative and quantitative study on 231 change-induced incidents in a real-world, large-scale online service system. Detailed change tickets and incident timeline in the post-mortems provides extensive information about the incident life cycle, enabling us to understand each incident in depth. Based on the data, we give a generic model of the complicated life cycle of change-induced incidents. Following the model, we systematically study the whole life cycle of the incident, including the introduction and resolution stages, and answer what affects the efficiency of resolution. We obtain 9 major findings from our study. Based on the findings, we discuss existing techniques and promising future directions for improving change-induced incident management.

We study sequential probability assignment in the context of online learning under logarithmic loss and obtain tight lower and upper bounds for sequential minimax regret. Sequential minimax regret is defined as the minimum excess loss over data horizon$T$that a predictor incurs over the best expert in a class, when the samples are presented sequentially and adversarially. Our upper bounds are established by applying Bayesian averaging over a novel “smooth truncated covering” of the expert class. This allows us to obtain tight (minimax) upper bounds that subsume the best known non-constructive bounds in an algorithmic fashion. For lower bounds, we reduce the problem to analyzing the fixed design regret via a novel application of Shtarkov sum adapted to online learning. We demonstrate the effectiveness of our approach by establishing tight regret bounds for a wide range of expert classes. In particular, we fully characterize the regret of generalized linear function with worst Lipschitz transform functions when the parameters are restricted to a unit norm$\ell _{s}$($s\ge 2$) ball of dimension$d$. We show that the regret grows as$\Theta (d\log T)$when$d\le O(T^{s/(s+1)-\epsilon })$for all$\epsilon >0$(with precise constant 1 when$d\le e^{o(\log T)}$) and$\tilde {O}(T^{s/(s+1)})$when$d\ge \Omega (T^{s/(s+1)})$. Finally, we show that the Bayesian approach may not always be optimal if the support of the prior is included in the reference class itself.

In source coding since Davisson’s seminal paper [1] various redundancy and regrets were thoroughly analyzed, from pointwise redundancy, to average and maximal minimax and maxmin regrets. Similarly, in online learning, there are various formulations of regrets that are grouped into fixed-design (when data is known in advance) and sequential. This position paper gives a brief overview of current formulations of regrets, and provides a thorough comparison of the sequential and fixed design formulations. Moreover, inspired by the source coding literature, new classes of regrets, from average to worst case minimax, are introduced. In particular, it is shown that the fixed design and sequential regrets are equal in the worst case and average sense when data is known in advance; but, in maximal sense (when maximizing over data), the former can be significantly smaller than the latter. Specifically, this paper proves that under logarithmic loss (i) for linear predictors the two maximal formulations are of the same order; and (ii) for linear threshold predictors, fixed design maximal regret is logarithmically smaller than the sequential one.

We study sequential general online regression, known also as sequential probability assignments, under logarithmic loss when compared against a broad class of experts. We obtain tight, often matching, lower and upper bounds for sequential minimax regret, which is defined as the excess loss incurred by the predictor over the best expert in the class. After proving a general upper bound we consider some specific classes of experts from Lipschitz class to bounded Hessian class and derive matching lower and upper bounds with provably optimal constants. Our bounds work for a wide range of values of the data dimension and the number of rounds. To derive lower bounds, we use tools from information theory (e.g., Shtarkov sum) and for upper bounds, we resort to new "smooth truncated covering" of the class of experts. This allows us to find constructive proofs by applying a simple and novel truncated Bayesian algorithm. Our proofs are substantially simpler than the existing ones and yet provide tighter (and often optimal) bounds.

Using only samples from a probabilistic model, we predict properties of the model and of future observations. The prediction game continues in an online fashion as the sample size grows with new observations. After each prediction, the predictor incurs a binary (0-1) loss. The probability model underlying a sample is otherwise unknown except that it belongs to a known class of models. The goal is to make finitely many errors (i.e. loss of 1) with probability 1 under the generating model, no matter what it may be in the known model class. Model classes admitting predictors that make only finitely many errors are eventually almost surely (eas) predictable. When the losses incurred are observable (the supervised case), we completely characterize eas predictable classes. We provide analogous results in the unsupervised case. Our results have a natural interpretation in terms of regularization. In eas-predictable classes, we study if it is possible to have a universal stopping rule that identifies (to any given confidence) when no more errors will be made. Classes admitting such a stopping rule are eas learnable. When samples are generated iid, we provide a complete characterization of eas learnability. We also study cases when samples are not generated iid, but a full characterization remains open at this point.

We study the problem of online learning a hypothesis class and a given binary 0-1 loss function, using instances generated $i.i.d.$ by a given distribution. The goal of the online learner is to make only finitely many errors (loss 1) with probability $1$ in the infinite horizon. In the binary label case, we show that hypothesis classes are online learnable in the above sense if and only if the class is effectively countable. We extend the results to hypothesis classes where labels can be non-binary. Characterization of non-binary online learnable classes is more involved for general loss functions and is not captured fully by the countability condition even for the ternary label case. In the computational bounded setup, we compare our results with well known results in recursive function learning, showing that the class of all total computable functions is indeed learnable with computable online learners and randomized sampling. Finally, we also show that the finite error guarantee will not be affected even when independent noise is added to the label.

We study the problem of estimating properties of dynamic graphical models in the non-asymptotic regime. Instead of characterizing the behavior of estimation rules with asymptotic consistency, we study sharp bounds on the sample size required to estimate the properties. We show that for certain spatio-temporal Markov random fields governed by an underlying graph, one can estimate certain natural properties with logarithmic (w.r.t. the size of the underlying graph) sample complexity. Matching lower bounds are also established for such estimation problems. We highlight our results with a “bit river” abstraction, where a Bernoulli source at one node flows along the edges of an underlying graph, and the task is to obtain the flow trajectory. If we do not have any restriction on the model class under consideration, we also show that an exponential sample size is required for even very simple properties.

Let P be a class of distributions over natural numbers, and A be a subset of ℝ+. We study the problem of deciding, using i.i.d. samples X1,X2,... from an unknown p ∈ P, whether the entropy H(p) is in A or not. The decision is updated based on every new observation Xn-we are interested in decision rules that make only finitely many errors no matter what the underlying source is. We give necessary and sufficient conditions on the class P and A that can be decided with only finitely many errors. We show for example that such rules exist for testing the rationality of entropy within a given interval, for testing if the entropy falls in an interval of form (a,b], but no such decision rule exists to determine if the entropy is finite or if the entropy falls in an interval of form [a,b]. In the process, we also highlight the conceptual foundation this framework shares with regularization.

We study the problem of predicting upper bounds on the next draw of an unknown probability distribution after observing a sample generated by it. The unknown distribution is modeled as belonging to a class P of distributions over natural numbers. The goal is to err only finitely many times even though the game proceeds over an infinite horizon, and though there is no upper bound on what the next sample can be. If a universal prediction scheme exists that makes only finitely many errors regardless of what model in P generated the data, we say P is eventually almost surely (e.a.s.) predictable. In this paper, we fully characterize when P can be e.a.s.-predictable.

We study the optimal sampling set selection problem in sampling a noisy k -bandlimited graph signal. To minimize the effect of noise when trying to reconstruct a k -bandlimited graph signal from m samples, the optimal sampling set selection problem has been shown to be equivalent to finding a m×k submatrix with the maximum smallest singular value, σmin [3]. As the problem is NP-hard, we present a greedy algorithm inspired by a similar submatrix selection problem known in computer science and to which we add a local search refinement. We show that 1) in experiments, our algorithm finds a submatrix with larger σmin than prior greedy algorithm [3], and 2) has a proven worst-case approximation ratio of 1/(1+ε)k, where ε is a constant.

We study the redundancy of universally compressing strings X1, ...,Xn generated by a binary Markov source p without any bound on the memory. To better understand the connection between compression and estimation in the Markov regime, we consider a class of Markov sources restricted by a continuity condition. In the absence of an upper bound on memory, the continuity condition implies that p(X0|X-m-1) gets closer to the true probability p(X0|X-∞-1) as m increases, rather than vary around arbitrarily. For such sources, we prove asymptotically matching upper and lower bounds on the redundancy. In the process, we identify what sources in the class matter the most from a redundancy perspective.

The jackknife resampling procedure is a technique to reduce the bias of a statistic. As with other resampling techniques, the jackknife procedure is motivated by and is well understood in the i.i.d. regime. However, analysis of the procedure when samples have memory is limited, and is predominantly restricted to cases with strong mixing or memory constraints. In this paper, we analyze a natural jackknife resampling procedure for Markov sources with no mixing assumptions. For the problem to be well posed without mixing assumptions, we instead adopt a physically motivated continuity condition that ensures that the information a bit in the past provides about the current bit, conditioned on all bits in between, diminishes with the amount of history we have. We analyze the jackknife estimate of the variance of conditional probability estimates given arbitrary contexts, and show that the bias of this jackknife procedure can be bounded by a small constant.