Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy

Devansh Gupta, Cristóbal Guzman, Enayat Ullah

Sequential data such as documents, conversations, and trajectories are naturally partitioned across users, motivating privacy guarantees that protect each user's entire trajectory.…