As the era of autonomous agents making decisions on behalf of users unfolds, ensuring contextual integrity (CI) -- what is the appropriate information to share while carrying out a certain task -- becomes a central question to the field. We posit that CI demands a form of reasoning where the agent needs to reason about the context in which it is operating. To test this, we first prompt LLMs to reason explicitly about CI when deciding what information to disclose. We then extend this approach by developing a reinforcement learning (RL) framework that further instills in models the reasoning necessary to achieve CI. Using a synthetic, automatically created, dataset of only $\sim700$ examples but with diverse contexts and information disclosure norms, we show that our method substantially reduces inappropriate information disclosure while maintaining task performance across multiple model sizes and families. Importantly, improvements transfer from this synthetic dataset to established CI benchmarks such as PrivacyLens that has human annotations and evaluates privacy leakage of AI assistants in actions and tool calls.

We study the problem of in-context learning (ICL) with large language models (LLMs) on private datasets. This scenario poses privacy risks, as LLMs may leak or regurgitate the private examples demonstrated in the prompt. We propose a novel algorithm that generates synthetic few-shot demonstrations from the private dataset with formal differential privacy (DP) guarantees, and show empirically that it can achieve effective ICL. We conduct extensive experiments on standard benchmarks and compare our algorithm with non-private ICL and zero-shot solutions. Our results demonstrate that our algorithm can achieve competitive performance with strong privacy levels. These results open up new possibilities for ICL with privacy protection for a broad range of applications.

Positioned between pre-training and user deployment, aligning large language models (LLMs) through reinforcement learning (RL) has emerged as a prevailing strategy for training instruction following-models such as ChatGPT. In this work, we initiate the study of privacy-preserving alignment of LLMs through Differential Privacy (DP) in conjunction with RL. Following the influential work of Ziegler et al. (2020), we study two dominant paradigms: (i) alignment via RL without human in the loop (e.g., positive review generation) and (ii) alignment via RL from human feedback (RLHF) (e.g., summarization in a human-preferred way). We give a new DP framework to achieve alignment via RL, and prove its correctness. Our experimental results validate the effectiveness of our approach, offering competitive utility while ensuring strong privacy protections.

Text data has become extremely valuable due to the emergence of machine learning algorithms that learn from it. A lot of high-quality text data generated in the real world is private and therefore cannot be shared or used freely due to privacy concerns. Generating synthetic replicas of private text data with a formal privacy guarantee, i.e., differential privacy (DP), offers a promising and scalable solution. However, existing methods necessitate DP finetuning of large language models (LLMs) on private data to generate DP synthetic data. This approach is not viable for proprietary LLMs (e.g., GPT-3.5) and also demands considerable computational resources for open-source LLMs. Lin et al. (2024) recently introduced the Private Evolution (PE) algorithm to generate DP synthetic images with only API access to diffusion models. In this work, we propose an augmented PE algorithm, named Aug-PE, that applies to the complex setting of text. We use API access to an LLM and generate DP synthetic text without any model training. We conduct comprehensive experiments on three benchmark datasets. Our results demonstrate that Aug-PE produces DP synthetic text that yields competitive utility with the SOTA DP finetuning baselines. This underscores the feasibility of relying solely on API access of LLMs to produce high-quality DP synthetic texts, thereby facilitating more accessible routes to privacy-preserving LLM applications.

Xiang Yue, Huseyin Inan, Xuechen Li, Girish Kumar, Julia McAnallen, Hoda Shajari, Huan Sun, David Levitan, Robert Sim. Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2023.

Large pretrained models can be fine-tuned with differential privacy to achieve performance approaching that of non-private models. A common theme in these results is the surprising observation that high-dimensional models can achieve favorable privacy-utility trade-offs. This seemingly contradicts known results on the model-size dependence of differentially private convex learning and raises the following research question: When does the performance of differentially private learning not degrade with increasing model size? We identify that the magnitudes of gradients projected onto subspaces is a key factor that determines performance. To precisely characterize this for private convex learning, we introduce a condition on the objective that we term restricted Lipschitz continuity and derive improved bounds for the excess empirical and population risks that are dimension- independent under additional conditions. We empirically show that in private fine-tuning of large language models, gradients obtained during fine-tuning are mostly controlled by a few principal components. This behavior is similar to conditions under which we obtain dimension-independent bounds in convex settings. Our theoretical and empirical results together provide a possible explanation for the recent success of large-scale private fine-tuning. Code to reproduce our results can be found at https://github.com/lxuechen/private-transformers/tree/main/examples/classification/spectral_analysis.

