dataset instead of a large, labelled, less similar dataset.

  2. 2.

Using a moderately sized closely related dataset either instead of a large
source dataset for pretraining or as an intermediary fine-tuning step when
transferring weights from a less related source task to the final target task.

If it is not possible to use a more related dataset then a high initial
learning rate and momentum should be used, but the learning rate should be
decayed quickly. Recent regularization techniques like L2-SP, DELTA, BSS,
stochastic normalization, etc. should not be used on all layers, but in some
cases may be beneficial on lower layers.

## References

  * [1] Samira Abnar, Mostafa Dehghani, Behnam Neyshabur, and Hanie Sedghi.  Exploring the limits of large scale pre-training.  arXiv preprint arXiv:2110.02095, 2021.
  * [2] Pulkit Agrawal, Ross Girshick, and Jitendra Malik.  Analyzing the performance of multilayer neural networks for object recognition.  In European conference on computer vision, pages 329–344. Springer, 2014.
  * [3] Shekoofeh Azizi, Basil Mustafa, Fiona Ryan, Zachary Beaver, Jan Freyberg, Jonathan Deaton, Aaron Loh, Alan Karthikesalingam, Simon Kornblith, Ting Chen, et al.  Big self-supervised models advance medical image classification.  arXiv preprint arXiv:2101.05224, 2021.
  * [4] Hossein Azizpour, Ali Sharif Razavian, Josephine Sullivan, Atsuto Maki, and Stefan Carlsson.  Factors of transferability for a generic convnet representation.  IEEE transactions on pattern analysis and machine intelligence, 38(9):1790–1802, 2015.
  * [5] Yajie Bao, Yang Li, Shao-Lun Huang, Lin Zhang, Lizhong Zheng, Amir Zamir, and Leonidas Guibas.  An information-theoretic approach to transferability in task transfer learning.  In 2019 IEEE International Conference on Image Processing (ICIP), pages 2309–2313. IEEE, 2019.
  * [6] Samy Bengio.  Sharing representations for long tail computer vision problems.  In Proceedings of the 2015 ACM on International Conference on Multimodal Interaction, pages 1–1, 2015.
  * [7] Thomas Berg, Jiongxin Liu, Seung Woo Lee, Michelle L Alexander, David W Jacobs, and Peter N Belhumeur.  Birdsnap: Large-scale fine-grained visual categorization of birds.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2011–2018, 2014.
  * [8] Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool.  Food-101 – mining discriminative components with random forests.  In European Conference on Computer Vision, 2014.
  * [9] Léon Bottou and Olivier Bousquet.  The tradeoffs of large scale learning.  In Advances in neural information processing systems, pages 161–168, 2008.
  * [10] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  arXiv preprint arXiv:2005.14165, 2020.
  * [11] Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam.  Encoder-decoder with atrous separable convolution for semantic image segmentation.  In Proceedings of the European conference on computer vision (ECCV), pages 801–818, 2018.
  * [12] Xinyang Chen, Sinan Wang, Bo Fu, Mingsheng Long, and Jianmin Wang.  Catastrophic forgetting meets negative transfer: Batch spectral shrinkage for safe transfer learning.  openreview, 2019.
  * [13] Brian Chu, Vashisht Madhavan, Oscar Beijbom, Judy Hoffman, and Trevor Darrell.  Best practices for fine-tuning visual classifiers to new domains.  In European conference on computer vision, pages 435–442. Springer, 2016.
  * [14] Mircea Cimpoi, Subhransu Maji, Iasonas Kokkinos, Sammy Mohamed, and Andrea Vedaldi.  Describing textures in the wild.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3606–3613, 2014.
  * [15] Gabriela Csurka.  Domain adaptation for visual applications: A comprehensive survey.  arXiv preprint arXiv:1702.05374, 2017.
  * [16] Yin Cui, Yang Song, Chen Sun, Andrew Howard, and Serge Belongie.  Large scale fine-grained categorization and domain-specific transfer learning.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4109–4118, 2018.
  * [17] Yin Cui, Feng Zhou, Yuanqing Lin, and Serge Belongie.  Fine-grained categorization and dataset bootstrapping using deep metric learning with humans in the loop.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1153–1162, 2016.
  * [18] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.  ImageNet: A Large-Scale Hierarchical Image Database.  In CVPR09, 2009.
  * [19] Jiankang Deng, Jia Guo, Niannan Xue, and Stefanos Zafeiriou.  Arcface: Additive angular margin loss for deep face recognition.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4690–4699, 2019.
  * [20] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman.  The PASCAL Visual Object Classes Challenge 2007 (VOC2007) Results.  http://www.pascal-network.org/challenges/VOC/voc2007/ workshop/index.html.
  * [21] Li Fei-Fei, Rob Fergus, and Pietro Perona.  Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories.  In 2004 conference on computer vision and pattern recognition workshop, pages 178–178. IEEE, 2004.
  * [22] Robert M French.  Catastrophic forgetting in connectionist networks.  Trends in cognitive sciences, 3(4):128–135, 1999.
  * [23] Alberto Garcia-Garcia, Sergio Orts-Escolano, Sergiu Oprea, Victor Villena-Martinez, Pablo Martinez-Gonzalez, and Jose Garcia-Rodriguez.  A survey on deep learning techniques for image and video semantic segmentation.  Applied Soft Computing, 70:41–65, 2018.
  * [24] Weifeng Ge and Yizhou Yu.  Borrowing treasures from the wealthy: Deep transfer learning through selective joint fine-tuning.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1086–1095, 2017.
  * [25] Swarnendu Ghosh, Nibaran Das, Ishita Das, and Ujjwal Maulik.  Understanding deep learning techniques for image segmentation.  ACM Computing Surveys (CSUR), 52(4):1–35, 2019.
  * [26] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 580–587, 2014.
  * [27] Boqing Gong, Yuan Shi, Fei Sha, and Kristen Grauman.  Geodesic flow kernel for unsupervised domain adaptation.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 2066–2073. IEEE, 2012.
  * [28] Nicolas Gonthier, Yann Gousseau, and Saïd Ladjal.  An analysis of the transfer learning of convolutional neural networks for artistic images.  arXiv preprint arXiv:2011.02727, 2020.
  * [29] Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio.  Deep learning, volume 1.  MIT press Cambridge, 2016.
  * [30] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  Advances in neural information processing systems, 27, 2014.
  * [31] Gregory Griffin, Alex Holub, and Pietro Perona.  Caltech-256 object category dataset.  authors.library.caltech.edu, 2007.
  * [32] Yunhui Guo, Honghui Shi, Abhishek Kumar, Kristen Grauman, Tajana Rosing, and Rogerio Feris.  Spottune: transfer learning through adaptive fine-tuning.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4805–4814, 2019.
  * [33] Kevin Gurney.  An introduction to neural networks.  CRC press, 1997.
  * [34] Kaiming He, Ross Girshick, and Piotr Dollár.  Rethinking imagenet pre-training.  arXiv preprint arXiv:1811.08883, 2018.
  * [35] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 2961–2969, 2017.
  * [36] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [37] Michal Heker and Hayit Greenspan.  Joint liver lesion segmentation and classification via transfer learning.  arXiv preprint arXiv:2004.12352, 2020.
  * [38] Dan Hendrycks and Thomas Dietterich.  Benchmarking neural network robustness to common corruptions and perturbations.  arXiv preprint arXiv:1903.12261, 2019.
  * [39] Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song.  Natural adversarial examples.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15262–15271, 2021.
  * [40] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  arXiv preprint arXiv:1503.02531, 2015.
  * [41] Kurt Hornik, Maxwell Stinchcombe, Halbert White, et al.  Multilayer feedforward networks are universal approximators.  Neural networks, 2(5):359–366, 1989.
  * [42] Minyoung Huh, Pulkit Agrawal, and Alexei A Efros.  What makes imagenet good for transfer learning?  arXiv preprint arXiv:1608.08614, 2016.
  * [43] Sergey Ioffe.  Batch renormalization: Towards reducing minibatch dependence in batch-normalized models.  arXiv preprint arXiv:1702.03275, 2017.
  * [44] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  arXiv preprint arXiv:1502.03167, 2015.
  * [45] Yunho Jeon, Yongseok Choi, Jaesun Park, Subin Yi, Dongyeon Cho, and Jiwon Kim.  Sample-based regularization: A transfer learning strategy toward better generalization.  arXiv preprint arXiv:2007.05181, 2020.
  * [46] Junguang Jiang, Yang Shu, Jianmin Wang, and Mingsheng Long.  Transferability in deep learning: A survey.  arXiv preprint arXiv:2201.05867, 2022.
  * [47] Longlong Jing and Yingli Tian.  Self-supervised visual feature learning with deep neural networks: A survey.  IEEE transactions on pattern analysis and machine intelligence, 2020\.
  * [48] Mahmut Kaya and Hasan Şakir Bilge.  Deep metric learning: A survey.  Symmetry, 11(9):1066, 2019.
  * [49] Aditya Khosla, Nityananda Jayadevaprakash, Bangpeng Yao, and Fei-Fei Li.  Novel dataset for fine-grained image categorization: Stanford dogs.  In Proc. CVPR Workshop on Fine-Grained Visual Categorization (FGVC), volume 2, 2011.
  * [50] Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby.  Big transfer (bit): General visual representation learning.  arXiv preprint arXiv:1912.11370, 2019.
  * [51] Simon Kornblith, Ting Chen, Honglak Lee, and Mohammad Norouzi.  Why do better loss functions lead to less transferable features?  Advances in Neural Information Processing Systems, 34, 2021.
  * [52] Simon Kornblith, Jonathon Shlens, and Quoc V Le.  Do better imagenet models transfer better?  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2661–2671, 2019.
  * [53] Zhi Kou, Kaichao You, Mingsheng Long, and Jianmin Wang.  Stochastic normalization.  Advances in Neural Information Processing Systems, 33, 2020.
  * [54] Oren Z Kraus, Ben T Grys, Jimmy Ba, Yolanda Chong, Brendan J Frey, Charles Boone, and Brenda J Andrews.  Automated analysis of high-content microscopy data with deep learning.  Molecular systems biology, 13(4):924, 2017.
  * [55] Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei.  3d object representations for fine-grained categorization.  In 4th International IEEE Workshop on 3D Representation and Recognition (3dRR-13), Sydney, Australia, 2013.
  * [56] Sajja Tulasi Krishna and Hemantha Kumar Kalluri.  Deep learning and transfer learning approaches for image classification.  International Journal of Recent Technology and Engineering (IJRTE), 7(5S4):427–432, 2019.
  * [57] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  cs.toronto.edu, 2009.
  * [58] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In Advances in neural information processing systems, pages 1097–1105, 2012.
  * [59] Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum.  Human-level concept learning through probabilistic program induction.  Science, 350(6266):1332–1338, 2015.
  * [60] Christian Ledig, Lucas Theis, Ferenc Huszár, Jose Caballero, Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, et al.  Photo-realistic single image super-resolution using a generative adversarial network.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4681–4690, 2017.
  * [61] Hao Li, Pratik Chaudhari, Hao Yang, Michael Lam, Avinash Ravichandran, Rahul Bhotika, and Stefano Soatto.  Rethinking the hyperparameters for fine-tuning.  arXiv preprint arXiv:2002.11770, 2020.
  * [62] Shan Li and Weihong Deng.  Deep facial expression recognition: A survey.  IEEE Transactions on Affective Computing, 2020.
  * [63] Xingjian Li, Haoyi Xiong, Hanchao Wang, Yuxuan Rao, Liping Liu, and Jun Huan.  Delta: Deep learning transfer using feature map with attention for convolutional networks.  arXiv preprint arXiv:1901.09229, 2019.
  * [64] Xuhong Li, Yves Grandvalet, and Franck Davoine.  Explicit inductive bias for transfer learning with convolutional networks.  arXiv preprint arXiv:1802.01483, 2018.
  * [65] Xuhong Li, Yves Grandvalet, and Franck Davoine.  A baseline regularization scheme for transfer learning with convolutional neural networks.  Pattern Recognition, 98:107049, 2020.
  * [66] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In European conference on computer vision, pages 740–755. Springer, 2014.
  * [67] Hong Liu, Mingsheng Long, Jianmin Wang, and Michael I Jordan.  Towards understanding the transferability of deep representations.  arXiv preprint arXiv:1909.12031, 2019.
  * [68] Weiyang Liu, Yandong Wen, Zhiding Yu, Ming Li, Bhiksha Raj, and Le Song.  Sphereface: Deep hypersphere embedding for face recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 212–220, 2017.
  * [69] Weiyang Liu, Yandong Wen, Zhiding Yu, and Meng Yang.  Large-margin softmax loss for convolutional neural networks.  In ICML, volume 2, page 7, 2016.
  * [70] Dhruv Mahajan, Ross Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li, Ashwin Bharambe, and Laurens van der Maaten.  Exploring the limits of weakly supervised pretraining.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 181–196, 2018.
  * [71] S. Maji, J. Kannala, E. Rahtu, M. Blaschko, and A. Vedaldi.  Fine-grained visual classification of aircraft.  Technical report, Toyota Technological Institute at Chicago, 2013.
  * [72] Fabio Maria Carlucci, Lorenzo Porzi, Barbara Caputo, Elisa Ricci, and Samuel Rota Bulo.  Autodial: Automatic domain alignment layers.  In Proceedings of the IEEE International Conference on Computer Vision, pages 5067–5075, 2017.
  * [73] Iacopo Masi, Yue Wu, Tal Hassner, and Prem Natarajan.  Deep face recognition: A survey.  In 2018 31st SIBGRAPI conference on graphics, patterns and images (SIBGRAPI), pages 471–478. IEEE, 2018.
  * [74] Maciej A Mazurowski, Mateusz Buda, Ashirbani Saha, and Mustafa R Bashir.  Deep learning in radiology: An overview of the concepts and a survey of the state of the art with focus on mri.  Journal of magnetic resonance imaging, 49(4):939–954, 2019.
  * [75] Michael McCloskey and Neal J Cohen.  Catastrophic interference in connectionist networks: The sequential learning problem.  In Psychology of learning and motivation, volume 24, pages 109–165. Elsevier, 1989.
  * [76] Thomas Mensink, Jasper Uijlings, Alina Kuznetsova, Michael Gygli, and Vittorio Ferrari.  Factors of influence for transfer learning across diverse appearance domains and task types.  arXiv preprint arXiv:2103.13318, 2021.
  * [77] George A Miller.  Wordnet: a lexical database for english.  Communications of the ACM, 38(11):39–41, 1995.
  * [78] Shervin Minaee, Yuri Boykov, Fatih Porikli, Antonio Plaza, Nasser Kehtarnavaz, and Demetri Terzopoulos.  Image segmentation using deep learning: A survey.  arXiv preprint arXiv:2001.05566, 2020.
  * [79] Tom M Mitchell et al.  Machine learning. 1997.  Burr Ridge, IL: McGraw Hill, 45(37):870–877, 1997.
  * [80] Romain Mormont, Pierre Geurts, and Raphaël Marée.  Comparison of deep transfer learning strategies for digital pathology.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 2262–2271, 2018.
  * [81] Stefan Munder and Dariu M Gavrila.  An experimental study on pedestrian classification.  IEEE transactions on pattern analysis and machine intelligence, 28(11):1863–1868, 2006.
  * [82] Kevin Musgrave, Serge Belongie, and Ser-Nam Lim.  A metric learning reality check.  In European Conference on Computer Vision, pages 681–699. Springer, 2020.
  * [83] Basil Mustafa, Aaron Loh, Jan Freyberg, Patricia MacWilliams, Megan Wilson, Scott Mayer McKinney, Marcin Sieniek, Jim Winkens, Yuan Liu, Peggy Bui, et al.  Supervised transfer learning at scale for medical imaging.  arXiv preprint arXiv:2101.05913, 2021.
  * [84] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng.  Reading digits in natural images with unsupervised feature learning.  research.google, 2011.
  * [85] Behnam Neyshabur, Hanie Sedghi, and Chiyuan Zhang.  What is being transferred in transfer learning?  arXiv preprint arXiv:2008.11687, 2020.
  * [86] Hong-Wei Ng, Viet Dung Nguyen, Vassilios Vonikakis, and Stefan Winkler.  Deep learning for emotion recognition on small datasets using transfer learning.  In Proceedings of the 2015 ACM on international conference on multimodal interaction, pages 443–449, 2015.
  * [87] Jiquan Ngiam, Daiyi Peng, Vijay Vasudevan, Simon Kornblith, Quoc V Le, and Ruoming Pang.  Domain adaptive transfer learning with specialist models.  arXiv preprint arXiv:1811.07056, 2018.
  * [88] Cuong Nguyen, Tal Hassner, Matthias Seeger, and Cedric Archambeau.  Leep: A new measure to evaluate transferability of learned representations.  In International Conference on Machine Learning, pages 7294–7305. PMLR, 2020.
  * [89] Maria-Elena Nilsback and Andrew Zisserman.  Automated flower classification over a large number of classes.  In 2008 Sixth Indian Conference on Computer Vision, Graphics & Image Processing, pages 722–729. IEEE, 2008.
  * [90] Tom Le Paine, Pooya Khorrami, Wei Han, and Thomas S Huang.  An analysis of unsupervised pre-training in light of recent advances.  arXiv preprint arXiv:1412.6597, 2014.
  * [91] Sinno Jialin Pan and Qiang Yang.  A survey on transfer learning.  IEEE Transactions on knowledge and data engineering, 22(10):1345–1359, 2009.
  * [92] Omkar M Parkhi, Andrea Vedaldi, Andrew Zisserman, and CV Jawahar.  Cats and dogs.  In 2012 IEEE conference on computer vision and pattern recognition, pages 3498–3505. IEEE, 2012.
  * [93] Deepak Pathak, Philipp Krahenbuhl, Jeff Donahue, Trevor Darrell, and Alexei A Efros.  Context encoders: Feature learning by inpainting.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2536–2544, 2016.
  * [94] Shmuel Peleg, Michael Werman, and Hillel Rom.  A unified approach to the change of resolution: Space and gray-level.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(7):739–742, 1989.
  * [95] Jo Plested and Tom Gedeon.  An analysis of the interaction between transfer learning protocols in deep neural networks.  In International Conference on Neural Information Processing, pages 312–323. Springer, 2019.
  * [96] Jo Plested, Xuyang Shen, and Tom Gedeon.  Non-binary deep transfer learning for imageclassification.  arXiv e-prints, page arXiv:2107.08585, July 2021.
  * [97] Joan Puigcerver, Carlos Riquelme, Basil Mustafa, Cedric Renggli, André Susano Pinto, Sylvain Gelly, Daniel Keysers, and Neil Houlsby.  Scalable transfer learning with expert models.  arXiv preprint arXiv:2009.13239, 2020.
  * [98] Ariadna Quattoni and Antonio Torralba.  Recognizing indoor scenes.  In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 413–420. IEEE, 2009.
  * [99] Alec Radford, Luke Metz, and Soumith Chintala.  Unsupervised representation learning with deep convolutional generative adversarial networks.  arXiv preprint arXiv:1511.06434, 2015.
  * [100] Maithra Raghu, Chiyuan Zhang, Jon Kleinberg, and Samy Bengio.  Transfusion: Understanding transfer learning for medical imaging.  arXiv preprint arXiv:1902.07208, 2019.
  * [101] Rajeev Ranjan, Carlos D Castillo, and Rama Chellappa.  L2-constrained softmax loss for discriminative face verification.  arXiv preprint arXiv:1703.09507, 2017.
  * [102] Roger Ratcliff.  Connectionist models of recognition memory: constraints imposed by learning and forgetting functions.  Psychological review, 97(2):285, 1990.
  * [103] Sylvestre-Alvise Rebuffi, Hakan Bilen, and Andrea Vedaldi.  Learning multiple visual domains with residual adapters.  In Advances in Neural Information Processing Systems, pages 506–516, 2017.
  * [104] Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi.  You only look once: Unified, real-time object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 779–788, 2016.
  * [105] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  Advances in neural information processing systems, 28:91–99, 2015\.
  * [106] Ricardo Ribani and Mauricio Marengoni.  A survey of transfer learning for convolutional neural networks.  In 2019 32nd SIBGRAPI Conference on Graphics, Patterns and Images Tutorials (SIBGRAPI-T), pages 47–57. IEEE, 2019.
  * [107] Tal Ridnik, Hussam Lawen, Asaf Noy, and Itamar Friedman.  Tresnet: High performance gpu-dedicated architecture.  arXiv preprint arXiv:2003.13630, 2020.
  * [108] Michael T Rosenstein, Zvika Marx, Leslie Pack Kaelbling, and Thomas G Dietterich.  To transfer or not to transfer.  In NIPS 2005 workshop on transfer learning, volume 898, pages 1–4, 2005.
  * [109] Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas.  The earth mover’s distance as a metric for image retrieval.  International journal of computer vision, 40(2):99–121, 2000.
  * [110] David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams.  Learning representations by back-propagating errors.  nature, 323(6088):533–536, 1986.
  * [111] Matthia Sabatelli, Mike Kestemont, Walter Daelemans, and Pierre Geurts.  Deep transfer learning for art classification problems.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 0–0, 2018.
  * [112] Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell.  Adapting visual category models to new domains.  In European conference on computer vision, pages 213–226. Springer, 2010.
  * [113] Florian Schroff, Dmitry Kalenichenko, and James Philbin.  Facenet: A unified embedding for face recognition and clustering.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 815–823, 2015.
  * [114] Tyler Scott, Karl Ridgeway, and Michael C Mozer.  Adapted deep embeddings: A synthesis of methods for k-shot inductive transfer learning.  In Advances in Neural Information Processing Systems, pages 76–85, 2018.
  * [115] Ling Shao, Fan Zhu, and Xuelong Li.  Transfer learning for visual categorization: A survey.  IEEE transactions on neural networks and learning systems, 26(5):1019–1034, 2014.
  * [116] Ali Sharif Razavian, Hossein Azizpour, Josephine Sullivan, and Stefan Carlsson.  Cnn features off-the-shelf: an astounding baseline for recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pages 806–813, 2014.
  * [117] Zhiqiang Shen, Zhuang Liu, Jianguo Li, Yu-Gang Jiang, Yurong Chen, and Xiangyang Xue.  Dsod: Learning deeply supervised object detectors from scratch.  In Proceedings of the IEEE international conference on computer vision, pages 1919–1927, 2017.
  * [118] Zhiqiang Shen, Honghui Shi, Rogerio Feris, Liangliang Cao, Shuicheng Yan, Ding Liu, Xinchao Wang, Xiangyang Xue, and Thomas S Huang.  Learning object detectors from scratch with gated recurrent feature pyramids.  arXiv preprint arXiv:1712.00886, 1, 2017.
  * [119] Jun Shu, Zongben Xu, and Deyu Meng.  Small sample learning in big data era.  arXiv preprint arXiv:1808.04572, 2018.
  * [120] Jake Snell, Kevin Swersky, and Richard S Zemel.  Prototypical networks for few-shot learning.  arXiv preprint arXiv:1703.05175, 2017.
  * [121] Khurram Soomro, Amir Roshan Zamir, and Mubarak Shah.  Ucf101: A dataset of 101 human actions classes from videos in the wild.  arXiv preprint arXiv:1212.0402, 2012.
  * [122] Nitish Srivastava, Elman Mansimov, and Ruslan Salakhudinov.  Unsupervised learning of video representations using lstms.  In International conference on machine learning, pages 843–852, 2015.
  * [123] Johannes Stallkamp, Marc Schlipsing, Jan Salmen, and Christian Igel.  Man vs. computer: Benchmarking machine learning algorithms for traffic sign recognition.  Neural networks, 32:323–332, 2012.
  * [124] Emma Strubell, Ananya Ganesh, and Andrew McCallum.  Energy and policy considerations for deep learning in nlp.  arXiv preprint arXiv:1906.02243, 2019.
  * [125] Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta.  Revisiting unreasonable effectiveness of data in deep learning era.  In Proceedings of the IEEE international conference on computer vision, pages 843–852, 2017.
  * [126] Nima Tajbakhsh, Jae Y Shin, Suryakanth R Gurudu, R Todd Hurst, Christopher B Kendall, Michael B Gotway, and Jianming Liang.  Convolutional neural networks for medical image analysis: Full training or fine tuning?  IEEE transactions on medical imaging, 35(5):1299–1312, 2016.
  * [127] Chuanqi Tan, Fuchun Sun, Tao Kong, Wenchang Zhang, Chao Yang, and Chunfang Liu.  A survey on deep transfer learning.  In International conference on artificial neural networks, pages 270–279. Springer, 2018.
  * [128] Mingxing Tan and Quoc V Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  arXiv preprint arXiv:1905.11946, 2019.
  * [129] Tatiana Tommasi and Tinne Tuytelaars.  A testbed for cross-dataset analysis.  In European Conference on Computer Vision, pages 18–31. Springer, 2014.
  * [130] Anh T Tran, Cuong V Nguyen, and Tal Hassner.  Transferability and hardness of supervised classification tasks.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1395–1405, 2019.
  * [131] Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pietro Perona, and Serge Belongie.  The inaturalist species classification and detection dataset.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8769–8778, 2018.
  * [132] Vladimir Vapnik.  Principles of risk minimization for learning theory.  In Advances in neural information processing systems, pages 831–838, 1992.
  * [133] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al.  Matching networks for one shot learning.  Advances in neural information processing systems, 29:3630–3638, 2016.
  * [134] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie.  The caltech-ucsd birds-200-2011 dataset.  vision.caltech.edu, 2011.
  * [135] Ruosi Wan, Haoyi Xiong, Xingjian Li, Zhanxing Zhu, and Jun Huan.  Towards making deep transfer learning never hurt.  In 2019 IEEE International Conference on Data Mining (ICDM), pages 578–587. IEEE, 2019.
  * [136] Hao Wang, Yitong Wang, Zheng Zhou, Xing Ji, Dihong Gong, Jingchao Zhou, Zhifeng Li, and Wei Liu.  Cosface: Large margin cosine loss for deep face recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5265–5274, 2018.
  * [137] Mei Wang and Weihong Deng.  Deep visual domain adaptation: A survey.  Neurocomputing, 312:135–153, 2018.
  * [138] Ximei Wang, Ying Jin, Mingsheng Long, Jianmin Wang, and Michael Jordan.  Transferable normalization: Towards improving transferability of deep neural networks.  openreview.net, 2019.
  * [139] Yaqing Wang, Quanming Yao, James T Kwok, and Lionel M Ni.  Generalizing from a few examples: A survey on few-shot learning.  ACM Computing Surveys (CSUR), 53(3):1–34, 2020.
  * [140] Zirui Wang, Zihang Dai, Barnabás Póczos, and Jaime Carbonell.  Characterizing and avoiding negative transfer.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11293–11302, 2019.
  * [141] Karl Weiss, Taghi M Khoshgoftaar, and DingDing Wang.  A survey of transfer learning.  Journal of Big data, 3(1):9, 2016.
  * [142] Yandong Wen, Kaipeng Zhang, Zhifeng Li, and Yu Qiao.  A discriminative feature learning approach for deep face recognition.  In European conference on computer vision, pages 499–515. Springer, 2016.
  * [143] Yue Wu, Tal Hassner, KangGeon Kim, Gerard Medioni, and Prem Natarajan.  Facial landmark detection with tweaked convolutional neural networks.  IEEE transactions on pattern analysis and machine intelligence, 40(12):3067–3074, 2018.
  * [144] Yuxin Wu and Kaiming He.  Group normalization.  In Proceedings of the European conference on computer vision (ECCV), pages 3–19, 2018.
  * [145] Jianxiong Xiao, James Hays, Krista A Ehinger, Aude Oliva, and Antonio Torralba.  Sun database: Large-scale scene recognition from abbey to zoo.  In 2010 IEEE computer society conference on computer vision and pattern recognition, pages 3485–3492. IEEE, 2010.
  * [146] Qizhe Xie, Minh-Thang Luong, Eduard Hovy, and Quoc V Le.  Self-training with noisy student improves imagenet classification.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10687–10698, 2020.
  * [147] I Zeki Yalniz, Hervé Jégou, Kan Chen, Manohar Paluri, and Dhruv Mahajan.  Billion-scale semi-supervised learning for image classification.  arXiv preprint arXiv:1905.00546, 2019.
  * [148] Jinsung Yoon, Sercan Arik, and Tomas Pfister.  Data valuation using reinforcement learning.  In International Conference on Machine Learning, pages 10842–10851. PMLR, 2020.
  * [149] Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson.  How transferable are features in deep neural networks?  In Advances in neural information processing systems, pages 3320–3328, 2014.
  * [150] Kaichao You, Zhi Kou, Mingsheng Long, and Jianmin Wang.  Co-tuning for transfer learning.  Advances in Neural Information Processing Systems, 33, 2020.
  * [151] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz.  mixup: Beyond empirical risk minimization.  arXiv preprint arXiv:1710.09412, 2017.
  * [152] Jing Zhang, Wanqing Li, and Philip Ogunbona.  Transfer learning for cross-dataset recognition: a survey.  arXiv preprint arXiv:1705.04396, 2017.
  * [153] Jing Zhang, Wanqing Li, Philip Ogunbona, and Dong Xu.  Recent advances in transfer learning for cross-dataset visual recognition: A problem-oriented perspective.  ACM Computing Surveys (CSUR), 52(1):1–38, 2019.
  * [154] Yutong Zheng, Dipan K Pal, and Marios Savvides.  Ring loss: Convex feature normalization for face recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5089–5097, 2018.
  * [155] Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba.  Places: A 10 million image database for scene recognition.  IEEE transactions on pattern analysis and machine intelligence, 40(6):1452–1464, 2017.
  * [156] Linchao Zhu, Sercan O Arik, Yi Yang, and Tomas Pfister.  Learning to transfer learn.  openreview.net, 2019.
  * [157] Rui Zhu, Shifeng Zhang, Xiaobo Wang, Longyin Wen, Hailin Shi, Liefeng Bo, and Tao Mei.  Scratchdet: Training single-shot object detectors from scratch.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2268–2277, 2019.
  * [158] Fuzhen Zhuang, Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong, and Qing He.  A comprehensive survey on transfer learning.  Proceedings of the IEEE, 2020.
  * [159] Barret Zoph, Golnaz Ghiasi, Tsung-Yi Lin, Yin Cui, Hanxiao Liu, Ekin D Cubuk, and Quoc V Le.  Rethinking pre-training and self-training.  arXiv preprint arXiv:2006.06882, 2020.


