Concept erasure is the task of erasing information about a concept (e.g., gender or race) from a representation set while retaining the maximum possible utility – information from original representations. Concept erasure is useful in several applications, such as removing sensitive concepts to achieve fairness and interpreting the impact of specific concepts on a model’s performance. Previous concept erasure techniques have prioritized robustly erasing concepts over retaining the utility of the resultant representations. However, there seems to be an inherent tradeoff between erasure and retaining utility, making it unclear how to achieve perfect concept erasure while maintaining high utility. In this paper, we offer a fresh perspective toward solving this problem by quantifying the fundamental limits of concept erasure through an information-theoretic lens. Using these results, we investigate constraints on the data distribution and the erasure functions required to achieve the limits of perfect concept erasure. Empirically, we show that the derived erasure functions achieve the optimal theoretical bounds. Additionally, we show that our approach outperforms existing methods on a range of synthetic and real-world datasets using GPT-4 representations.

With the widespread deployment of Multimodal Large Language Models (MLLMs) for visual-reasoning tasks, improving their safety has become crucial. Recent research indicates that despite training-time safety alignment, these models remain vulnerable to jailbreak attacks. In this work, we first highlight an important safety gap to describe that alignment achieved solely through safety training may be insufficient against jailbreak attacks. To address this vulnerability, we propose Immune, an inference-time defense framework that leverages a safety reward model through controlled decoding to defend against jailbreak attacks. Additionally, we provide a mathematical characterization of Immune, offering insights on why it improves safety against jailbreaks. Extensive evaluations on diverse jailbreak benchmarks using recent MLLMs reveal that Immune effectively enhances model safety while preserving the model’s original capabilities. For instance, against text-based jailbreak attacks on LLaVA-1.6, Immune reduces the attack success rate by 57.82% and 16.78% compared to the base MLLM and state-of-the-art defense strategy, respectively.

Jessica Hoffmann, Christiane Ahlheim, Zac Yu, Aria Walfrand, Jarvis Jin, Marie Tano, Ahmad Beirami, Erin MacMurray van Liemt, Nithum Thain, Hakim Sidahmed, Lucas Dixon. Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing. 2025.

The safety alignment of current Large Language Models (LLMs) is vulnerable. Simple attacks, or even benign fine-tuning, can jailbreak aligned models. We note that many of these vulnerabilities are related to a shared underlying issue: safety alignment can take shortcuts, wherein the alignment adapts a model's generative distribution primarily over only its very first few output tokens. We unifiedly refer to this issue as shallow safety alignment. In this paper, we present case studies to explain why shallow safety alignment can exist and show how this issue universally contributes to multiple recently discovered vulnerabilities in LLMs, including the susceptibility to adversarial suffix attacks, prefilling attacks, decoding parameter attacks, and fine-tuning attacks. The key contribution of this work is that we demonstrate how this consolidated notion of shallow safety alignment sheds light on promising research directions for mitigating these vulnerabilities. We show that deepening the safety alignment beyond the first few tokens can meaningfully improve robustness against some common exploits. We also design a regularized fine-tuning objective that makes the safety alignment more persistent against fine-tuning attacks by constraining updates on initial tokens. Overall, we advocate that future safety alignment should be made more than just a few tokens deep.

Despite their significant advancements, Multimodal Large Language Models (MLLMs) often generate factually inaccurate information, referred to as hallucination. In this work, we address object hallucinations in MLLMs, where information is generated about an object not present in the input image. We introduce Data-augmented Phrase-level Alignment (DPA), a novel loss which can be applied to instruction-tuned off-the-shelf MLLMs to mitigate hallucinations, while preserving their general vision-language capabilities. To fine-tune MLLMs with DPA, we first generate a set of 'hallucinated' and 'correct' response pairs through generative data augmentation by selectively altering the ground-truth information of the correct responses at a phrase level. The DPA loss is then used to train MLLMs to reduce the likelihood of hallucinated phrases compared to the correct ones. Our thorough evaluation on various benchmarks confirms the effectiveness of DPA in mitigating hallucination while retaining the out-of-the-box performance of the MLLMs on general tasks. For instance, MLLMs finetuned with DPA, which we refer to as Hallucination Attenuated Language and Vision Assistant (HALVA), improve F1 by up to 13.4% on hallucination visual question-answering and reduce the hallucination rate by up to 4.2% on image description tasks.

Speculative decoding is an effective method for lossless acceleration of large language models during inference. It uses a fast model to draft a block of tokens which are then verified in parallel by the target model, and provides a guarantee that the output is distributed identically to a sample from the target model. In prior works, draft verification is performed independently token-by-token. Surprisingly, we show that this approach is not optimal. We propose *Block Verification*, a simple draft verification algorithm that verifies the entire block jointly and provides additional wall-clock speedup. We prove that the proposed mechanism is optimal in the expected number of tokens produced each iteration and specifically is never worse than the standard token-level verification. Empirically, block verification provides modest but consistent wall-clock speedups over the standard token verification algorithm of 5\%-8\% in a range of tasks and datasets. Given that block verification does not increase code complexity, maintains the strong lossless guarantee of the standard speculative decoding verification algorithm, cannot deteriorate performance, and, in fact, consistently improves it, it can be used as a good default in speculative decoding implementations.

The generalization error (risk) of a supervised statistical learning algorithm quantifies its prediction ability on previously unseen data. Inspired by exponential tilting, Li et al. (2021) proposed the tilted empirical risk (TER) as a non-linear risk metric for machine learning applications such as classification and regression problems. In this work, we examine the generalization error of the tilted empirical risk in the robustness regime under negative tilt. Our first contribution is to provide uniform and information-theoretic bounds on the tilted generalization error, defined as the difference between the population risk and the tilted empirical risk, under negative tilt for unbounded loss function under bounded $(1+\epsilon)$-th moment of loss function for some $\epsilon\in(0,1]$ with a convergence rate of $O(n^{-\epsilon/(1+\epsilon)})$ where $n$ is the number of training samples, revealing a novel application for TER under no distribution shift. Secondly, we study the robustness of the tilted empirical risk with respect to noisy outliers at training time and provide theoretical guarantees under distribution shift for the tilted empirical risk. We empirically corroborate our findings in simple experimental setups where we evaluate our bounds to select the value of tilt in a data-driven manner.

