# Note for secure learning
###### tags: `DPLearning`
> This note is about private learning, differential privacy
## References of Learning Privately:
1. [Privately learning thresholds: Closing the exponential gap, Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, Uri Stemmer](https://arxiv.org/abs/1911.10137)
2. [On the Sample Complexity of Privately Learning Axis-Aligned Rectangles, Menachem Sadigurschi, Uri Stemmer](https://arxiv.org/pdf/2107.11526.pdf)
3. [Efficient Private Algorithms for Learning Large-Margin Halfspaces, Huy L. Nguyen, Jonathan Ullman, Lydia Zakynthinou](https://arxiv.org/abs/1902.09009)
4. [PAC learning halfspaces in non-interactive local differential privacy model with public unlabeled data, J Su, J Xu, D Wang, 2023](https://pdf.sciencedirectassets.com/272574/1-s2.0-S0022000023X00099/1-s2.0-S0022000023001010/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjEHkaCXVzLWVhc3QtMSJIMEYCIQDmPEyE097V8qdj%2FWN4RsgbQrF64yw8ThyWQgu0wk7ZdQIhAK1A5gR6tAEyETk4Vc5%2FvOF08AdxeAreuY8IjU9UKVgEKrMFCDIQBRoMMDU5MDAzNTQ2ODY1Igx%2BPWNtdViZK8hX8YEqkAV8fcpIQhshDUUECKUavb6fktHUnBwmTxxev7%2F045oUGRlKzmIu9HNZwzojuVZIggGjUwTxTAQ%2F0ap%2F6AZbsahrWHBXugQOnEFkbmteakOT8xDe4f9BbrewtkF2y%2BL3ikagRayq5DbG5zpMS9UwyGCFmHVbLltAAJu8BpqGo83rPdl0d7q%2Bd1vZme7p45G6BgJoaumlsS6Jcb0I%2B1ujsBDKiNGy%2FisGcPeHMZLpHwXypVEElbNU6wz736IXPTT1LVqw7c%2Bq81LO5O6dz1Y6sXNViZ%2Fo2sh8h%2FKbkyoC3zsTvCKkkmBkxbR263E6IVdl1%2BaEQz8BlwR8RXgph5Lr%2FRB6tOy10TLg5aVDUd7mazwpdzVRyH5zFBorioJ1JG8Bl%2F2L9E6KSoEZZoxZYJ95XSQUz4Q1hZDw39BCU46SDcH9s2Tmms%2F74vSLMNkMsJa0xuSIsvSFhVt%2FQA%2FAKKGY8L8SubOC0Eir2UrqmTkNrvndlIILt2j8tk8n%2B0yBPgkTSqF53netUCmtoydM5aX0FEVhSF20LX95AVswFVwgsZuYNW0echw6JeAHU41ZPiSEZWE497T3s5bb0C8w5vlqDBR%2BwJch0Cn9cRo40Oh%2BZfXDLU3DuPG3gfAenGBOexvMOXO0fmTWeYYPxXmHyRwMQbYznuCkb13MltTITmN%2BGk0lgrMTnWFUDb6%2BrXgNya%2FEOfGfRKEn2C8MLvvfrewGb7shqOOeLiRKfAPHUKBAgzPgQRKCaydZIHc7FRyvyno31Jad9HJqhCPpiMXYJbWMW783df4ireuK7pYtlJIKWirq0uTXUhr3yp2EpVKG2WdHVjXxZyeQKGoHUDx%2FdiVcNH2QcnWeUfQVQWRUbuu4OeidDzD2jrWtBjqwAefoV%2FZWXA3wlcoAuCG3dBEuHV9K78rc1mcOx4xHG03xWKmz%2BlBgBsOGLIFLqnEVZr3NfVjUGXGZkdU9oe2l9L9X9Esi3LHqWyKonyKFTRWvzHInKI%2Bdo102RsjE3MDyEIAIFkYGFUaxKoGKN5DK1gfKYAWnlzoIieHrnqLYMCXWP75bcM845dBqfc%2FWqX81baBHmv80QHQBZN%2FYcFWl2zaUpOAdn5iEkBL6xI85LJ2I&X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Date=20240121T170752Z&X-Amz-SignedHeaders=host&X-Amz-Expires=300&X-Amz-Credential=ASIAQ3PHCVTY5CYQ5G3M%2F20240121%2Fus-east-1%2Fs3%2Faws4_request&X-Amz-Signature=8b917dc3fcc4baf4120e34971db6a85370f9b501260dbfa1f8cbd75a34b63ff3&hash=ee95c859867446918a41577621a14e47b15b1c7eb43fc1686062343d23c9f744&host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&pii=S0022000023001010&tid=spdf-518a74a6-f346-4f21-bd00-5473c1a2e436&sid=23957f8f5b26d5451e699b6-9ee85cae19fdgxrqa&type=client&tsoh=d3d3LnNjaWVuY2VkaXJlY3QuY29t&ua=12195c5656575c580500&rr=849127eb3aafa343&cc=tw)
5. [Reproducibility in Learning, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell](https://arxiv.org/abs/2201.08430)
6. [Differentially Private Approximate Quantiles, Haim Kaplan, Shachar Schnapp, Uri Stemmer](https://arxiv.org/pdf/2110.05429.pdf)
7. [Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization, Cohen, Edith ; Lyu, Xin ; Nelson, Jelani ; Sarlós, Tamás ; Stemmer, Uri](https://arxiv.org/abs/2211.06387)
8. [The Target-Charging Technique for Privacy Analysis across Interactive Computations, Edith Cohen, Xin Lyu](https://openreview.net/pdf?id=7yjsYrajlt)
9. [Differentially Private Medians and Interior Points for Non-Pathological Data, Maryam Aliakbarpour, Rose Silver, Thomas Steinke, Jonathan Ullman](https://arxiv.org/pdf/2305.13440.pdf)
10. [A Theory of PAC Learnability of Partial Concept Classes, N Alon, S Hanneke, R Holzman, S Moran - 2021](https://www.cs.tau.ac.il/~nogaa/PDFS/PCC.pdf)
11. [Differentially Private Generalized Linear Models Revisited, Raman Arora, Raef Bassily, Cristóbal Guzmán, Michael Menart, Enayat Ullah - 2022](https://arxiv.org/abs/2205.03014)
12. [Robust and Private Learning of Halfspaces, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thao Nguyen - 2021](https://arxiv.org/abs/2011.14580)
13. [What Can We Learn Privately?, Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith - 2011](https://epubs.siam.org/doi/epdf/10.1137/090756090)
14. [How to Find a Point in the Convex Hull Privately, Haim Kaplan, Micha Sharir, Uri Stemmer - 2020](https://arxiv.org/pdf/2003.13192.pdf)
15. [Privacy via the Johnson-Lindenstrauss Transform, Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, Nina Mishra, - 2013](https://journalprivacyconfidentiality.org/index.php/jpc/article/view/625/608)
16. [A Survey on Differential Privacy for Unstructured Data Content, YING ZHAO and JINJUN CHEN, - 2022 a survey](https://dl.acm.org/doi/pdf/10.1145/3490237)
17. [Mechanism design via differential privacy, F McSherry, K Talwar - 2007](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/mdviadp.pdf)
18. [PAC Privacy: Automatic Privacy Measurement and Control of Data Processing, Hanshen Xiao and Srinivas Devadas - CRYPTO 2023](https://link.springer.com/content/pdf/10.1007/978-3-031-38545-2_20.pdf?pdf=inline%20link)[-- (Slide 投影片)](https://iacr.org/submit/files/slides/2023/crypto/crypto2023/60/slides.pptx)
20. [Learning with differential privacy: Stability, learnability and the sufficiency and necessity of ERM principle, YX Wang, J Lei, SE Fienberg - The Journal of Machine Learning Research, 2016](https://www.jmlr.org/papers/volume17/15-313/15-313.pdf)
21. [Cryptographic hardness for learning intersections of halfspaces, Adam R. Klivans, AlexanderA.Sherstov, - 2009, JCSS](https://www.sciencedirect.com/science/article/pii/S0022000008000706)
22. [Additive Randomized Encodings and Their Applications, Shai Halevi1, Yuval Ishai, Eyal Kushilevitz, and Tal Rabin, -- CRYTO 2023](https://eprint.iacr.org/2023/870.pdf)
23. [On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, O. Regev, 2024](https://arxiv.org/pdf/2401.03703.pdf)
24. [New lattice-based cryptographic constructions, O. Regev, JACM 2004](https://arxiv.org/pdf/cs/0309051.pdf)(https://dl.acm.org/doi/pdf/10.1145/1039488.1039490)
25. [Lattice Problems in NP ∩ coNP, DORIT AHARONOV AND ODED REGEV, JACM 2005](https://dl.acm.org/doi/pdf/10.1145%2F1089023.1089025)
26. [On the Complexity of Lattice Problems with Polynomial Approximation Factors, O. Regev](https://link.springer.com/content/pdf/10.1007/978-3-642-02295-1_15?pdf=chapter%20toc)
27. [Cryptography from Anonymity, Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai, FOCS 2006](https://eprint.iacr.org/2006/084.pdf)
28. [Secure Summation: Capacity Region, Groupwise Key, and Feasibility, IEEE Trans. on Information Theory, 2024](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=10359136)
29. [Practical Secure Aggregation for Privacy-Preserving Machine Learning, 2017](https://systems.cs.columbia.edu/private-systems-class/papers/Bonawitz2017Practical.pdf)
30. [Differentially Private Empirical Risk Minimization, Journal of Machine Learning Research 12 (2011) 1069-1109](https://www.jmlr.org/papers/volume12/chaudhuri11a/chaudhuri11a.pdf)
### Coding theory for Differential Privacy:
1. [Shannon meets Gray: Noise-robust, Low-sensitivity Codes with Applications in Differential Privacy, David Rasmussen, Lolck Rasmus Pagh - 2024](https://epubs.siam.org/doi/epdf/10.1137/1.9781611977912.40)
2. [REPRESENTING SPARSE VECTORS WITH DIFFERENTIALPRIVACY, LOW ERROR, OPTIMAL SPACE, AND FAST ACCESS, MARTIN AUM ̈ULLER, CHRISTIAN JANOS LEBEDA, AND RASMUS PAGH - 2022](https://journalprivacyconfidentiality.org/index.php/jpc/article/view/809/739)
3. [Additive Randomized Encodings and Their Applications, Shai Halevi, Yuval Ishai, Eyal Kushilevitz, Tal Rabin - CRYPTO 2023](https://eprint.iacr.org/2023/870.pdf)[--(Slide 投影片)](https://iacr.org/submit/files/slides/2023/crypto/crypto2023/314/slides.pptx)
### Applications and issues with DP:
1. [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy, Ponomareva, Hazimeh, Kurakin, Xu, Denison, McMahan, Vassilvitskii, Chien & Thakurta, Journal of Artificial Intelligence Research 77 (2023) 1113-1201](https://www.jair.org/index.php/jair/article/view/14649/26952)
2. [A Survey of Privacy Attacks in Machine Learning, MARIA RIGAKI and SEBASTIAN GARCIA, ACM Computing SurveysVolume 56Issue 410 November 2023Article No.: 101pp 1–34](https://dl.acm.org/doi/pdf/10.1145/3624010)
3. [Age-Dependent Differential Privacy, IEEE Trans. on Information Theory 2024](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=10359365&tag=1)
### Complexity of Transformer
1. [A Logic for Expressing Log-Precision Transformers, William Merrill, Ashish Sabharwal, 2023](https://arxiv.org/pdf/2210.02671)
2. [The Expressive Power of Transformers with Chain of Thought, William Merrill, Ashish Sabharwal, 2023, ICLR](https://arxiv.org/abs/2310.07923)
3. [Transformers in Uniform $TC^0$, David Chiang ](https://arxiv.org/pdf/2409.13629)
4. [Ask, and it shall be given: Turing completeness of prompting, R Qiu, Z Xu, W Bao, H Tong, 2025](https://arxiv.org/pdf/2411.01992)
5.
========================= Ignore the following
Let's try it out!
Apply different styling to this paragraph:
**HackMD gets everyone on the same page with Markdown.** ==Real-time collaborate on any documentation in markdown.== Capture fleeting ideas and formalize tribal knowledge.
- [x] **Bold**
- [ ] *Italic*
- [ ] Super^script^
- [ ] Sub~script~
- [ ] ~~Crossed~~
- [x] ==Highlight==
:::info
:bulb: **Hint:** You can also apply styling from the toolbar at the top :arrow_upper_left: of the editing area.
:::
> Drag-n-drop image from your file system to the editor to paste it!
### Step 3: Invite your team to collaborate!
Click on the <i class="fa fa-share-alt"></i> **Sharing** menu :arrow_upper_right: and invite your team to collaborate on this note!
- [ ] Register and sign-in to HackMD (to use advanced features :tada: )
- [ ] Set Permalink for this note
- [ ] Copy and share the link with your team
:::info
:pushpin: Want to learn more? ➜ [HackMD Tutorials](https://hackmd.io/c/tutorials)
:::
---
## BONUS: More cool ways to HackMD!
- Table
| Features | Tutorials |
| ----------------- |:----------------------- |
| GitHub Sync | [:link:][GitHub-Sync] |
| Browser Extension | [:link:][HackMD-it] |
| Book Mode | [:link:][Book-mode] |
| Slide Mode | [:link:][Slide-mode] |
| Share & Publish | [:link:][Share-Publish] |
[GitHub-Sync]: https://hackmd.io/c/tutorials/%2Fs%2Flink-with-github
[HackMD-it]: https://hackmd.io/c/tutorials/%2Fs%2Fhackmd-it
[Book-mode]: https://hackmd.io/c/tutorials/%2Fs%2Fhow-to-create-book
[Slide-mode]: https://hackmd.io/c/tutorials/%2Fs%2Fhow-to-create-slide-deck
[Share-Publish]: https://hackmd.io/c/tutorials/%2Fs%2Fhow-to-publish-note
- LaTeX for formulas
$$
x = {-b \pm \sqrt{b^2-4ac} \over 2a}
$$
- Code block with color and line numbers：
```javascript=16
var s = "JavaScript syntax highlighting";
alert(s);
```
- UML diagrams
```sequence
Alice->Bob: Hello Bob, how are you?
Note right of Bob: Bob thinks
Bob-->Alice: I am good thanks!
Note left of Alice: Alice responds
Alice->Bob: Where have you been?
```
- Auto-generated Table of Content
[ToC]
> Leave in-line comments! [color=#3b75c6]
- Embed YouTube Videos
{%youtube PJuNmlE74BQ %}
> Put your cursor right behind an empty bracket {} :arrow_left: and see all your choices.
- And MORE ➜ [HackMD Tutorials](https://hackmd.io/c/tutorials)
Sign in with Wallet
Connect another wallet