Private learning of markov chains with optimal sample use
Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
Cryptography and Security
Summary
Understanding sequences like user journeys or conversations often involves models called Markov chains. Protecting the privacy of entire user sequences while learning these models is challenging. The authors studied how to estimate such chains privately, balancing accuracy, data size, and privacy levels. They provide nearly the best possible bounds on the amount of data needed to learn Markov chains both at the level of individual items and entire user sequences.
What this means in practice
- •For data privacy teams: Design privacy-preserving algorithms to estimate user behavior sequences with strong guarantees on user data protection.
- •For security engineers: Implement methods to learn behavioral models from sequential data without exposing individual user trajectories.
Authors
Devansh Gupta, Cristóbal Guzman, Enayat Ullah
Abstract
Sequential data such as documents, conversations, and trajectories are naturally partitioned across users, motivating privacy guarantees that protect each user's entire trajectory. We initiate the study of privately estimating the transition matrix of a discrete ergodic Markov chain from N independent trajectories of length T, with arbitrary initial distributions, under maximum row-wise ell 1 error. Besides N, T, and the number of states, our bounds depend on the minimum stationary probability and the pseudo-spectral gap, which govern state coverage and mixing. Under item-level privacy, we give upper and lower bounds that separate the costs of sampling, state occupancy and mixing, and privacy. Under user-level privacy, we reduce the problem for sufficiently long trajectories to private product distribution estimation. Along the way, we establish optimal user-level private bounds for estimating products of discrete distributions, which may be of independent interest. In the user level setting, our bounds are nearly tight in the large T regime, whereas in the item-level setting, our bounds as tight up-to a non-private term.