Language model alignment is a critical step in training modern generative language models. Alignment targets to improve win rate of a sample from the aligned model against the base model. Today, we are increasingly using inference-time algorithms (e.g., Best-of-$N$ , controlled decoding, tree search) to decode from language models rather than standard sampling. We show that this train/test mismatch makes standard RLHF framework sub-optimal in view of such inference-time methods. To this end, we propose a framework for inference-aware alignment (InfAlign), which aims to optimize *inference-time win rate* of the aligned policy against the base model. We prove that for any inference-time decoding procedure, the optimal aligned policy is the solution to the standard RLHF problem with a *transformation* of the reward. This motivates us to provide the calibrate-and-transform RL (InfAlign-CTRL) algorithm to solve this problem, which involves a reward calibration step and a KL-regularized reward maximization step with a transformation of the calibrated reward. For best-of-$N$ sampling and best-of-$N$ jailbreaking, we propose specific transformations offering up to 3-8% improvement on inference-time win rates. Finally, we also show that our proposed reward calibration method is a strong baseline for optimizing standard win rate.

A simple and effective method for the inference-time alignment of generative models is the best-of-$n$ policy, where $n$ samples are drawn from a reference policy, ranked based on a reward function, and the highest ranking one is selected. A commonly used analytical expression in the literature claims that the KL divergence between the best-of-$n$ policy and the reference policy is equal to $\log (n) - (n-1)/n.$ We disprove the validity of this claim, and show that it is an upper bound on the actual KL divergence. We also explore the tightness of this upper bound in different regimes, and propose a new estimator for the KL divergence and empirically show that it provides a tight approximation. We also show that the win rate of the best-of-$n$ policy against the reference policy is upper bounded by $n/(n+1)$ and derive bounds on the tightness of this characterization. We conclude with analyzing the tradeoffs between win rate and KL divergence of the best-of-$n$ alignment policy, which demonstrate that very good tradeoffs are achievable with $n < 1000$.

