8 papers
Reasoning with Sampling: Cutting at Decision Points
Felix Zhou, Anay Mehrotra, Quanquan C. Liu
Frontier reasoning models are produced by post-training base language models with reinforcement learning. Recent work has challenged this by showing that sampling from a sharpened…
Differentially Private Language Generation and Identification in the Limit
Anay Mehrotra, Grigoris Velegkas, Xifan Yu +1
We initiate the study of language generation in the limit, a model recently introduced by Kleinberg and Mullainathan [KM24], under the constraint of differential privacy. We consid…
Private Training & Data Generation by Clustering Embeddings
Felix Zhou, Samson Zhou, Vahab Mirrokni +2
Deep neural networks often use large, high-quality datasets to achieve high performance on many machine learning tasks. When training involves potentially sensitive data, this proc…
Edge-Private Matching Kernels Through Local Decoding
Michael Dinitz, George Z. Li, Quanquan C. Liu +1
A matching is a set of edges with no shared endpoints. We study how participants can retain useful matching structure when each knows its own relationships but those relationships…
Sublinear Space Graph Algorithms in the Continual Release Model
Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee +1
The graph continual release model of differential privacy seeks to produce differentially private solutions to graph problems under a stream of edge updates where new private solut…
On the Computational Landscape of Replicable Learning
Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas +1
We study computational aspects of algorithmic replicability, a notion of stability introduced by Impagliazzo, Lei, Pitassi, and Sorrell [2022]. Motivated by a recent line of work t…
Pointwise Lipschitz Continuous Graph Algorithms
Quanquan C. Liu, Grigoris Velegkas, Yuichi Yoshida +1
In many real-world applications, it is undesirable to drastically change the problem solution after a small perturbation in the input, as unstable outputs can lead to costly transa…
Replicable Learning of Large-Margin Halfspaces
Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen +2
We provide efficient replicable algorithms for the problem of learning large-margin halfspaces. Our results improve upon the algorithms provided by Impagliazzo, Lei, Pitassi, and S…