$\displaystyle\overset{(1)}{\geq}\frac{||X_{S_{*}}^{T}X_{S_{*}}\alpha_{S_{*}}||}{\sqrt{s}}-\frac{||X_{S_{*}}^{T}e||_{2}}{\sqrt{s}}-\kappa_{a}\sqrt{p}$
$\displaystyle=\frac{n||\frac{X_{S_{*}}^{T}X_{S_{*}}}{n}\alpha_{S_{*}}||}{\sqrt{s}}-\frac{||X_{S_{*}}^{T}e||_{2}}{\sqrt{s}}-\kappa_{a}\sqrt{p}$

(1) follows by the reverse-triangle inequality. We know that by construction
$X/\sqrt{n}$ has isotropic, sub-gaussian, independent rows and thus satisfies
RIP of order $s+1$ (14). Thus, by Lemma 16,

$\displaystyle C$
$\displaystyle\geq\frac{n(1-\zeta_{s+1})||\alpha_{S_{*}}||_{2}}{\sqrt{s}}-\sqrt{n}\frac{||\frac{X_{S_{*}}^{T}}{\sqrt{n}}e||_{2}}{\sqrt{s}}-\kappa_{a}\sqrt{p}$

From Lemma 18 and since $\frac{X}{\sqrt{n}}$ satisfies and RIP of order $s+1$
we observe that,
$||\frac{X_{S_{*}}^{T}}{\sqrt{n}}e||_{2}\leq\sqrt{1+\zeta_{s+1}}||e||_{2}\leq\sqrt{(1+\zeta_{s+1})n}||e||_{\infty}$.
Combining these two results, we have,

