Janardhan Kulkarni

NeurIPS Conference 2025 Conference Paper

Contextual Integrity in LLMs via Reasoning and Reinforcement Learning

• Guangchen (Eric) Lan
• Huseyin A. Inan
• Sahar Abdelnabi
• Janardhan Kulkarni
• Lukas Wutschitz
• Reza Shokri
• Christopher Brinton
• Robert Sim

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.

NeurIPS Conference 2025 Conference Paper

SAS: Simulated Attention Score

• Chuanyang Zheng
• Jiankai Sun
• Yihang Gao
• Yuehao Wang
• Peihao Wang
• Jing Xiong
• Liliang Ren
• Hao Cheng

The attention mechanism is a core component of the Transformer architecture. Various methods have been developed to compute attention scores, including multi-head attention (MHA), multi-query attention, group-query attention and so on. We further analyze the MHA and observe that its performance improves as the number of attention heads increases, provided the hidden size per head remains sufficiently large. Therefore, increasing both the head count and hidden size per head with minimal parameter overhead can lead to significant performance gains at a low cost. Motivated by this insight, we introduce Simulated Attention Score (SAS), which maintains a compact model size while simulating a larger number of attention heads and hidden feature dimension per head. This is achieved by projecting a low-dimensional head representation into a higher-dimensional space, effectively increasing attention capacity without increasing parameter count. Beyond the head representations, we further extend the simulation approach to feature dimension of the key and query embeddings, enhancing expressiveness by mimicking the behavior of a larger model while preserving the original model size. To control the parameter cost, we also propose Parameter-Efficient Attention Aggregation (PEAA). Comprehensive experiments on a variety of datasets and tasks demonstrate the effectiveness of the proposed SAS method, achieving significant improvements over different attention variants.

ICLR Conference 2025 Conference Paper

Towards Foundation Models for Mixed Integer Linear Programming

• Sirui Li
• Janardhan Kulkarni
• Ishai Menache
• Cathy Wu 0002
• Beibin Li

Mixed Integer Linear Programming (MILP) is essential for modeling complex decision-making problems but faces challenges in computational tractability and interpretability. Current deep learning approaches for MILP focus on specific problem classes and do not generalize to unseen classes. To address this shortcoming, we take a foundation model training approach, where we train a single deep learning model on a diverse set of MILP problems to generalize across problem classes. As existing datasets for MILP lack diversity and volume, we introduce MILP-Evolve, a novel LLM-based evolutionary framework that is capable of generating a large set of diverse MILP classes with an unlimited amount of instances. We study our methodology on three key learning tasks that capture diverse aspects of MILP: (1) integrality gap prediction, (2) learning to branch, and (3) a new task of aligning MILP instances with natural language descriptions. Our empirical results show that models trained on the data generated by MILP-Evolve achieve significant improvements on unseen problems, including MIPLIB benchmarks. Our work highlights the potential of moving towards a foundation model approach for MILP that can generalize to a broad range of MILP problem classes. Our code and data are publicly available at https://github.com/microsoft/OptiGuide.

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.

STOC Conference 2024 Conference Paper

Optimal Online Discrepancy Minimization

• Janardhan Kulkarni
• Victor Reis
• Thomas Rothvoss

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.

ICLR Conference 2024 Conference Paper

Privately Aligning Language Models with Reinforcement Learning

• Fan Wu
• Huseyin A. Inan
• Arturs Backurs
• Varun Chandrasekaran
• Janardhan Kulkarni
• Robert Sim

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.

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.

ICLR Conference 2023 Conference Paper

Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping

• Jiyan He
• Xuechen Li
• Da Yu
• Huishuai Zhang
• Janardhan Kulkarni
• Yin Tat Lee
• Arturs Backurs
• Nenghai Yu

