Privately Learning Decision Lists and a Differentially Private Winnow

• URL: http://arxiv.org/abs/2602.07370v1
• Date: Sat, 07 Feb 2026 05:30:09 GMT
• Title: Privately Learning Decision Lists and a Differentially Private Winnow
• Authors: Mark Bun, William Fang,
• Abstract summary: We give new differentially private algorithms for the classic problems of learning decision lists and large-margin halfspaces.<n>In the PAC model, we give a computationally efficient algorithm for learning decision lists with minimal sample overhead over the best non-private algorithms.<n>In the online model, we give a private analog of the influential Winnow algorithm for learning halfspaces with mistake bound polylogarithmic in the analog dimension and inverse in the margin.
• Score: 6.7839141352275645
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
  We propose a model-based primal-dual algorithm to learn in an unknown CMDP. We prove that our algorithm achieves sublinear regret without error cancellations.
  arXiv  Detail & Related papers  (2024-02-24T09:47:46Z)
• Private PAC Learning May be Harder than Online Learning [14.180842831990999]
  We show that any concept class of Littlestone dimension $d$ can be privately PAC learned using $mathrmpoly(d)$ samples. This raises the natural question of whether there might be a generic conversion from online learners to private PAC learners.
  arXiv  Detail & Related papers  (2024-02-16T22:44:52Z)
• Stochastic Differentially Private and Fair Learning [7.971065005161566]
  We provide the first differentially private algorithm for fair learning that is guaranteed to converge. Our framework is flexible enough to permit different fairness, including demographic parity and equalized odds. Our algorithm can be applied to non-binary classification tasks with multiple (non-binary) sensitive attributes.
  arXiv  Detail & Related papers  (2022-10-17T06:54:57Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• A Graph Federated Architecture with Privacy Preserving Learning [48.24121036612076]
  Federated learning involves a central processor that works with multiple agents to find a global model. The current architecture of a server connected to multiple clients is highly sensitive to communication failures and computational overloads at the server. We use cryptographic and differential privacy concepts to privatize the federated learning algorithm that we extend to the graph structure.
  arXiv  Detail & Related papers  (2021-04-26T09:51:24Z)
• Learning Differentially Private Mechanisms [13.40946759638048]
  We propose a technique for automatically learning an accurate and differentially private version of a given non-private program. We demonstrate that our approach is able to learn foundational algorithms from the differential privacy literature and significantly outperforms natural program synthesis baselines.
  arXiv  Detail & Related papers  (2021-01-04T13:33:57Z)
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms [95.73230376153872]
  This paper studies the relationship between generalization and privacy preservation in iterative learning algorithms by two sequential steps. We prove that $(varepsilon, delta)$-differential privacy implies an on-average generalization bound for multi-Database learning algorithms. We then investigate how the iterative nature shared by most learning algorithms influence privacy preservation and further generalization.
  arXiv  Detail & Related papers  (2020-07-18T09:12:03Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime. We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive. In an extensive experimental study with the standard benchmark ASlib, our approach is shown to be highly competitive and in many cases even superior to state-of-the-art AS approaches.
  arXiv  Detail & Related papers  (2020-07-06T15:20:17Z)
• User-Level Privacy-Preserving Federated Learning: Analysis and Performance Optimization [77.43075255745389]
  Federated learning (FL) is capable of preserving private data from mobile terminals (MTs) while training the data into useful models. From a viewpoint of information theory, it is still possible for a curious server to infer private information from the shared models uploaded by MTs. We propose a user-level differential privacy (UDP) algorithm by adding artificial noise to the shared models before uploading them to servers.
  arXiv  Detail & Related papers  (2020-02-29T10:13:39Z)
• Efficient, Noise-Tolerant, and Private Learning via Boosting [15.62988331732388]
  We show how to construct noise-tolerant and private PAC learners for large-margin halfspaces. This first bound illustrates a general methodology for obtaining PAC learners from privacy. The second bound uses standard techniques to match the best known sample complexity for differentially private learning of large-margin halfspaces.
  arXiv  Detail & Related papers  (2020-02-04T03:16:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.