Recent papers have shown that large pre-trained language models (LLMs) such as BERT, GPT-2 can be fine-tuned on private data to achieve performance comparable to non-private models for many downstream Natural Language Processing (NLP) tasks while simultaneously guaranteeing differential privacy. The inference cost of these models -- which consist of hundreds of millions of parameters -- however, can be prohibitively large. Hence, often in practice, LLMs are compressed before they are deployed in specific applications. In this paper, we initiate the study of differentially private model compression and propose frameworks for achieving 50% sparsity levels while maintaining nearly full performance. We demonstrate these ideas on standard GLUE benchmarks using BERT models, setting benchmarks for future research on this topic.

Fatemehsadat Mireshghallah, Huseyin Inan, Marcello Hasegawa, Victor Rühle, Taylor Berg-Kirkpatrick, Robert Sim. Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2021.

We consider the non-adaptive probabilistic group testing problem where d random defective items are identified with high probability from a population of N items by applying t binary group tests. There has been recent progress towards developing explicit and efficiently decodable group testing schemes with t = Θ(dlogN) tests, which is known to be order-optimal for this setting when d = O(N1-α) for some constant α > 0. In particular, a recent work develops an explicit scheme while another one develops an efficiently decodable scheme for this setting, both with the order-optimal t = Θ(dlogN) tests. However, to the best of our knowledge, there is no order-optimal scheme that is both explicit and efficiently decodable. In this paper, we close this gap by introducing the first (strongly) explicit and efficiently decodable construction that is order-optimal for the non-adaptive probabilistic group testing problem.

In combinatorial group testing, the primary objective is to fully identify the set of at most d defective items from a pool of n items using as few tests as possible. The celebrated result for the combinatorial group testing problem is that the number of tests, denoted by t, can be made logarithmic in n when d = O(poly(log n)). However, state-of-the-art group testing codes require the items to be tested w = Ω (d log n)/[(q log d+log log n)] times and tests to include p = Ω (n/(d logdn)) items. In many emerging applications, items can only participate in a limited number of tests and tests are constrained to include a limited number of items. In this paper, we study the “sparse” regime for the group testing problem where we restrict the number of tests each item can participate in by wmaxor the number of items each test can include by pmaxin both noiseless and noisy settings. These constraints lead to a largely unexplored regime where t is a fractional power of n, rather than logarithmic in n as in the classical setting. Our results characterize the number of tests t needed in this regime as a function of wmax or pmax and show, for example, that t decreases drastically when wmax is increased beyond a bare minimum. In particular, in the noiseless case it can be shown that if wmax≤ d, then we must have t = n, i.e., testing every item individually is optimal. We show that if wmax= d+1, the number of tests decreases suddenly from t = n to t = Θ(d√n). The order-optimal construction is obtained via a modification of the classical Kautz-Singleton construction, which is known to be suboptimal for the classical group testing problem. For the more general case, when wmax= ld + 1 for integer l > 1, the modified Kautz-Singleton construction requires t = Θ(dn1/(l+1)) tests, which we prove to be near order-optimal. We also show that our constructions have a favorable encoding and decoding complexity, i.e. they can be decoded in (poly(d) + O(t))-time and each entry in any codeword can be computed in poly(log n) memory space. We finally discuss an application of our results to the construction of energy-limited random access schemes for Internet of Things networks, which provided the initial motivation for our work.

We propose a grant-free random access scheme for short-packet communication on a collision channel without feedback, where user identities are conveyed through their activity patterns. We show that this problem is inherently related to the non-adaptive group testing problem, where the goal is to identify a small subset of defective items within a larger population, using as few (pre-determined) tests as possible. In the frame-synchronous case, where users' transmissions are aligned, we find that any solution to the non-adaptive group testing problem is also a solution to the random access problem. Similar connections to group testing are identified in the asynchronous variant of the problem, in which case users' transmissions within a frame are received with arbitrary and unknown delays at the receiver. We show that such delays can be accommodated without any additional penalty with respect to the scaling of the transmission length, and that in the regime where the data payload is small, the performance of the proposed random access scheme comes close to that of fully coordinated access schemes.

We consider the probabilistic group testing problem where d random defective items in a large population of N items are identified with high probability by applying binary tests. It is known that the Θ(d log N) tests are necessary and sufficient to recover the defective set with vanishing probability of error when d = O(Nα) for some α ∈ (0, 1). However, to the best of our knowledge, there is no explicit (deterministic) construction achieving Θ(d log N) tests in general. In this paper, we show that a famous construction introduced by Kautz and Singleton for the combinatorial group testing problem (which is known to be suboptimal for combinatorial group testing for moderate values of d) achieves the order optimal Θ(d log N) tests in the probabilistic group testing problem when d = Ω(log2N). This provides a strongly explicit construction achieving the order optimal result in the probabilistic group testing setting for a wide range of values of d. To prove the order-optimality of Kautz and Singleton's construction in the probabilistic setting, we provide a novel analysis of the probability of a non-defective item being covered by a random defective set directly, rather than arguing from combinatorial properties of the underlying code, which has been the main approach in the literature. Furthermore, we use a recursive technique to convert this construction into one that can also be efficiently decoded with only a log-log factor increase in the number of tests.