Differentially private deep learning has recently witnessed advances in computational efficiency and privacy-utility trade-off. We explore whether further improvements along the two axes are possible and provide affirmative answers leveraging two instantiations of \emph{group-wise clipping}. To reduce the compute time overhead of private learning, we show that \emph{per-layer clipping}, where the gradient of each neural network layer is clipped separately, allows clipping to be performed in conjunction with backpropagation in differentially private optimization. This results in private learning that is as memory-efficient and almost as fast per training update as non-private learning for many workflows of interest. While per-layer clipping with constant thresholds tends to underperform standard flat clipping, per-layer clipping with adaptive thresholds matches or outperforms flat clipping under given training epoch constraints, hence attaining similar or better task performance within less wall time. To explore the limits of scaling (pretrained) models in differentially private deep learning, we privately fine-tune the 175 billion-parameter GPT-3. We bypass scaling challenges associated with clipping gradients that are distributed across multiple devices with \emph{per-device clipping} that clips the gradient of each model piece separately on its host device. Privately fine-tuning GPT-3 with per-device clipping achieves a task performance at $\epsilon=1$ better than what is attainable by non-privately fine-tuning the largest GPT-2 on a summarization task.

TMLR Journal 2023 Journal Article

Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent

• Da Yu
• Gautam Kamath
• Janardhan Kulkarni
• Tie-Yan Liu
• Jian Yin
• Huishuai Zhang

Differentially private stochastic gradient descent (DP-SGD) is the workhorse algorithm for recent advances in private deep learning. It provides a single privacy guarantee to all datapoints in the dataset. We propose \emph{output-specific} $(\varepsilon,\delta)$-DP to characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We also design an efficient algorithm to investigate individual privacy across a number of datasets. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. We further discover that the training loss and the privacy parameter of an example are well-correlated. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees. For example, on CIFAR-10, the average $\varepsilon$ of the class with the lowest test accuracy is 44.2\% higher than that of the class with the highest accuracy.

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 2022 Conference Paper

Differentially Private Model Compression

• FatemehSadat Mireshghallah
• Arturs Backurs
• Huseyin A. Inan
• Lukas Wutschitz
• Janardhan Kulkarni

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.

SODA Conference 2022 Conference Paper

On the Hardness of Scheduling With Non-Uniform Communication Delays

• Sami Davies
• Janardhan Kulkarni
• Thomas Rothvoss
• Sai Sandeep
• Jakub Tarnawski
• Yihao Zhang

In the problem of scheduling with non-uniform communication delays, the input is a set of jobs with precedence constraints. Associated with every precedence constraint between a pair of jobs is a communication delay, the time duration the scheduler has to wait between the two jobs if they are scheduled on different machines. The objective is to assign the jobs to machines to minimize the makespan of the schedule. Despite being a fundamental problem in theory and a consequential problem in practice, the approximability of scheduling problems with communication delays is not very well understood. One of the top ten open problems in scheduling theory, in the influential list by Schuurman and Woeginger and its latest update by Bansal, asks if the problem admits a constant-factor approximation algorithm. In this paper, we answer this question in the negative by proving a logarithmic hardness for the problem under the standard complexity theory assumption that NP-complete problems do not admit quasi-polynomial-time algorithms. Our hardness result is obtained using a surprisingly simple reduction from a problem that we call Unique Machine Precedence constraints Scheduling (UMPS). We believe that this problem is of central importance in understanding the hardness of many scheduling problems and we conjecture that it is very hard to approximate. Among other things, our conjecture implies a logarithmic hardness of related machine scheduling with precedences, a long-standing open problem in scheduling theory and approximation algorithms.

STOC Conference 2022 Conference Paper

Online edge coloring via tree recurrences and correlation decay

• Janardhan Kulkarni
• Yang P. Liu
• Ashwin Sah
• Mehtaab Sawhney
• Jakub Tarnawski

NeurIPS Conference 2022 Conference Paper

When Does Differentially Private Learning Not Suffer in High Dimensions?

• Xuechen Li
• Daogao Liu
• Tatsunori B. Hashimoto
• Huseyin A. Inan
• Janardhan Kulkarni
• Yin-Tat Lee
• Abhradeep Guha Thakurta

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.

ICML Conference 2021 Conference Paper

Accuracy, Interpretability, and Differential Privacy via Explainable Boosting

• Harsha Nori
• Rich Caruana
• Zhiqi Bu
• Judy Hanwen Shen
• Janardhan Kulkarni

We show that adding differential privacy to Explainable Boosting Machines (EBMs), a recent method for training interpretable ML models, yields state-of-the-art accuracy while protecting privacy. Our experiments on multiple classification and regression datasets show that DP-EBM models suffer surprisingly little accuracy loss even with strong differential privacy guarantees. In addition to high accuracy, two other benefits of applying DP to EBMs are: a) trained models provide exact global and local interpretability, which is often important in settings where differential privacy is needed; and b) the models can be edited after training without loss of privacy to correct errors which DP noise may have introduced.