$\displaystyle C$
$\displaystyle\geq\frac{n(1-\zeta_{s+1})||\alpha_{S_{*}}||_{2}}{\sqrt{s}}-\frac{n\sqrt{(1+\zeta_{s+1})}||e||_{\infty}}{\sqrt{s}}-\kappa_{a}\sqrt{p}$

Consider the events $B_{1},B_{2},...,B_{n}$ s.t.
$\text{Pr}[B_{i}]=\text{Pr}[|e_{i}|\leq B_{b}]\geq(1-p_{e}),i\in[n]$ (for some
probability $p_{e}\in[0,1]$. Comparing the expression with Lemma 32 and noting
that $e\sim\mathcal{N}(0,\sigma_{\epsilon}^{2})$ we observe that
$B_{e}=\sigma_{\epsilon}\sqrt{2\text{log}(\frac{2}{p_{e}})}=\kappa_{\epsilon}$.
We bound the probability of event $B$ with the union bound s.t.,
$\text{Pr}[B]=\text{Pr}[\max_{i\in[n]}|e_{i}|\leq B_{e}]$. Therefore,
$\text{Pr}[B^{c}]\leq\sum_{i\in[n]}\text{Pr}[B_{i}^{c}]\leq n\cdot p_{e}$.
Thus, $\text{Pr}[B]\geq 1-np_{e}$. Thus, w.p. $1-np_{e}$ event $B$ occurs and
thus,

$\displaystyle C$
$\displaystyle\geq\frac{n(1-\zeta_{s+1})||\alpha_{S_{*}}||_{2}}{\sqrt{s}}-n\kappa_{\epsilon}\frac{\sqrt{(1+\zeta_{s+1})}}{\sqrt{s}}-\kappa_{a}\sqrt{p}=C_{*}$

Next, we identify the expression for $C_{*}^{{}^{\prime}}$. For any $j\notin
S_{*}$ let us upper bound $|(\gamma_{0}^{-})_{j}|$,

$\displaystyle C^{{}^{\prime}}$ $\displaystyle=\max_{j\notin
S_{*}}|(\gamma_{0}^{-})_{j}|$ $\displaystyle=\max_{j\notin
S_{*}}|X_{j}^{T}y+\eta_{(\gamma_{0}^{-})_{j}}|$ $\displaystyle=\max_{j\notin
S_{*}}|X_{j}^{T}X_{S_{*}}\alpha_{S_{*}}+X_{j}^{T}e+\eta_{(\gamma_{0}^{-})_{j}}|$
$\displaystyle\overset{(1)}{\leq}||X_{j}^{T}X_{S_{*}}\alpha_{S_{*}}||_{2}+||X_{j}^{T}e||_{2}+\max_{j\notin
S_{*}}|\eta_{(\gamma_{0}^{-})_{j}}|$ $\displaystyle\leq
n||\frac{X_{j}^{T}X_{S_{*}}}{n}\alpha_{S_{*}}||_{2}+\sqrt{n}||\frac{X_{j}^{T}}{\sqrt{n}}e||_{2}+\max_{j\notin
S_{*}}|\eta_{(}\gamma_{0}^{-})_{j}|$

(1) follows by the $L_{2}$-$L_{\infty}$ inequality. Considering event $B$
again, we have that $\text{Pr}[B]=\text{Pr}[\max_{i\in[n]}|e_{i}|\leq B_{e}]$
and $B$ occurs w.p. $1-np_{e}$.

Further, consider events $C_{k},k\notin
S_{*}s.t.,\text{Pr}[C_{k}]=\text{Pr}[|\eta_{(}\gamma_{0}^{-})_{k}|\leq
B_{c}]\geq(1-p_{c})$. To bound the maximum of the noise terms, we need all
$C_{k},k\in[p-s]$ events to hold. By Lemma 33, $\text{Pr}[\max_{k\notin
S_{*}}|\eta_{(\gamma_{0}^{-})_{k}}|>B_{c}]=\text{Pr}[\cup_{k\in
S_{*}}C_{k}^{c}]\leq\sum\limits_{k\in S_{*}}\text{Pr}[C_{k}^{c}]=(p-s)\cdot
p_{c}$. Therefore, $\text{Pr}[\max_{k\notin
S_{*}}|\eta_{(\gamma_{0}^{-})_{k}}|\leq B_{c}]\geq 1-(p-s)\cdot p_{c}$. By
Lemma 32,
$B_{c}=\sigma_{0}\sqrt{2\text{log}(\frac{2}{p_{c}})}=\sqrt{2\text{log}(\frac{2}{p_{c}})}\frac{\kappa_{p}}{\epsilon_{step}}\sqrt{p}=\kappa_{c}\cdot\sqrt{p}$.

Combined with the RIP Lemmas 16, 18 for any $j\notin S_{*}$, we get the upper
bound,

$\displaystyle C^{{}^{\prime}}$ $\displaystyle\leq
n\zeta_{s+1}||\alpha_{S_{*}}||_{2}+n\sqrt{1+\zeta_{s+1}}\kappa_{\epsilon}+\kappa_{c}\sqrt{p}=C_{*}^{{}^{\prime}}$

Note that by the union bound (Lemma 33), events A, B, C hold w.p. at least
$1-sp_{a}-2np_{e}-(p-s)p_{c}$. Let
$p_{a}\triangleq\frac{p_{0}}{4s},p_{e}\triangleq\frac{p_{0}}{4n},p_{c}\triangleq\frac{p_{0}}{4(p-s)}$.

With probability $1-p_{0}$ the bounds, $C_{*},C_{*}^{{}^{\prime}}$ hold. Let
us identify the conditions for $C_{*}^{{}^{\prime}}<C_{*}$.

$\displaystyle\frac{n||\alpha_{S_{*}}||_{2}}{\sqrt{s}}$
$\displaystyle<n\zeta_{s+1}||\alpha_{S_{*}}||_{2}(1+\frac{1}{\sqrt{s}})$
$\displaystyle+n\sqrt{1+\zeta_{s+1}}\kappa_{\epsilon}(1+\frac{1}{\sqrt{s}})+(\kappa_{a}+\kappa_{c})\sqrt{p}$

Thus, put together we obtain the following condition on the RIC,
$\zeta_{s+1}$,

$\displaystyle\zeta_{s+1}$
$\displaystyle<\frac{n||\alpha_{S_{*}}||_{2}-n\sqrt{1+\zeta_{s+1}}\kappa_{\epsilon}(1+\sqrt{s})-(\kappa_{a}+\kappa_{c})\sqrt{ps}}{n||\alpha_{S_{*}}||_{2}(\sqrt{s}+1)}$
$\displaystyle<\frac{n||\alpha_{S_{*}}||_{2}-\sqrt{2}(1+\sqrt{s})n\kappa_{\epsilon}-(\kappa_{a}+\kappa_{c})\sqrt{ps}}{n||\alpha_{S_{*}}||_{2}(\sqrt{s}+1)}$

where the last line follows from the fact that $\zeta_{s+1}<1$. Suppose, we
can bound
$\sqrt{2}(1+\sqrt{s})n\kappa_{\epsilon}+(\kappa_{a}+\kappa_{c})\sqrt{p}\leq\frac{n||\alpha_{S_{*}}||_{2}}{2}$
that would give us
$\zeta_{s+1}<\frac{n||\alpha_{S_{*}}||_{2}}{2n||\alpha_{S_{*}}||_{2}(\sqrt{s}+1)}=\frac{1}{2(\sqrt{s}+1)}$.
It remains to characterize the condition for
$\sqrt{2}(1+\sqrt{s})n\kappa_{\epsilon}+(\kappa_{a}+\kappa_{c})\sqrt{p}\leq\frac{n||\alpha_{S_{*}}||_{2}}{2}$
to hold. Thus, we only need,

$\displaystyle n$
$\displaystyle\geq\frac{2\sqrt{2}(1+\sqrt{s})n\kappa_{\epsilon}}{||\alpha_{S_{*}}||_{2}}+\frac{2(\kappa_{a}+\kappa_{c})\sqrt{p}}{||\alpha_{S_{*}}||_{2}}$
$\displaystyle\rightarrow
n(1-\frac{2\sqrt{2}(1+\sqrt{s})\kappa_{\epsilon}}{||\alpha_{S_{*}}||_{2}})$
$\displaystyle\geq\frac{2(\kappa_{a}+\kappa_{c})\sqrt{p}}{||\alpha_{S_{*}}||_{2}}$
$\displaystyle\rightarrow n$
$\displaystyle\geq\frac{2(\kappa_{a}+\kappa_{c})}{||\alpha_{S_{*}}||_{2}-2\sqrt{2}(1+\sqrt{s})\kappa_{\epsilon}}\sqrt{p}$

Note,
$\kappa_{c}=\sqrt{2\text{log}(\frac{8(p-s)}{p_{0}})}\frac{\kappa_{p}}{\epsilon_{step}}$
and so $n=\Omega(\frac{\sqrt{p\log(p)}}{||\alpha_{S_{*}}||_{2}})$. We also
require that $||\alpha_{S_{*}}||_{2}-2\sqrt{2}(1+\sqrt{s})\kappa_{\epsilon}>0$
which is generally applicable since $\kappa_{\epsilon}$ (dependent on
$\sigma_{\epsilon}$) is generally smaller or comparable to $1$.

Step (l+1): By induction, $C_{*}^{{}^{\prime}}<C_{*}$ holds for all steps from
$1$ to $l$. We now prove the same for the $(l+1)^{th}$ step.

Case A: Analysis for when chosen column $j\in S_{\mathcal{A}}^{c}$ Let us
determine a lower bound for the correlation for when the column chosen belongs
to the true basis,

$\displaystyle C$ $\displaystyle=\max_{j\in S_{*}}|(\gamma_{l}^{-})_{j}|$
$\displaystyle=\max_{j\in
S_{*}}|(\gamma_{0}^{-}-\beta(\beta_{S_{\mathcal{A}}})^{-1}\gamma_{S_{\mathcal{A}}}|$
$\displaystyle=\max_{j\in S_{*}}|(X_{j}^{T}y+\eta_{(\gamma_{0}^{-})_{j}})$
$\displaystyle-(X_{j}^{T}X_{S_{\mathcal{A}}}+\eta_{\beta_{j,S_{\mathcal{A}}}})(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}})^{-1}$
$\displaystyle\cdot(X_{S_{\mathcal{A}}}^{T}y+\eta_{\gamma_{\mathcal{S_{\mathcal{A}}}}})|$

We now separate the signal and noise terms in order to analyze them further.
Consider the following expression to relate the true (_i.e.,_ non-private)
signal- $S_{true}^{j}$, the privatized version of the signal $S_{priv}^{j}$
for the $j^{th}$ and the various noise values (denoted by the $\eta$ terms)
for the $j^{th}$ dimension where $j\in\\{1,...,p\\}$.

$\displaystyle S_{priv}^{j}$
$\displaystyle\triangleq(X_{j}^{T}y+\eta_{(\gamma_{0}^{-})_{j}})$
$\displaystyle-(X_{j}^{T}X_{S_{\mathcal{A}}}+\eta_{\beta_{j,S_{\mathcal{A}}}})(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}})^{-1}$
$\displaystyle\cdot(X_{S_{\mathcal{A}}}^{T}y+\eta_{\gamma_{\mathcal{S_{\mathcal{A}}}}})$
$\displaystyle=\underbrace{X_{j}^{T}y-X_{j}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}})^{-1}X_{S_{\mathcal{A}}}^{T}y}_{S^{j}_{noisy}}$
$\displaystyle-\underbrace{(X_{j}^{T}X_{S_{\mathcal{A}}})(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}})^{-1}(\eta_{\gamma_{\mathcal{S_{\mathcal{A}}}}})}_{\eta_{31}^{j}}$
$\displaystyle-\underbrace{(\eta_{\beta_{j,S_{\mathcal{A}}}})(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}})^{-1}(X_{S_{\mathcal{A}}}^{T}y)}_{\eta_{32}^{j}}$
$\displaystyle-\underbrace{(\eta_{\beta_{j,S_{\mathcal{A}}}})(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}})^{-1}(\eta_{\gamma_{\mathcal{S_{\mathcal{A}}}}})}$
$\displaystyle+\underbrace{\eta_{(\gamma_{0}^{-})_{j}}}_{\eta_{2}^{j}}$

We apply the Woodbury Identity-Kailath Variant (Eqn.31) to each expression
marked by an asterisk to obtain the following simplifications,

$\displaystyle S^{j}_{noisy}$
$\displaystyle\overset{*}{=}\underbrace{X_{j}^{T}y-X_{j}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}X_{S_{\mathcal{A}}}^{T}y}_{S^{j}_{true}}$
$\displaystyle-\underbrace{X_{j}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}M_{1}\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}X_{S_{\mathcal{A}}}^{T}y}_{\eta^{j}_{1}}$
$\displaystyle\eta_{31}^{j}$
$\displaystyle\overset{*}{=}X_{j}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}M_{2}\eta_{\gamma_{\mathcal{S_{\mathcal{A}}}}}$
$\displaystyle\eta_{32}^{j}$
$\displaystyle\overset{*}{=}\eta_{\beta_{j,S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}M_{2}L_{2}$
$\displaystyle\eta_{33}^{j}$
$\displaystyle\overset{*}{=}\eta_{\beta_{j,S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}M_{2}\eta_{\gamma_{\mathcal{S_{\mathcal{A}}}}}$

Here,
$M_{1}=[\mathbb{I}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}]^{-1}$,
$M_{2}=\Big{(}\mathbb{I}-[\mathbb{I}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}]^{-1}\cdot\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}\Big{)}$
and $L_{2}=X_{S_{\mathcal{A}}}^{T}y$.

We look at the correlation values for the true support columns and non-support
columns. Let us suppose the lower bound and upper bound for
$C,C^{{}^{\prime}}$ (defined below) are $C_{*}$ and $C^{{}^{\prime}}_{*}$
respectively. We wish to identify the expressions for
$C_{*},C_{*}^{{}^{\prime}}$ and compare their values
$C_{*}^{{}^{\prime}}<C_{*}$ so that we always pick the column from the true
basis (steps follows similarly to Step $1$). For $j\in S_{*}$ we have,

