More Like this

1. Optimal high-precision shadow estimation

   Chen, Sitan; Li, Jerry; Liu, Allen (July 2024, https://doi.org/10.48550/arXiv.2407.13874)

   The authors provide the first tight sample complexity bounds for shadow tomography and classical shadows in the regime where the target error is below some sufficiently small inverse polynomial in the dimension of the Hilbert space. Specifically, they present a protocol that, given any 𝑚 ∈ 𝑁 m∈N and 𝜖 ≤ 𝑂 ( 𝑑 − 1 / 2 ) ϵ≤O(d −1/2 ), measures 𝑂 ( log ⁡ ( 𝑚 ) / 𝜖 2 ) O(log(m)/ϵ 2 ) copies of an unknown mixed state 𝜌 ∈ 𝐶 𝑑 × 𝑑 ρ∈C d×d and outputs a classical description of 𝜌 ρ. This description can then be used to estimate any collection of 𝑚 m observables to within additive accuracy 𝜖 ϵ. Previously, even for the simpler case of shadow tomography where observables are known in advance, the best known rates either scaled benignly but suboptimally in all of 𝑚 , 𝑑 , 𝜖 m,d,ϵ, or scaled optimally in 𝜖 , 𝑚 ϵ,m but included additional polynomial factors in 𝑑 d. Interestingly, the authors also show via dimensionality reduction that one can rescale 𝜖 ϵ and 𝑑 d to reduce to the regime where 𝜖 ≤ 𝑂 ( 𝑑 − 1 / 2 ) ϵ≤O(d −1/2 ). Their algorithm draws on representation-theoretic tools developed in the context of full state tomography. 

   more » « less
2. Recurrent Shadow Attention Model (RSAM) for shadow removal in high-resolution urban land-cover mapping

   https://doi.org/10.1016/j.rse.2020.111945  

   Zhang, Yindan; Chen, Gang; Vukomanovic, Jelena; Singh, Kunwar K.; Liu, Yong; Holden, Samuel; Meentemeyer, Ross K. (September 2020, Remote Sensing of Environment)

   null (Ed.)
3. Leveraging shadow networks for procedural justice

   https://doi.org/10.1016/j.cosust.2022.101190  

   York, Abigail; Yazar, Mahir (August 2022, Current Opinion in Environmental Sustainability)
4. Supermartingale shadow couplings: The decreasing case

   https://doi.org/10.3150/23-BEJ1592  

   Bayraktar, Erhan; Deng, Shuoqing; Norgilas, Dominykas (February 2024, Bernoulli)

   For two measures that are in convex-decreasing order, Nutz and Stebegg (Canonical supermartingale couplings, Ann. Probab. 46(6) 3351–3398, 2018) studied the optimal transport problem with supermartingale constraints and introduced two canonical couplings, namely the increasing and decreasing transport plans, that are optimal for a large class of cost functions. In the present paper we provide an explicit construction of the decreasing coupling by establishing a Brenier-type result: (a generalised version of) this coupling concentrates on the graphs of two functions. Our construction is based on the concept of the supermartingale shadow measure and requires a suitable extension of the results by Juillet (Stability of the shadow projection and the left-curtain coupling, Ann. Inst. H. Poincaré Probab. Statist. 52(4) 1823–1843, November 2016) and Beiglböck and Juillet (Shadow couplings, Trans. Amer. Math. Soc. 374 4973–5002, 2021) established in the martingale setting. In particular, we prove the stability of the supermartingale shadow measure with respect to initial and target measures introduce an infinite family of lifted supermartingale couplings that arise via shadow measure, and show how to explicitly determine the martingale points of each such coupling. 

   more » « less
5. Proving Differential Privacy with Shadow Execution

   Wang, Yuxin; Ding, Zeyu; Wang, Guanhong; Kifer, Daniel; Zhang, Danfeng (January 2019, Programming Language Design and Implementation (PLDI))

   Recent work on formal verification of differential privacy shows a trend toward usability and expressiveness – generating a correctness proof of sophisticated algorithm while minimizing the annotation burden on programmers. Sometimes, combining those two requires substantial changes to program logics: one recent paper is able to verify Report Noisy Max automatically, but it involves a complex verification system using customized program logics and verifiers. In this paper, we propose a new proof technique, called shadow execution, and embed it into a language called ShadowDP. ShadowDP uses shadow execution to generate proofs of differential privacy with very few programmer annotations and without relying on customized logics and verifiers. In addition to verifying Report Noisy Max, we show that it can verify a new variant of Sparse Vector that reports the gap between some noisy query answers and the noisy threshold. Moreover, ShadowDP reduces the complexity of verification: for all of the algorithms we have evaluated, type checking and verification in total takes at most 3 seconds, while prior work takes minutes on the same algorithms. 

   more » « less