ICML Conference 2021 Conference Paper

Differentially Private Correlation Clustering

• Mark Bun
• Marek Eliás 0001
• Janardhan Kulkarni

Correlation clustering is a widely used technique in unsupervised machine learning. Motivated by applications where individual privacy is a concern, we initiate the study of differentially private correlation clustering. We propose an algorithm that achieves subquadratic additive error compared to the optimal cost. In contrast, straightforward adaptations of existing non-private algorithms all lead to a trivial quadratic error. Finally, we give a lower bound showing that any pure differentially private algorithm for correlation clustering requires additive error $\Omega$(n).

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

Private Non-smooth ERM and SCO in Subquadratic Steps

• Janardhan Kulkarni
• Yin Tat Lee
• Daogao Liu

We study the differentially private Empirical Risk Minimization (ERM) and Stochastic Convex Optimization (SCO) problems for non-smooth convex functions. We get a (nearly) optimal bound on the excess empirical risk for ERM with $O(\frac{N^{3/2}}{d^{1/8}}+ \frac{N^2}{d})$ gradient queries, which is achieved with the help of subsampling and smoothing the function via convolution. Combining this result with the iterative localization technique of Feldman et al. \cite{fkt20}, we achieve the optimal excess population loss for the SCO problem with $O(\min\{N^{5/4}d^{1/8}, \frac{ N^{3/2}}{d^{1/8}}\})$ gradient queries. Our work makes progress towards resolving a question raised by Bassily et al. \cite{bfgt20}, giving first algorithms for private SCO with subquadratic steps. In a concurrent work, Asi et al. \cite{afkt21} gave other algorithms for private ERM and SCO with subquadratic steps.

SODA Conference 2021 Conference Paper

Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines

• Sami Davies
• Janardhan Kulkarni
• Thomas Rothvoss
• Jakub Tarnawski
• Yihao Zhang

We consider the problem of scheduling jobs with precedence constraints on related machines to minimize the weighted sum of completion times, in the presence of communication delays. In this setting, denoted by Q | prec, c | Σ w j C j, if two dependent jobs are scheduled on different machines, then at least c units of communication delay time must pass between their executions. Our main result is an O (log 4 n )-approximation algorithm for the problem. As a byproduct of our result, we also obtain an O (log 3 n )-approximation algorithm for the problem of minimizing makespan Q | prec, c | C max, which improves upon the O (log 5 n/ log log n )-approximation algorithm due to a recent work of Maiti et al. [MRS + 20].

SODA Conference 2020 Conference Paper

An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs

• Sayan Bhattacharya
• Janardhan Kulkarni

SODA Conference 2020 Conference Paper

Differentially Private Release of Synthetic Graphs

• Marek Eliás 0001
• Michael Kapralov
• Janardhan Kulkarni
• Yin Tat Lee

We propose a ( ϵ, δ )-differentially private mechanism that, given an input graph G with n vertices and m edges, in polynomial time generates a synthetic graph G’ approximating all cuts of the input graph up to an additive error of. This is the first construction of differentially private cut approximator that allows additive error o ( m ) for all m > n log C n. The best known previous results gave additive O ( n 3/2 ) error and hence only retained information about the cut structure on very dense graphs. Thus, we are making a notable progress on a promiment problem in differential privacy. We also present lower bounds showing that our utility/privacy trade-off is essentially the best possible if one seeks to get purely additive cut approximations.

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.

SODA Conference 2020 Conference Paper

Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints

• Janardhan Kulkarni
• Shi Li 0001
• Jakub Tarnawski
• Minwei Ye