$\displaystyle C_{j}$
$\displaystyle=|S_{true}^{j}+\eta_{1}^{j}+\eta_{2}^{j}+\eta_{31}^{j}+\eta_{32}^{j}+\eta_{33}^{j}|$
$\displaystyle\geq\frac{1}{\sqrt{s}}||S_{true}||_{2}-||\eta_{1}||_{\infty}-||\eta_{2}||_{\infty}$
$\displaystyle-||\eta_{31}||_{\infty}-||\eta_{32}||_{\infty}-||\eta_{33}||_{\infty}$

Similarly, when $j\notin S_{*}$ we have,

$\displaystyle C_{j}^{{}^{\prime}}$
$\displaystyle=|(S_{true}^{{}^{\prime}})^{j}+(\eta_{1}^{j})^{{}^{\prime}}+(\eta_{2}^{j})^{{}^{\prime}}+(\eta_{31}^{j})^{{}^{\prime}}+(\eta_{32}^{j})^{{}^{\prime}}+(\eta_{33}^{j})^{{}^{\prime}}|$
$\displaystyle\leq||(S_{true}^{{}^{\prime}})^{j}||_{2}$
$\displaystyle+||(\eta_{1}^{{}^{\prime}})^{j}||_{2}+||(\eta_{2}^{{}^{\prime}})^{j}||_{2}+||(\eta_{31}^{{}^{\prime}})^{j}||_{2}+||(\eta_{32}^{{}^{\prime}})^{j}||_{2}+||(\eta_{33}^{{}^{\prime}})^{j}||_{2}$

where we leverage the $L_{2}$-$L_{\infty}$ inequality, the triangle
inequality, and the fact that each term
$S_{true}^{j},\eta_{1}^{j},\eta_{2}^{j},\eta_{3}^{j}$ is 1-dimensional and
thus their $L_{2}$, $L_{\infty}$ norms are the same.

We now bound the signal values,

$\displaystyle||S_{true}||_{2}$
$\displaystyle=||X_{S_{\mathcal{A}}^{c}}^{T}[\mathbb{I}-P_{S}]y||_{2}$
$\displaystyle=||X_{S_{\mathcal{A}}^{c}}^{T}[\mathbb{I}-P_{S}](X_{S_{*}}\alpha_{S_{*}}+\epsilon)||_{2}$
$\displaystyle\overset{(1)}{=}||X_{S_{\mathcal{A}}^{c}}^{T}(X_{S_{\mathcal{A}}^{c}}\alpha_{S_{\mathcal{A}}^{c}}+\epsilon)||_{2}$
$\displaystyle=n||\frac{X_{S_{\mathcal{A}}^{c}}^{T}(X_{S_{\mathcal{A}}^{c}}^{T}\alpha_{S_{\mathcal{A}}^{c}}+\epsilon)}{n}$
$\displaystyle-\frac{X_{S_{\mathcal{A}}^{c}}^{T}X_{S_{\mathcal{A}}}}{n}(\frac{X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}}}{n})^{-1}\frac{X_{S_{\mathcal{A}}}^{T}(X_{S_{\mathcal{A}}^{c}}\alpha_{S_{\mathcal{A}}^{c}}+\epsilon)}{n}||_{2}$
$\displaystyle\overset{(2)}{\geq}n\Big{(}||\frac{X_{S_{\mathcal{A}}^{c}}^{T}X_{S_{\mathcal{A}}^{c}}\alpha_{S_{\mathcal{A}}^{c}}}{n}||_{2}-||\frac{X_{S_{\mathcal{A}}^{c}}^{T}e}{n}||_{2}$
$\displaystyle-||\frac{X_{S_{\mathcal{A}}^{c}}^{T}X_{S_{\mathcal{A}}}}{n}(\frac{X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}}}{n})^{-1}\frac{X_{S_{\mathcal{A}}}^{T}[X_{S_{\mathcal{A}}^{c}}\alpha_{S_{\mathcal{A}}^{c}}+\epsilon]}{n}||_{2}\Big{)}$
$\displaystyle\overset{(3)}{\geq}n(1-\zeta_{s+1})||\alpha_{S_{\mathcal{A}}^{c}}||_{2}-n\sqrt{1+\zeta_{s+1}}\kappa_{\epsilon}-\frac{n\zeta_{s+1}}{1-\zeta_{s+1}}||L_{1}||_{2}$
$\displaystyle\overset{(4)}{\geq}n(1-\zeta_{s+1})||\alpha_{S_{\mathcal{A}}^{c}}||_{2}-n\sqrt{1+\zeta_{s+1}}\kappa_{\epsilon}$
$\displaystyle-\frac{n\zeta_{s+1}}{(1-\zeta_{s+1})}[\zeta_{s+1}||\alpha_{S_{\mathcal{A}}^{c}}||_{2}+\sqrt{1+\zeta_{s+1}}\kappa_{\epsilon}]$
$\displaystyle\overset{(5)}{\geq}n(1-\zeta_{s+1})||\alpha_{S_{\mathcal{A}}^{c}}||_{2}-n\sqrt{1+\nu\zeta_{s+1}}\kappa_{\epsilon}$
$\displaystyle-n\zeta_{s+1}(1+\nu\zeta_{s+1})[\zeta_{s+1}||\alpha_{S_{\mathcal{A}}^{c}}||_{2}+\sqrt{1+\nu\zeta_{s+1}}\kappa_{\epsilon}]$

We observe (1) since the projection matrix nullifies the impact of the columns
already picked by OMP. (2) follows from the reverse triangle inequality and by
definition of $y$. (3) follows from Lemma 18 and 36 for the first and second
terms and Lemma 17, eigen-value bounds for the third term. (4) follows from
Lemma 21. (5) follows by Lemma 22.

Case B: Analysis for when chosen column $j\in S_{*}^{c}$ Let us determine an
upper bound for the correlation when the column chosen does not belong to the
true basis. These columns are also referred to as non-basis columns. For the
non-basis columns, we consider a single column each time. By definition, the
non-basis columns are separate and thus disjoint from the true basis set, and
thus $X_{S_{*}^{c}}$ is independent of $X_{S_{*}}$. Consider any $j\in
S_{*}^{c}$;

$\displaystyle|S_{true}^{j^{{}^{\prime}}}|$
$\displaystyle=||X_{j}^{T}[\mathbb{I}-P_{S}](X_{S_{*}}\alpha_{S_{*}}+\epsilon)||_{2}$
$\displaystyle\overset{(1)}{\leq}n||\frac{X_{j}^{T}X_{S_{\mathcal{A}}^{c}}\alpha_{S_{\mathcal{A}}^{c}}}{n}||_{2}+n||\frac{X_{j}^{T}e}{n}||_{2}$
$\displaystyle+n||\frac{X_{j}^{T}X_{S_{\mathcal{A}}}}{n}(\frac{X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}}}{n})^{-1}\frac{X_{S_{\mathcal{A}}}^{T}[X_{S_{\mathcal{A}}^{c}}\alpha_{S_{\mathcal{A}}^{c}}+\epsilon]}{n}||_{2}$
$\displaystyle\overset{(2)}{\leq}n\zeta_{s+1}||\alpha_{S_{\mathcal{A}}^{c}}||_{2}+n\sqrt{1+\zeta_{s+1}}\kappa_{\epsilon}$
$\displaystyle+\frac{n\zeta_{s+1}}{1-\zeta_{s+1}}[\zeta_{s+1}||\alpha_{S_{\mathcal{A}}^{c}}||+\sqrt{1+\zeta_{s+1}}\kappa_{\epsilon}]$
$\displaystyle\overset{(3)}{\leq}n\zeta_{s+1}||\alpha_{S_{\mathcal{A}}^{c}}||_{2}+n\sqrt{1+\nu\zeta_{s+1}}\kappa_{\epsilon}$
$\displaystyle+n\zeta_{s+1}(1+\nu\zeta_{s+1})[\zeta_{s+1}||\alpha_{S_{\mathcal{A}}^{c}}||+\sqrt{1+\nu\zeta_{s+1}}\kappa_{\epsilon}]$

(1) follows from the triangle inequality and since a 1-dimensional value $a$
has $||a||_{\infty}=||a||_{2}$. We have reduced columns in (1) for the
measurement matrix due to the projection matrix $\mathbb{I}-P_{S}$. (2)
follows steps identical to $||S_{true}||_{2}$ except for the first term. The
first term uses the approximate orthogonality property (Lemma 17) due to the
Restricted Isometry. By the union bound over all $j\notin S_{*}$ we can
conclude that the $||S_{true}^{j^{{}^{\prime}}}||_{\infty}$ is upper bounded.
(3) holds due to Lemma 22. We bound the remaining noise terms in the Appendix
section D.1.

A note about the probabilistic concentration bounds: We re-use common
concentration bounds for bounding the values of maximal noise contributions
across matrices and vectors. Since keeping track of such values is non-trivial
we note that, the number of dimensions $p$ and the stopping point $s$ of our
algorithm are both finite. Thus, given that we have several highly probable
bounds with the form $1-k_{1}e^{k_{2}}$ where both $k_{1},k_{2}$ are positive
numbers. Thus, the overall probability bound for our result will hold with a
similar form as well mainly because our iterations are finite and small ($s$)

Combination of Case A and Case B: Therefore, now, we can begin combining the
two bounds for this induction. Or more appropriately we compare the lower
bound and upper bounds of the correlations for the columns picked from the
true basis and the non-basis sets respectively. We have
$C^{{}^{\prime}}_{*}<C_{*}$. By combining the maximum values for any columns
we can compare $\max_{j\notin S_{*}}C_{j}^{{}^{\prime}}<\max_{j\in
S_{*}}C_{j}$ and substituting these terms we obtain,

$\displaystyle\frac{1}{\sqrt{s}}||S_{true}||_{2}$ $\displaystyle\geq$
$\displaystyle||S_{true}^{{}^{\prime}}||_{2}+\Big{(}||\eta_{1}^{j}||_{2}+||(\eta_{1}^{j})^{{}^{\prime}}||_{2}\Big{)}$
$\displaystyle+$
$\displaystyle\Big{(}||\eta_{2}^{j}||_{2}+||(\eta_{2}^{j})^{{}^{\prime}}||_{2}\Big{)}+\Big{(}||\eta_{31}^{j}||_{2}+||(\eta_{31}^{j})^{{}^{\prime}}||_{2}\Big{)}$
$\displaystyle+$
$\displaystyle\Big{(}||\eta_{32}^{j}||_{2}+||(\eta_{32}^{j})^{{}^{\prime}}||_{2}\Big{)}+\Big{(}||\eta_{33}^{j}||_{2}+||(\eta_{33}^{j})^{{}^{\prime}}||_{2}\Big{)}$

We simplify by substituting the noise bounds derived in previous Lemmas 23,
27, 24, 25, 26 as well as the signal norms $||S_{true}||_{2}$ and
$||S_{true}^{{}^{\prime}}||_{2}$.

$\displaystyle n||\alpha_{S_{\mathcal{A}}}^{c}||_{2}$ $\displaystyle\geq
n(\sqrt{s}+1)\zeta_{s+1}||\alpha_{S_{\mathcal{A}}}^{c}||_{2}$
$\displaystyle+n(\sqrt{s}+1)\sqrt{1+\nu\zeta_{s+1}}\kappa_{\epsilon}$
$\displaystyle+n(\sqrt{s}+1)\zeta_{s+1}^{2}(1+\nu\zeta_{s+1})||\alpha_{S_{\mathcal{A}}}^{c}||_{2}$
$\displaystyle+n(\sqrt{s}+1)\zeta_{s+1}(1+\nu\zeta_{s+1})^{3/2}\kappa_{\epsilon}$
$\displaystyle+s^{5/2}\kappa_{1}(1+\nu\zeta_{s+1})^{5/2}(1+(\nu+1)\zeta_{s+1})||\alpha_{S_{\mathcal{A}}}^{c}||_{2}$
$\displaystyle+s^{5/2}\kappa_{1}(1+\nu\zeta_{s+1})^{2}(1+(\nu+1)\zeta_{s+1})\kappa_{\epsilon}$
$\displaystyle+s^{3/2}\kappa_{31}(1+\nu\zeta_{s+1})(1+(\nu+1)\zeta_{s+1})$
$\displaystyle+2\sqrt{p}s\kappa_{32}(1+\nu\zeta_{s+1})^{3/2}||\alpha_{S_{\mathcal{A}}}^{c}||_{2}$
$\displaystyle+2\sqrt{p}s\kappa_{32}(1+\nu\zeta_{s+1})\kappa_{\epsilon}$
$\displaystyle+4\frac{\sqrt{p}s^{2}}{n}\kappa_{33}(1+\nu\zeta_{s+1})$
$\displaystyle+2\frac{\sqrt{ps}}{n}\kappa_{2}$

where,