State-of-the-art techniques for enhancing robustness of deep networks mostly rely on empirical risk minimization with suitable data augmentation. In this paper, we propose a complementary approach motivated by communication theory, aimed at enhancing the signal-to-noise ratio at the output of a neural network layer via neural competition during learning and inference. In addition to standard empirical risk minimization, neurons compete to sparsely represent layer inputs by maximization of a tilted exponential (TEXP) objective function for the layer. TEXP learning can be interpreted as maximum likelihood estimation of matched filters under a Gaussian model for data noise. Inference in a TEXP layer is accomplished by replacing batch norm by a tilted softmax, which can be interpreted as computation of posterior probabilities for the competing signaling hypotheses represented by each neuron. After providing insights via simplified models, we show, by experimentation on standard image datasets, that TEXP learning and inference enhances robustness against noise and other common corruptions, without requiring data augmentation. Further cumulative gains in robustness against this array of distortions can be obtained by appropriately combining TEXP with data augmentation techniques. The code for all our experiments is available at \url{https://github.com/bhagyapuranik/texp_for_robustness}.

that may be offensive or upsetting.

Aligning language models (LMs) based on human-annotated preference data is a crucial step in obtaining practical and performant LMbased systems.However, multilingual human preference data are difficult to obtain at scale, making it challenging to extend this framework to diverse languages.In this work, we evaluate a simple approach for zero-shot crosslingual alignment, where a reward model is trained on preference data in one source language and directly applied to other target languages.On summarization and open-ended dialog generation, we show that this method is consistently successful under comprehensive evaluation settings, including human evaluation: cross-lingually aligned models are preferred by humans over unaligned models on up to >70% of evaluation instances.We moreover find that a different-language reward model sometimes yields better aligned models than a same-language reward model.We also identify best practices when there is no languagespecific data for even supervised finetuning, another component in alignment.en de en es en ru en tr en vi de en es en ru en tr en vi en 0 20 40 60 ROUGE-L (a) Summarization, unaligned SFT model Target-Language SFT Data

Fairness, especially group fairness, is an important consideration in the context of machine learning systems. The most commonly adopted group fairness-enhancing techniques are in-processing methods that rely on a mixture of a fairness objective (e.g., demographic parity) and a task-specific objective (e.g., cross-entropy) during the training process. However, when data arrives in an online fashion – one instance at a time – optimizing such fairness objectives poses several challenges. In particular, group fairness objectives are defined using expectations of predictions across different demographic groups. In the online setting, where the algorithm has access to a single instance at a time, estimating the group fairness objective requires additional storage and significantly more computation (e.g., forward/backward passes) than the task-specific objective at every time step. In this paper, we propose Aranyani, an ensemble of oblique decision trees, to make fair decisions in online settings. The hierarchical tree structure of Aranyani enables parameter isolation and allows us to efficiently compute the fairness gradients using aggregate statistics of previous decisions, eliminating the need for additional storage and forward/backward passes. We also present an efficient framework to train Aranyani and theoretically analyze several of its properties. We conduct empirical evaluations on 5 publicly available benchmarks (including vision and language datasets) to show that Aranyani achieves a better accuracy-fairness trade-off compared to baseline approaches.

KL-regularized reinforcement learning (RL) is a popular alignment framework to control the language model responses towards high reward outcomes. We pose a tokenwise RL objective and propose a modular solver for it, called *controlled decoding (CD)*. CD exerts control through a separate *prefix scorer* module, which is trained to learn a value function for the reward. The prefix scorer is used at inference time to control the generation from a frozen base model, provably sampling from a solution to the RL objective. We empirically demonstrate that CD is effective as a control mechanism on popular benchmarks. We also show that prefix scorers for multiple rewards may be combined at inference time, effectively solving a multi-objective RL problem with no additional training. We show that the benefits of applying CD transfer to an unseen base model with no further tuning as well. Finally, we show that CD can be applied in a blockwise decoding fashion at inference-time, essentially bridging the gap between the popular best-of-$K$ strategy and tokenwise control through reinforcement learning. This makes CD a promising approach for alignment of language models.

Despite achieving promising fairness-error trade-offs, in-processing mitigation techniques for group fairness cannot be employed in numerous practical applications with limited computation resources or no access to the training pipeline of the prediction model. In these situations, post-processing is a viable alternative. However, current methods are tailored to specific problem settings and fairness definitions and hence, are not as broadly applicable as in-processing. In this work, we propose a framework that turns any regularized in-processing method into a post-processing approach. This procedure prescribes a way to obtain post-processing techniques for a much broader range of problem settings than the prior post-processing literature. We show theoretically and through extensive experiments that our framework preserves the good fairness-error trade-offs achieved with in-processing and can improve over the effectiveness of prior post-processing methods. Finally, we demonstrate several advantages of a modular mitigation strategy that disentangles the training of the prediction model from the fairness mitigation, including better performance on tasks with partial group labels.

Let$\boldsymbol{p}$denote a reference generative language model. Let$\boldsymbol{r}$denote a reward model that returns a scalar to capture the degree at which a draw from$\boldsymbol{p}$is preferred. The goal of language model alignment is to alter$\boldsymbol{p}$to a new distribution$\phi$that results in a higher expected reward while keeping$\phi$close to$\boldsymbol{p}$. A popular alignment method is the KL-constrained reinforcement learning$(\boldsymbol{RL})$, which chooses a distribution$\Phi_\Delta$that maximizes$E_{\phi_{\Delta}}\boldsymbol{r}(\boldsymbol{y})$subject to a relative entropy constraint$D_{\mathrm{K}\mathrm{L}}(\phi_{\Delta}\Vert \boldsymbol{p})\leq\Delta$. Another simple alignment method is best-of-N, where$N$samples are drawn from$\boldsymbol{p}$and one with highest reward is selected. In this paper, we offer a closed-form characterization of the optimal KL-constrained RL solution. We then demonstrate that any alignment method that achieves a comparable trade-off between KL divergence and expected reward must approximate the optimal KL-constrained RL solution in terms of relative entropy. To analyze the properties of alignment methods, we introduce two simplifying assumptions: we let the language model be memoryless, and the reward model be linear. Although these assumptions may not reflect complex real-world scenarios, they enable a precise characterization of the asymptotic (in the sequence length) behavior of the best-of-N and the KL-constrained RL methods, in terms of information-theoretic quantities.1

This paper introduces the Ninth Dialog System Technology Challenge (DSTC-9). This edition of the DSTC focuses on applying end-to-end dialog technologies for four distinct tasks in dialog systems, namely, 1. Task-oriented dialog Modeling with Unstructured Knowledge Access, 2. Multi-domain task-oriented dialog, 3. Interactive evaluation of dialog and 4. Situated interactive multimodal dialog. This paper describes the task definition, provided datasets, baselines, and evaluation setup for each track. We also summarize the results of the submitted systems to highlight the general trends of the state-of-the-art technologies for the tasks.

Preethi Lahoti, Nicholas Blumm, Xiao Ma, Raghavendra Kotikalapudi, Sahitya Potluri, Qijun Tan, Hansa Srinivasan, Ben Packer, Ahmad Beirami, Alex Beutel, Jilin Chen. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 2023.

Video self-supervised learning (VSSL) has made significant progress in recent years. However, the exact behavior and dynamics of these models under different forms of distribution shift are not yet known. In this paper, we comprehensively study the behavior of six popular self-supervised methods (v-SimCLR, v-MoCo, v-BYOL, v-SimSiam, v-DINO, v-MAE) in response to various forms of natural distribution shift, i.e., (i) context shift, (ii) viewpoint shift, (iii) actor shift, (iv) source shift, (v) generalizability to unknown classes (zero-shot), and (vi) open-set recognition. To perform this extensive study, we carefully craft a test bed consisting of 17 in-distribution and out-of-distribution benchmark pairs using available public datasets and a series of evaluation protocols to stress-test the different methods under the intended shifts. Our study uncovers a series of intriguing findings and interesting behaviors of VSSL methods. For instance, we observe that while video models generally struggle with context shifts, v-MAE and supervised learning exhibit more robustness. Moreover, our study shows that v-MAE is a strong temporal learner, whereas contrastive methods, v-SimCLR and v-MoCo, exhibit strong performances against viewpoint shifts. When studying the notion of open-set recognition, we notice a trade-off between closed-set and open-set recognition performance if the pretrained VSSL encoders are used without finetuning. We hope that our work will contribute to the development of robust video representation learning frameworks for various real-world scenarios. The project page and code are available at: https://pritamqu.github.io/OOD-VSSL.

Autoregressive sampling from large language models has led to state-of-the-art results in several natural language tasks. However, autoregressive sampling generates tokens one at a time making it slow, and even prohibitive in certain tasks. One way to speed up sampling is *speculative decoding*: use a small model to sample a *draft* (block or sequence of tokens), and then score all tokens in the draft by the large language model in parallel. A subset of the tokens in the draft are accepted (and the rest rejected) based on a statistical method to guarantee that the final output follows the distribution of the large model. In this work, we provide a principled understanding of speculative decoding through the lens of optimal transport (OT) with *membership cost*. This framework can be viewed as an extension of the well-known *maximal-coupling* problem. This new formulation enables us to generalize the speculative decoding method to allow for a set of $k$ candidates at the token-level, which leads to an improved optimal membership cost. We show that the optimal draft selection algorithm (transport plan) can be computed via linear programming, whose best-known runtime is exponential in $k$. We then propose a valid draft selection algorithm whose acceptance probability is $(1-1/e)$-optimal multiplicatively. Moreover, it can be computed in time almost linear with size of domain of a single token. Using this new draft selection algorithm, we develop a new autoregressive sampling algorithm called *SpecTr*, which provides speedup in decoding while ensuring that there is no quality degradation in the decoded output. We experimentally demonstrate that for state-of-the-art large language models, the proposed approach achieves a wall clock speedup of 2.13X, a further 1.37X speedup over speculative decoding on standard benchmarks.

Exponential tilting is a technique commonly used in fields such as statistics, probability, information theory, and optimization to create parametric distribution shifts. Despite its prevalence in related fields, tilting has not seen widespread use in machine learning. In this work, we aim to bridge this gap by exploring the use of tilting in risk minimization. We study a simple extension to ERM---tilted empirical risk minimization (TERM)---which uses exponential tilting to flexibly tune the impact of individual losses. The resulting framework has several useful properties: We show that TERM can increase or decrease the influence of outliers, respectively, to enable fairness or robustness; has variance-reduction properties that can benefit generalization; and can be viewed as a smooth approximation to the tail probability of losses. Our work makes connections between TERM and related objectives, such as Value-at-Risk, Conditional Value-at-Risk, and distributionally robust optimization (DRO). We develop batch and stochastic first-order optimization methods for solving TERM, provide convergence guarantees for the solvers, and show that the framework can be efficiently solved relative to common alternatives. Finally, we demonstrate that TERM can be used for a multitude of applications in machine learning, such as enforcing fairness between subgroups, mitigating the effect of outliers, and handling class imbalance. Despite the straightforward modification TERM makes to traditional ERM objectives, we find that the framework can consistently outperform ERM and deliver competitive performance with state-of-the-art, problem-specific approaches.

Ninareh Mehrabi, Ahmad Beirami, Fred Morstatter, Aram Galstyan. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2022.

Kun Qian, Satwik Kottur, Ahmad Beirami, Shahin Shayandeh, Paul Crook, Alborz Geramifard, Zhou Yu, Chinnadhurai Sankar. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2022.

Hung Le, Chinnadhurai Sankar, Seungwhan Moon, Ahmad Beirami, Alborz Geramifard, Satwik Kottur. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

Fairness and robustness are two important concerns for federated learning systems. In this work, we identify that robustness to data and model poisoning attacks and fairness, measured as the uniformity of performance across devices, are competing constraints in statistically heterogeneous networks. To address these constraints, we propose employing a simple, general framework for personalized federated learning, Ditto, that can inherently provide fairness and robustness benefits, and develop a scalable solver for it. Theoretically, we analyze the ability of Ditto to achieve fairness and robustness simultaneously on a class of linear problems. Empirically, across a suite of federated datasets, we show that Ditto not only achieves competitive performance relative to recent personalization methods, but also enables more accurate, robust, and fair models relative to state-of-the-art fair or robust baselines.

Satwik Kottur, Paul Crook, Seungwhan Moon, Ahmad Beirami, Eunjoon Cho, Rajen Subba, Alborz Geramifard. Proceedings of the 22nd Annual Meeting of the Special Interest Group on Discourse and Dialogue. 2021.

MultiWOZ (Budzianowski et al., 2018) is one of the most popular multi-domain taskoriented dialog datasets, containing 10K+ annotated dialogs covering eight domains.It has been widely accepted as a benchmark for various dialog tasks, e.g., dialog state tracking (DST), natural language generation (NLG) and end-to-end (E2E) dialog modeling.In this work, we identify an overlooked issue with dialog state annotation inconsistencies in the dataset, where a slot type is tagged inconsistently across similar dialogs leading to confusion for DST modeling.We propose an automated correction for this issue, which is present in 70% of the dialogs.Additionally, we notice that there is significant entity bias in the dataset (e.g., "cambridge" appears in 50% of the destination cities in the train domain).The entity bias can potentially lead to named entity memorization in generative models, which may go unnoticed as the test set suffers from a similar entity bias as well.We release a new test set with all entities replaced with unseen entities.Finally, we benchmark joint goal accuracy (JGA) of the state-of-theart DST baselines on these modified versions of the data.Our experiments show that the annotation inconsistency corrections lead to 7-10% improvement in JGA.On the other hand, we observe a 29% drop in JGA when models are evaluated on the new test set with unseen entities.* The work of KQ and ZY was done as a research intern and a visiting research scientist at Facebook AI.

Competition is a primary driver of player satisfaction and engagement in multiplayer online games. Traditional matchmaking systems aim at creating matches involving teams of similar aggregated individual skill levels, such as Elo score or TrueSkill. However, team dynamics cannot be solely captured using such linear predictors. Recently, it has been shown that nonlinear predictors that target to learn probability of winning as a function of player and team features significantly outperforms these linear skill-based methods. In this paper, we show that using final score difference provides yet a better prediction metric for competitive balance. We also show that a linear model trained on a carefully selected set of team and individual features achieves almost the performance of the more powerful neural network model while offering two orders of magnitude inference speed improvement. This shows significant promise for implementation in online matchmaking systems.

Seungwhan Moon, Satwik Kottur, Paul Crook, Ankita De, Shivani Poddar, Theodore Levin, David Whitney, Daniel Difranco, Ahmad Beirami, Eunjoon Cho, Rajen Subba, Alborz Geramifard. Proceedings of the 28th International Conference on Computational Linguistics. 2020.

Motivated by the needs of resource constrained dialog policy learning, we introduce dialog policy via differentiable inductive logic (DILOG).We explore the tasks of one-shot learning and zero-shot domain transfer with DILOG on SimDial and MultiWoZ.Using a single representative dialog from the restaurant domain, we train DILOG on the SimDial dataset and obtain 99+% in-domain test accuracy.We also show that the trained DILOG zero-shot transfers to all other domains with 99+% accuracy, proving the suitability of DILOG to slot-filling dialogs.We further extend our study to the MultiWoZ dataset achieving 90+% inform and success metrics.We also observe that these metrics are not capturing some of the shortcomings of DILOG in terms of false positives, prompting us to measure an auxiliary Action F1 score.We show that DILOG is 100x more data efficient than state-of-the-art neural approaches on MultiWoZ while achieving similar performance metrics.We conclude with a discussion on the strengths and weaknesses of DILOG.

Recently, there have been several high-profile achievements of agents learning to play games against humans and beat them. In this article, we study the problem of training intelligent agents in service of game development. Unlike the agents built to “beat the game,” our agents aim to produce human-like behavior to help with game evaluation and balancing. We discuss two fundamental metrics based on which we measure the human-likeness of agents, namely skill and style, which are multifaceted concepts with practical implications outlined in this article. We report four case studies in which the style and skill requirements inform the choice of algorithms and metrics used to train agents; ranging from A* search to state-of-the-art deep reinforcement learning (RL). Furthermore, we, show that the learning potential of state-of-the-art deep RL models does not seamlessly transfer from the benchmark environments to target ones without heavily tuning their hyperparameters, leading to linear scaling of the engineering efforts, and computational cost with the number of target domains.

According to recent empirical studies, a majority of users have the same, or very similar, passwords across multiple password-secured online services. This practice can have disastrous consequences, as one password being compromised puts all the other accounts at much higher risk. Generally, an adversary may use any side-information he/she possesses about the user, be it demographic information, password reuse on a previously compromised account, or any other relevant information to devise a better brute-force strategy (so called targeted attack). In this work, we consider a distributed brute-force attack scenario in which m adversaries, each observing some side information, attempt breaching a password secured system. We compare two strategies: an uncoordinated attack in which the adversaries query the system based on their own side-information until they find the correct password, and a fully coordinated attack in which the adversaries pool their side-information and query the system together. For passwords X of length n, generated independently and identically from a distribution PX, we establish an asymptotic closed-form expression for the uncoordinated and coordinated strategies when the side-information Y(m) are generated independently from passing X through a memoryless channel PY|X, as the length of the password n goes to infinity. We illustrate our results for binary symmetric channels and binary erasure channels, two families of side-information channels which model password reuse. We demonstrate that two coordinated agents perform asymptotically better than any finite number of uncoordinated agents for these channels, meaning that sharing side-information is very valuable in distributed attacks.

We study the problem of mismatched guesswork, where we evaluate the number of symbols y ∈ Y which have higher likelihood than X ~ μ according to a mismatched distribution μ. We discuss the role of the tilted/exponential families of the source distribution μ and of the mismatched distribution ν. We show that the value of guesswork can be characterized using the tilted family of the mismatched distribution v, while the probability of guessing is characterized by an exponential family which passes through μ. Using this characterization, we demonstrate that the mismatched guesswork follows a large deviation principle (LDP), where the rate function is described implicitly using information theoretic quantities. We apply these results to one-to-one source coding (without prefix free constraint) to obtain the cost of mismatch in terms of average codeword length. We show that the cost of mismatch in one-to-one codes is no larger than that of the prefix-free codes, i.e., D(μ||ν). Further, the cost of mismatch vanishes if and only if ν lies on the tilted family of the true distribution μ, which is in stark contrast to the prefix-free codes. These results imply that one-to-one codes are inherently more robust to mismatch.

In September 2017, McAffee Labs quarterly report estimated that brute force attacks represent 20\% of total network attacks, making them the most prevalent type of attack ex-aequo with browser based vulnerabilities. These attacks have sometimes catastrophic consequences, and understanding their fundamental limits may play an important role in the risk assessment of password-secured systems, and in the design of better security protocols. While some solutions exist to prevent online brute-force attacks that arise from one single IP address, attacks performed by botnets are more challenging. In this paper, we analyze these distributed attacks by using a simplified model. Our aim is to understand the impact of distribution and asynchronization on the overall computational effort necessary to breach a system. Our result is based on Guesswork, a measure of the number of queries (guesses) required of an adversary before a correct sequence, such as a password, is found in an optimal attack. Guesswork is a direct surrogate for time and computational effort of guessing a sequence from a set of sequences with associated likelihoods. We model the lack of synchronization by a worst-case optimization in which the queries made by multiple adversarial agents are received in the worst possible order for the adversary, resulting in a min-max formulation. We show that, even without synchronization, and for sequences of growing length, the asymptotic optimal performance is achievable by using randomized guesses drawn from an appropriate distribution. Therefore, randomization is key for distributed asynchronous attacks. In other words, asynchronous guessers can asymptotically perform brute-force attacks as efficiently as synchronized guessers.

Given a collection of strings, each with an associated probability of occurrence, the guesswork of each of them is their position in a list ordered from most likely to least likely, breaking ties arbitrarily. The guesswork is central to several applications in information theory: average guesswork provides a lower bound on the expected computational cost of a sequential decoder to decode successfully the transmitted message; the complementary cumulative distribution function of guesswork gives the error probability in list decoding; the logarithm of guesswork is the number of bits needed in optimal lossless one-to-one source coding; and the guesswork is the number of trials required of an adversary to breach a password protected system in a brute-force attack. In this paper, we consider memoryless string sources that generate strings consisting of independent and identically distributed characters drawn from a finite alphabet, and characterize their corresponding guesswork. Our main tool is the tilt operation on a memoryless string source. We show that the tilt operation on a memoryless string source parametrizes an exponential family of memoryless string sources, which we refer to as the tilted family of the string source. We provide an operational meaning to the tilted families by proving that two memoryless string sources result in the same guesswork on all strings of all lengths if and only if their respective categorical distributions belong to the same tilted family. Establishing some general properties of the tilt operation, we generalize the notions of weakly typical set and asymptotic equipartition property to tilted weakly typical sets of different orders. We use this new definition to characterize the large deviations for all atypical strings and characterize the volume of tilted weakly typical sets of different orders. We subsequently build on this characterization to prove large deviation bounds on guesswork and provide an accurate approximation of its probability mass function.

Achieving highly detailed terrain models spanning vast areas is crucial to modern computer graphics. The pipeline for obtaining such terrains is via amplification of a low-resolution terrain to refine the details given a desired theme, which is a time-consuming and labor-intensive process. Recently, data-driven methods, such as the sparse construction tree, have provided a promising direction to equip the artist with better control over the theme. These methods learn to amplify terrain details by using an exemplar of high-resolution detailed terrains to transfer the theme. In this paper, we propose Generative Adversarial Terrain Amplification (GATA) that achieves better local/global coherence compared to the existing data-driven methods while providing even more ways to control the theme. GATA is comprised of two key ingredients. Thefi rst one is a novel embedding of themes into vectors of real numbers to achieve a single tool for multi-theme amplification. The theme component can leverage existing LIDAR data to generate similar terrain features. It can also generate newfi ctional themes by tuning the embedding vector or even encoding a new example terrain into an embedding. The second one is an adversarially trained model that, conditioned on an embedding and a low-resolution terrain, generates a high-resolution terrain adhering to the desired theme. The proposed integral approach reduces the need for unnecessary manual adjustments, can speed up the development, and brings the model quality to a new level. Our implementation of the proposed method has proved successful in large-scale terrain authoring for an open-world game.

The randomized-feature approach has been successfully employed in large-scale kernel approximation and supervised learning. The distribution from which the random features are drawn impacts the number of features required to efficiently perform a learning task. Recently, it has been shown that employing data-dependent randomization improves the performance in terms of the required number of random features. In this paper, we are concerned with the randomized-feature approach in supervised learning for good generalizability. We propose the Energy-based Exploration of Random Features (EERF) algorithm based on a data-dependent score function that explores the set of possible features and exploits the promising regions. We prove that the proposed score function with high probability recovers the spectrum of the best fit within the model class. Our empirical results on several benchmark datasets further verify that our method requires smaller number of random features to achieve a certain generalization error compared to the state-of-the-art while introducing negligible pre-processing overhead. EERF can be implemented in a few lines of code and requires no additional tuning parameters.

We study a notion of guesswork, where multiple agents intend to launch a coordinated brute-force attack to find a single binary secret string, and each agent has access to side information generated through either a BEC or a BSC. The average number of trials required to find the secret string grows exponentially with the length of the string, and the rate of the growth is called the guesswork exponent. We compute the guesswork exponent for several multi-agent attacks. We show that a multi-agent attack reduces the guesswork exponent compared to a single agent, even when the agents do not exchange information to coordinate their attack, and try to individually guess the secret string using a predetermined scheme in a decentralized fashion. Further, we show that the guesswork exponent of two agents who do coordinate their attack is strictly smaller than that of any finite number of agents individually performing decentralized guesswork.

We consider the parametric learning problem, where the objective of the learner is determined by a parametric loss function. Employing empirical risk minimization with possibly regularization, the inferred parameter vector will be biased toward the training samples. Such bias is measured by the cross validation procedure in practice where the data set is partitioned into a training set used for training and a validation set, which is not used in training and is left to measure the out-of-sample performance. A classical cross validation strategy is the leave-one-out cross validation (LOOCV) where one sample is left out for validation and training is done on the rest of the samples that are presented to the learner, and this process is repeated on all of the samples. LOOCV is rarely used in practice due to the high computational complexity. In this paper, we first develop a computationally efficient approximate LOOCV (ALOOCV) and provide theoretical guarantees for its performance. Then we use ALOOCV to provide an optimization algorithm for finding the regularizer in the empirical risk minimization framework. In our numerical experiments, we illustrate the accuracy and efficiency of ALOOCV as well as our proposed framework for the optimization of the regularizer.

An information-theoretic framework is presented for estimating the number of labeled samples needed to train a classifier in a parametric Bayesian setting. Ideas from rate-distortion theory are used to derive bounds for the average L1or L∞distance between the learned classifier and the true maximum a posteriori classifier in terms of familiar information-theoretic quantities and the number of training samples available. The maximum a posteriori classifier is viewed as a random source, labeled training data are viewed as a finite-rate encoding of the source, and the L1or L∞Bayes risk is viewed as the average distortion. The result is a framework dual to the well-known probably approximately correct (PAC) framework. PAC bounds characterize worst-case learning performance of a family of classifiers whose complexity is captured by the Vapnik-Chervonenkis (VC) dimension. The rate-distortion framework, on the other hand, characterizes the average-case performance of a family of data distributions in terms of a quantity called the interpolation dimension, which represents the complexity of the family of data distributions. The resulting bounds do not suffer from the pessimism typical of the PAC framework, particularly when the training set is small.

We consider large-scale linear inverse problems in Bayesian settings. Our general approach follows a recent line of work that applies the approximate message passing (AMP) framework in multi-processor (MP) computational systems by storing and processing a subset of rows of the measurement matrix along with corresponding measurements at each MP node. In each MP-AMP iteration, nodes of the MP system and its fusion center exchange lossily compressed messages pertaining to their estimates of the input. There is a trade-off between the physical costs of the reconstruction process including computation time, communication loads, and the reconstruction quality, and it is impossible to simultaneously minimize all the costs. We pose this minimization as a multi-objective optimization problem (MOP), and study the properties of the best trade-offs (Pareto optimality) in this MOP. We prove that the achievable region of this MOP is convex, and conjecture how the combined cost of computation and communication scales with the desired mean squared error. These properties are verified numerically.

The existence of considerable amount of redundancy in the Internet traffic at the packet level has stimulated the deployment of packet-level redundancy elimination techniques within the network by enabling network nodes to memorize data packets. Redundancy elimination results in traffic reduction which in turn improves the efficiency of network links. In this paper, the concept of network compression is introduced that aspires to exploit the statistical correlation beyond removing large duplicate strings from the flow to better suppress redundancy. In the first part of the paper, we introduce “memory-assisted compression,” which utilizes the memorized content within the network to learn the statistics of the information source generating the packets which can then be used toward reducing the length of codewords describing the packets emitted by the source. Using simulations on data gathered from real network traces, we show that memory-assisted compression can result in significant traffic reduction. In the second part of the paper, we study the scaling of the average network-wide benefits of memory-assisted compression. We discuss routing and memory placement problems in network for the reduction of overall traffic. We derive a closed-form expression for the scaling of the gain in Erdös-Rényi random network graphs, where obtain a threshold value for the number of memories deployed in a random graph beyond which network-wide benefits start to shine. Finally, the network-wide benefits are studied on Internet-like scale-free networks. We show that non-vanishing network compression gain is obtained even when only a tiny fraction of the total number of nodes in the network are memory-enabled.

Traces derived from real-world traffic show that significant redundancy exists at the packet level in mobile network traffic. This has inspired new solutions to suppress the redundancy present in the packet data to manage the explosive traffic. In this paper, we propose a novel approach to performing redundancy elimination by employing universal compression using memory-enabled overhearing helpers without backhaul connectivity, referred to as wireless network compression. The helpers overhear the data packets previously sent by the wireless gateway to various mobile clients within their coverage and use them as side information to reduce the overall communication cost. We study wireless network compression via overhearing helpers from an information-theoretic point of view and conclude that this approach potentially offers a threefold benefit: 1) offloading the wireless gateway and hence increasing the maximum number of mobile nodes the gateway can reliably serve; 2) reducing the average packet delay; and 3) improving the overall throughput in the network.