We consider the classic problem of scheduling jobs with precedence constraints on a set of identical machines to minimize the makespan objective function. Understanding the exact approximability of the problem when the number of machines is a constant is a well-known question in scheduling theory. Indeed, an outstanding open problem from the classic book of Garey and Johnson [9] asks whether this problem is NP-hard even in the case of 3 machines and unit-length jobs. In a recent breakthrough, Levey and Rothvoss [24] gave a (1 + ϵ )-approximation algorithm, which runs in nearly quasi-polynomial time, for the case when job have unit lengths. However, a substantially more difficult case where jobs have arbitrary processing lengths has remained open. We make progress on this more general problem. We show that there exists a (1 + ϵ )-approximation algorithm (with similar running time as that of [24]) for the nonmigratory setting: when every job has to be scheduled entirely on a single machine, but within a machine the job need not be scheduled during consecutive time steps. Further, we also show that our algorithmic framework generalizes to another classic scenario where, along with the precedence constraints, the jobs also have communication delay constraints. Both of these fundamental problems are highly relevant to the practice of datacenter scheduling.

SODA Conference 2020 Conference Paper

Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds

• Laxman Dhulipala
• David Durfee
• Janardhan Kulkarni
• Richard Peng
• Saurabh Sawlani
• Xiaorui Sun

In this paper we study the problem of dynamically maintaining graph properties under batches of edge insertions and deletions in the massively parallel model of computation. In this setting, the graph is stored on a number of machines, each having space strongly sublinear with respect to the number of vertices, that is, n ϵ for some constant 0 < ϵ < 1. Our goal is to handle batches of updates and queries where the data for each batch fits onto one machine in constant rounds of parallel computation, as well as to reduce the total communication between the machines. This objective corresponds to the gradual buildup of databases over time, while the goal of obtaining constant rounds of communication for problems in the static setting has been elusive for problems as simple as undirected graph connectivity. We give an algorithm for dynamic graph connectivity in this setting with constant communication rounds and communication cost almost linear in terms of the batch size. Our techniques combine a new graph contraction technique, an independent random sample extractor from correlated samples, as well as distributed data structures supporting parallel updates and queries in batches. We also illustrate the power of dynamic algorithms in the MPC model by showing that the batched version of the adaptive connectivity problem is P-complete in the centralized setting, but sub-linear sized batches can be handled in a constant number of rounds. Due to the wide applicability of our approaches, we believe it represents a practically-motivated workaround to the current difficulties in designing more efficient massively parallel static graph algorithms.

TCS Journal 2020 Journal Article

Prior-free multi-unit auctions with ordered bidders

• Sayan Bhattacharya
• Elias Koutsoupias
• Janardhan Kulkarni
• Stefano Leonardi
• Tim Roughgarden
• Xiaoming Xu

Prior-free auctions are robust auctions that assume no distribution over bidders' valuations and provide worst-case (input-by-input) approximation guarantees. In contrast to previous work on this topic, we pursue good prior-free auctions with non-identical bidders. Prior-free auctions can approximate meaningful benchmarks for non-identical bidders only when sufficient qualitative information about the bidder asymmetry is publicly known. We consider digital goods auctions where there is a total ordering of the bidders that is known to the seller, where earlier bidders are in some sense thought to have higher valuations. We use the framework of Hartline and Roughgarden (STOC'08) to define an appropriate revenue benchmark: the maximum revenue that can be obtained from a bid vector using prices that are nonincreasing in the bidder ordering and bounded above by the second-highest bid. This monotone-price benchmark is always as large as the well-known fixed-price benchmark F ( 2 ), so designing prior-free auctions with good approximation guarantees is only harder. By design, an auction that approximates the monotone-price benchmark satisfies a very strong guarantee: it is, in particular, simultaneously near-optimal for essentially every Bayesian environment in which bidders' valuation distributions have nonincreasing monopoly prices, or in which the distribution of each bidder stochastically dominates that of the next. Even when there is no distribution over bidders' valuations, such an auction still provides a quantifiable input-by-input performance guarantee. In this paper, we design a simple O ( 1 ) -competitive prior-free auction for digital goods with ordered bidders. We also extend the monotone-price benchmark and our O ( 1 ) -competitive prior-free auction to multi-unit settings with limited supply.

ICML Conference 2020 Conference Paper

Privately Learning Markov Random Fields

• Huanyu Zhang
• Gautam Kamath 0001
• Janardhan Kulkarni
• Zhiwei Steven Wu