We consider a random access scheme with a massive number of low-energy wireless devices, where a small but arbitrary subset of them can be active at a given time. We develop a solution to this problem via the noisy group testing framework, where the goal is to identify with high probability a small set of defectives in a large set of items with minimum number of noisy binary tests. We translate the power constraint for the wireless devices to a constraint on the number of tests each item can participate in the group testing problem. We present fundamental upper and lower bounds on the length of the codewords in terms of the total number of devices, the number of active devices, the error probability, the noise and the power constraint. We conclude with a scheme that enjoys low decoding complexity under this model.

We consider an energy harvesting multiple access channel where the transmitters are powered by an exogenous stochastic energy harvesting process and equipped with finite batteries. We characterize the capacity region of this channel as n-letter mutual information rate and develop inner and outer bounds that differ by a constant gap. An interesting conclusion that emerges from our results is that in a symmetric system, where transmitters are statistically equivalent to each other, the largest achievable common rate point approaches that of a standard AWGN MAC with an average power constraint, as the number of users in the MAC becomes large.

We consider online power control for a K-user energy harvesting multiple-access channel (MAC). We show that a simple online power control policy that requires each user to know only the mean of its own energy harvesting process and does not require any information regarding the energy harvesting processes of the other users is near optimal for any joint distribution of the energy harvesting processes and for arbitrary battery sizes at the K users. In particular, for any parameter values this strategy achieves a throughput region which is within a constant gap to the capacity region of the classical additive white Gaussian noise (AWGN) MAC. When the number of users in the MAC becomes large, the gap becomes negligible. Therefore, an interesting consequence of our result is that in the limit when the number of users becomes large, the sum throughput of the online energy harvesting MAC approaches the sum capacity of the classical AWGN MAC. While it has been known that the online throughput of an energy harvesting system can approach the AWGN capacity in the limit when the battery size goes to infinity, it is interesting that the AWGN capacity can be also approached in limit of large number of users.

Bounded component analysis (BCA) is a framework that can be considered as a more general framework than independent component analysis (ICA) under the boundedness constraint on sources. Using this framework, it is possible to separate dependent as well as independent components from their mixtures. In this paper, as an extension of a recently introduced instantaneous BCA approach, we introduce a family of convolutive BCA criteria and corresponding algorithms. We prove that the global optima of the proposed criteria, under generic BCA assumptions, are equivalent to a set of perfect separators. The algorithms introduced in this paper are capable of separating not only the independent sources but also the sources that are dependent/correlated in both component (space) and sample (time) dimensions. Therefore, under the condition that the sources are bounded, they can be considered as extended convolutive ICA algorithms with additional dependent/correlated source separation capability. Furthermore, they have potential to provide improvement in separation performance, especially for short data records. This paper offers examples to illustrate the space-time correlated source separation capability through a copula distribution-based example. In addition, a frequency-selective Multiple Input Multiple Output equalization example demonstrates the clear performance advantage of the proposed BCA approach over the state-of-the-art ICA-based approaches in setups involving convolutive mixtures of digital communication sources.

Bounded Component Analysis is a new framework for Blind Source Separation problem. It allows separation of both dependent and independent sources under the assumption about the magnitude boundedness of sources. This article proposes a novel Bounded Component Analysis optimization setting for the separation of the convolutive mixtures of sources as an extension of a recent geometric framework introduced for the instantaneous mixing problem. It is shown that the global maximizers of this setting are perfect separators. The article also provides the iterative algorithm corresponding to this setting and the numerical examples to illustrate its performance especially for separating convolutive mixtures of sources that are correlated in both space and time dimensions.

We investigate affinely constrained mixture methods adaptively combining outputs of m constituent filters running in parallel to model a desired signal. We use Bregman divergences and obtain multiplicative updates to train these linear combination weights under the affine constraints. We use the unnormalized relative entropy and the relative entropy that produce the exponentiated gradient update with unnormalized weights (EGU) and the exponentiated gradient update with positive and negative weights (EG), respectively. We carry out the mean and the mean-square transient analysis of the affinely constrained mixtures of m filters using the EGU or EG algorithms. We compare performances of different algorithms through our simulations and illustrate the accuracy of our results.