Characterizing the sample complexity of private learners
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 7164746
- Computing and Combinatorics
- Bounds on the sample complexity for private learning and private data release
- Bounds on the sample complexity for private learning and private data release
- Sample complexity bounds on differentially private learning via communication complexity
- Improved bounds on the sample complexity of learning
- scientific article; zbMATH DE number 1445318
- On the sample complexity of weak learning
- Sample size lower bounds in PAC learning by Algorithmic Complexity Theory
- The sample complexity of learning linear predictors with the squared loss
Cites work
- scientific article; zbMATH DE number 3154781 (Why is no real title available?)
- scientific article; zbMATH DE number 67625 (Why is no real title available?)
- scientific article; zbMATH DE number 67631 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- A model of interactive teaching
- A theory of goal-oriented communication
- A theory of the learnable
- Algorithmic Learning Theory
- Derandomizing polynomial identity tests means proving circuit lower bounds
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Learning from different teachers
- Measuring teachability using variants of the teaching dimension
- Models of cooperative teaching and learning
- Occam's razor
- On specifying Boolean functions by labelled examples
- On the complexity of teaching
- On the limits of efficient teachability
- On the power of inductive inference from good examples
- Pseudorandom generators for space-bounded computation
- Recent Developments in Algorithmic Teaching
- Teachability in computational learning
- Teaching Randomized Learners
- Teaching a smarter learner.
Cited in
(98)- Parallel algorithms for geometric graph problems
- Bandits with switching costs, \(T^{2/3}\) regret
- Fourier PCA and robust tensor decomposition
- Optimal competitive auctions
- Black-box non-black-box zero knowledge
- Sample complexity bounds on differentially private learning via communication complexity
- On the existence of extractable one-way functions
- scientific article; zbMATH DE number 7164746 (Why is no real title available?)
- Distributed approximation algorithms for weighted shortest paths
- Formulas vs. circuits for small distance connectivity
- Embedding and canonizing graphs of bounded genus in logspace
- Homological product codes
- Learning privately with labeled and unlabeled examples
- Realizable learning is all you need
- The sample complexity of revenue maximization
- Smoothed analysis of tensor decompositions
- Query complexity of approximate nash equilibria
- Efficient density estimation via piecewise polynomial approximation
- Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- Polynomial bounds for the grid-minor theorem
- Simultaneous private learning of multiple concepts
- Fingerprinting codes and the price of approximate differential privacy
- Simultaneous private learning of multiple concepts
- Approximate distance oracles with constant query time
- Breaking the quadratic barrier for 3-LCC's over the reals
- Communication lower bounds via critical block sensitivity
- Online local learning via semidefinite programming
- Primal beats dual on online packing LPs in the random-order model
- Efficient deterministic approximate counting for low-degree polynomial threshold functions
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- A characterization of strong approximation resistance
- Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions
- Entropy, optimization and counting
- A characterization of locally testable affine-invariant properties via decomposition theorems
- A super-polynomial lower bound for regular arithmetic formulas
- How to delegate computations
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
- Economic efficiency requires interaction
- Fingerprinting codes and the price of approximate differential privacy
- Turnstile streaming algorithms might as well be linear sketches
- Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
- Testing surface area with arbitrary accuracy
- An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
- Optimal error rates for interactive coding. I: Adaptivity and other settings
- Breaking the Minsky-Papert barrier for constant-depth circuits
- Federated learning on Riemannian manifolds with differential privacy
- A strongly polynomial algorithm for generalized flow maximization
- Analytical approach to parallel repetition
- Coin flipping of any constant bias implies one-way functions
- Private sequential learning
- Constant rank bimatrix games are PPAD-hard
- Differentially private learning of geometric concepts
- L_p-testing
- Satisfiability threshold for random regular NAE-SAT
- Distributed computability in Byzantine asynchronous systems
- Faster all-pairs shortest paths via circuit complexity
- How to use indistinguishability obfuscation
- Analyze Gauss: optimal bounds for privacy-preserving principal component analysis
- The asymptotic \(k\)-SAT threshold
- The complexity of differential privacy
- Learners that use little information
- Constant factor approximation for balanced cut in the PIE model
- On derandomizing algorithms that err extremely rarely
- What can we learn privately?
- Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing
- Every list-decodable code for high noise has abundant near-optimal rate puncturings
- Private matchings and allocations
- Infinite randomness expansion with a constant number of devices
- Private PAC learning implies finite Littlestone dimension
- Minimum bisection is fixed parameter tractable
- Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits
- Bounds on the sample complexity for private learning and private data release
- Bounds on the sample complexity for private learning and private data release
- scientific article; zbMATH DE number 7626777 (Why is no real title available?)
- Community detection thresholds and the weak Ramanujan property
- Zig-zag sort
- Private learning and sanitization: pure vs. approximate differential privacy
- Linear time construction of compressed text indices in compact space
- Shortest paths on polyhedral surfaces and terrains
- The limits of depth reduction for arithmetic formulas
- From average case complexity to improper learning complexity
- Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing
- Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements
- An efficient parallel solver for SDD linear systems
- From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics
- On the sample complexity of weak learning
- Approximation algorithms for bipartite matching with metric and geometric costs
- Circuits resilient to additive attacks with applications to secure computation
- Rounding sum-of-squares relaxations
- Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints
- The average sensitivity of an intersection of half spaces
- Computing with a full memory: catalytic space
- Non-malleable codes from additive combinatorics (extended abstract)
- A quantum algorithm for computing the unit group of an arbitrary degree number field
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Multiway cut, pairwise realizable distributions, and descending thresholds
This page was built for publication: Characterizing the sample complexity of private learners
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986862)
