Sivakanth Gopi

STOC Conference 2025 Conference Paper

Tensor Concentration Inequalities: A Geometric Approach

• Afonso S. Bandeira
• Sivakanth Gopi
• Haotian Jiang
• Kevin Lucca
• Thomas Rothvoss

Matrix concentration inequalities, commonly used in the forms of non-commutative Khintchine inequalities or matrix Chernoff bounds, are central to a wide range of applications in computer science and mathematics. However, they fall short in many applications where tensor versions of these inequalities are needed. In this work, we study the ℓ p injective norms of sums of independent tensors. We obtain the first non-trivial concentration inequalities in this setting, and our inequalities are nearly tight in certain regimes of p and the order of the tensors. Previously, tensor concentration inequalities were known only in the special cases of rank-1 tensors or p =2. Our results are obtained via a geometric argument based on estimating the covering numbers for the natural stochastic processes corresponding to tensor injective norms. Our approach is quite general and might be applicable to other settings of matrix and tensor concentration. We discuss applications and connections of our inequalities to various other problems, including tensor principle component analysis, various models of random tensors and matrices, type-2 constants of certain Banach spaces, and locally decodable codes.

STOC Conference 2024 Conference Paper

AG Codes Achieve List Decoding Capacity over Constant-Sized Fields

• Joshua Brakensiek
• Manik Dhar
• Sivakanth Gopi
• Zihan Zhang 0001

The recently-emerging field of higher order MDS codes has sought to unify a number of concepts in coding theory. Such areas captured by higher order MDS codes include maximally recoverable (MR) tensor codes, codes with optimal list-decoding guarantees, and codes with constrained generator matrices (as in the GM-MDS theorem). By proving these equivalences, Brakensiek-Gopi-Makam showed the existence of optimally list-decodable Reed-Solomon codes over exponential sized fields. Building on this, recent breakthroughs by Guo-Zhang and Alrabiah-Guruswami-Li have shown that randomly punctured Reed-Solomon codes achieve list-decoding capacity (which is a relaxation of optimal list-decodability) over linear size fields. We extend these works by developing a formal theory of relaxed higher order MDS codes. In particular, we show that there are two inequivalent relaxations which we call lower and upper relaxations. The lower relaxation is equivalent to relaxed optimal list-decodable codes and the upper relaxation is equivalent to relaxed MR tensor codes with a single parity check per column. We then generalize the techniques of Guo-Zhang and Alrabiah-Guruswami-Li to show that both these relaxations can be constructed over constant size fields by randomly puncturing suitable algebraic-geometric codes. For this, we crucially use the generalized GM-MDS theorem for polynomial codes recently proved by Brakensiek-Dhar-Gopi. We obtain the following corollaries from our main result: Randomly punctured algebraic-geometric codes of rate R are list-decodable up to radius L / L +1(1− R −є) with list size L over fields of size exp( O ( L /є)). In particular, they achieve list-decoding capacity with list size O (1/є) and field size exp( O (1/є 2 )). Prior to this work, AG codes were not even known to achieve list-decoding capacity. By randomly puncturing algebraic-geometric codes, we can construct relaxed MR tensor codes with a single parity check per column over constant-sized fields, whereas (non-relaxed) MR tensor codes require exponential field size.

ICLR Conference 2024 Conference Paper

Differentially Private Synthetic Data via Foundation Model APIs 1: Images

• Zinan Lin 0001
• Sivakanth Gopi
• Janardhan Kulkarni
• Harsha Nori
• Sergey Yekhanin

Generating differentially private (DP) synthetic data that closely resembles the original private data is a scalable way to mitigate privacy concerns in the current data-driven world. In contrast to current practices that train customized models for this task, we aim to generate DP Synthetic Data via APIs (DPSDA), where we treat foundation models as blackboxes and only utilize their inference APIs. Such API-based, training-free approaches are easier to deploy as exemplified by the recent surge in the number of API-based apps. These approaches can also leverage the power of large foundation models which are only accessible via their inference APIs. However, this comes with greater challenges due to strictly more restrictive model access and the need to protect privacy from the API provider. In this paper, we present a new framework called Private Evolution (PE) to solve this problem and show its initial promise on synthetic images. Surprisingly, PE can match or even outperform state-of-the-art (SOTA) methods without any model training. For example, on CIFAR10 (with ImageNet as the public data), we achieve FID ≤ 7.9 with privacy cost ε = 0.67, significantly improving the previous SOTA from ε = 32. We further demonstrate the promise of applying PE on large foundation models such as Stable Diffusion to tackle challenging private datasets with a small number of high-resolution images. The code and data are released at https://github.com/microsoft/DPSDA.

