More Like this

1. New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs

   https://doi.org/10.4230/LIPIcs.ICALP.2023.39  

   Chen, Lijie ; Lyu, Xin ; Tal, Avishay ; Wu, Hongxun ( January 2023 , Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Etessami, Kousha ; Feige, Uriel ; Puppis, Gabriele (Ed.)

   We give the first pseudorandom generators with sub-linear seed length for the following variants of read-once branching programs (roBPs): 1) First, we show there is an explicit PRG of seed length O(log²(n/ε)log(n)) fooling unbounded-width unordered permutation branching programs with a single accept state, where n is the length of the program. Previously, [Lee-Pyne-Vadhan RANDOM 2022] gave a PRG with seed length Ω(n) for this class. For the ordered case, [Hoza-Pyne-Vadhan ITCS 2021] gave a PRG with seed length Õ(log n ⋅ log 1/ε). 2) Second, we show there is an explicit PRG fooling unbounded-width unordered regular branching programs with a single accept state with seed length Õ(√{n ⋅ log 1/ε} log 1/ε). Previously, no non-trivial PRG (with seed length less than n) was known for this class (even in the ordered setting). For the ordered case, [Bogdanov-Hoza-Prakriya-Pyne CCC 2022] gave an HSG with seed length Õ(log n ⋅ log 1/ε). 3) Third, we show there is an explicit PRG fooling width w adaptive branching programs with seed length O(log n ⋅ log² (nw/ε)). Here, the branching program can choose an input bit to read depending on its current state, while it is guaranteed that on any input x ∈ {0,1}ⁿ, the branching program reads each input bit exactly once. Previously, no PRG with a non-trivial seed length is known for this class. We remark that there are some functions computable by constant-width adaptive branching programs but not by sub-exponential-width unordered branching programs. In terms of techniques, we indeed show that the Forbes-Kelley PRG (with the right parameters) from [Forbes-Kelley FOCS 2018] already fools all variants of roBPs above. Our proof adds several new ideas to the original analysis of Forbes-Kelly, and we believe it further demonstrates the versatility of the Forbes-Kelley PRG. 

   more » « less
2. Privacy-Aware Rejection Sampling

   Awan, Jordan ; Rao, Vinayak ( February 2023 , Journal of machine learning research)

   Weller, Adrian (Ed.)

   While differential privacy (DP) offers strong theoretical privacy guarantees, implementations of DP mechanisms may be vulnerable to side-channel attacks, such as timing attacks. When sampling methods such as MCMC or rejection sampling are used to implement a privacy mechanism, the runtime can leak private information. We characterize the additional privacy cost due to the runtime of a rejection sampler in terms of both (, δ)-DP as well as f -DP. We also show that unless the acceptance probability is constant across databases, the runtime of a rejection sampler does not satisfy -DP for any . We show that there is a similar breakdown in privacy with adaptive rejection samplers. We propose three modifications to the rejection sampling algorithm, with varying assumptions, to protect against timing attacks by making the runtime independent of the data. The modification with the weakest assumptions is an approximate sampler, introducing a small increase in the privacy cost, whereas the other modifications give perfect samplers. We also use our techniques to develop an adaptive rejection sampler for log-H ̈older densities, which also has data-independent runtime. We give several examples of DP mechanisms that fit the assumptions of our methods and can thus be implemented using our samplers. 

   more » « less
3. Privacy-Aware Rejection Sampling

   Awan, Jordan ; Rao, Vinayak ( January 2023 , Journal of machine learning research)

   Weller, Adrian (Ed.)

   Differential privacy (DP) offers strong theoretical privacy guarantees, though implementations of DP mechanisms may be vulnerable to side-channel attacks, such as timing attacks. When sampling methods such as MCMC or rejection sampling are used to implement a mechanism, the runtime can leak private information. We characterize the additional privacy cost due to the runtime of a rejection sampler in terms of both (epsilon,delta)-DP as well as f-DP. We also show that unless the acceptance probability is constant across databases, the runtime of a rejection sampler does not satisfy epsilon-DP for any epsilon. We show that there is a similar breakdown in privacy with adaptive rejection samplers. We propose three modifications to the rejection sampling algorithm, with varying assumptions, to protect against timing attacks by making the runtime independent of the data. The modification with the weakest assumptions is an approximate sampler, introducing a small increase in the privacy cost, whereas the other modifications give perfect samplers. We also use our techniques to develop an adaptive rejection sampler for log-Holder densities, which also has data-independent runtime. We give several examples of DP mechanisms that fit the assumptions of our methods and can thus be implemented using our samplers. 

   more » « less
4. Online Revenue Maximization for Server Pricing

   https://doi.org/10.24963/ijcai.2020/568  

   Boodaghians, Shant ; Fusco, Federico ; Leonardi, Stefano ; Mansour, Yishay ; Mehta, Ruta ( July 2020 , Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20))

   null (Ed.)

   Efficient and truthful mechanisms to price time on remote servers/machines have been the subject of much work in recent years due to the importance of the cloud market. This paper considers online revenue maximization for a unit capacity server, when jobs are non preemptive, in the Bayesian setting: at each time step, one job arrives, with parameters drawn from an underlying distribution.We design an efficiently computable truthful posted price mechanism, which maximizes revenue in expectation and in retrospect, up to additive error. The prices are posted prior to learning the agent's type, and the computed pricing scheme is deterministic.We also show the pricing mechanism is robust to learning the job distribution from samples, where polynomially many samples suffice to obtain near optimal prices.

    

   more » « less
5. Scalable Differential Privacy with Certified Robustness in Adversarial Learning

   Phan, NhatHai ; Thai, My T. ; Hu, Han ; Jin, Ruoming ; Sun, Tong ; Dou, Dejing ( July 2022 , Proceedings of the 37th International Conference on Machine Learning)

   In this paper, we aim to develop a scalable algorithm to preserve differential privacy (DP) in adversarial learning for deep neural networks (DNNs), with certified robustness to adversarial examples. By leveraging the sequential composition theory in DP, we randomize both input and latent spaces to strengthen our certified robustness bounds. To address the trade-off among model utility, privacy loss, and robustness, we design an original adversarial objective function, based on the post-processing property in DP, to tighten the sensitivity of our model. A new stochastic batch training is proposed to apply our mechanism on large DNNs and datasets, by bypassing the vanilla iterative batch-by-batch training in DP DNNs. An end-to-end theoretical analysis and evaluations show that our mechanism notably improves the robustness and scalability of DP DNNs. 

   more » « less