We consider the problem of learning Markov Random Fields (including the prototypical example, the Ising model) under the constraint of differential privacy. Our learning goals include both \emph{structure learning}, where we try to estimate the underlying graph structure of the model, as well as the harder goal of \emph{parameter learning}, in which we additionally estimate the parameter on each edge. We provide algorithms and lower bounds for both problems under a variety of privacy constraints – namely pure, concentrated, and approximate differential privacy. While non-privately, both learning goals enjoy roughly the same complexity, we show that this is not the case under differential privacy. In particular, only structure learning under approximate differential privacy maintains the non-private logarithmic dependence on the dimensionality of the data, while a change in either the learning goal or the privacy notion would necessitate a polynomial dependence. As a result, we show that the privacy constraint imposes a strong separation between these two learning problems in the high-dimensional data regime.

FOCS Conference 2020 Conference Paper

Scheduling with Communication Delays via LP Hierarchies and Clustering

• Sami Davies
• Janardhan Kulkarni
• Thomas Rothvoss
• Jakub Tarnawski
• Yihao Zhang

We consider the classic problem of scheduling jobs with precedence constraints on identical machines to minimize makespan, in the presence of communication delays. In this setting, denoted by P | prec, c | Cmax, if two dependent jobs are scheduled on different machines, then at least c units of time must pass between their executions. Despite its relevance to many applications, this model remains one of the most poorly understood in scheduling theory. Even for a special case where an unlimited number of machines is available, the best known approximation ratio is 2/3·(c+1), whereas Graham's greedy list scheduling algorithm already gives a ( c+1) -approximation in that setting. An outstanding open problem in the top-10 list by Schuurman and Woeginger and its recent update by Bansal asks whether there exists a constant-factor approximation algorithm. In this work we give a polynomial-time O(logc·logm)-approximation algorithm for this problem, where m is the number of machines and c is the communication delay. Our approach is based on a Sherali-Adams lift of a linear programming relaxation and a randomized clustering of the semimetric space induced by this lift. The full version of this paper is available on arXiv.

SODA Conference 2019 Conference Paper

A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time

• Uriel Feige
• Janardhan Kulkarni
• Shi Li 0001

We consider the classic scheduling problem of minimizing the total weighted flow-time on a single machine (min-WPFT), when preemption is allowed. In this problem, we are given a set of n jobs, each job having a release time r j, a processing time p j, and a weight w j. The flow-time of a job is defined as the amount of time the job spends in the system before it completes; that is, F j = C j – r j, where C j is the completion time of job. The objective is to minimize the total weighted flow-time of jobs. This NP-hard problem has been studied quite extensively for decades. In a recent breakthrough, Batra, Garg, and Kumar [6] presented a pseudo-polynomial time algorithm that has an O (1) approximation ratio. The design of a truly polynomial time algorithm, however, remained an open problem. In this paper, we show a transformation from pseudo-polynomial time algorithms to polynomial time algorithms in the context of min-WPFT. Our result combined with the result of Batra, Garg, and Kumar [6] settles the long standing conjecture that there is a polynomial time algorithm with O (1)-approximation for min-WPFT.

NeurIPS Conference 2019 Conference Paper

An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors

• Joshua Allen
• Bolin Ding
• Janardhan Kulkarni
• Harsha Nori
• Olga Ohrimenko
• Sergey Yekhanin

Differential privacy has emerged as the main definition for private data analysis and machine learning. The global model of differential privacy, which assumes that users trust the data collector, provides strong privacy guarantees and introduces small errors in the output. In contrast, applications of differential privacy in commercial systems by Apple, Google, and Microsoft, use the local model. Here, users do not trust the data collector, and hence randomize their data before sending it to the data collector. Unfortunately, local model is too strong for several important applications and hence is limited in its applicability. In this work, we propose a framework based on trusted processors and a new definition of differential privacy called Oblivious Differential Privacy, which combines the best of both local and global models. The algorithms we design in this framework show interesting interplay of ideas from the streaming algorithms, oblivious algorithms, and differential privacy.

SODA Conference 2019 Conference Paper

Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time

• Sayan Bhattacharya
• Janardhan Kulkarni