Guesswork forms the mathematical framework for quantifying computational security subject to brute-force determination by query. In this paper, we consider guesswork subject to a per-symbol Shannon entropy budget. We introduce inscrutability rate as the asymptotic rate of increase in the exponential number of guesses required of an adversary to determine one or more secret strings. We prove that the inscrutability rate of any string-source supported on a finite alphabet χ, if it exists, lies between the per-symbol Shannon entropy constraint and log |χ|. We further prove that the inscrutability rate of any finite-order Markov string-source with hidden statistics remains the same as the unhidden case, i.e., the asymptotic value of hiding the statistics per each symbol is vanishing. On the other hand, we show that there exists a string-source that achieves the upper limit on the inscrutability rate, i.e., log |χ|, under the same Shannon entropy budget.

We study the excess mean square error (EMSE) above the minimum mean square error (MMSE) in large linear systems where the posterior mean estimator (PME) is evaluated with a postulated prior that differs from the true prior of the input signal. We focus on large linear systems where the measurements are acquired via an independent and identically distributed random matrix, and are corrupted by additive white Gaussian noise (AWGN). The relationship between the EMSE in large linear systems and EMSE in scalar channels is derived, and closed form approximations are provided. Our analysis is based on the decoupling principle, which links scalar channels to large linear system analyses. Numerical examples demonstrate that our closed form approximations are accurate.

