skip to main content


Search for: All records

Award ID contains: 1815893

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Loh, Po-Ling ; Raginsky, Maxim (Ed.)
  2. Loh, Po-Ling ; Raginsky, Maxim (Ed.)
  3. We obtain tight minimax rates for the problem of distributed estimation of discrete distributions under communication constraints, where n users observing m samples each can broadcast only ℓ bits. Our main result is a tight characterization (up to logarithmic factors) of the error rate as a function of m, ℓ, the domain size, and the number of users under most regimes of interest. 
    more » « less
  4. We study robust testing and estimation of discrete distributions in the strong contamination model. Our results cover both centralized setting and distributed setting with general local information constraints including communication and LDP constraints. Our technique relates the strength of manipulation attacks to the earth-mover distance using Hamming distance as the metric between messages (samples) from the users. In the centralized setting, we provide optimal error bounds for both learning and testing. Our lower bounds under local information constraints build on the recent lower bound methods in distributed inference. In the communication constrained setting, we develop novel algorithms based on random hashing and an L1-L1 isometry. 
    more » « less
  5. We consider the problem of estimating sparse discrete distributions under local differential privacy (LDP) and communication constraints. We characterize the sample complexity for sparse estimation under LDP constraints up to a constant factor, and the sample complexity under communication constraints up to a logarithmic factor. Our upper bounds under LDP are based on the Hadamard Response, a private coin scheme that requires only one bit of communication per user. Under communication constraints we propose public coin schemes based on random hashing functions. Our tight lower bounds are based on recently proposed method of chi squared contractions. 
    more » « less
  6. Ranzato, M ; Beygelzimer, A ; Dauphin, Y ; Liang, P. S. ; Wortman Vaughan, J (Ed.)
  7. Ranzato, M ; Beygelzimer, A ; Dauphin, Y ; Liang, P. S. ; Wortman Vaughan, J (Ed.)
  8. Ranzato, M ; Beygelzimer, A ; Dauphin, Y ; Liang, P. S. ; Wortman Vaughan, J (Ed.)