We consider the problem of maintaining an (approximately) minimum vertex cover in an n -node graph G = ( V, E ) that is getting updated dynamically via a sequence of edge insertions/deletions. We show how to maintain a (2 + ∊ )-approximate minimum vertex cover, deterministically, in this setting in O (1/ ∊ 2 ) amortized update time. Prior to our work, the best known deterministic algorithm for maintaining a (2 + ∊ )-approximate minimum vertex cover was due to Bhattacharya, Henzinger and Italiano [SODA 2015]. Their algorithm has an update time of O (log n / ∊ 2 ). Recently, Bhattacharya, Chakrabarty, Henzinger [IPCO 2017] and Gupta, Krishnaswamy, Kumar, Panigrahi [STOC 2017] showed how to maintain an O (1)-approximation in O (1)-amortized update time for the same problem. Our result gives an exponential improvement over the update time of Bhattacharya et al. [SODA 2015], and nearly matches the performance of the randomized algorithm of Solomon [FOCS 2016] who gets an approximation ratio of 2 and an expected amortized update time of O (1). We derive our result by analyzing, via a novel technique, a variant of the algorithm by Bhattacharya et al. We consider an idealized setting where the update time of an algorithm can take any arbitrary fractional value, and use insights from this setting to come up with an appropriate potential function. Conceptually, this framework mimics the idea of an LP-relaxation for an optimization problem. The difference is that instead of relaxing an integral objective function, we relax the update time of an algorithm itself. We believe that this technique will find further applications in the analysis of dynamic algorithms.

SODA Conference 2019 Conference Paper

Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time

• Shashwat Garg
• Janardhan Kulkarni
• Shi Li 0001

We consider the classic problem of scheduling jobs with precedence constraints on a set of identical machines to minimize the weighted completion time objective. Understanding the exact approximability of the problem when job lengths are uniform is a well known open problem in scheduling theory. In this paper, we show an optimal algorithm that runs in polynomial time and achieves an approximation factor of (2 + ∊ ) for the weighted completion time objective when the number of machines is a constant. The result is obtained by building on the lift and project approach introduced in a breakthrough work by Levey and Rothvoss [15] for the makespan minimization problem.

NeurIPS Conference 2019 Conference Paper

Locally Private Gaussian Estimation

• Matthew Joseph
• Janardhan Kulkarni
• Jieming Mao
• Steven Wu

We study a basic private estimation problem: each of n users draws a single i. i. d. sample from an unknown Gaussian distribution N(\mu, \sigma^2), and the goal is to estimate \mu while guaranteeing local differential privacy for each user. As minimizing the number of rounds of interaction is important in the local setting, we provide adaptive two-round solutions and nonadaptive one-round solutions to this problem. We match these upper bounds with an information-theoretic lower bound showing that our accuracy guarantees are tight up to logarithmic factors for all sequentially interactive locally private protocols.

NeurIPS Conference 2017 Conference Paper

Collecting Telemetry Data Privately

• Bolin Ding
• Janardhan Kulkarni
• Sergey Yekhanin

The collection and analysis of telemetry data from user's devices is routinely performed by many software companies. Telemetry collection leads to improved user experience but poses significant risks to users' privacy. Locally differentially private (LDP) algorithms have recently emerged as the main tool that allows data collectors to estimate various population statistics, while preserving privacy. The guarantees provided by such algorithms are typically very strong for a single round of telemetry collection, but degrade rapidly when telemetry is collected regularly. In particular, existing LDP algorithms are not suitable for repeated collection of counter data such as daily app usage statistics. In this paper, we develop new LDP mechanisms geared towards repeated collection of counter data, with formal privacy guarantees even after being executed for an arbitrarily long period of time. For two basic analytical tasks, mean estimation and histogram estimation, our LDP mechanisms for repeated data collection provide estimates with comparable or even the same accuracy as existing single-round LDP collection mechanisms. We conduct empirical evaluation on real-world counter datasets to verify our theoretical results. Our mechanisms have been deployed by Microsoft to collect telemetry across millions of devices.

FOCS Conference 2015 Conference Paper

Competitive Flow Time Algorithms for Polyhedral Scheduling

• Sungjin Im
• Janardhan Kulkarni
• Kamesh Munagala

