arXiv preprint ·
Private Uniform Language Generation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study uniform language generation under approximate differential privacy. Given a uniformly bounded number of distinct examples from an unknown target language, a generator must produce infinitely many new examples from that language with probability one while protecting the privacy of its input. We introduce a new combinatorial dimension termed the nested branching dimension and prove that a language class is privately uniformly generatable if and only if both its closure dimension and nested branching dimension are finite. Previous work characterizes non-private uniform generation by the finiteness of the closure dimension alone. Our results therefore identify an additional combinatorial obstruction imposed by privacy.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
The Scope Grammar of Natural-Language Rules: Counting and Enumerating Readings modulo Logical Equivalence
Maximal input entropy for binary two-deletion and two-insertion channels
An Engineering Reading of the Bounded Halting Problem and Observable Properties of a Universal Machine
Learning Erasing Equal-Length Relational Pattern Languages in the Limit from Positive Data over Binary Alphabets
Relational Composition as Parallel Transport: What Per-Entity Frames Force in Attention
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.