ICML Conference 2024 Conference Paper

Differentially Private Synthetic Data via Foundation Model APIs 2: Text

• Chulin Xie
• Zinan Lin 0001
• Arturs Backurs
• Sivakanth Gopi
• Da Yu
• Huseyin A. Inan
• Harsha Nori
• Haotian Jiang

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.

STOC Conference 2024 Conference Paper

Generalized GM-MDS: Polynomial Codes Are Higher Order MDS

• Joshua Brakensiek
• Manik Dhar
• Sivakanth Gopi

The GM-MDS theorem, conjectured by Dau-Song-Dong-Yuen and proved by Lovett and Yildiz-Hassibi, shows that the generator matrices of Reed-Solomon codes can attain every possible configuration of zeros for an MDS code. The recently emerging theory of higher order MDS codes has connected the GM-MDS theorem to other important properties of Reed-Solomon codes, including showing that Reed-Solomon codes can achieve list decoding capacity, even over fields of size linear in the message length. A few works have extended the GM-MDS theorem to other families of codes, including Gabidulin and skew polynomial codes. In this paper, we generalize all these previous results by showing that the GM-MDS theorem applies to any polynomial code, i.e., a code where the columns of the generator matrix are obtained by evaluating linearly independent polynomials at different points. We also show that the GM-MDS theorem applies to dual codes of such polynomial codes, which is non-trivial since the dual of a polynomial code may not be a polynomial code. More generally, we show that GM-MDS theorem also holds for algebraic codes (and their duals) where columns of the generator matrix are chosen to be points on some irreducible variety which is not contained in a hyperplane through the origin. Our generalization has applications to constructing capacity-achieving list-decodable codes as shown in a follow-up work [Brakensiek, Dhar, Gopi, Zhang; 2024], where it is proved that randomly punctured algebraic-geometric (AG) codes achieve list-decoding capacity over constant-sized fields.

ICLR Conference 2024 Conference Paper

Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation

• Xinyu Tang 0003
• Richard Shin
• Huseyin A. Inan
• Andre Manoel
• Niloofar Mireshghallah
• Zinan Lin 0001
• Sivakanth Gopi
• Janardhan Kulkarni

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.

TMLR Journal 2024 Journal Article

Selective Pre-training for Private Fine-tuning

• Da Yu
• Sivakanth Gopi
• Janardhan Kulkarni
• Zinan Lin
• Saurabh Naik
• Tomasz Lukasz Religa
• Jian Yin
• Huishuai Zhang

Text prediction models, when used in applications like email clients or word processors, must protect user data privacy and adhere to model size constraints. These constraints are crucial to meet memory and inference time requirements, as well as to reduce inference costs. Building small, fast, and private domain-specific language models is a thriving area of research. In this work, we show that a careful pre-training on a subset of the public dataset that is guided by the private dataset is crucial to train small language models with differential privacy. On standard benchmarks, small models trained with our new framework achieve state-of-the-art performance. In addition to performance improvements, our results demonstrate that smaller models, through careful pre-training and private fine-tuning, can match the performance of much larger models that do not have access to private data. This underscores the potential of private learning for model compression and enhanced efficiency.

STOC Conference 2023 Conference Paper

Generic Reed-Solomon Codes Achieve List-Decoding Capacity

• Joshua Brakensiek
• Sivakanth Gopi
• Visu Makam

In a recent paper, Brakensiek, Gopi and Makam introduced higher order MDS codes as a generalization of MDS codes. An order-ℓ MDS code, denoted by MDS(ℓ), has the property that any ℓ subspaces formed from columns of its generator matrix intersect as minimally as possible. An independent work by Roth defined a different notion of higher order MDS codes as those achieving a generalized singleton bound for list-decoding. In this work, we show that these two notions of higher order MDS codes are (nearly) equivalent. We also show that generic Reed-Solomon codes are MDS(ℓ) for all ℓ, relying crucially on the GM-MDS theorem which shows that generator matrices of generic Reed-Solomon codes achieve any possible zero pattern. As a corollary, this implies that generic Reed-Solomon codes achieve list decoding capacity. More concretely, we show that, with high probability, a random Reed-Solomon code of rate R over an exponentially large field is list decodable from radius 1− R −є with list size at most (1− R −є)/є, resolving a conjecture of Shangguan and Tamo.