Many scheduling problems can be viewed as allocating rates to jobs, subject to convex packing constraints on the rates. In this paper, we consider the problem of rate allocation when jobs of unknown size arrive online (non-clairvoyant setting), with the goal of minimizing weighted delay or flow time. Though this problem has strong lower bounds on competitive ratio in its full generality, we show positive results for natural and fairly broad sub-classes. More specifically, the subclasses we consider not only generalize several well-studied models such as scheduling with speedup curves and related machine scheduling, but also capture as special cases hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We establish several first positive results by making connections with two disparate disciplines: Economics and Queueing theory. First, we view the instantaneous allocation of rates as a resource allocation problem. We analyze the natural proportional fairness algorithm from economics. To do this, we extend results from market clearing literature, particularly the Eisenberg-Gale markets and the notions of Walrasian equilibria and Gross Substitutes. This yields the first constant competitive algorithm with constant speed augmentation for single-sink flow routing, routing multicast trees, and multidimensional resource allocation with substitutes resources. Next, we consider the general scheduling problem with packing constraints on rates, but with the restriction that the number of different job types is fixed. We model this problem as a non-stochastic queueing problem. We generalize a natural algorithm from queueing literature and analyze it by extending queueing theoretic ideas. We show that the competitive ratio, for any constant speed, depends polynomially only on the number of job types. Further, such a dependence on the number of job types is unavoidable for non-clairvoyant algorithms. This yields the first algorithm for scheduling multicommodity flows whose competitive ratio depends polynomially on the size of the underlying graph, and not on the number of jobs.

STOC Conference 2015 Conference Paper

Minimizing Flow-Time on Unrelated Machines

• Nikhil Bansal 0001
• Janardhan Kulkarni

We consider some classical flow-time minimization problems in the unrelated machines setting. In this setting, there is a set of m machines and a set of n jobs, and each job j has a machine dependent processing time of p ij on machine i. The flow-time of a job is the amount of time the job spends in a system (its completion time minus its arrival time), and is one of the most natural measure of quality of service. We show the following two results: an $O(min(log 2 n, log n log P)) approximation algorithm for minimizing the total flow-time, and an O(log n) approximation for minimizing the maximum flow-time. Here P is the ratio of maximum to minimum job size. These are the first known poly-logarithmic guarantees for both the problems.

SODA Conference 2015 Conference Paper

Robust Price of Anarchy Bounds via LP and Fenchel Duality

• Janardhan Kulkarni
• Vahab Mirrokni

Bounding the price of anarchy (PoA), which quantifies the degradation in the quality of outcomes in a (pure) Nash equilibrium of a game, is one of the fundamental questions in computational game theory. However, for a large class of games, a pure NE may not always exist and hence a natural question to pursue is to quantify the inefficiency for weaker notions of equilibrium such as mixed Nash equilibrium, correlated equilibrium or coarse correlated equilibrium, all of which are known to exist for finite games. Several techniques have been developed for bounding the price of anarchy, yet, only a handful of them are applicable for proving the PoA bounds for general equilibrium concepts. Most notable among such techniques is Roughgarden's elegant smoothness framework, which led to the concept of robust price of anarchy. The term refers to the inefficiency bounds applicable to general equilibrium notions such as coarse correlated equilibrium. In this paper, we develop a new framework based on LP and Fenchel duality for bounding the robust price of anarchy for a large class of games. We use our framework to give the first PoA bounds for temporal routing games on graphs and energy minimization games in machine scheduling. Most notably, we present the first coordination mechanisms with bounded PoA for temporal routing over general graphs, show a related lowerbound result, and an improved bound on the price of stability for this game. Previously, coordination mechanisms with bounded PoA were only known for restricted classes of graphs such as trees or parallel edges. Furthermore, we demonstrate the wide applicability of our framework by giving new proofs of the PoA bounds for three classical games – weighted affine congestion games, competitive facility location games and simultaneous second price auctions. Our price anarchy bounds for these games match the ones known in the literature or obtained using the smoothness framework. All our proofs use the following technique: we first show that for a wide class of games, one can formulate the underlying optimization problem as a linear (or convex) program such that the (Fenchel) dual of the relaxation encodes the equilibrium condition. Further, the dual program has a specific structure with variables for players and resources, which can be naturally interpreted as the cost incurred by the players and the congestion of the resource in an equilibrium outcome. This lets us argue that our definition of dual variables satisfy the dual constraints and using the weak duality theorem we establish the PoA bounds.

FOCS Conference 2015 Conference Paper

Tight Bounds for Online Vector Scheduling