We consider a channel model based on the diffusion of particles in the medium which is motivated by the natural communication mechanisms between biological cells based on exchange of molecules. In this model, the transmitter secretes particles into the medium via a particle dissemination rate. The concentration of particles at any point in the medium is a function of its distance from the transmitter and the particle dissemination rate. The reception process is a doubly stochastic Poisson process whose rate is a function of the concentration of the particles in the vicinity of the receiver. We derive a closed-form for the mutual information between the input and output processes in this communication scenario and establish useful properties about the mutual information. We also provide a signaling strategy using which we derive a lower bound on the capacity of the diffusion channel with Poisson reception process under average and peak power constraints. Furthermore, it is shown that the capacity of discretized diffusion channel can be a negligible factor of the capacity of continuous time diffusion channel. Finally, the application of the considered model to the molecular communication systems is discussed.

Rapid growth of emerging medical applications such as e-health and tele-medicine requires fast, low cost, and often lossless access to massive amount of medical images and data over bandlimited channels. In this paper, we first show that significant amount of correlation and redundancy exist across different medical images. Such a correlation can be utilized to achieve better compression, and consequently less storage and less communication overhead on the network. We propose a novel memory-assisted compression technique, as a learning-based universal coding, which can be used to complement any existing algorithm to further eliminate redundancies across images. The approach is motivated by the fact that, often in medical applications, massive amount of correlated images from the same family are available as training data for learning the dependencies and deriving appropriate reference models. Such models can then be used for compression of any new image from the same family. In particular, Principal Component Analysis (PCA) is applied on a set of images from training data to form the required reference models. The proposed memory-assisted compression allows each image to be processed independently of other images, and hence allows individual image access and transmission. Experimental results on X-ray images show that the proposed algorithm achieves 20% improvement over and above traditional lossless image compression methods reported in the literature.

