Privately Learning Decision Lists and a Differentially Private Winnow

We give new differentially private algorithms for the classic problems of learning decision lists and large-margin halfspaces in the PAC and online models. In the PAC model, we give a computationally efficient algorithm for learning decision lists with minimal sample overhead over the best non-private algorithms. In the online model, we give a private analog of the influential Winnow algorithm for learning halfspaces with mistake bound polylogarithmic in the dimension and inverse polynomial in the margin. As an application, we describe how to privately learn decision lists in the online model, qualitatively matching state-of-the art non-private guarantees.

• Publication year

  2026

• Venue

  Unknown venue

• Publication date

  2026-02-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2602.07370
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• PREM: Privately Answering Statistical Queries with Relative Error

  2025cited by this paper
• Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings

  2025cited by this paper
• Private Learning of Littlestone Classes, Revisited

  2025cited by this paper
• The Limits of Differential Privacy in Online Learning

  2024cited by this paper
• Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries

  2024cited by this paper
• On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective

  2024cited by this paper
• Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime

  2023cited by this paper
• Private Online Prediction from Experts: Separations and Faster Rates

  2022cited by this paper
• Concurrent Composition Theorems for Differential Privacy

  2022cited by this paper
• Foundations of Machine Learning

  2021cited by this paper
• Practical and Private (Deep) Learning without Sampling or Shuffling

  2021cited by this paper
• Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges

  2021cited by this paper
• Concurrent Composition of Differential Privacy

  2021cited by this paper
• Littlestone Classes are Privately Online Learnable

  2021cited by this paper
• Efficient, Noise-Tolerant, and Private Learning via Boosting

  2020cited by this paper
• Differentially Private Learning of Geometric Concepts

  2019cited by this paper
• Efficient Private Algorithms for Learning Large-Margin Halfspaces

  2019cited by this paper
• The Price of Differential Privacy for Online Learning

  2017cited by this paper
• Dual Query: Practical Private Query Release for High Dimensional Data

  2014cited by this paper
• (Near) Dimension Independent Risk Bounds for Differentially Private Learning

  2014cited by this paper
• The Algorithmic Foundations of Differential Privacy

  2014influential reference
• (Nearly) Optimal Algorithms for Private Online Learning in Full-information and Bandit Settings

  2013cited by this paper
• Differential privacy for the analyst via private equilibrium computation

  2012cited by this paper
• A Simple and Practical Algorithm for Differentially Private Data Release

  2010cited by this paper
• A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis

  2010cited by this paper
• Differential privacy under continual observation

  2010cited by this paper
• Boosting and Differential Privacy

  2010cited by this paper
• Agnostic Learning of Monomials by Halfspaces Is Hard

  2009cited by this paper
• Differentially private combinatorial optimization

  2009cited by this paper
• What Can We Learn Privately?

  2008cited by this paper
• Mechanism Design via Differential Privacy

  2007cited by this paper
• Calibrating Noise to Sensitivity in Private Data Analysis

  2006cited by this paper
• Learning decision lists

  2004cited by this paper
• On Online Learning of Decision Lists

  2003cited by this paper
• PAC learning with irrelevant attributes

  1994cited by this paper
• Learning functions of k terms

  1990cited by this paper
• Learnability and the Vapnik-Chervonenkis dimension

  1989cited by this paper
• Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

  1987cited by this paper
• JMLR: Workshop and Conference Proceedings vol (2012) 1–34 Differentially Private Online Learning

  year unknowncited by this paper

• No citing papers are available for this paper.