• Sungjin Im
• Nathaniel Kell
• Janardhan Kulkarni
• Debmalya Panigrahi

Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests are inherently multi-dimensional and characterized by demand vectors over multiple resources such as processor cycles, storage space, and network bandwidth. Typically, different resources require different objectives to be optimized, and L r norms of loads are among the most popular objectives considered. Furthermore, the server clusters are also often heterogeneous making the scheduling problem more challenging. To address these problems, we consider the online vector scheduling problem in this paper. Introduced by Chekuri and Khanna (SIAM J. of Comp. 2006), vector scheduling is a generalization of classical load balancing, where every job has a vector load instead of a scalar load. The scalar problem, introduced by Graham in 1966, and its many variants (identical and unrelated machines, makespan and L r -norm optimization, offline and online jobs, etc.) have been extensively studied over the last 50 years. In this paper, we resolve the online complexity of the vector scheduling problem and its important generalizations - for all L r norms and in both the identical and unrelated machines settings. Our main results are: · For identical machines, we show that the optimal competitive ratio is Θ(log d/ log log d) by giving an online lower bound and an algorithm with an asymptotically matching competitive ratio. The lower bound is technically challenging, and is obtained via an online lower bound for the minimum mono-chromatic clique problem using a novel online coloring game and randomized coding scheme. Our techniques also extend to asymptotically tight upper and lower bounds for general L r norms. · For unrelated machines, we show that the optimal competitive ratio is Θ(log m + log d) by giving an online lower bound that matches a previously known upper bound. Unlike identical machines, however, extending these results, particularly the upper bound, to general L r norms requires new ideas. In particular, we use a carefully constructed potential function that balances the individual L r objectives with the overall (convexified) min-max objective to guide the online algorithm and track the changes in potential to bound the competitive ratio.

STOC Conference 2014 Conference Paper

Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints

• Sungjin Im
• Janardhan Kulkarni
• Kamesh Munagala

We introduce and study a general scheduling problem that we term the Packing Scheduling problem (PSP). In this problem, jobs can have different arrival times and sizes; a scheduler can process job j at rate x j , subject to arbitrary packing constraints over the set of rates (x) of the outstanding jobs. The PSP framework captures a variety of scheduling problems, including the classical problems of unrelated machines scheduling, broadcast scheduling, and scheduling jobs of different parallelizability. It also captures scheduling constraints arising in diverse modern environments ranging from individual computer architectures to data centers. More concretely, PSP models multidimensional resource requirements and parallelizability, as well as network bandwidth requirements found in data center scheduling.

FOCS Conference 2014 Conference Paper

SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors

• Sungjin Im
• Janardhan Kulkarni
• Kamesh Munagala
• Kirk Pruhs

We consider the classical problem of minimizing the total weighted flow-time for unrelated machines in the online non-clairvoyant setting. In this problem, a set of jobs J arrive over time to be scheduled on a set of M machines. Each job J has processing length pj, weight wj, and is processed at a rate of lij when scheduled on machine i. The online scheduler knows the values of wj and lij upon arrival of the job, but is not aware of the quantity pj. We present the first online algorithm that is scalable ((1+ε)-speed O(1/2)-competitive for any constant ε > 0) for the total weighted flow-time objective. No non-trivial results were known for this setting, except for the most basic case of identical machines. Our result resolves a major open problem in online scheduling theory. Moreover, we also show that no job needs more than a logarithmic number of migrations. We further extend our result and give a scalable algorithm for the objective of minimizing total weighted flow-time plus energy cost for the case of unrelated machines. In this problem, each machine can be sped up by a factor of f-1i(P) when consuming power P, where fi is an arbitrary strictly convex power function. In particular, we get an O(γ2)-competitive algorithm when all power functions are of form sγ. These are the first non-trivial non-clairvoyant results in any setting with heterogeneous machines. The key algorithmic idea is to let jobs migrate selfishly until they converge to an equilibrium. Towards this end, we define a game where each job's utility which is closely tied to the instantaneous increase in the objective the job is responsible for, and each machine declares a policy that assigns priorities to jobs based on when they migrate to it, and the execution speeds. This has a spirit similar to coordination mechanisms that attempt to achieve near optimum welfare in the presence of selfish agents (jobs). To the best our knowledge, this is the first work that demonstrates the usefulness of ideas from coordination mechanisms and Nash equilibria for designing and analyzing online algorithms.