Recently, we proposed wireless network compression via memory-enabled overhearing helpers as an endeavor to reduce the traffic load on the wireless gateway via elimination of the redundant data in the network. In this setup, each memory-enabled helper overhears the data packets previously sent by the wireless gateway to various mobile clients within its coverage and uses them toward forming a model about the content of the packets from the traffic. The resulting model is then used as side information by the wireless network compression module in a two-part code to reduce the overall cost of delivering a packet to a client over links with asymmetric cost (where the helper-client link is far less costly than the gateway-client link). One main challenge in this scenario is the fact that memory-enabled overhearing helpers do not receive all of the sequences sent to the mobile clients (as there is no feedback in place in the overhearing link), resulting in mismatched side information between the encoder (i.e., gateway) and the helper. In this paper, we present an information theoretic formulation for the mismatched side information problem. We study this problem in the context of universal lossless compression and derive bounds on the average minimax redundancy of encoding each packet. Our results also lead to construction of coding schemes for the mismatched side information using two-part codes.

In this paper, the problem of universal lossless one-to-one compression (without prefix constraint) is studied. A converse bound is obtained on the average minimax (and maximin) redundancy that shows the redundancy is at least (d-2)=2 log n+O(1) for the universal compression of a sequence of length n from a d-dimensional parametric source. Further, the type-size coding strategy is shown to be minimax optimal up to o(log n) for the class of memoryless sources, achieving the converse leading to characterization of the fundamental performance limit of universal compression for memoryless sources. Finally, through a numerical example, our results imply that the reduction on the codeword length due to relaxing the prefix constraint is negligible when compared to the cost of universality.