$\displaystyle\kappa_{1}$
$\displaystyle=\kappa_{s}\kappa_{M_{2}}\sqrt{2\log(\frac{2s^{2}}{p_{b}})}$
$\displaystyle\kappa_{31}$
$\displaystyle=\kappa_{s}\kappa_{M_{2}}\sqrt{2\log(\frac{2s}{p_{b}})},$
$\displaystyle\kappa_{32}$
$\displaystyle=\kappa_{p}\kappa_{M_{2}}\sqrt{2\log(\frac{2(p-s)}{p_{b}})},$
$\displaystyle\kappa_{33}$
$\displaystyle=\frac{2\kappa_{M_{2}}s\kappa_{s}\kappa_{p}}{\kappa_{n}}\sqrt{2\log(\frac{2s}{p_{b}})\log(\frac{2(p-s)}{p_{b}}},$
$\displaystyle\kappa_{2}$
$\displaystyle=\kappa_{p}\sqrt{2\log(\frac{2(p-s)}{p_{b}})}$

and $p_{b}$ is the failure probability used in the Lemma 36.

To identify bounds on the various terms in our system model, we allocate the
left-hand side budget of $n||\alpha_{S_{\mathcal{A}}}^{c}||_{2}/2$
appropriately. Therefore, we obtain, the bound on $n$,

$\displaystyle\frac{n||\alpha_{S_{\mathcal{A}}}^{c}||_{2}}{2}\geq
2\sqrt{p}s\kappa_{32}(1+\nu\zeta_{s+1})^{3/2}||\alpha_{S_{\mathcal{A}}}^{c}||_{2}$
$\displaystyle\rightarrow$ $\displaystyle n\geq
4\sqrt{p}s\kappa_{32}(1+\nu\zeta_{s+1})^{3/2}=\mathcal{O}(\sqrt{p})$ (3)

Similarly, we can obtain a bound on the RIC, $\zeta_{s+1}$, by allocating the
budget of $n||\alpha_{S_{\mathcal{A}}}^{c}||_{2}/4$

$\displaystyle\frac{n||\alpha_{S_{\mathcal{A}}}^{c}||_{2}}{4}\geq
n(\sqrt{s}+1)\zeta_{s+1}||\alpha_{S_{\mathcal{A}}}^{c}||_{2}$
$\displaystyle\rightarrow$
$\displaystyle\zeta_{s+1}\leq\frac{1}{4(\sqrt{s}+1)}$ (4)

Now, the $\kappa_{\varepsilon}$ terms can be combined such that,

$\displaystyle\kappa_{\varepsilon}$
$\displaystyle\Big{(}2\sqrt{p}s\kappa_{32}(1+\nu\zeta_{s+1})+n(\sqrt{s}+1)(1+\nu\zeta_{s+1})$
$\displaystyle+n(\sqrt{s}+1)\zeta_{s+1}(1+\nu\zeta_{s+1})^{3/2}$
$\displaystyle+s^{5/2}\kappa_{1}(1+\nu\zeta_{s+1})^{2}(1+(\nu+1)\zeta_{s+1})\Big{)}$
$\displaystyle\leq$
$\displaystyle\kappa_{\epsilon}\Big{(}\frac{n}{2\sqrt{1+\nu\zeta_{s+1}}}+n(\sqrt{s}+1)(1+\nu\zeta_{s+1})$
$\displaystyle+\frac{n(1+\nu\zeta_{s+1})^{3/2}}{8}$
$\displaystyle+s^{5/2}\kappa_{1}(1+\nu\zeta_{s+1})^{2}(1+(\nu+1)\zeta_{s+1})\Big{)}$

Here, these inequalities arise from the first two bounds on $\sqrt{p}$ and the
RIC $\zeta_{s+1}$ (Eqns. 3 and 4). Clearly, the dominating term should be
$n(\sqrt{s}+1)(1+\nu\zeta_{s+1})$ as long as,

$\displaystyle s^{5/2}\kappa_{1}(1+\nu\zeta_{s+1})(1+(\nu+1)\zeta_{s+1})\leq
n(\sqrt{s}+1)$ $\displaystyle\rightarrow$ $\displaystyle
n\geq\frac{s^{5/2}\kappa_{1}(1+\nu\zeta_{s+1})(1+(\nu+1)\zeta_{s+1})}{\sqrt{s}+1}$
(5)

Thus, the $\kappa_{\epsilon}$ bound can be obtained by assuming that,

$\displaystyle
4\kappa_{\epsilon}n(\sqrt{s}+1)(1+\nu\zeta_{s+1})\leq\frac{1}{16}n||\alpha_{S_{\mathcal{A}}}^{c}||_{2}$
$\displaystyle\rightarrow$
$\displaystyle\kappa_{\epsilon}\leq\frac{||\alpha_{S_{\mathcal{A}}}^{c}||_{2}}{16(\sqrt{s}+1)(1+\nu\zeta_{s+1})}$
(6)

From the remaining terms which are independent of both $p$ and $n$, we pick
the dominant term to obtain another bound on $n$ in terms of $s$,

$\displaystyle
2s^{5/2}\kappa_{1}(1+\nu\zeta_{s+1})^{5/2}(1+(\nu+1)\zeta_{s+1})||\alpha_{S_{\mathcal{A}}}^{c}||_{2}\leq\frac{n||\alpha_{S_{\mathcal{A}}}^{c}||_{2}}{8}$
$\displaystyle\rightarrow$ $\displaystyle n\geq
16s^{5/2}\kappa_{1}(1+\nu\zeta_{s+1})^{5/2}(1+(\nu+1)\zeta_{s+1})$ (7)

We can see that the remaining terms are extremely small and can be easily
bounded by the remaining budget.

##  Appendix F Proof of Main Theorem 8

Before proving the convergence result in Theorem 8, we will include some
additional results required by our analysis. First, we calculate the upper
bound on the $l_{2}$ differential privacy sensitivity of the maximum absolute
correlation in Lemma 28.

######  Lemma 28.

Consider a design matrix $X\in\mathbb{R}^{n\times p}$ satisfying RIP of order
$s+1$ and with RIC $\zeta_{s+1}$. Now given the correlation/gradient $C_{j}$
(as computed in Line 4 of algorithm 4) for any $j\in[p]$, we show that the
$L_{2}$ sensitivity of $C_{j}$ is upper bounded by the following values,

$\displaystyle\Delta_{2}(C_{j})\leq
1+2X_{M}\kappa_{\varepsilon}+2\sqrt{s}X_{M}^{2}(\frac{\lVert(\alpha_{*})_{S^{c}_{\mathcal{A}}}\rVert_{\infty}}{1-\zeta_{s+1}}+\frac{\sqrt{1+\zeta_{s+1}}\kappa_{\varepsilon}}{1-\zeta_{s+1}})\triangleq
B_{C}$

where $\alpha_{*}$ is the underlying ground-truth model,
$\kappa_{\varepsilon}=\sqrt{2\log(2n/p_{b})}\sigma_{\varepsilon}$ and
$\sigma_{\varepsilon}$ is the additive system error’s standard deviation. We
also need to assume that $\zeta_{s+1}<\frac{1}{\sqrt{s}}$ and
$n>\frac{6s^{2}C_{1}X_{M}^{5}y_{M}\sqrt{2\log(2s/p_{b})}}{\mu_{s}^{2}(1-\zeta_{s+1})^{2}}$.
Here, the result holds with probability $1-3p_{b}$.

###### Proof.

Consider arbitrary adjacent datasets $X,X^{{}^{\prime}}\in\mathbb{R}^{n\times
p}$ such that they differ in only their $k^{th}$ record/row. At any iteration
of Line 4 in Algorithm 4, the set $S_{\mathcal{A}}$ of basis identified until
now has been fixed. Furthermore, we note that the private model received from
the server before the current iteration is also fixed. Denote this model by
$\alpha+\eta_{\alpha}$ where $\alpha$ is based on the currently predicted
feature set $S_{\mathcal{A}}$ and $\eta_{\alpha}$ denotes the privacy-related
noise added to the model using the NOISY-SMPC algorithm (Algorithm 1). Note,
here we refer to the model as fixed due to the differential privacy post-
processing wherein the model has already been privatized, and thus, future
processing will not affect its privacy. In comparison with standardized
private methods, we could consider this equivalent to using the same private
model while computing gradient sensitivity in DP-SGD under FL constraints.
Thus, the $l_{2}$ sensitivity of the correlation of the $j^{th}$ column
(denoted as $C_{j}$) can be computed as such,

$\displaystyle\Delta_{2}(C_{j})$ $\displaystyle=\max_{k\in[n]}\lVert
X^{T}_{j}y-(X^{{}^{\prime}})_{j}^{T}y^{{}^{\prime}}+X^{T}_{j}X_{S_{\mathcal{A}}}(\alpha+\eta_{\alpha})-(X^{{}^{\prime}})^{T}_{j}X^{{}^{\prime}}_{S_{\mathcal{A}}}(\alpha+\eta_{\alpha})\rVert_{2}$
$\displaystyle=\max_{k\in[n]}\lVert X^{T}_{j}(X_{S_{*}}\alpha_{*}+\varepsilon-
X_{S_{\mathcal{A}}}\alpha_{S_{\mathcal{A}}})-((X^{{}^{\prime}})^{T}_{j}(X^{{}^{\prime}}_{S_{*}}\alpha_{*}+\varepsilon-X^{{}^{\prime}}_{S_{\mathcal{A}}}\alpha_{S_{\mathcal{A}}}))\rVert+\lVert\Delta
A\eta_{\alpha}\rVert$
$\displaystyle=\max_{k\in[n]}\lVert(X_{jk}-X^{{}^{\prime}}_{jk})\varepsilon_{k}\rVert+\lVert(X^{T}_{j}X_{S_{\mathcal{A}}}-(X^{{}^{\prime}})^{T}_{j}X^{{}^{\prime}}_{S_{\mathcal{A}}})((\alpha_{*})_{S_{\mathcal{A}}}-\alpha)\rVert$
$\displaystyle+\lVert(X^{T}_{j}X_{S^{c}_{\mathcal{A}}}-(X^{{}^{\prime}})^{T}_{j}X^{{}^{\prime}}_{S^{c}_{\mathcal{A}}})(\alpha_{*})_{S^{c}_{\mathcal{A}}}\rVert+\lVert\Delta
A\eta_{\alpha}\rVert$ $\displaystyle\leq
2X_{M}\kappa_{\varepsilon}+\big{(}\lVert\Delta
A^{c}(\alpha_{*})_{S^{c}_{\mathcal{A}}}\rVert+\lVert\Delta
A((\alpha_{*})_{S_{\mathcal{A}}}-\alpha)\rVert\big{)}+\lVert\Delta
A\eta_{\alpha}\rVert$

Here, $A=X_{j}^{T}X_{S_{\mathcal{A}}},\Delta
A=-X_{jk}X_{S_{\mathcal{A}},k}+X^{{}^{\prime}}_{jk}X^{{}^{\prime}}_{S_{\mathcal{A}},k}$,
$\Delta
A^{c}=-X_{jk}X_{S^{c}_{\mathcal{A}},k}+X^{{}^{\prime}}_{jk}X^{{}^{\prime}}_{S^{c}_{\mathcal{A}},k}$
$\alpha=(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}X_{S_{\mathcal{A}}}^{T}y$
and $\kappa_{\varepsilon}=\sqrt{2\log(2n/p_{b})}\sigma_{\varepsilon}$ where
$p_{b}$ is a small positive probability. We also see that

$\displaystyle\lVert\Delta A\alpha\rVert_{2}$ $\displaystyle=\lVert
X_{jk}X_{S_{\mathcal{A}},k}+X^{{}^{\prime}}_{jk}X^{{}^{\prime}}_{S_{\mathcal{A}},k})\alpha\rVert$
$\displaystyle\leq X_{M}(\lVert X_{S_{\mathcal{A}},k}\alpha\rVert_{2}+\lVert
X^{{}^{\prime}}_{S_{\mathcal{A}},k}\alpha\rVert_{2})$
$\displaystyle\leq\sqrt{s}X_{M}(\lVert
X_{S_{\mathcal{A}},k}\alpha\rVert_{\infty}+\lVert
X^{{}^{\prime}}_{S_{\mathcal{A}},k}\alpha\rVert_{\infty})$ $\displaystyle\leq
2\sqrt{s}X_{M}^{2}\lVert\alpha\rVert_{\infty}$

Similar results can be derived for other terms in the expression for the
correlation bound. Thus, we simplify the correlation bound such that,

$\displaystyle\Delta_{2}(C_{j})\leq
2X_{M}\kappa_{\varepsilon}+2\sqrt{s}X_{M}^{2}(\lVert(\alpha_{*})_{S^{c}_{\mathcal{A}}}\rVert_{\infty}+\lVert\eta_{\alpha}\rVert_{\infty}+\lVert(\alpha_{*})_{S_{\mathcal{A}}}-\alpha)\rVert_{\infty})$

Now, suppose without loss of generality, suppose $\alpha$ is developed on
matrix $X$ and feature set $S_{\mathcal{A}}$ then we have,

$\displaystyle\alpha$
$\displaystyle=(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}X_{S_{\mathcal{A}}}^{T}y$
$\displaystyle=(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}X_{S_{\mathcal{A}}}^{T}(X_{S_{\mathcal{A}}}(\alpha_{*})_{S_{\mathcal{A}}}+X_{S^{c}_{\mathcal{A}}}(\alpha_{*})_{S^{c}_{\mathcal{A}}}+\varepsilon)$
$\displaystyle=(\alpha_{*})_{S_{\mathcal{A}}}+(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}X_{S_{\mathcal{A}}}^{T}(X_{S^{c}_{\mathcal{A}}}(\alpha_{*})_{S^{c}_{\mathcal{A}}}+\varepsilon)$
$\displaystyle\rightarrow$
$\displaystyle\lVert\alpha-(\alpha_{*})_{S_{\mathcal{A}}}\rVert_{2}\leq\frac{\zeta_{s+1}\lVert(\alpha_{*})_{S^{c}_{\mathcal{A}}}\rVert_{2}}{1-\zeta_{s+1}}+\frac{\sqrt{1+\zeta_{s+1}}\kappa_{\varepsilon}}{1-\zeta_{s+1}}$

Here, the final set of inequalities follows from the inequalities (1)-(10)
below.

Furthermore, we consider the value of $\eta_{\alpha}$, which denotes the noise
added to the model via the NOISY-SMPC mechanism using noisy correlations. We
can compute this exact value using the Kailath (Woodbury Variant) (Eqn. 31),
and the value is defined as follows,

$\displaystyle\eta_{\alpha}=(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}\Big{(}\eta_{\gamma_{S_{\mathcal{A}}}}-\eta_{\beta_{S_{\mathcal{A}}}}(\mathbb{I}+(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}\eta_{\beta_{S_{\mathcal{A}}}})^{-1}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}(X_{S_{\mathcal{A}}}^{T}y+\eta_{\gamma_{S_{\mathcal{A}}}})\Big{)}$

We now note the following $l_{2}$ bounds,

$\displaystyle\max_{k\in[n]}\lVert\Delta A\rVert_{2}$
$\displaystyle\overset{(1)}{\leq}2\sqrt{s}X_{M}^{2}$
$\displaystyle\max_{k\in[n]}\lVert
X^{T}_{j}y-(X^{{}^{\prime}})_{j}^{T}y^{{}^{\prime}}\rVert$
$\displaystyle\overset{(2)}{\leq}2X_{M}y_{M}$
$\displaystyle\lVert\frac{X_{S_{\mathcal{A}}}^{T}y}{n}\rVert$
$\displaystyle\overset{(3)}{\leq}\sqrt{s}X_{M}y_{M}$
$\displaystyle\lVert\alpha\rVert=\lVert(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}X_{S_{\mathcal{A}}}^{T}y\rVert=\lVert(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}X_{S_{\mathcal{A}}}^{T}(X_{S_{*}}\alpha_{*}+\varepsilon)\rVert$
$\displaystyle\overset{(4)}{\leq}\frac{1+\zeta_{s+1}}{1-\zeta_{s+1}}\lVert\alpha_{*}\rVert+\frac{\sqrt{1+\zeta_{s+1}}}{1-\zeta_{s+1}}\kappa_{\varepsilon}$
$\displaystyle\triangleq\kappa_{\alpha}$
$\displaystyle\lVert(\frac{X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}}}{n})^{-1}\rVert$
$\displaystyle\overset{(5)}{\leq}\frac{1}{1-\zeta_{s+1}}$
$\displaystyle\lVert\eta_{\gamma_{S_{\mathcal{A}}}}\rVert$
$\displaystyle\overset{(6)}{\leq}\frac{\sqrt{2s\log(2s/p_{b})}X_{M}y_{M}}{\mu_{s}}$
$\displaystyle\lVert\eta_{\beta_{S_{\mathcal{A}}}}\rVert$
$\displaystyle\overset{(7)}{\leq}\frac{sC_{1}X_{M}^{2}}{\mu_{s}}$
$\displaystyle\lVert(\mathbb{I}+(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}\eta_{\beta_{S_{\mathcal{A}}}})^{-1}\rVert$
$\displaystyle\overset{(8)}{\leq}1$
$\displaystyle\lVert\frac{X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}}}{n}\rVert$
$\displaystyle\overset{(9)}{\leq}1+\zeta_{s+1}$
$\displaystyle\lVert\frac{X_{P}^{T}X_{Q}}{n}\rVert\overset{(10)}{\leq}\zeta_{s+1}$