SODA Conference 2023 Conference Paper

Private Convex Optimization in General Norms

• Sivakanth Gopi
• Yin Tat Lee
• Daogao Liu
• Ruoqi Shen
• Kevin Tian

We propose a new framework for differentially private optimization of convex functions which are Lipschitz in an arbitrary norm ||·|| x. Our algorithms are based on a regularized exponential mechanism which samples from the density ∞ exp(- k ( F + μ r )) where F is the empirical loss and τ is a regularizer which is strongly convex with respect to ||·|| x, generalizing a recent work of [GLL22] to non-Euclidean settings. We show that this mechanism satisfies Gaussian differential privacy and solves both DP-ERM (empirical risk minimization) and DP-SCO (stochastic convex optimization), by using localization tools from convex geometry. Our framework is the first to apply to private convex optimization in general normed spaces, and directly recovers non-private SCO rates achieved by mirror descent, as the privacy parameter ε → ∞. As applications, for Lipschitz optimization in ℓ p norms for all p ∈ (1, 2), we obtain the first optimal privacy-utility tradeoffs; for p = 1, we improve tradeoffs obtained by the recent works [AFKT21, BGN21] by at least a logarithmic factor. Our ℓ p norm and Schatten-p norm optimization frameworks are complemented with polynomial-time samplers whose query complexity we explicitly bound.

ICLR Conference 2022 Conference Paper

Differentially Private Fine-tuning of Language Models

• Da Yu
• Saurabh Naik
• Arturs Backurs
• Sivakanth Gopi
• Huseyin A. Inan
• Gautam Kamath 0001
• Janardhan Kulkarni
• Yin Tat Lee

We give simpler, sparser, and faster algorithms for differentially private fine-tuning of large-scale pre-trained language models, which achieve the state-of-the-art privacy versus utility tradeoffs on many standard NLP tasks. We propose a meta-framework for this problem, inspired by the recent success of highly parameter-efficient methods for fine-tuning. Our experiments show that differentially private adaptations of these approaches outperform previous private algorithms in three important dimensions: utility, privacy, and the computational and memory cost of private training. On many commonly studied datasets, the utility of private models approaches that of non-private models. For example, on the MNLI dataset we achieve an accuracy of $87.8\%$ using RoBERTa-Large and $83.5\%$ using RoBERTa-Base with a privacy budget of $\epsilon = 6.7$. In comparison, absent privacy constraints, RoBERTa-Large achieves an accuracy of $90.2\%$. Our findings are similar for natural language generation when privately fine-tuning GPT-2. Our experiments also show that larger models are better suited for private fine-tuning: while they are well known to achieve superior accuracy non-privately, we find that they also better maintain their accuracy when privacy is introduced.

NeurIPS Conference 2021 Conference Paper

Differentially Private n-gram Extraction

• Kunho Kim
• Sivakanth Gopi
• Janardhan Kulkarni
• Sergey Yekhanin

We revisit the problem of $n$-gram extraction in the differential privacy setting. In this problem, given a corpus of private text data, the goal is to release as many $n$-grams as possible while preserving user level privacy. Extracting $n$-grams is a fundamental subroutine in many NLP applications such as sentence completion, auto response generation for emails, etc. The problem also arises in other applications such as sequence mining, trajectory analysis, etc. , and is a generalization of recently studied differentially private set union (DPSU) by Gopi et al. (2020). In this paper, we develop a new differentially private algorithm for this problem which, in our experiments, significantly outperforms the state-of-the-art. Our improvements stem from combining recent advances in DPSU, privacy accounting, and new heuristics for pruning in the tree-based approach initiated by Chen et al. (2012).

NeurIPS Conference 2021 Conference Paper

Fast and Memory Efficient Differentially Private-SGD via JL Projections

• Zhiqi Bu
• Sivakanth Gopi
• Janardhan Kulkarni
• Yin Tat Lee
• Hanwen Shen
• Uthaipon Tantipongpipat