Recent studies have shown the existence of considerable amount of packet-level redundancy in the network flows. Since application-layer solutions cannot capture the packet-level redundancy, development of new content-aware approaches capable of redundancy elimination at the packet and sub-packet levels is necessary. These requirements motivate the redundancy elimination of packets from an information-theoretic point of view. For efficient compression of packets, a new framework called memory-assisted universal compression has been proposed. This framework is based on learning the statistics of the source generating the packets at some intermediate nodes and then leveraging these statistics to effectively compress a new packet. This paper investigates both theoretically and experimentally the memory-assisted compression of network packets. Clearly, a simple source cannot model the data traffic. Hence, we consider traffic from a complex source that is consisted of a mixture of simple information sources for our analytic study. We develop a practical code for memory-assisted compression and combine it with a proposed hierarchical clustering to better utilize the memory. Finally, we validate our results via simulation on real traffic traces. Memory-assisted compression combined with hierarchical clustering method results in compression of packets close to the fundamental limit. As a result, we report a factor of two improvement over traditional end-to-end compression.

The problem of the universal compression of a sequence from a library of several small to moderate length sequences from similar context arises in many practical scenarios, such as the compression of the storage data and the Internet traffic. In such scenarios, it is often required to compress and decompress every sequence individually. However, the universal compression of the individual sequences suffers from significant redundancy overhead. In this paper, we aim at answering whether or not having a memory unit in the middle can result in a fundamental gain in the universal compression. We present the problem setup in the most basic scenario consisting of a server node S, a relay node R (i.e., the memory unit), and a client node C.