Here, inequalities (1)-(3) follow from the boundedness requirement on elements
of $X,y$. Inequalities (4)-(5) follows from the RIP condition on $X/\sqrt{n}$
matrix. Specifically, in (4),
$\kappa_{\varepsilon}=\sqrt{2\log(2n/p_{b})}\sigma_{\varepsilon}$ generated
from Lemma 36. Inequality (6) follows from Lemma 36 where elements in
$\eta_{\gamma_{S_{\mathcal{A}}}}$ have distribution
$\mathcal{N}(0,\frac{\sqrt{2s\log(2s/p_{b})}}{\mu_{s}})$. Inequality (7)
follows by noting the inequality of largest singular value inequality for a
random matrix inequality from Rudelson & Vershynin (2008) where the elements
in $\eta_{\beta_{S_{\mathcal{A}}}}$ are from distribution
$\mathcal{N}(0,\frac{\sqrt{s}}{\mu_{s}})$. (8) follows from Lemma 19. (9)
follows from the RIP property of $\bm{X}/\sqrt{n}$. Combining inequalities
above, we can find the bound on $\lVert\eta_{\alpha}\rVert$,

$\displaystyle\lVert\eta_{\alpha}\rVert$
$\displaystyle\leq\frac{\sqrt{2s\log(2s/p_{b})}X_{M}y_{M}}{n\mu_{s}(1-\zeta_{s+1})}+\frac{sC_{1}X_{M}^{2}}{\mu_{s}(1-\zeta_{s+1})^{2}}\cdot(\frac{\sqrt{2s\log(2s/p_{b})}X_{M}y_{M}}{n\mu_{s}}+\frac{\sqrt{s}X_{M}y_{M}}{n})$
$\displaystyle=\frac{\sqrt{2s\log(2s/p_{b})}X_{M}y_{M}}{n\mu_{s}(1-\zeta_{s+1})}+\frac{s^{3/2}C_{1}X_{M}^{3}y_{M}}{n\mu_{s}(1-\zeta_{s+1})^{2}}(\frac{\sqrt{2\log(2s/p_{b})}}{\mu_{s}}+1)$

where this bound holds with probability $1-2p_{b}$ and $p_{b}$ is a small
positive probability. We quickly note that given the $n$ (sample size) in the
denominator, then we can say that $\lVert\Delta A\eta_{\alpha}\rVert\leq 1$ if
$n>\frac{6s^{2}C_{1}X_{M}^{5}y_{M}\sqrt{2\log(2s/p_{b})}}{\mu_{s}^{2}(1-\zeta_{s+1})^{2}}$.
We now continue finding the upper bound of $\Delta_{2}(C_{j})$ using the
inequalities computed above,

$\displaystyle\Delta_{2}(C_{j})$ $\displaystyle\leq
1+2X_{M}\kappa_{\varepsilon}+2\sqrt{s}X_{M}^{2}(\lVert(\alpha_{*})_{S^{c}_{\mathcal{A}}}\rVert_{\infty}+\frac{\zeta_{s+1}\lVert(\alpha_{*})_{S^{c}_{\mathcal{A}}}\rVert_{2}}{1-\zeta_{s+1}}+\frac{\sqrt{1+\zeta_{s+1}}\kappa_{\varepsilon}}{1-\zeta_{s+1}})$
$\displaystyle=1+2X_{M}\kappa_{\varepsilon}+2\sqrt{s}X_{M}^{2}(\frac{\lVert(\alpha_{*})_{S^{c}_{\mathcal{A}}}\rVert_{\infty}}{1-\zeta_{s+1}}+\frac{\sqrt{1+\zeta_{s+1}}\kappa_{\varepsilon}}{1-\zeta_{s+1}})$
$\displaystyle=1+2X_{M}\kappa_{\varepsilon}+2\sqrt{s}X_{M}^{2}\kappa_{\alpha}^{{}^{\prime}}$
$\displaystyle\triangleq B_{C}$

where we assume that $\zeta_{s+1}<\frac{1}{\sqrt{s}}$ and
$\kappa_{\alpha}^{{}^{\prime}}=(\frac{\lVert(\alpha_{*})_{S^{c}_{\mathcal{A}}}\rVert_{\infty}}{1-\zeta_{s+1}}+\frac{\sqrt{1+\zeta_{s+1}}\kappa_{\varepsilon}}{1-\zeta_{s+1}})$.

∎

###  F.1 Performance of Algorithm 4

Here, similar to main theorem 7, we will demonstrate that Algorithm 4 can
recover the correct basis w.h.p. Again, we will use induction to prove our
result. We note from our proof sketch that the first induction step for both
the current theorem and main theorem 7 are the same (since the correlation and
the gradient have the same value for linear regression model. Thus, we can
immediately proceed to prove the induction step. Before proceeding, we restate
the preliminary steps of the induction.

Step 1: Here, we show that in the first step of the algorithm involving
picking the feature with the highest absolute correlation, we will pick the
correct feature (_i.e.,_ the one from the true basis set). Similar to Theorem
7, we find a condition on the sample size such that the lower bound of the
maximum absolute correlation of the true feature set is greater than the upper
bound of the maximum absolute correlation of the wrong feature set w.h.p.
Thus, we need to find the conditions that ensure $C_{*}>C^{{}^{\prime}}_{*}$
where $C_{*}$ and $C^{{}^{\prime}}_{*}$ are lower and upper bounds of $C$ and
$C^{{}^{\prime}}$ respectively. Here,

$\displaystyle C=\max_{j\in S_{*}}\lvert
X_{j}^{T}y+\eta_{(\gamma_{0}^{-})_{j}}\rvert$ $\displaystyle
C^{{}^{\prime}}=\max_{j\notin S_{*}}\lvert
X_{j}^{T}y+\eta_{(\gamma_{0}^{-})_{j}}\rvert$

and the rest of the notation follows from Algorithms 4 and 3. Note that the
proof follows exactly as Theorem 7’s step 1 and the sample size condition
remains the same.

Step (l+1): By induction, $C_{*}>C^{{}^{\prime}}_{*}$ holds for all steps from
$1$ to $l$. We will now show that a similar result holds for the $(l+1)^{th}$
step for Algorithm 4.

We first note the private correlation value is,

$\displaystyle C_{j}$
$\displaystyle=X_{j}^{T}y-X_{j}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}})^{-1}(X_{S_{\mathcal{A}}}^{T}y+\eta_{\gamma_{S_{\mathcal{A}}}})+\eta_{C_{j}}$
$\displaystyle=X_{j}^{T}y-X_{j}^{T}X_{\mathcal{S_{\mathcal{A}}}}\Big{(}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}-(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}(\mathbb{I}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1})^{-1}\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}\Big{)}(X_{S_{\mathcal{A}}}^{T}y+\eta_{\gamma_{S_{\mathcal{A}}}})$
$\displaystyle+\eta_{C_{j}}$
$\displaystyle=X_{j}^{T}y-X_{j}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}X_{S_{\mathcal{A}}}^{T}y-X_{j}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}\eta_{\gamma_{S_{\mathcal{A}}}}+\eta_{C_{j}}$
$\displaystyle-
X_{j}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}(\mathbb{I}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1})^{-1}\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}(X_{S_{\mathcal{A}}}^{T}y+\eta_{\gamma_{S_{\mathcal{A}}}})$

where $\eta_{C_{j}}\sim\mathcal{N}(0,\sigma_{C}^{2})$,
$\sigma_{C}=\frac{\sqrt{p}B_{C}}{\mu_{p}}$,
$B_{C}=\kappa_{\alpha}^{{}^{\prime}}\sqrt{s}+2X_{M}y_{M}$ and
$\eta_{\gamma_{S_{\mathcal{A}}}}\sim\mathcal{N}(0,\frac{s}{\mu_{s}^{2}}\mathbb{I}_{s})$
and
$\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}\sim\mathcal{N}(0,\frac{s}{\mu_{s}^{2}}\mathbb{I}_{s})$.
Note that the first term is the true correlation and can be re-written as
$X_{j}^{T}(\mathbb{I}-P)X_{S_{\mathcal{A}}}^{T}y$ where
$P=X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}X_{S_{\mathcal{A}}})^{-1}X_{S_{\mathcal{A}}}^{T}$
is the projection matrix.

Case A: Analysis for when chosen column $j\in S_{\mathcal{A}}^{c}$ (true
feature set except for features already chosen):

First, we will find a lower bound for the maximum correlation/gradient when
the features are chosen from the true set (except for the features already
chosen),

$\displaystyle\lVert C_{j}\rVert_{\infty}$
$\displaystyle\geq\frac{1}{\sqrt{s}}\lVert C_{j}\rVert_{2}$
$\displaystyle\overset{(1)}{\geq}\frac{1}{\sqrt{s}}\Big{(}\lVert
X_{S_{\mathcal{A}}^{c}}^{T}(\mathbb{I}-P)y\rVert_{2}-\lVert
X_{S_{\mathcal{A}}^{c}}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}\eta_{\gamma_{S_{\mathcal{A}}}}\rVert_{2}-\lVert\eta_{C_{j}}\rVert_{2}$
$\displaystyle-\lVert
X_{S_{\mathcal{A}}^{c}}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}(\mathbb{I}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1})\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}(X_{S_{\mathcal{A}}}^{T}y+\eta_{\gamma_{S_{\mathcal{A}}}})\rVert_{2}\Big{)}$
$\displaystyle\overset{(2)}{\geq}\frac{1}{\sqrt{s}}\lVert
X_{S_{\mathcal{A}}^{c}}^{T}(\mathbb{I}-P)y\rVert_{2}-\frac{1}{\sqrt{s}}\lVert
X_{S_{\mathcal{A}}^{c}}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}\eta_{\gamma_{S_{\mathcal{A}}}}\rVert_{2}-\lVert\eta_{C_{j}}\rVert_{\infty}$
$\displaystyle-\frac{1}{\sqrt{s}}\lVert
X_{S_{\mathcal{A}}^{c}}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}(\mathbb{I}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1})^{-1}\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}(X_{S_{\mathcal{A}}}^{T}y+\eta_{\gamma_{S_{\mathcal{A}}}})\rVert_{2}$
$\displaystyle\overset{(3)}{\geq}\frac{n(1-\zeta_{s+1})\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}{\sqrt{s}}-\frac{1}{\sqrt{s}}\lVert
X_{S_{\mathcal{A}}^{c}}^{T}\varepsilon\rVert_{2}-\frac{1}{\sqrt{s}}\lVert
X_{S_{\mathcal{A}}^{c}}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}X_{S_{\mathcal{A}}}^{T}(X_{S_{\mathcal{A}}^{c}}\alpha_{S_{\mathcal{A}}^{c}}+\varepsilon)\rVert_{2}$
$\displaystyle-\frac{\zeta_{s+1}}{\sqrt{s}(1-\zeta_{s+1})}\lVert\eta_{\gamma_{S_{\mathcal{A}}}}\rVert_{2}-\frac{\sqrt{p}B_{C}\kappa_{p}}{\mu_{p}}-\frac{\zeta_{s+1}}{\sqrt{s}(1-\zeta_{s+1})^{2}}\lVert\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}y+\eta_{\gamma_{S_{\mathcal{A}}}})\rVert_{2}$
$\displaystyle\overset{(4)}{\geq}\frac{n(1-\zeta_{s+1})\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}{\sqrt{s}}-\frac{n\zeta_{s+1}^{2}\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}{\sqrt{s}(1-\zeta_{s+1})}-\frac{\lVert
X_{S_{\mathcal{A}}^{c}}^{T}\varepsilon\rVert_{2}}{\sqrt{s}}-\frac{\zeta_{s+1}\lVert
X_{S_{\mathcal{A}}}^{T}\varepsilon\rVert_{2}}{\sqrt{s}(1-\zeta_{s+1})}$
$\displaystyle-\frac{\zeta_{s+1}}{\sqrt{s}(1-\zeta_{s+1})}\lVert\eta_{\gamma_{S_{\mathcal{A}}}}\rVert_{2}-\frac{\sqrt{p}B_{C}\kappa_{p}}{\mu_{p}}-\frac{\zeta_{s+1}}{\sqrt{s}(1-\zeta_{s+1})^{2}}\lVert\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}y+\eta_{\gamma_{S_{\mathcal{A}}}})\rVert_{2}$
$\displaystyle\overset{(5)}{\geq}\frac{n(1-\zeta_{s+1})\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}{\sqrt{s}}-\frac{n\zeta_{s+1}^{2}\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}{\sqrt{s}(1-\zeta_{s+1})}-\frac{1}{\sqrt{s}}n(\sqrt{1+\zeta_{s+1}})\kappa_{\varepsilon}\Big{(}1+\frac{\zeta_{s+1}}{1-\zeta_{s+1}}\Big{)}$
$\displaystyle-\frac{2X_{M}y_{M}\kappa_{s}\zeta_{s+1}}{\mu_{s}(1-\zeta_{s+1})}-\frac{\sqrt{p}B_{C}\kappa_{p}}{\mu_{p}}-\frac{\zeta_{s+1}C_{1}\sqrt{s}\kappa_{s}}{\mu_{s}\sqrt{s}(1-\zeta_{s+1})^{2}}\Big{(}(1+\zeta_{s+1})\lVert\alpha_{S_{*}}\rVert_{2}+\kappa_{\varepsilon}+\frac{2X_{M}y_{M}\kappa_{s}}{\mu_{s}}\Big{)}$
$\displaystyle\overset{(6)}{=}\frac{n(1-\zeta_{s+1})\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}{\sqrt{s}}-\frac{n\zeta_{s+1}^{2}\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}{\sqrt{s}(1-\zeta_{s+1})}-\frac{n(\sqrt{1+\zeta_{s+1}})\kappa_{\varepsilon}}{\sqrt{s}(1-\zeta_{s+1})}$
$\displaystyle-\frac{2X_{M}y_{M}\kappa_{s}\zeta_{s+1}}{\mu_{s}(1-\zeta_{s+1})}-\frac{\sqrt{p}B_{C}\kappa_{p}}{\mu_{p}}-\frac{\zeta_{s+1}C_{1}\kappa_{s}}{\mu_{s}(1-\zeta_{s+1})^{2}}\Big{(}(1+\zeta_{s+1})\lVert\alpha_{S_{*}}\rVert_{2}+\kappa_{\varepsilon}+\frac{2X_{M}y_{M}\kappa_{s}}{\mu_{s}}\Big{)}$

(1) follows by reverse triangle inequality. (2) holds due to the
$l_{2}$-$l_{\infty}$ inequality. (3)-(4) follow from the RIP properties of
$\bm{X}/\sqrt{n}$ as described in the inequalities in the proof of Lemma 28
alongside the Lemma 36 where
$\kappa_{p}^{{}^{\prime}}=\sqrt{2\log(\frac{2p}{p_{b}})}$ where $p_{b}$ is a
small positive failure probability. (5) follows from Lemma 36 where
$\kappa_{s}^{{}^{\prime}}=\sqrt{2\log(\frac{2s}{p_{b}})}$ and Theorem 2.4
(upper bound on largest singular value of random matrix) from Rudelson &
Vershynin (2008).

Case B: Analysis for when chosen column $j\notin S_{*}^{c}$:

We now compute the upper bound on the correlations of the features not in the
true set,