Differentially Private-SGD (DP-SGD) of Abadi et al. and its variations are the only known algorithms for private training of large scale neural networks. This algorithm requires computation of per-sample gradients norms which is extremely slow and memory intensive in practice. In this paper, we present a new framework to design differentially private optimizers called DP-SGD-JL and DP-Adam-JL. Our approach uses Johnson–Lindenstrauss (JL) projections to quickly approximate the per-sample gradient norms without exactly computing them, thus making the training time and memory requirements of our optimizers closer to that of their non-DP versions. Unlike previous attempts to make DP-SGD faster which work only on a subset of network architectures or use compiler techniques, we propose an algorithmic solution which works for any network in a black-box manner which is the main contribution of this paper. To illustrate this, on IMDb dataset, we train a Recurrent Neural Network (RNN) to achieve good privacy-vs-accuracy tradeoff, while being significantly faster than DP-SGD and with a similar memory footprint as non-private SGD.

NeurIPS Conference 2021 Conference Paper

Numerical Composition of Differential Privacy

• Sivakanth Gopi
• Yin Tat Lee
• Lukas Wutschitz

We give a fast algorithm to compose privacy guarantees of differentially private (DP) algorithms to arbitrary accuracy. Our method is based on the notion of privacy loss random variables to quantify the privacy loss of DP algorithms. The running time and memory needed for our algorithm to approximate the privacy curve of a DP algorithm composed with itself $k$ times is $\tilde{O}(\sqrt{k})$. This improves over the best prior method by Koskela et al. (2020) which requires $\tilde{\Omega}(k^{1. 5})$ running time. We demonstrate the utility of our algorithm by accurately computing the privacy loss of DP-SGD algorithm of Abadi et al. (2016) and showing that our algorithm speeds up the privacy computations by a few orders of magnitude compared to prior work, while maintaining similar accuracy.

ICML Conference 2020 Conference Paper

Differentially Private Set Union

• Sivakanth Gopi
• Pankaj Gulhane
• Janardhan Kulkarni
• Judy Hanwen Shen
• Milad Shokouhi
• Sergey Yekhanin

We study the basic operation of set union in the global model of differential privacy. In this problem, we are given a universe $U$ of items, possibly of infinite size, and a database $D$ of users. Each user $i$ contributes a subset $W_i \subseteq U$ of items. We want an ($\epsilon$, $\delta$)-differentially private Algorithm which outputs a subset $S \subset \cup_i W_i$ such that the size of $S$ is as large as possible. The problem arises in countless real world applications, and is particularly ubiquitous in natural language processing (NLP) applications. For example, discovering words, sentences, $n$-grams etc. , from private text data belonging to users is an instance of the set union problem. In this paper we design new algorithms for this problem that significantly outperform the best known algorithms.

STOC Conference 2019 Conference Paper

CSPs with global modular constraints: algorithms and hardness via polynomial representations

• Joshua Brakensiek
• Sivakanth Gopi
• Venkatesan Guruswami

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo M , for various choices of the modulus M . Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2-SAT, HORN-SAT, and LIN-2 (linear equations mod 2). We classify the moduli M for which these respective problems are polynomial time solvable, and when they are not (assuming the ETH). Our study reveals that this modular constraint lends a surprising richness to these classic, well-studied problems, with interesting broader connections to complexity theory and coding theory. The HORN-SAT case is connected to the covering complexity of polynomials representing the NAND function mod M . The LIN-2 case is tied to the sparsity of polynomials representing the OR function mod M , which in turn has connections to modular weight distribution properties of linear codes and locally decodable codes. In both cases, the analysis of our algorithm as well as the hardness reduction rely on these polynomial representations, highlighting an interesting algebraic common ground between hard cases for our algorithms and the gadgets which show hardness. These new complexity measures of polynomial representations merit further study. The inspiration for our study comes from a recent work by N'agele, Sudakov, and Zenklusen on submodular minimization with a global congruence constraint. Our algorithm for HORN-SAT has strong similarities to their algorithm, and in particular identical kind of set systems arise in both cases. Our connection to polynomial representations leads to a simpler analysis of such set systems, and also sheds light on (but does not resolve) the complexity of submodular minimization with a congruency requirement modulo a composite M .

SODA Conference 2019 Conference Paper

Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities

• Sivakanth Gopi
• Venkatesan Guruswami
• Sergey Yekhanin

SODA Conference 2017 Conference Paper

Competitive analysis of the top- K ranking problem

• Xi Chen 0010
• Sivakanth Gopi
• Jieming Mao
• Jon Schneider

