There has been a recent interest in understanding and characterizing the sample complexity of list learning tasks, where the learning algorithm is allowed to make a short list of $k$ predictions, and we simply require one of the predictions to be correct. This includes recent works characterizing the PAC sample complexity of standard list classification and online list classification. Adding to this theme, in this work, we provide a complete characterization of list PAC {\em regression}. We propose two combinatorial dimensions, namely the $k$-OIG dimension and the $k$-fat-shattering dimension, and show that they characterize realizable and agnostic $k$-list regression respectively. These quantities generalize known dimensions for standard regression. Our work thus extends existing list learning characterizations from classification to regression.

This paper investigates the integration of response time data into human preference learning frameworks for more effective reward model elicitation. While binary preference data has become fundamental in fine-tuning foundation models, generative AI systems, and other large-scale models, the valuable temporal information inherent in user decision-making remains largely unexploited. We propose novel methodologies to incorporate response time information alongside binary choice data, leveraging the Evidence Accumulation Drift Diffusion (EZ) model, under which response time is informative of the preference strength. We develop Neyman-orthogonal loss functions that achieve oracle convergence rates for reward model learning, matching the theoretical optimal rates that would be attained if the expected response times for each query were known a priori. Our theoretical analysis demonstrates that for linear reward functions, conventional preference learning suffers from error rates that scale exponentially with reward magnitude. In contrast, our response time-augmented approach reduces this to polynomial scaling, representing a significant improvement in sample efficiency. We extend these guarantees to non-parametric reward function spaces, establishing convergence properties for more complex, realistic reward models. Our extensive experiments validate our theoretical findings in the context of preference learning over images.

Metric distortion in social choice is a framework for evaluating how well voting rules minimize social cost when both voters and candidates exist in a shared metric space, with a voter's cost defined by their distance to a candidate. Voters submit rankings, and the rule aggregates these rankings to determine a winner. We extend this framework to incorporate probabilistic voting, recognizing that real-world voters exhibit randomness in how they vote. Our extension includes various probability functions, notably the widely studied Plackett-Luce (PL) model.

Video conferencing tools have seen a significant increase in usage in the past few years but they still consume a significant bandwidth of $\sim 100$ Kbps to a few Mbps. In this work, we present Txt2Vid-Web: a practical, web-based, low bandwidth, video conferencing platform building upon the Txt2Vid work [1]. We introduce multiple improvements over the existing Txt2Vid framework – implementing it on browser application stack making it much more accessible and portable, reducing the implementation complexity of the plat-form via WebGL, and implementing a new WebGL shader for ConvTranspose in ONNX runtime – thereby enabling it to run on web-browsers of modern laptops (Fig. 1a). We use WebRTC to establish peer-to-peer data channels over network connections and utilize SDP’s multimedia negotiation scheme over SRTP connections, allowing our platform to provide high-quality video calls for the majority of connections and fall back to Txt2Vid when bandwidth limitations overconstrain SDP’s chosen codecs. We verified our plat-form via subjective study $(n =126)$ consisting of comparison of five different audio-video (AV) contents compressed via standard codecs and Txt2Vid-Web. We choose bitrates of {6 kbps, 10 kbps} for encoding the audio and bitrates of {15 kbps, 35 kbps, 100 kbps} for encoding the video using standard AV codec. Results show that at similar quality of experience our platform requires $100 - 500 \times$ less bandwidth than H.264 and VP9 as video codec and OPUS as audio codec (Fig. 1b). We envision our platform can open up many novel applications. Towards this end, we also open-source both our new tool as a Github repository (https://github.com/tpulkit/txt2vid_browser), and our subjective study dataset (https://tinyurl.com/SubjectiveStudyDataset).

We study low sample complexity mechanisms in participatory budgeting (PB), where each voter votes for a preferred allocation of funds to various projects, subject to project costs and total spending constraints. We analyse the distortion that PB mechanisms introduce relative to the minimum-social-cost outcome in expectation. The Random Dictator mechanism for this problem obtains a distortion of 2. In a special case where every voter votes for exactly one project, [Fain et al., 2017] obtain a distortion of 4/3. We show that when PB outcomes are determined as any convex combination of the votes of two voters, the distortion is 2. When three uniformly randomly sampled votes are used, we give a PB mechanism that obtains a distortion of at most 1.66, thus breaking the barrier of 2 with the smallest possible sample complexity. We give a randomized Nash bargaining scheme where two uniformly randomly chosen voters bargain with the disagreement point as the vote of a voter chosen uniformly at random. This mechanism has a distortion of at most 1.66. We provide a lower bound of 1.38 for the distortion of this scheme. Further, we show that PB mechanisms that output a median of the votes of three voters chosen uniformly at random, have a distortion of at most 1.80.

We consider a generalization of the gradient coding framework where a dataset is divided across$n$workers and each worker transmits to a master node one or more linear combinations of the gradients over its assigned data subsets. Unlike the conventional framework which requires the master node to recover the sum of the gradients over all the data subsets in the presence of straggler workers, we relax the goal to computing the sum of at least some$\alpha $fraction of the gradients. We begin by deriving a lower bound on the computation load of any scheme and also propose two strategies which achieve this lower bound, albeit at the cost of high communication load and a number of data partitions which can be polynomial in$n$. We then propose schemes based on cyclic assignment which utilize$n$data partitions and have a lower communication load. When each worker transmits a single linear combination, we prove lower bounds on the computation load of any scheme using$n$data partitions. Finally, we describe a class of schemes which achieve different intermediate operating points for the computation and communication load and provide simulation results to demonstrate the empirical performance of our schemes.

We consider a generalization of the recently proposed gradient coding framework where a large dataset is divided across$n$workers and each worker transmits to a master node one or more linear combinations of the gradients over the data subsets assigned to it. Unlike the conventional framework which requires the master node to recover the sum of the gradients over all the data subsets in the presence of$s$straggler workers, we relax the goal of the master node to computing the sum of at least some α fraction of the gradients. The broad goal of our work is to study the optimal computation and communication load per worker for this approximate gradient coding framework. We begin by deriving a lower bound on the computation load of any feasible scheme and also propose a strategy which achieves this lower bound, albeit at the cost of high communication load and a number of data partitions which can be polynomial in the number of workers n. We then restrict attention to schemes which utilize a number of data partitions equal to$n$and propose schemes based on cyclic assignment which have a lower communication load. When each worker transmits a single linear combination, we also prove lower bounds on the computation load of any scheme using$n$data partitions. A full version of this paper is accessible at: https://arxiv.org/abs/2102.10163

We consider the problem of identifying the subset$S$γPof elements in the support of an underlying distribution$P$whose probability value is larger than a given threshold γ, by actively querying an oracle to gain information about a sequence$X$1,$X$2, … of i.i.d. samples drawn from P. We consider two query models: (a) each query is an index$i$and the oracle return the value Xiand (b) each query is a pair of indices (i, j) and the oracle gives a binary answer confirming if Xi= Xjor not. For each of these query models, we design sequential estimation algorithms which at each round, either decide what query to send to the oracle depending on the entire history of responses, or decide to stop and output an estimate of$S$γP, which is required to be correct with some prespecified large probability. We provide upper bounds on the query complexity of the algorithms for any distribution$\mathcal{P}$and also derive lower bounds on the optimal query complexity under the two query models. We also consider noisy versions of the two query models and propose robust estimators which can effectively counter the noise in the oracle responses. A full version of this paper is accessible at: https://arxiv.org/pdf/2005.14425.pdf