$\displaystyle\lVert C_{j}\rVert_{\infty}$ $\displaystyle\leq\lVert
C_{j}\rVert_{2}$ $\displaystyle\leq\lVert
X_{j}^{T}(\mathbb{I}-P)y\rVert_{2}+\lVert
X_{j}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}\eta_{\gamma_{S_{\mathcal{A}}}}\rVert_{2}+\lVert\eta_{C_{j}}\rVert_{2}$
$\displaystyle-\lVert
X_{j}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}(\mathbb{I}+\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1})\eta_{\beta_{S_{\mathcal{A}},S_{\mathcal{A}}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}(X_{S_{\mathcal{A}}}^{T}y+\eta_{\gamma_{S_{\mathcal{A}}}})\rVert_{2}\Big{)}$
$\displaystyle\overset{(1)}{\leq}\lVert
X_{j}^{T}(X_{S_{\mathcal{A}}^{c}\alpha_{S_{\mathcal{A}}^{c}}}+\varepsilon)\rVert_{2}+\lVert
X_{j}^{T}X_{S_{\mathcal{A}}}(X_{S_{\mathcal{A}}}^{T}X_{S_{\mathcal{A}}})^{-1}X_{S_{\mathcal{A}}}^{T}(X_{S_{\mathcal{A}}^{c}\alpha_{S_{\mathcal{A}}^{c}}}+\varepsilon)\rVert+\frac{2\sqrt{s}X_{M}y_{M}\kappa_{s}\zeta_{s+1}}{\mu_{s}(1-\zeta_{s+1})}+\frac{\sqrt{p}B_{C}\kappa_{p}}{\mu_{p}}$
$\displaystyle+\frac{\zeta_{s+1}C_{1}\sqrt{s}\kappa_{s}}{\mu_{s}(1-\zeta_{s+1})^{2}}\Big{(}(1+\zeta_{s+1})\lVert\alpha_{S_{*}}\rVert_{2}+\kappa_{\varepsilon}+\frac{2X_{M}y_{M}\kappa_{s}}{\mu_{s}}\Big{)}$
$\displaystyle\overset{(2)}{\leq}\frac{n\zeta_{s+1}\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}+n\sqrt{1+\zeta_{s+1}}\kappa_{\varepsilon}}{1-\zeta_{s+1}}+\frac{2\sqrt{s}X_{M}y_{M}\kappa_{s}\zeta_{s+1}}{\mu_{s}(1-\zeta_{s+1})}+\frac{\sqrt{p}B_{C}\kappa_{p}}{\mu_{p}}$
$\displaystyle+\frac{\zeta_{s+1}C_{1}\sqrt{s}\kappa_{s}}{\mu_{s}(1-\zeta_{s+1})^{2}}\Big{(}(1+\zeta_{s+1})\lVert\alpha_{S_{*}}\rVert_{2}+\kappa_{\varepsilon}+\frac{2X_{M}y_{M}\kappa_{s}}{\mu_{s}}\Big{)}$

(1)-(2) follow the same inequalities as the one developed in case A.

Combining Case A and Case B: We compare the upper bound of Case B with the
lower bound of Case A to find the conditions on the system parameters and
mainly the sample size.

$\displaystyle n\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}$
$\displaystyle\geq
n\zeta_{s+1}\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}\Big{(}1+\frac{\sqrt{s}}{1-\zeta_{s+1}}\Big{)}+(\sqrt{s}+1)\Bigg{(}\frac{n(\sqrt{1+\zeta_{s+1}})\kappa_{\varepsilon}}{1-\zeta_{s+1}}+\frac{2\sqrt{s}X_{M}y_{M}\kappa_{s}\zeta_{s+1}}{\mu_{s}(1-\zeta_{s+1})}+\frac{\sqrt{p}B_{C}\kappa_{p}}{\mu_{p}}$
$\displaystyle+\frac{\zeta_{s+1}C_{1}\sqrt{s}\kappa_{s}}{\mu_{s}(1-\zeta_{s+1})^{2}}\Big{(}(1+\zeta_{s+1})\lVert\alpha_{S_{*}}\rVert_{2}+\kappa_{\varepsilon}+\frac{2X_{M}y_{M}\kappa_{s}}{\mu_{s}}\Big{)}\Bigg{)}$

We now compare specific terms so as to maintain the inequality above and set
$\zeta_{s+1}<\frac{1}{\sqrt{s}+1}$

$\displaystyle\frac{n\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}{2}$
$\displaystyle>\frac{(\sqrt{s}+1)\sqrt{p}B_{c}\kappa_{p}}{\mu_{p}}$
$\displaystyle\frac{n\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}{6}$
$\displaystyle>\kappa_{\varepsilon}(1+\nu\zeta_{s+1})^{3/2}\Big{(}n(\sqrt{s}+1)+\frac{C_{1}\sqrt{s}\kappa_{s}\sqrt{1+\zeta_{s+1}}}{\mu_{s}}\Big{)}$
$\displaystyle>(\sqrt{s}+1)\kappa_{\varepsilon}\Big{(}\frac{n\sqrt{1+\zeta_{s+1}}}{1-\zeta_{s+1}}+\frac{\zeta_{s+1}C_{1}\sqrt{s}\kappa_{s}}{\mu_{s}(1-\zeta_{s+1})^{2}}\Big{)}$
$\displaystyle\frac{n\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}{6}$
$\displaystyle>\frac{2\sqrt{s}X_{M}y_{M}\kappa_{s}}{\mu_{s}(1-\zeta_{s+1})}>\frac{2\sqrt{s}(\sqrt{s}+1)X_{M}y_{M}\kappa_{s}\zeta_{s+1}}{\mu_{s}(1-\zeta_{s+1})}$
$\displaystyle\frac{n\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}{6}$
$\displaystyle>\frac{C_{1}\sqrt{s}\kappa_{s}}{\mu_{s}(1-\zeta_{s+1})^{2}}\Big{(}(1+\zeta_{s+1})\lVert\alpha_{S_{*}}\rVert_{2}+\frac{2X_{M}y_{M}\kappa_{s}}{\mu_{s}}\Big{)}$
$\displaystyle>\frac{\zeta_{s+1}(\sqrt{s}+1)C_{1}\sqrt{s}\kappa_{s}}{\mu_{s}(1-\zeta_{s+1})^{2}}\Big{(}(1+\zeta_{s+1})\lVert\alpha_{S_{*}}\rVert_{2}+\frac{2X_{M}y_{M}\kappa_{s}}{\mu_{s}}\Big{)}$

Simplifying these conditions, we obtain the following,

$\displaystyle n$
$\displaystyle>\frac{2(\sqrt{s}+1)\sqrt{p}B_{c}\kappa_{p}}{\mu_{p}\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}=\frac{2(\sqrt{s}+1)(\sqrt{s}\kappa_{\alpha}^{{}^{\prime}}+2X_{M}y_{M})\sqrt{p}\kappa_{p}}{\mu_{p}\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}$
$\displaystyle\kappa_{\varepsilon}$
$\displaystyle<\frac{\lVert\alpha_{S_{\mathcal{A}}^{c}}\rVert_{2}}{6(1+\nu\zeta_{s+1})^{3/2}\Big{(}\sqrt{s}+1+\frac{C_{1}\sqrt{s}\kappa_{s}\sqrt{1+\zeta_{s+1}}}{n\mu_{s}}\Big{)}}$

Note that here, we do not need to work with the remaining terms of order
$\sqrt{s}$ since we know $n$ and $\sqrt{p}$ are much larger than $\sqrt{s}$.

##  Appendix G Proofs of Risk and Estimation Error for the SPriFed-OMP
algorithm

Before we provide the risk and estimation error analyses we first state and
derive a commonly referred to result (Lemma 3 in Meinshausen & Yu (2009) and
Lemma 3.1 in Wasserman & Roeder (2009)) regarding the 2-norm of the product
$X_{S_{*}}^{T}\epsilon$ where $X_{S_{*}}$ refers to the features coinciding
with the true model indices and $\epsilon$ is the model error as shown in
Section 2.

######  Lemma 29.

The 2-norm of the product $X_{S_{*}}^{T}\epsilon$ is upper bounded by
$\sqrt{ns\sigma X_{M}}(2\log(2s/p_{b}))^{1/4}$ with probability $1-p_{b}$
where $p_{b}$ is the base probability and the terms in the product are defined
in Section 2.

Proof:

$\displaystyle||X_{S_{*}}^{T}\epsilon||_{2}$
$\displaystyle\overset{(1)}{\leq}\sqrt{n}\sqrt{\sum_{j\in S_{*}}Z_{j}^{2}}$
$\displaystyle\overset{(2)}{\leq}\sqrt{ns}\sqrt{\max_{j\in S_{*}}Z_{j}^{2}}$
$\displaystyle\overset{(3)}{\leq}\sqrt{2ns\log(2s/p_{b}))}\sigma_{\epsilon}X_{M}$

(1) sets $Z_{j}=\frac{1}{\sqrt{n}}X_{j}^{T}\epsilon$. (2) follows by
definition of a maximum. Now, $\mu(Z_{j})=0$ and
$Var(Z_{j})=\frac{1}{n}\sum_{i=1}^{n}X_{ij}^{2}\sigma_{\epsilon}^{2}\leq
X_{M}^{2}\sigma_{\epsilon}^{2}$ as the absolute value of coordinates $X_{ij}$
is bounded by $X_{M}$. Therefore, (3) follows by the Lemma 36 with probability
$1-p_{b}$.

###  G.1 Proof of Estimation Error Theorem 9

From Theorem 7 we know given that if satisfy the theorem’s assumptions we can
recover the true model basis with high probability. We will function under
this high probability event and assume that the predicted basis
$S_{\mathcal{A}}$ is equal to $S_{*}$ while computing the estimation error.
Thus, by SPriFed-OMP our estimation error can be derived as below,

$\displaystyle\Delta\alpha$
$\displaystyle\coloneqq||\hat{\alpha}-\alpha_{S_{*}}||_{2}$
$\displaystyle=||(\beta_{S_{*}})^{-1}\gamma_{S_{*}}-\alpha_{S_{*}}||_{2}$
$\displaystyle=||(X_{S_{*}}^{T}X_{S_{*}}+\eta_{\beta})^{-1}(X_{S_{*}}^{T}y+\eta_{\gamma_{S_{*}}})-\alpha_{S_{*}}||_{2}$
$\displaystyle\overset{(1)}{=}||(X_{S_{*}}^{T}X_{S_{*}})^{-1}(X_{S_{*}}^{T}y+\eta_{\gamma_{S_{*}}})-\alpha_{S_{*}}$
$\displaystyle-(X_{S_{*}}^{T}X_{S_{*}})^{-1}(\mathbb{I}+\eta_{\beta}(X_{S_{*}}^{T}X_{S_{*}})^{-1})^{-1}$
$\displaystyle\eta_{\beta}(X_{S_{*}}^{T}X_{S_{*}})^{-1}(X_{S_{*}}^{T}y+\eta_{\gamma_{S_{*}}})||_{2}$
$\displaystyle\overset{(2)}{=}||(X_{S_{*}}^{T}X_{S_{*}})^{-1}X_{S_{*}}^{T}\epsilon+(X_{S_{*}}^{T}X_{S_{*}})^{-1}\eta_{\gamma_{S_{*}}}$
$\displaystyle-(X_{S_{*}}^{T}X_{S_{*}})^{-1}(\mathbb{I}+\eta_{\beta}(X_{S_{*}}^{T}X_{S_{*}})^{-1})^{-1}$
$\displaystyle\cdot\eta_{\beta}(X_{S_{*}}^{T}X_{S_{*}})^{-1}(X_{S_{*}}^{T}y+\eta_{\gamma_{S_{*}}})||_{2}$
$\displaystyle\overset{(3)}{\leq}||(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1}\frac{X_{S_{*}}^{T}\epsilon}{n}||+||(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1}\frac{\eta_{\gamma_{S_{*}}}}{n}||_{2}$
$\displaystyle+||(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1}(\mathbb{I}+\frac{\eta_{\beta}}{n}(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1})^{-1}$
$\displaystyle\cdot\frac{\eta_{\beta}}{n}(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1}(\frac{X_{S_{*}}^{T}y}{n}+\frac{\eta_{\gamma_{S_{*}}}}{n})||_{2}$
$\displaystyle\overset{(4)}{\leq}\frac{(1-\zeta_{s+1})\sqrt{2ns\log(2s/p_{b}))}\sigma_{\epsilon}X_{M}}{n}+\frac{\kappa_{s}s\sqrt{2\log(\frac{2s}{p_{b}})}}{n(1-\zeta_{s+1})}$
$\displaystyle+\frac{\kappa_{M}}{(1-\zeta_{s+1})}||\frac{\eta_{\beta}}{n}(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1}(\frac{X_{S_{*}}^{T}y}{n}+\frac{\eta_{\gamma_{S_{*}}}}{n})||_{2}$
$\displaystyle\overset{(5)}{\leq}\frac{(1-\zeta_{s+1})\sqrt{2s\log(2s/p_{b}))}\sigma_{\epsilon}X_{M}}{\sqrt{n}}+\frac{\kappa_{s}s\sqrt{2\log(\frac{2s}{p_{b}})}}{n(1-\zeta_{s+1})}$
$\displaystyle+\frac{\kappa_{M}}{(1-\zeta_{s+1})^{2}}\cdot\frac{s^{3/2}\kappa_{s}\sqrt{2\log(\frac{2s^{2}}{p_{b}})}}{n}||(\frac{X_{S_{*}}^{T}y}{n}+\frac{\eta_{\gamma_{S_{*}}}}{n})||_{2}$
$\displaystyle\overset{(6)}{\leq}\frac{(1-\zeta_{s+1})\sqrt{2s\log(2s/p_{b}))}\sigma_{\epsilon}X_{M}}{\sqrt{n}}+\frac{\kappa_{s}s\sqrt{2\log(\frac{2s}{p_{b}})}}{n(1-\zeta_{s+1})}$
$\displaystyle+\frac{s^{3/2}\kappa_{s}\kappa_{M}\sqrt{2\log(\frac{2s^{2}}{p_{b}})}}{n(1-\zeta_{s+1})^{2}}\Big{(}(1+\zeta_{s+1})||\alpha_{S_{*}}||_{2}$
$\displaystyle+\sqrt{1+\zeta_{s+1}}\kappa_{\epsilon}+\frac{\kappa_{s}\sqrt{s}\sqrt{2\log(\frac{2s}{p_{b}})}}{n}\Big{)}$
$\displaystyle=\mathcal{O}\Big{(}\sqrt{\frac{s\log(s)}{n}}\Big{)}$