Motivated by applications in recommender systems, web search, social choice and crowdsourcing, we consider the problem of identifying the set of top K items from noisy pairwise comparisons. In our setting, we are non-actively given r pairwise comparisons between each pair of n items, where each comparison has noise constrained by a very general noise model called the strong stochastic transitivity (SST) model. We analyze the competitive ratio of algorithms for the top- K problem. In particular, we present a linear time algorithm for the top- K problem which has a competitive ratio of i. e. to solve any instance of top -K, our algorithm needs at most times as many samples needed as the best possible algorithm for that instance (in contrast, all previous known algorithms for the top- K problem have competitive ratios of Ω( n ) or worse). We further show that this is tight: any algorithm for the top- K problem has competitive ratio at least

SODA Conference 2017 Conference Paper

Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound

• Sivakanth Gopi
• Swastik Kopparty
• Rafael Oliveira 0002
• Noga Ron-Zewi
• Shubhangi Saraf

One of the most important open problems in the theory of error-correcting codes is to determine the tradeoff between the rate R and minimum distance δ of a binary code. The best known tradeoff is the Gilbert-Varshamov bound, and says that for every δ ∊ (0, 1/2), there are codes with minimum distance δ and rate R = r GV (δ) > 0 (for a certain simple function r GV (·)). In this paper we show that the Gilbert-Varshamov bound can be achieved by codes which support local error-detection and error- correction algorithms. Specifically, we show the following results. 1. Local Testing: For all δ ∊ (0, 1/2) and all R < r GV (δ), there exist codes with length n, rate R and minimum distance δ that are locally testable with quasipolylog( n ) query complexity. 2. Local Correction: For all ∊ > 0, for all δ < 1/2 sufficiently large, and all R < (1 — ∊)R GV (δ), there exist codes with length n, rate R and minimum distance δ that are locally correctable from fraction errors with O ( n e ) query complexity. Furthermore, these codes have an efficient randomized construction, and the local testing and local correction algorithms can be made to run in time polynomial in the query complexity. Our results on locally correctable codes also immediately give locally decodable codes with the same parameters. Our local testing result is obtained by combining Thommesen's random concatenation technique and the best known locally testable codes from [KMRS16]. Our local correction result, which is significantly more involved, also uses random concatenation, along with a number of further ideas: the Guruswami-Sudan-Indyk list decoding strategy for concatenated codes, Alon- Edmonds-Luby distance amplification, and the local list-decodability, local list-recoverability and local testability of Reed-Muller codes. Curiously, our final local correction algorithms go via local list-decoding and local testing algorithms; this seems to be the first time local testability is used in the construction of a locally correctable code.

STOC Conference 2015 Conference Paper

2-Server PIR with Sub-Polynomial Communication

• Zeev Dvir
• Sivakanth Gopi

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the ith bit of an n-bit database replicated among two non-communicating servers, while not revealing any information about i to either server. In this work we construct a 2-server PIR scheme with total communication cost n O√(log log n)/(log n) . This improves over current 2-server protocols which all require Ω(n 1/3 ) communication. Our construction circumvents the n 1/3 barrier of Razborov and Yekhanin which holds for the restricted model of bilinear group-based schemes (covering all previous 2-server schemes). The improvement comes from reducing the number of servers in existing protocols, based on Matching Vector Codes, from 3 or 4 servers to 2. This is achieved by viewing these protocols in an algebraic way (using polynomial interpolation) and extending them using partial derivatives.

ICML Conference 2013 Conference Paper

One-Bit Compressed Sensing: Provable Support and Vector Recovery

• Sivakanth Gopi
• Praneeth Netrapalli
• Prateek Jain 0002
• Aditya V. Nori

In this paper, we study the problem of one-bit compressed sensing (1-bit CS), where the goal is to design a measurement matrix A and a recovery algorithm s. t. a k-sparse vector \x^* can be efficiently recovered back from signed linear measurements, i. e. , b=\sign(A\x^*). This is an important problem in the signal acquisition area and has several learning applications as well, e. g. , multi-label classification \citeHsuKLZ10. We study this problem in two settings: a) support recovery: recover \supp(\x^*), b) approximate vector recovery: recover a unit vector \hx s. t. || \hatx-\x^*/||\x^*|| ||_2≤ε. For support recovery, we propose two novel and efficient solutions based on two combinatorial structures: union free family of sets and expanders. In contrast to existing methods for support recovery, our methods are universal i. e. a single measurement matrix A can recover almost all the signals. For approximate recovery, we propose the first method to recover sparse vector using a near optimal number of measurements. We also empirically demonstrate effectiveness of our algorithms; we show that our algorithms are able to recover signals with smaller number of measurements than several existing methods.