21 citations · 47 across the 19 of their papers we have counts for
22 papers
Algorithmic Guarantees for Distilling Supervised and Offline RL Datasets
Aaryan Gupta, Rishi Saket, Aravindan Raghuveer
Given a training dataset, the goal of dataset distillation is to derive a synthetic dataset such that models trained on the latter perform as well as those trained on the training…
Dense and Diverse Goal Coverage in Multi Goal Reinforcement Learning
Sagalpreet Singh, Rishi Saket, Aravindan Raghuveer
Reinforcement Learning algorithms are primarily focused on learning a policy that maximizes expected return. As a result, the learned policy can exploit one or few reward sources.…
Aggregating Data for Optimal and Private Learning
Sushant Agarwal, Yukti Makhija, Rishi Saket +1
Multiple Instance Regression (MIR) and Learning from Label Proportions (LLP) are learning frameworks arising in many applications, where the training data is partitioned into disjo…
Weak to Strong Learning from Aggregate Labels
Yukti Makhija, Rishi Saket
In learning from aggregate labels, the training data consists of sets or "bags" of feature-vectors (instances) along with an aggregate label for each bag derived from the (usually…
Learning from Label Proportions and Covariate-shifted Instances
Sagalpreet Singh, Navodita Sharma, Shreyas Havaldar +2
In many applications, especially due to lack of supervision or privacy concerns, the training data is grouped into bags of instances (feature-vectors) and for each bag we have only…
FRACTAL: Fine-Grained Scoring from Aggregate Text Labels
Yukti Makhija, Priyanka Agrawal, Rishi Saket +1
Large language models (LLMs) are being increasingly tuned to power complex generation tasks such as writing, fact-seeking, querying and reasoning. Traditionally, human or model fee…
Hardness of Learning Boolean Functions from Label Proportions
Venkatesan Guruswami, Rishi Saket
In recent years the framework of learning from label proportions (LLP) has been gaining importance in machine learning. In this setting, the training examples are aggregated into s…
Label Differential Privacy via Aggregation
Anand Brahmbhatt, Rishi Saket, Shreyas Havaldar +3
This paper explores the use of linear aggregation to protect the privacy of sensitive training labels through the concept of \emph{label differential privacy} (label-DP) while main…
PAC Learning Linear Thresholds from Label Proportions
Anand Brahmbhatt, Rishi Saket, Aravindan Raghuveer
Learning from label proportions (LLP) is a generalization of supervised learning in which the training data is available as sets or bags of feature-vectors (instances) along with t…
LLP-Bench: A Large Scale Tabular Benchmark for Learning from Label Proportions
Anand Brahmbhatt, Mohith Pokala, Rishi Saket +1
In the task of Learning from Label Proportions (LLP), a model is trained on groups (a.k.a bags) of instances and their corresponding label proportions to predict labels for individ…
Multi-Variate Time Series Forecasting on Variable Subsets
Jatin Chauhan, Aravindan Raghuveer, Rishi Saket +2
We formulate a new inference task in the domain of multivariate time series forecasting (MTSF), called Variable Subset Forecast (VSF), where only a small subset of the variables is…
Hardness of Learning DNFs using Halfspaces
Suprovat Ghoshal, Rishi Saket
The problem of learning -term DNF formulas (for ) has been studied extensively in the PAC model since its introduction by Valiant (STOC 1984). A -term DNF can be ef…
Hardness of learning noisy halfspaces using polynomial thresholds
Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket
We prove the hardness of weakly learning halfspaces in the presence of adversarial noise using polynomial threshold functions (PTFs). In particular, we prove that for any constants…
Approximation Algorithms for Stochastic k-TSP
Alina Ene, Viswanath Nagarajan, Rishi Saket
We consider the stochastic -TSP problem where rewards at vertices are random and the objective is to minimize the expected length of a tour that collects reward . We present…
On the hardness of learning sparse parities
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal +1
This work investigates the hardness of computing sparse solutions to systems of linear equations over F_2. Consider the k-EvenSet problem: given a homogeneous system of linear equa…
On the Approximability of Digraph Ordering
Sreyash Kenkre, Vinayaka Pandit, Manish Purohit +1
Given an n-vertex digraph D = (V, A) the Max-k-Ordering problem is to compute a labeling maximizing the number of forward edges, i.e. edges (u,v) such that $\ell…
Tight Hardness of the Non-commutative Grothendieck Problem
Jop Briët, Oded Regev, Rishi Saket
We prove that for any $\eps > 0$ it is -hard to approximate the non-commutative Grothendieck problem to within a factor $1/2 + \eps$,…
Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs
Rishi Saket
This work revisits the PCP Verifiers used in the works of Hastad [Has01], Guruswami et al.[GHS02], Holmerin[Hol02] and Guruswami[Gur00] for satisfiable Max-E3-SAT and Max-Ek-Set-Sp…
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
Subhash Khot, Rishi Saket
This work studies the hardness of finding independent sets in hypergraphs which are either 2-colorable or are almost 2-colorable, i.e. can be 2-colored after removing a small fract…
A PTAS for the Classical Ising Spin Glass Problem on the Chimera Graph Structure
Rishi Saket
We present a polynomial time approximation scheme (PTAS) for the minimum value of the classical Ising Hamiltonian with linear terms on the Chimera graph structure as defined in the…
Stochastic Vehicle Routing with Recourse
Inge Li Goertz, Viswanath Nagarajan, Rishi Saket
We study the classic Vehicle Routing Problem in the setting of stochastic optimization with recourse. StochVRP is a two-stage optimization problem, where demand is satisfied using…
Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
Sushant Sachdeva, Rishi Saket
We study the problem of computing the minimum vertex cover on k-uniform k-partite hypergraphs when the k-partition is given. On bipartite graphs (k = 2), the minimum vertex cover c…