(1) follows by the Woodbury Identity (Eqn. 31). (2) follows since
$(X_{S_{*}}^{T}X_{S_{*}})^{-1}X_{S_{*}}^{T}y=\alpha_{S_{*}}+X_{S_{*}}^{T}\epsilon$
as $y=X_{S_{*}}\alpha_{S_{*}}+\epsilon$. (3) follows by the triangle
inequality and division and multiplication by $n$. (4) is based on bounds on
the eigenvalues of $X_{S_{*}}^{T}X_{S_{*}}$, the Lemma 19 as well as by the
Gaussian concentration bounds for the noise term
$\eta_{\gamma_{S_{*}}};\eta_{\gamma_{S_{*}}}\sim\mathcal{N}(0,\kappa_{s}^{2}s\mathbb{I}_{s})$
with probability $1-p_{b}$. Furthermore, the first term’s bound is derived by
the Lemma 29 and it holds with probability $1-p_{b}$. (5) follows from bounds
on eigenvalues of $X_{S_{*}}^{T}X_{S_{*}}$ and the upper bound of square
matrices’ maximum singular value (Theorem 2.4 from Rudelson & Vershynin (2008)
and the by the Gaussian concentration bounds for the term
$\eta_{\beta};\eta_{\beta}\sim\mathcal{N}(0,\kappa_{s}^{2}s^{2}\mathbb{I}_{s^{2}})$.
(5) also holds with probability $1-p_{b}$. Assuming $\kappa_{\epsilon}$ is
reasonably small, we notice that if $n\geq s^{3/2}||\alpha_{S_{*}}||_{2}$ then
the estimation error will be dominated by the second term. The expression
holds with $1-4p_{b}$ as we use the concentration inequality four times and
combine these events via the union bound.

###  G.2 Proof of Risk Analysis Theorem 10

From Theorem 7 we again know given that if satisfy the theorem’s assumptions
we can recover the true model basis with high probability. We will function
under this high probability event and assume that the predicted basis
$S_{\mathcal{A}}$ is equal to $S_{*}$ while computing the estimation error.
Thus, by SPriFed-OMP our estimation error can be derived as below,

$\displaystyle\Delta R$ $\displaystyle\coloneqq R(\hat{\alpha};X,y,n)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\Big{(}(x_{i}\hat{\alpha}-y_{i})^{2}-(x_{i}\alpha_{S_{*}}-y_{i})^{2}\Big{)}$
$\displaystyle\overset{(1)}{=}\frac{1}{n}\Big{(}||X_{S_{*}}\hat{\alpha}-y||^{2}-||X_{S_{*}}\alpha_{S_{*}}-y||^{2}\Big{)}$
$\displaystyle\overset{(2)}{=}\frac{1}{n}\Big{(}||X_{S_{*}}\beta_{S_{*}})^{-1}\gamma_{S_{*}}-y||^{2}-||X_{S_{*}}\alpha_{S_{*}}-y||^{2}\Big{)}$
$\displaystyle\overset{(3)}{=}\frac{1}{n}\Big{(}||X_{S_{*}}(X_{S_{*}}^{T}X_{S_{*}}+\eta_{\beta})^{-1}(X_{S_{*}}^{T}y+\eta_{\gamma_{S_{*}}})-y||^{2}$
$\displaystyle-||X_{S_{*}}\alpha_{S_{*}}-y||^{2}\Big{)}$
$\displaystyle\overset{(4)}{=}\frac{1}{n}\Big{(}||X_{S_{*}}((X_{S_{*}}^{T}X_{S_{*}})^{-1})(X_{S_{*}}^{T}y+\eta_{\gamma_{S_{*}}})$
$\displaystyle-
X_{S_{*}}(X_{S_{*}}^{T}X_{S_{*}})^{-1}(\mathbb{I}+\eta_{\beta}(X_{S_{*}}^{T}X_{S_{*}})^{-1})^{-1}$
$\displaystyle\cdot\eta_{\beta}(X_{S_{*}}^{T}X_{S_{*}})^{-1}(X_{S_{*}}^{T}y+\eta_{\gamma_{S_{*}}})-y||^{2}$
$\displaystyle-||X_{S_{*}}\alpha_{S_{*}}-y||^{2}\Big{)}$
$\displaystyle\overset{(5)}{=}\frac{1}{n}\Big{(}||X_{S_{*}}((X_{S_{*}}^{T}X_{S_{*}})^{-1})(\eta_{\gamma_{S_{*}}}+X_{S_{*}}^{T}\epsilon)$
$\displaystyle-
X_{S_{*}}(X_{S_{*}}^{T}X_{S_{*}})^{-1}(\mathbb{I}+\eta_{\beta}(X_{S_{*}}^{T}X_{S_{*}})^{-1})^{-1}$
$\displaystyle\eta_{\beta}(X_{S_{*}}^{T}X_{S_{*}})^{-1}(X_{S_{*}}^{T}y+\eta_{\gamma_{S_{*}}})||^{2}\Big{)}$
$\displaystyle\overset{(6)}{\leq}||\frac{X_{S_{*}}}{\sqrt{n}}(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1}\frac{(\eta_{\gamma_{S_{*}}}+X_{S_{*}}^{T}\epsilon)}{n}$
$\displaystyle-\frac{X_{S_{*}}}{\sqrt{n}}(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1}(\mathbb{I}+\frac{\eta_{\beta}}{n}(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1})^{-1}$
$\displaystyle\frac{\eta_{\beta}}{n}(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1}(\frac{X_{S_{*}}^{T}y}{n}+\frac{\eta_{\gamma_{S_{*}}}}{n})||_{2}^{2}$
$\displaystyle\overset{(7)}{\leq}2||\frac{X_{S_{*}}}{\sqrt{n}}(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1}\frac{\eta_{\gamma_{S_{*}}}}{n}||^{2}$
$\displaystyle+2||\frac{X_{S_{*}}}{\sqrt{n}}(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1}\frac{X_{S_{*}}^{T}\epsilon}{n}||^{2}$
$\displaystyle+2||\frac{X_{S_{*}}}{\sqrt{n}}(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1}(\mathbb{I}+\frac{\eta_{\beta}}{n}$
$\displaystyle\cdot(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1})^{-1}\frac{\eta_{\beta}}{n}(\frac{X_{S_{*}}^{T}X_{S_{*}}}{n})^{-1}(\frac{X_{S_{*}}^{T}y}{n}+\frac{\eta_{\gamma_{S_{*}}}}{n})||_{2}^{2}$
$\displaystyle\overset{(8)}{\leq}2\Big{(}\frac{(1+\zeta_{s+1})\kappa_{s}s\sqrt{2\log(\frac{2s}{p_{b}})}}{n(1-\zeta_{s+1})}\Big{)}^{2}$
$\displaystyle+2\Big{(}\frac{(1+\zeta_{s+1})\sqrt{2ns\log(2s/p_{b}))}\sigma_{\epsilon}X_{M}}{n(1-\zeta_{s+1})}\Big{)}^{2}$
$\displaystyle+2\Big{(}\frac{s^{3/2}\kappa_{s}\kappa_{M}\sqrt{2\log(\frac{2s^{2}}{p_{b}})}}{n(1-\zeta_{s+1})^{2}}\Big{(}(1+\zeta_{s+1})||\alpha_{S_{*}}||_{2}$
$\displaystyle+\sqrt{1+\zeta_{s+1}}\kappa_{\epsilon}+\frac{\kappa_{s}\sqrt{s}\sqrt{2\log(\frac{2s}{p_{b}})}}{n}\Big{)}\Big{)}^{2}$
$\displaystyle=\mathcal{O}\Big{(}\frac{2s\log(s))}{n}\Big{)}$

(1)-(3) follow from definitions of risk and the output of SPriFed-OMP. (4)
follows by the Woodbury expression (Eqn. 31). (5) follows since
$\alpha_{S_{*}}=(X_{S_{*}}^{T}X_{S_{*}})^{-1}X_{S_{*}}^{T}y$,
$X_{S_{*}}(X_{S_{*}}^{T}X_{S_{*}})^{-1}X_{S_{*}}^{T}=y$ and
$y=X_{S_{*}}\alpha_{S_{*}}+\epsilon$. (6) follows by including the $n$ inside
the squared norm. (7) follows since $||a-b||^{2}\leq 2(||a||^{2}+||b||^{2})$
which follows from Cauchy-Schwartz inequality. (7) The terms in (7) however
are similar to the intermdiate term (3) from Theorem 9 except for
multiplication by $X_{S_{*}}/\sqrt{n}$ and the squared $l_{2}$ norm. Clearly
by leveraging, the same inequalities and the RIP definition we can obtain (8).

##  Appendix H Additional Results and Notation

###  H.1 Simple Matrix Properties

For a general matrix $A\in\mathbb{R}^{n\times p}$, we state some simple
properties that normally hold irrespective of its distributions. For a column
index subset $S$, the pseudo-inverse of $A_{S}$ is given by
$A^{{\dagger}}=(A_{S}^{T}A_{S})^{-1}A_{S}^{T}$. Furthermore, we can easily
identify the projection matrix for $A_{S}$, that maps $A_{S}$ onto its
orthogonal components by, $P_{S}^{\perp}=I-P_{S}$, where
$P_{S}=A_{S}A_{S}^{{\dagger}}$. A projection matrix $P_{S}$ has the properties
$P_{S}^{2}=P_{S}$ and $P_{S}^{T}=P_{S}$. Verifying these properties is
straightforward by plugging in the value of $P_{S}$ in terms of $A_{S}$.

The Singular Value Decomposition of $A$, is written as $A=U\Sigma V^{T}$
where, $u\in\mathbb{R}^{n\times n},\Sigma\in\mathbb{R}^{n\times p}\text{(diag.
matrix)},V\in\mathbb{R}^{p\times p}$. $U,V$ are unitary and
$U^{T}U=UU^{T}=\mathbb{I};V^{T}V=VV^{T}=\mathbb{I}$. Furthermore, the SVD of
$A^{T}A$ is given by $V(\Sigma^{T}\Sigma)V^{T}=VDV^{T}$, where
$D=(\Sigma^{T}\Sigma)$. Thus, we can see that $A^{T}AV=VD$ and therefore, the
matrix $A^{T}A$ shares the same eigenvalue and singular values.

Denote the maximum and minimum singular values of a matrix $A$ by
$\sigma_{max}(A)$ and $\sigma_{min}(A)$, respectively. Similarly, define the
maximum and minimum eigenvalues of matrix $A$ by $\sigma_{\min}(A)$ and
$\lambda_{min}(A)$ respectively. Thus,
$\lambda_{\min}(X^{T}X)=\sigma_{max}(X^{T}X)=\sigma^{2}_{max}(X)$ and
$\lambda_{min}(X^{T}X)=\sigma_{min}(X^{T}X)=\sigma^{2}_{min}(X)$. Finally, the
$i^{th}$ singular value and eigenvalue of the matrix $A$ is given by
$\sigma_{i}(A)$ and $\lambda_{i}(A)$ respectively.

######  Lemma 30.

[Spectral Norm eigen-value bounds] Consider the matrix
$A\in\mathbb{R}^{n\times p}$ and vector $w\in\mathbb{R}^{p}$ then,

$\displaystyle\sigma_{\min}(A)||w||_{2}\leq||Aw||_{2}\leq\sigma_{\max}(A)||w||_{2}$

######  Lemma 31.

[Woodbury Identity: Kailath Variant] (page 153 from Bishop et al. (1995),
Petersen et al. (2008)) For conformable matrices $A,B,C$ we have the following
expression for the inverse of matrix sum,

$\displaystyle(A+BC)^{-1}=A^{-1}-A^{-1}B(\mathbb{I}+CA^{-1}B)^{-1}CA^{-1}$

Assuming, $B=\mathbb{I},C=N$ we obtain $\rightarrow$

$\displaystyle(A+N)^{-1}$
$\displaystyle=A^{-1}-A^{-1}(\mathbb{I}+NA^{-1})^{-1}NA^{-1}$

Assuming, $B=N,C=I$ we obtain $\rightarrow$

$\displaystyle(A+N)^{-1}=A^{-1}-A^{-1}N(\mathbb{I}+A^{-1}N)^{-1}A^{-1}$

###  H.2 Concentration bounds for Random Variables

We have previously seen in the differential privacy section, that we require
that the matrix values or their functional outputs be bounded. Therefore, here
we consider some of the useful properties of random variables that allows us
to bound their contributions.

######  Lemma 32.

[Concentration Inequality (Boucheron et al., 2013)] For Gaussian random
variable x with distribution $\mathcal{N}(0,\sigma^{2})$ we have,

$\displaystyle\text{Pr}[|x|\geq t]$ $\displaystyle\leq
2e^{\frac{-t^{2}}{2\sigma^{2}}}\rightarrow\text{Pr}[|x|<t]>1-2e^{\frac{-t^{2}}{2\sigma^{2}}}$

######  Lemma 33.

[Union Bound] The union bound states for any events $E_{1},E_{2},...,E_{n}$ we
have,

$\displaystyle\text{Pr}(\cup_{i=1}^{n}E_{i})\leq\sum_{i=1}^{n}\text{Pr}(E_{i})$

######  Lemma 34.

[Norm of matrix with subgaussian entries] (Theorem 4.3.5 from Vershynin
(2018))

Consider matrix $A\in\mathbb{R}^{n\times p}$ where its entries $A_{i,j}$ are
independent, mean zero, subgaussian random variables. Then, for any $t>0$ we
have,

$\displaystyle||A||_{2}\leq CK(\sqrt{n}+\sqrt{p}+t)$

with probability at least $1-2e^{-t^{2}}$ and
$K=\max_{i,j}||A_{i,j}||_{\Psi_{2}};i\in[n],j\in[p]$.

######  Lemma 35.

[Lower Bound of Minimum Singular Value for a Random Matrix]: (Theorem 1.2 from
Rudelson & Vershynin (2008)) Let $z_{1},...,z_{p}$ be independent, centered
real random variables with variance at least $1$ and sub-Gaussian moments
bounded by $B$. Let $A\in\mathbb{R}^{p\times p}$ matrix whose rows are
independent copies of the random vector $(z_{1},...,z_{p})$. Then for every
$\varepsilon\geq 0\rightarrow$

$\displaystyle\Pr[\sigma_{\min}(A)\leq\frac{\varepsilon}{\sqrt{p}}]\leq
C\varepsilon+c^{p}$

where $C>0,c\in(0,1)$ depend polynomially only on $B$.

######  Lemma 36.

[Concentration of the maximum random variable] Suppose we have $k$ random
variables $x_{i};i\in[k]$ each with distribution $\mathcal{N}(0,\sigma^{2})$.
We provide an upper bound for the maximum of these $k$ random variables as
following,

$\displaystyle\Pr[\max_{i=1}^{k}|x_{i}|\leq B]\geq 1-p_{b}$

where $B=\sigma\sqrt{2\log(2/p_{0})}$ and $p_{b}$ is the total failure
probability such that $p_{0}=\frac{p_{b}}{k}$.
Proof: Consider the events $E_{i}$ s.t., $|x_{i}|\leq B;i\in[k]$ and suppose
$\Pr[|x_{i}|\geq B]\leq p_{0}$. With Lemma 32 applied to $x_{i}$, we have,

$\displaystyle\Pr[|x_{i}|\geq B]$ $\displaystyle\leq
2e^{\frac{-B^{2}}{2\sigma^{2}}}$
$\displaystyle\Pr[|x_{i}|\geq\sigma\sqrt{2\log(\frac{2}{p_{0}})}]$
$\displaystyle\leq 2\exp(-2\log(2/p_{0})\sigma^{2}/2\sigma^{2})$
$\displaystyle\leq 2\exp(-\log(2/p_{0}))$ $\displaystyle\leq p_{0}$

Then, with the union bound, we can consider the probability of the event
$E_{0}$ s.t. $\max_{i=1}^{k}|x_{i}|\leq B$. Then,
$\Pr[E_{0}^{c}]=\Pr[\cup_{i=1}^{k}|x_{i}|\geq B]$ (where at least one value is
larger than the bound). Then,

$\displaystyle\Pr[E_{0}^{c}]$ $\displaystyle=\Pr[\cup_{i=1}^{k}|x_{i}|\geq B]$
$\displaystyle\leq\sum_{i=1}^{k}\Pr[|x_{i}|\geq B]$ $\displaystyle=k\cdot
p_{0}$ $\displaystyle\rightarrow\Pr[E_{0}]$
$\displaystyle=1-\Pr[E_{0}^{c}]=1-k\cdot p_{0}$

The first inequality is due to Boole’s inequality. In particular, if we wish
to bound our failure probabilities to a fixed value $p_{b}$ then we can have
$p_{0}=\frac{p_{b}}{k}$ and thus our bound
$B=\sigma\sqrt{2\log(\frac{2k}{p_{b}})}$ is achieved.