Recently, the existence of considerable amount of redundancy in the Internet traffic has stimulated the deployment of several redundancy elimination techniques within the network. These techniques are often based on either packet-level Redundancy Elimination (RE) or Content-Centric Networking (CCN). However, these techniques cannot exploit sub-packet redundancies. Further, other alternative techniques such as the end-to-end universal compression solutions would not perform well either over the Internet traffic, as such techniques require infinite length traffic to effectively remove redundancy. This paper proposes a memory-assisted universal compression technique that holds a significant promise for reducing the amount of traffic in the networks. The proposed work is based on the observation that if a source is to be compressed and sent over a network, the associated universal code entails a substantial overhead in transmission due to finite length traffic. However, intermediate nodes can learn the source statistics and this can be used to reduce the cost of describing the source statistics, reducing the transmission overhead for such traffics. We present two algorithms (statistical and dictionary-based) for the memory-assisted universal lossless compression of information sources. These schemes are universal in the sense that they do not require any prior knowledge of the traffic's statistical distribution. We demonstrate the effectiveness of both algorithms and characterize the memorization gain using the real Internet traces. Furthermore, we apply these compression schemes to Internet-like power-law graphs and solve the routing problem for compressed flows. We characterize the network-wide gain of the memorization from the information theoretic point of view. In particular, through our analysis on power-law graphs, we show that non-vanishing network-wide gain of memorization is obtained even when the number of memory units is a tiny fraction of the total number of nodes in the network. Finally, we validate our predictions of the memorization gain by simulation on real traffic traces.

Slepian-Wolf theorem is a well-known framework that targets almost lossless compression of (two) data streams with symbol-by-symbol correlation between the outputs of (two) distributed sources. However, this paper considers a different scenario which does not fit in the Slepian-Wolf framework. We consider two identical but spatially separated sources. We wish to study the universal compression of a sequence of length n from one of the sources provided that the decoder has access to (i.e., memorized) a sequence of length m from the other source. Such a scenario occurs, for example, in the universal compression of data from multiple mirrors of the same server. In this setup, the correlation does not arise from symbol-by-symbol dependency of two outputs from the two sources. Instead, the sequences are correlated through the information that they contain about the unknown source parameter. We show that the finite-length nature of the compression problem at hand requires considering a notion of almost lossless source coding, where coding incurs an error probability pe(n) that vanishes with sequence length n. We obtain a lower bound on the average minimax redundancy of almost lossless codes as a function of the sequence length n and the permissible error probability pewhen the decoder has a memory of length m and the encoders do not communicate. Our results demonstrate that a strict performance loss is incurred when the two encoders do not communicate even when the decoder knows the unknown parameter vector (i.e., m → ∞).

Many applications require data processing to be performed on individual pieces of data which are of finite sizes, e.g., files in cloud storage units and packets in data networks. However, traditional universal compression solutions would not perform well over the finite-length sequences. Recently, we proposed a framework called memory-assisted universal compression that holds a significant promise for reducing the amount of redundant data from the finite-length sequences. The proposed compression scheme is based on the observation that it is possible to learn source statistics (by memorizing previous sequences from the source) at some intermediate entities and then leverage the memorized context to reduce redundancy of the universal compression of finite-length sequences. We first present the fundamental gain of the proposed memory-assisted universal source coding over conventional universal compression (without memorization) for a single parametric source. Then, we extend and investigate the benefits of the memory-assisted universal source coding when the data sequences are generated by a compound source which is a mixture of parametric sources. We further develop a clustering technique within the memory-assisted compression framework to better utilize the memory by classifying the observed data sequences from a mixture of parametric sources. Finally, we demonstrate through computer simulations that the proposed joint memorization and clustering technique can achieve up to 6-fold improvement over the traditional universal compression technique when a mixture of non-binary Markov sources is considered.

In this paper, we investigate the redundancy in the universal compression of finite length smooth parametric sources. Rissanen demonstrated that for a smooth parametric source with d unknown parameters, the expected redundancy for regular codes is asymp totically given by | logn + o(logn) for almost all sources. Clarke and Barron derived the "minimax expected redundancy" for memoryless sources, which is the maximum redundancy of the best code over the space of source parameters. However, the minimax redundancy is for a particular parameter value, which does not provide much insight about different source parameters. We derived a lower bound on the compression of finite-length memoryless sequences using a probabilistic treatment. In this paper, we extend our analysis to smooth parametric sequences. We focus on two part codes with an asymptotic 0(1) extra redundancy. We also require that the length function be regular, which is not restrictive since all codes that we know are regular.

In this paper, we investigate the redundancy of universal coding schemes on smooth parametric sources in the finite-length regime. We derive an upper bound on the probability of the event that a sequence of length n, chosen using Jeffreys' prior from the family of parametric sources with d unknown parameters, is compressed with a redundancy smaller than (1 - ∈) d/2 log n for any ∈ >; 0. Our results also confirm that for large enough n and d, the average minimax redundancy provides a good estimate for the redundancy of most sources. Our result may be used to evaluate the performance of universal source coding schemes on finite-length sequences. Additionally, we precisely characterize the minimax redundancy for two-stage codes. We demonstrate that the two-stage assumption incurs a negligible redundancy especially when the number of source parameters is large. Finally, we show that the redundancy is significant in the compression of small sequences.

In diffusion-based molecular communications, messages can be conveyed via the variation in the concentration of molecules in the medium. In this paper, we intend to analyze the achievable capacity in transmission of information from one node to another in a diffusion channel. We observe that because of the molecular diffusion in the medium, the channel possesses memory. We then model the memory of the channel by a two-step Markov chain and obtain the equations describing the capacity of the diffusion channel. By performing a numerical analysis, we obtain the maximum achievable rate for different levels of the transmitter power, i.e., the molecule production rate.

Several studies have identified a significant amount of redundancy in the network traffic. For example, it is demonstrated that there is a great amount of redundancy within the content of a server over time. This redundancy can be leveraged to reduce the network flow by the deployment of memory units in the network. The question that arises is whether or not the deployment of memory can result in a fundamental improvement in the performance of the network. In this paper, we answer this question affirmatively by first establishing the fundamental gains of memory-assisted source compression and then applying the technique to a network. Specifically, we investigate the gain of memory-assisted compression in random network graphs consisted of a single source and several randomly selected memory units. We find a threshold value for the number of memories deployed in a random graph and show that if the number of memories exceeds the threshold we observe network-wide reduction in the traffic.

In this paper, we present an exact model for the analysis of the performance of Random Linear Network Coding (RLNC) in wired erasure networks with finite buffers. In such networks, packets are delayed due to either random link erasures or blocking by full buffers. We assert that because of RLNC, the content of buffers have dependencies which cannot be captured directly using the classical queueing theoretical models. We model the performance of the network using Markov chains by a careful derivation of the buffer occupancy states and their transition rules. We verify by simulations that the proposed framework results in an accurate measure of the network throughput offered by RLNC. Further, we introduce a class of acyclic networks for which the number of state variables is significantly reduced.