* Bakhtin et al. (2019) Anton Bakhtin, Sam Gross, et al. 2019\.  Real or Fake? Learning to Discriminate Machine from Human Generated Text.  _CoRR_ abs/1906.03351 (2019).  arXiv:1906.03351 http://arxiv.org/abs/1906.03351
  * Baki et al. (2017) Shahryar Baki, Rakesh Verma, et al. 2017\.  Scaling and Effectiveness of Email Masquerade Attacks: Exploiting Natural Language Generation. In _Proc. 2017 ACM ASIA CCS ’17_. ACM, New York, NY, USA, 469–482.  https://doi.org/10.1145/3052973.3053037
  * Baracaldo et al. (2017) Nathalie Baracaldo, Bryant Chen, et al. 2017\.  Mitigating poisoning attacks on machine learning models: A data provenance based approach. In _Proc. 10th ACM Workshop on Artificial Intelligence and Security_. 103–110.
  * Baum and Petrie (1966) Leonard E Baum and Ted Petrie. 1966.  Statistical inference for probabilistic functions of finite state Markov chains.  _The annals of mathematical statistics_ 37, 6 (1966), 1554–1563.
  * Baumgartner et al. (2020) Jason Baumgartner, Savvas Zannettou, et al. 2020\.  The Pushshift Reddit Dataset.  _CoRR_ abs/2001.08435 (2020).  arXiv:2001.08435 https://arxiv.org/abs/2001.08435
  * Bellinger et al. (2012) Colin Bellinger, Shiven Sharma, et al. 2012\.  One-Class versus Binary Classification: Which and When?. In _2012 11th International Conference on Machine Learning and Applications_ , Vol. 2. 102–106.  https://doi.org/10.1109/ICMLA.2012.212
  * Beresneva (2016) Daria Beresneva. 2016\.  Computer-generated text detection using machine learning: A systematic review. In _International Conference on Applications of Natural Language to Information Systems_. Springer, 421–426.
  * Berger and Milkman (2012) Jonah Berger and Katherine L Milkman. 2012.  What makes online content viral?  _Journal of marketing research_ 49, 2 (2012), 192–205.
  * Berglund et al. (2015) Mathias Berglund, Tapani Raiko, et al. 2015\.  Bidirectional Recurrent Neural Networks as Generative Models. In _NIPS_.
  * Bhat and Parthasarathy (2020) Meghana Moorthy Bhat and Srinivasan Parthasarathy. 2020.  How Effectively Can Machines Defend Against Machine-Generated Fake News? An Empirical Study. In _Proc. First Workshop on Insights from Negative Results in NLP_. ACL, Online, 48–53.  https://doi.org/10.18653/v1/2020.insights-1.7
  * Bhatt and Rios (2021) Paras Bhatt and Anthony Rios. 2021.  Detecting Bot-Generated Text by Characterizing Linguistic Accommodation in Human-Bot Interactions.  _CoRR_ abs/2106.01170 (2021).  arXiv:2106.01170 https://arxiv.org/abs/2106.01170
  * Biderman and Raff (2022) Stella Biderman and Edward Raff. 2022.  Fooling moss detection with pretrained language models. In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_. 2933–2943.
  * Bitton et al. (2021) Ron Bitton, Nadav Maman, et al. 2021\.  A Framework for Evaluating the Cybersecurity Risk of Real World, Machine Learning Production Systems.  _CoRR_ abs/2107.01806 (2021).  arXiv:2107.01806 https://arxiv.org/abs/2107.01806
  * Black et al. (2022) Sid Black, Stella Biderman, et al. 2022\.  GPT-NeoX-20B: An Open-Source Autoregressive Language Model.  arXiv:cs.CL/2204.06745
  * Braiterman et al. (2020) Zoe Braiterman, Adam Shostack, et al. 2020\.  https://www.threatmodelingmanifesto.org/
  * Brief (2021) CSET Policy Brief. 2021\.  AI and the Future of Disinformation Campaigns.  (2021).
  * Bromander et al. (2016) Siri Bromander, Audun Jøsang, et al. 2016\.  Semantic Cyberthreat Modelling.. In _STIDS_. 74–78.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, et al. 2020\.  Language Models are Few-Shot Learners.  _ArXiv_ abs/2005.14165 (2020).
  * Burns et al. (2019) A. J. Burns, M. Eric Johnson, et al. 2019\.  Spear phishing in a barrel: Insights from a targeted phishing campaign.  _J. Organ. Comput. Electron. Commer._ 29, 1 (2019), 24–39.  https://doi.org/10.1080/10919392.2019.1552745 arXiv:https://doi.org/10.1080/10919392.2019.1552745
  * Cabanac and Labbé (2021) Guillaume Cabanac and Cyril Labbé. 2021.  Prevalence of nonsensical algorithmically generated papers in the scientific literature.  _Journal of the Association for Information Science and Technology_ 72, 12 (2021), 1461–1476.
  * Carlini et al. (2020) Nicholas Carlini, Florian Tramèr, et al. 2020\.  Extracting Training Data from Large Language Models.  _CoRR_ abs/2012.07805 (2020).  arXiv:2012.07805 https://arxiv.org/abs/2012.07805
  * Chakraborty et al. (2018) Anirban Chakraborty, Manaar Alam, et al. 2018\.  Adversarial attacks and defences: A survey.  _arXiv preprint arXiv:1810.00069_ (2018).
  * Chen et al. (2021) Mark Chen, Jerry Tworek, et al. 2021\.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_ (2021).
  * Chen et al. (2022) Xingyuan Chen, Peng Jin, et al. 2022\.  Automatic Detection of Chinese Generated Essayss Based on Pre-trained BERT. In _2022 IEEE 10th Joint International Information Technology and Artificial Intelligence Conference (ITAIC)_ , Vol. 10. IEEE, 2257–2260.
  * Chiew et al. (2018) Kang Leng Chiew, Kelvin Sheng Chek Yong, et al. 2018\.  A survey of phishing attacks: Their types, vectors and technical approaches.  _Expert Systems with Applications_ 106 (2018), 1–20.  https://doi.org/10.1016/j.eswa.2018.03.050
  * Chorowski et al. (2015) Jan K Chorowski, Dzmitry Bahdanau, et al. 2015\.  Attention-based models for speech recognition.  _NeurIPS_ 28 (2015).
  * Clark et al. (2021) Elizabeth Clark, Tal August, et al. 2021\.  All That’s ‘Human’ Is Not Gold: Evaluating Human Evaluation of Generated Text. In _Proc. 59th Annual Meeting of the ACL and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_. ACL, Online, 7282–7296.  https://doi.org/10.18653/v1/2021.acl-long.565
  * Clive et al. (2021) Jordan Clive, Kris Cao, et al. 2021\.  Control prefixes for text generation.  _arXiv preprint arXiv:2110.08329_ (2021).
  * Crothers et al. (2022) Evan Crothers, Nathalie Japkowicz, et al. 2022\.  Adversarial Robustness of Neural-Statistical Features in Detection of Generative Transformers.  _arXiv preprint arXiv:2203.07983_ (2022).
  * Crothers et al. (2019) Evan Crothers, Nathalie Japkowicz, et al. 2019\.  Towards ethical content-based detection of online influence campaigns. In _2019 IEEE 29th International Workshop on Machine Learning for Signal Processing (MLSP)_. IEEE, 1–6.
  * Crothers et al. (2021) Evan Crothers, Herna Viktor, et al. 2021\.  Mean User-Text Agglomeration (MUTA): Practical User Representation and Visualization for Detection of Online Influence Operations. In _International Conference on Computational Data and Social Networks_. Springer, 305–318.
  * Cui et al. (2021) Yiming Cui, Wanxiang Che, et al. 2021\.  Pre-training with whole word masking for chinese bert.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ 29 (2021), 3504–3514.
  * Cutler et al. (2022) Joseph Cutler, Liam Dugan, et al. 2022\.  Automatic Detection of Hybrid Human-Machine Text Boundaries.  (2022).  https://www.cis.upenn.edu/~jwc/assets/nlp.pdf
  * Dadas et al. (2020) Sławomir Dadas, Michał Perełkiewicz, et al. 2020\.  Pre-training polish transformer-based language models at scale. In _International Conference on Artificial Intelligence and Soft Computing_. Springer, 301–314.
  * Dathathri et al. (2020) Sumanth Dathathri, Andrea Madotto, et al. 2020\.  Plug and Play Language Models: A Simple Approach to Controlled Text Generation. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=H1edEyBKDS
  * Dehouche (2021) Nassim Dehouche. 2021\.  Plagiarism in the age of massive Generative Pre-trained Transformers (GPT-3).  _Ethics in Science and Environmental Politics_ 21 (2021), 17–23.
  * Dethlefs and Cuayáhuitl (2010) Nina Dethlefs and Heriberto Cuayáhuitl. 2010.  Hierarchical Reinforcement Learning for Adaptive Text Generation. In _Proc. 6th INLG_. ACL.  https://aclanthology.org/W10-4204
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, et al. 2018\.  BERT: Pre-training of Deep Bidirectional Transformers.  _CoRR_ abs/1810.04805 (2018).  arXiv:1810.04805 http://arxiv.org/abs/1810.04805
  * Dong et al. (2022) Chenhe Dong, Yinghui Li, et al. 2022\.  A Survey of Natural Language Generation.  _ACM Comput. Surv._ (jul 2022).  https://doi.org/10.1145/3554727 Just Accepted.
  * Dou et al. (2022) Yao Dou, Maxwell Forbes, et al. 2022\.  Is GPT-3 Text Indistinguishable from Human Text? Scarecrow: A Framework for Scrutinizing Machine Text. In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. 7250–7274.
  * Duboue and McKeown (2003) Pablo Ariel Duboue and Kathleen R. McKeown. 2003.  Statistical Acquisition of Content Selection Rules for Natural Language Generation. In _Proc. 2003 Conference on Empirical Methods in Natural Language Processing_. 121–128.  https://aclanthology.org/W03-1016
  * Dugan et al. (2020) Liam Dugan, Daphne Ippolito, et al. 2020\.  RoFT: A Tool for Evaluating Human Detection of Machine-Generated Text.  _ArXiv_ abs/2010.03070 (2020).
  * Edwards (2022) Benj Edwards. 2022\.  Flooded with AI-generated images, some art communities ban them completely.  https://arstechnica.com/information-technology/2022/09/flooded-with-ai-generated-images-some-art-communities-ban-them-completely/
  * European Commission (2018) European Commission. 2018\.  Guidelines on Automated individual decision-making and Profiling for the purposes of Regulation.  https://ec.europa.eu/newsroom/article29/items/612053/en
  * European Commission and Directorate-General for Communications Networks, Content and Technology (2019) European Commission and Directorate-General for Communications Networks, Content and Technology. 2019\.  _Ethics guidelines for trustworthy AI_.  Publications Office.  https://doi.org/doi/10.2759/346720
  * Fagni et al. (2021) Tiziano Fagni, Fabrizio Falchi, et al. 2021\.  TweepFake: About detecting deepfake tweets.  _PLOS ONE_ 16, 5 (05 2021), 1–16.  https://doi.org/10.1371/journal.pone.0251415
  * Feng et al. (2018) Xiaocheng Feng, Ming Liu, et al. 2018\.  Topic-to-essay generation with neural networks.. In _IJCAI_. 4078–4084.
  * Ferrandis et al. (2022) Carlos Muñoz Ferrandis, Danish Contractor, et al. 2022\.  BigScience RAIL License v1.0.  https://huggingface.co/spaces/bigscience/license
  * Fröhling and Zubiaga (2021) Leon Fröhling and Arkaitz Zubiaga. 2021.  Feature-based detection of automated language models: tackling GPT-2, GPT-3 and Grover.  _PeerJ Computer Science_ 7 (2021), e443.
  * Gabielkov et al. (2016) Maksym Gabielkov, Arthi Ramachandran, et al. 2016\.  Social Clicks: What and Who Gets Read on Twitter?. In _ACM SIGMETRICS / IFIP Performance 2016_. Antibes Juan-les-Pins, France.  https://hal.inria.fr/hal-01281190
  * Gallé et al. (2021) Matthias Gallé, Jos Rozen, et al. 2021\.  Unsupervised and Distributional Detection of Machine-Generated Text.  arXiv:cs.CL/2111.02878
  * Gao et al. (2018) Ji Gao, Jack Lanchantin, et al. 2018\.  Black-box generation of adversarial text sequences to evade deep learning classifiers. In _2018 IEEE Security and Privacy Workshops (SPW)_. IEEE, 50–56.
  * Gao et al. (2021) Leo Gao, Stella Biderman, et al. 2021\.  The Pile: An 800GB Dataset of Diverse Text for Language Modeling.  _CoRR_ abs/2101.00027 (2021).  arXiv:2101.00027 https://arxiv.org/abs/2101.00027
  * Gatt and Krahmer (2018) Albert Gatt and Emiel Krahmer. 2018.  Survey of the state of the art in natural language generation: Core tasks, applications and evaluation.  _Journal of Artificial Intelligence Research_ 61 (2018), 65–170.
  * Gehrmann et al. (2019) Sebastian Gehrmann, Hendrik Strobelt, et al. 2019\.  GLTR: Statistical Detection and Visualization of Generated Text. In _Proc. 57th Annual Meeting of the ACL: System Demonstrations_. ACL, Florence, Italy, 111–116.  https://doi.org/10.18653/v1/P19-3019
  * Giaretta and Dragoni (2020) Alberto Giaretta and Nicola Dragoni. 2020.  Community Targeted Phishing. In _Proceedings of 6th International Conference in Software Engineering for Defence Applications_ , Paolo Ciancarini, Manuel Mazzara, et al. (Eds.). Springer International Publishing, Cham, 86–93.
  * Gooden (2022) Drew Gooden. 2022\.  using AI to write a youtube video.  Retrieved September 4, 2022 from https://www.youtube.com/watch?v=BaVpeJlcQzg
  * Goodfellow et al. (2020) Ian Goodfellow, Jean Pouget-Abadie, et al. 2020\.  Generative adversarial networks.  _Commun. ACM_ 63, 11 (2020), 139–144.
  * Goodside (2022) Riley Goodside. 2022\.  Exploiting GPT-3 prompts with malicious inputs that order the model to ignore its previous directions.  https://twitter.com/goodside/status/1569128808308957185
  * Guadarrama et al. (2013) Sergio Guadarrama, Niveda Krishnamoorthy, et al. 2013\.  YouTube2Text: Recognizing and Describing Arbitrary Activities Using Semantic Hierarchies and Zero-Shot Recognition. In _2013 IEEE ICCV_. 2712–2719.  https://doi.org/10.1109/ICCV.2013.337
  * Guerar et al. (2021) Meriem Guerar, Luca Verderame, et al. 2021\.  Gotta CAPTCHA ’Em All: A Survey of 20 Years of the Human-or-Computer Dilemma.  _ACM Comput. Surv._ 54, 9, Article 192 (oct 2021), 33 pages.  https://doi.org/10.1145/3477142
  * Hargrave (2005) Jeffrey Hargrave. 2005\.  SCIgen - An Automatic CS Paper Generator.  https://pdos.csail.mit.edu/archive/scigen/
  * Harkous et al. (2020) Hamza Harkous, Isabel Groves, et al. 2020\.  Have your text and use it too! End-to-end neural data-to-text generation with semantic fidelity. In _COLING 2020_.  https://www.amazon.science/publications/have-your-text-and-use-it-too-end-to-end-neural-data-to-text-generation-with-semantic-fidelity
  * He et al. (2022) Sherry He, Brett Hollenbeck, et al. 2022\.  The market for fake reviews.  _Marketing Science_ (2022).
  * Holtzman et al. (2019) Ari Holtzman, Jan Buys, et al. 2019\.  The Curious Case of Neural Text Degeneration.  _CoRR_ abs/1904.09751 (2019).  arXiv:1904.09751 http://arxiv.org/abs/1904.09751
  * Howard and Ruder (2018) Jeremy Howard and Sebastian Ruder. 2018.  Universal language model fine-tuning for text classification.  _arXiv preprint arXiv:1801.06146_ (2018).
  * Huq and Pervin (2020) Aminul Huq and Mst. Tasnim Pervin. 2020.  Adversarial Attacks and Defense on Texts: A Survey.  _CoRR_ abs/2005.14108 (2020).  arXiv:2005.14108 https://arxiv.org/abs/2005.14108
  * Ippolito et al. (2020) Daphne Ippolito, Daniel Duckworth, et al. 2020\.  Automatic Detection of Generated Text is Easiest when Humans are Fooled. In _ACL_.
  * Janarthanam and Lemon (2009) Srinivasan Janarthanam and Oliver Lemon. 2009.  Learning lexical alignment policies for generating referring expressions for spoken dialogue systems. In _Proc. 12th ENLG_. 74–81.
  * Japkowicz et al. (2000) Nathalie Japkowicz et al. 2000\.  Learning from imbalanced data sets: a comparison of various strategies. In _AAAI workshop on learning from imbalanced data sets_ , Vol. 68. AAAI Press Menlo Park, CA, 10–15.
  * Jasper AI (2022) Jasper AI. 2022\.  The best ai writing assistant.  Retrieved September 4, 2022 from https://www.jasper.ai/
  * Jawahar et al. (2020) Ganesh Jawahar, Muhammad Abdul-Mageed, et al. 2020\.  Automatic Detection of Machine Generated Text: A Critical Survey. In _Proc. 28th International Conference on Computational Linguistics_. 2296–2309.
  * Jin et al. (2022) Di Jin, Zhijing Jin, et al. 2022\.  Deep Learning for Text Style Transfer: A Survey.  _Computational Linguistics_ 48, 1 (March 2022), 155–205.  https://doi.org/10.1162/coli_a_00426
  * Jin et al. (2019) Di Jin, Zhijing Jin, et al. 2019\.  Is BERT Really Robust? Natural Language Attack on Text Classification and Entailment.  _CoRR_ abs/1907.11932 (2019).  arXiv:1907.11932 http://arxiv.org/abs/1907.11932
  * Kalchbrenner and Blunsom (2013) Nal Kalchbrenner and Phil Blunsom. 2013.  Recurrent continuous translation models. In _Proc. 2013 conference on empirical methods in natural language processing_. 1700–1709.
  * Kanapala et al. (2019) Ambedkar Kanapala, Sukomal Pal, et al. 2019\.  Text summarization from legal documents: a survey.  _Artificial Intelligence Review_ 51, 3 (2019), 371–402.
  * Kaur et al. (2022) Davinder Kaur, Suleyman Uslu, et al. 2022\.  Trustworthy Artificial Intelligence: A Review.  _ACM Comput. Surv._ 55, 2, Article 39 (jan 2022), 38 pages.  https://doi.org/10.1145/3491209
  * Kemp (2022a) Simon Kemp. 2022a.  Content across cultures.  https://datareportal.com/reports/future-trends-2022-cross-cultural-content
  * Kemp (2022b) Simon Kemp. 2022b.  Digital 2022 Global Digital Overview.  https://datareportal.com/reports/digital-2022-global-overview-report
  * Keskar et al. (2019) Nitish Shirish Keskar, Bryan McCann, et al. 2019\.  CTRL: A Conditional Transformer Language Model for Controllable Generation.  _ArXiv_ abs/1909.05858 (2019).
  * Khrushchev et al. (2022) Michael Khrushchev, Ruslan Vasilev, et al. 2022\.  YaLM 100B.  "https://huggingface.co/yandex/yalm-100b".
  * Kilcher (2022) Yannic Kilcher. 2022\.  This is the worst ai ever.  https://www.youtube.com/watch?v=efPrtcLdcdM
  * Kim et al. (2019) Soomin Kim, Joonhwan Lee, et al. 2019\.  Comparing data from chatbot and web surveys: Effects of platform and conversational style on survey response quality. In _Proc. 2019 CHI conference on human factors in computing systems_. 1–12.
  * Kohnfelder and Garg (1999) Loren Kohnfelder and Praerit Garg. 1999.  The threats to our products.  _Microsoft Interface, Microsoft Corporation_ 33 (1999).
  * Kondadadi et al. (2013) Ravikumar Kondadadi, Blake Howald, et al. 2013\.  A statistical nlg framework for aggregated planning and realization. In _Proc. 51st Annual Meeting of the ACL (Volume 1: Long Papers)_. 1406–1415.
  * Kowalczyk et al. (2022) Peter Kowalczyk, Marco Röder, et al. 2022\.  Detecting and Understanding Textual Deepfakes in Online Reviews.  (2022).
  * Krause et al. (2020) Ben Krause, Akhilesh Deepak Gotmare, et al. 2020\.  Gedi: Generative discriminator guided sequence generation.  _arXiv preprint arXiv:2009.06367_ (2020).
  * Kurenkov (2022) Andrey Kurenkov. 2022\.  Lessons from the GPT-4Chan Controversy.  https://thegradient.pub/gpt-4chan-lessons.  _The Gradient_ (2022).
  * Kushnareva et al. (2021) Laida Kushnareva, Daniil Cherniavskii, et al. 2021\.  Artificial Text Detection via Examining the Topology of Attention Maps.  _CoRR_ abs/2109.04825 (2021).  arXiv:2109.04825 https://arxiv.org/abs/2109.04825
  * Labbé and Labbé (2013) Cyril Labbé and Dominique Labbé. 2013.  Duplicate and fake publications in the scientific literature: how many SCIgen papers in computer science?  _Scientometrics_ 94, 1 (2013), 379–396.
  * Langkilde and Knight (1998) Irene Langkilde and Kevin Knight. 1998.  Generation that exploits corpus-based statistical knowledge. In _COLING 1998 Volume 1: The 17th International Conference on Computational Linguistics_.
  * Latah (2020) Majd Latah. 2020\.  Detection of malicious social bots: A survey and a refined taxonomy.  _Expert Systems with Applications_ 151 (2020), 113383.  https://doi.org/10.1016/j.eswa.2020.113383
  * Lavoie and Krishnamoorthy (2010) Allen Lavoie and Mukkai S. Krishnamoorthy. 2010.  Algorithmic Detection of Computer Generated Text.  _ArXiv_ abs/1008.0706 (2010).
  * LeCun et al. (2006) Yann LeCun, Sumit Chopra, et al. 2006\.  A tutorial on energy-based learning.  _Predicting structured data_ 1, 0 (2006).
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, et al. 2020\.  BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension. In _Proc. 58th Annu. Meet. ACL Sys. Demo._ ACL, Online, 7871–7880.  https://doi.org/10.18653/v1/2020.acl-main.703
  * Li et al. (2019) Guang Li, Linchao Zhu, et al. 2019\.  Entangled transformer for image captioning. In _Proc. IEEE/CVF_. 8928–8937.
  * Li et al. (2017) Haoran Li, Junnan Zhu, et al. 2017\.  Multi-modal Summarization for Asynchronous Collection of Text, Image, Audio and Video. In _Proc. 2017 Conf. EMNLP_. ACL, Copenhagen, Denmark, 1092–1102.  https://doi.org/10.18653/v1/D17-1114
  * Li et al. (2016) Jiwei Li, Will Monroe, et al. 2016\.  Deep Reinforcement Learning for Dialogue Generation. In _EMNLP_.
  * Li et al. (2021) Junyi Li, Tianyi Tang, et al. 2021\.  Pretrained Language Model for Text Generation: A Survey. In _Proc. 30th IJCAI_ , Zhi-Hua Zhou (Ed.). IJCAI Organization, 4492–4499.  https://doi.org/10.24963/ijcai.2021/612 Survey Track.
  * Li et al. (2018) Ziming Li, Julia Kiseleva, et al. 2018\.  Dialogue Generation: From Imitation Learning to Inverse Reinforcement Learning.  _CoRR_ abs/1812.03509 (2018).  arXiv:1812.03509 http://arxiv.org/abs/1812.03509
  * Liang et al. (2022) Percy Liang, Rishi Bommasani, et al. 2022\.  The Time Is Now to Develop Community Norms for the Release of Foundation Models.  https://crfm.stanford.edu/2022/05/17/community-norms.html
  * Liang and Reich (2022) Percy Liang and Rob Reich. 2022.  Condemning the deployment of gpt-4chan.  https://docs.google.com/forms/d/e/1FAIpQLSdh3Pgh0sGrYtRihBu-GPN7FSQoODBLvF7dVAFLZk2iuMgoLw/viewform
  * Lin et al. (2017) Kevin Lin, Dianqi Li, et al. 2017\.  Adversarial Ranking for Language Generation. In _NIPS_.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, et al. 2019\.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.  _ArXiv_ abs/1907.11692 (2019).
  * Lufkin (2021) Bryan Lufkin. 2021\.  Why do cover letters still exist?  https://www.bbc.com/worklife/article/20211005-why-do-cover-letters-still-exist
  * Luhn (1958) Hans Peter Luhn. 1958\.  The automatic creation of literature abstracts.  _IBM Journal of research and development_ 2, 2 (1958), 159–165.
  * Lundberg and Lee (2017) Scott M Lundberg and Su-In Lee. 2017.  A unified approach to interpreting model predictions.  _Advances in neural information processing systems_ 30 (2017).
  * Lyons (1991) John Lyons. 1991\.  _Natural Language and Universal Grammar: Volume 1: Essays in Linguistic Theory_. Vol. 1.  Cambridge University Press.
  * Manjaramkar (2021) Arya Manjaramkar. 2021\.  CodeGenX.  https://github.com/DeepGenX/CodeGenX.
  * Martin et al. (2019) Louis Martin, Benjamin Muller, et al. 2019\.  CamemBERT: a Tasty French Language Model.  _ArXiv_ abs/1911.03894 (2019).
  * Meleshevich and Schafer (2018) Kirill Meleshevich and Bret Schafer. 2018.  Online information laundering: The role of social media.  https://securingdemocracy.gmfus.org/online-information-laundering-the-role-of-social-media/
  * Merity et al. (2017) Stephen Merity, Nitish Shirish Keskar, et al. 2017\.  Regularizing and optim. LSTM lang. models.  _arXiv preprint arXiv:1708.02182_ (2017).
  * Meroño-Peñuela and Spagnuelo (2020) Albert Meroño-Peñuela and Dayana Spagnuelo. 2020.  Can a Transformer Assist in Scientific Writing? Generating Semantic Web Paper Snippets with GPT-2. In _The Semantic Web: ESWC 2020 Satellite Events_ , Andreas Harth, Valentina Presutti, et al. (Eds.). Springer International Publishing, Cham, 158–163.
  * Mikolov et al. (2012) Tomáš Mikolov et al. 2012\.  Stat. lang. models based on neural networks.  _Presentation at Google, Mountain View, 2nd April_ 80, 26 (2012).
  * Mink et al. (2022) Jaron Mink, Licheng Luo, et al. 2022\.  DeepPhish: Understanding User Trust Towards Artificially Generated Profiles in Online Social Networks. In _31st USENIX Security Symposium (USENIX Security 22)_. USENIX Association, Boston, MA, 1669–1686.  https://www.usenix.org/conference/usenixsecurity22/presentation/mink
  * Munir et al. (2021) Shaoor Munir, Brishna Batool, et al. 2021\.  Through the Looking Glass: Learning to Attribute Synthetic Text Generated by Language Models. In _Proc. 16th Conf. Euro. Chap. ACL: Main Vol._ ACL, Online, 1811–1822.  https://doi.org/10.18653/v1/2021.eacl-main.155
  * Nguyen-Son et al. (2017) Hoang-Quoc Nguyen-Son, Ngoc-Dung T. Tieu, et al. 2017\.  Identifying computer-generated text using statistical analysis. In _2017 APSIPA ASC_. 1504–1511.  https://doi.org/10.1109/APSIPA.2017.8282270
  * Open Cover Letter (2022) Open Cover Letter. 2022\.  Open Cover Letter: Generate Cover Letters with AI.  https://www.opencoverletter.com/
  * OpenAI (2020) OpenAI. 2020.  GPT-3.  https://github.com/openai/gpt-3.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, et al. 2019\.  fairseq: A Fast, Extensible Toolkit for Sequence Modeling. In _Proc. of NAACL-HLT 2019: Demo._
  * Papers With Code (2022) Papers With Code. 2022\.  Natural language processing benchmarks.  https://paperswithcode.com/area/natural-language-processing
  * Pawade et al. (2018) Dipti Pawade, Avani M. Sakhapara, et al. 2018\.  Story Scrambler - Automatic Text Generation Using Word Level RNN-LSTM.  _International Journal of Information Technology and Computer Science_ (2018).
  * Perera and Nand (2017) Rivindu Perera and Parma Nand. 2017.  Recent advances in natural language generation: A survey and classification of the empirical literature.  _Computing and Informatics_ 36, 1 (2017), 1–32.
  * Phillips et al. (2020) P Jonathon Phillips, Carina A Hahn, et al. 2020\.  Four principles of explainable artificial intelligence.  _Gaithersburg, Maryland_ (2020).
  * Phillips et al. (2018) P Jonathon Phillips, Amy N Yates, et al. 2018\.  Face recognition accuracy of forensic examiners, superrecognizers, and face recognition algorithms.  _Proc. National Academy of Sciences_ 115, 24 (2018), 6171–6176.
  * Radford et al. (2019a) Alec Radford, Jeff Wu, et al. 2019a.  Language Models are Unsupervised Multitask Learners.  (2019).
  * Radford et al. (2019b) Alec Radford, Jeff Wu, et al. 2019b.  GPT-2 Output Dataset.  https://github.com/openai/gpt-2-output-dataset.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, et al. 2020\.  Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer.  _J. of Mach. Learn. Res._ 21, 140 (2020), 1–67.  http://jmlr.org/papers/v21/20-074.html
  * Ramesh et al. (2021) Aditya Ramesh, Mikhail Pavlov, et al. 2021\.  Zero-shot text-to-image generation. In _ICML_. PMLR, 8821–8831.
  * Ranade et al. (2021) Priyanka Ranade, Aritran Piplai, et al. 2021\.  Generating Fake Cyber Threat Intelligence Using Transformer-Based Models. In _2021 International Joint Conference on Neural Networks (IJCNN)_. 1–9.  https://doi.org/10.1109/IJCNN52387.2021.9534192
  * Reddit (2018) Reddit. 2018.  Reddit Transparency Report: Suspicious Accounts.  https://www.reddit.com/wiki/suspiciousaccounts.
  * Reed et al. (2022) Scott Reed, Konrad Zolna, et al. 2022\.  A Generalist Agent.  https://doi.org/10.48550/ARXIV.2205.06175
  * Reiter and Dale (2002) Ehud Reiter and Robert Dale. 2002.  Building Applied Natural Language Generation Systems.  _Natural Language Engineering_ 3 (03 2002).  https://doi.org/10.1017/S1351324997001502
  * Rodriguez et al. (2022) Juan Rodriguez, Todd Hay, et al. 2022\.  Cross-Domain Detection of GPT-2-Generated Technical Text. In _Proc. 2022 Conf. Nor. Amer. Chapt. ACL: Human Language Technologies_. ACL, Seattle, United States, 1213–1233.  https://doi.org/10.18653/v1/2022.naacl-main.88
  * Rombach et al. (2021) Robin Rombach, Andreas Blattmann, et al. 2021\.  High-Resolution Image Synthesis with Latent Diffusion Models.  arXiv:cs.CV/2112.10752
  * Rosati (2022) Domenic Rosati. 2022\.  SynSciPass: detecting appropriate uses of scientific text generation.  https://doi.org/10.48550/ARXIV.2209.03742
  * Salminen et al. (2022) Joni Salminen, Chandrashekhar Kandpal, et al. 2022\.  Creating and detecting fake reviews of online products.  _Journal of Retailing and Consumer Services_ 64 (2022), 102771.  https://doi.org/10.1016/j.jretconser.2021.102771
  * Santhanam and Shaikh (2019) Sashank Santhanam and Samira Shaikh. 2019.  A survey of natural language generation techniques with a focus on dialogue systems-past, present and future directions.  _arXiv preprint arXiv:1906.00500_ (2019).
  * Scao et al. (2022) Teven Le Scao, Angela Fan, et al. 2022\.  BLOOM: A 176B-Parameter Open-Access Multilingual Language Model.  https://doi.org/10.48550/ARXIV.2211.05100
  * Schrage and Ginsberg (2018) Elliot Schrage and David Ginsberg. 2018.  Facebook Launches New Initiative to Help Scholars Assess Social Media’s Impact on Elections.  https://newsroom.fb.com/news/2018/04/new-elections-initiative/
  * Schuster et al. (2021) Roei Schuster, Congzheng Song, et al. 2021\.  You autocomplete me: Poisoning vulnerabilities in neural code completion. In _30th USENIX Security Symposium (USENIX Security 21)_. 1559–1575.
  * See et al. (2019) Abigail See, Aneesh Pappu, et al. 2019\.  Do Massively Pretrained Language Models Make Better Storytellers?. In _Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL)_. 843–861.
  * Selbst et al. (2019) Andrew D. Selbst, Danah Boyd, et al. 2019\.  Fairness and Abstraction in Sociotechnical Systems. In _Proc. Conference on Fairness, Accountability, and Transparency_ _(FAT* ’19)_. ACM, New York, NY, USA, 59–68.  https://doi.org/10.1145/3287560.3287598
  * Shamardina et al. (2022) Tatiana Shamardina, Vladislav Mikhailov, et al. 2022\.  Findings of the The RuATD Shared Task 2022 on Artificial Text Detection in Russian.  _arXiv preprint arXiv:2206.01583_ (2022).
  * Sheikha and Inkpen (2011) Fadi Abu Sheikha and Diana Inkpen. 2011.  Generation of formal and informal sentences. In _Proc. 13th European Workshop on Natural Language Generation_. 187–193.
  * Shi et al. (2018) Zhan Shi, Xinchi Chen, et al. 2018\.  Toward Diverse Text Generation with Inverse Reinforcement Learning. In _IJCAI_.
  * Shostack (2014) Adam Shostack. 2014\.  _Threat modeling: Designing for security_.  John Wiley & Sons.
  * Shostack (2021) Adam Shostack. 2021\.  Shostack’s 4 Question Frame for Threat Modeling.  https://github.com/adamshostack/4QuestionFrame.
  * Shu et al. (2020) Kai Shu, Suhang Wang, et al. 2020\.  Mining disinformation and fake news: Concepts, methods, and recent advancements.  In _Disinformation, misinformation, and fake news in social media_. Springer, 1–19.
  * Shuster et al. (2022) Kurt Shuster, Jing Xu, et al. 2022\.  BlenderBot 3: a deployed conversational agent that continually learns to responsibly engage.  https://doi.org/10.48550/ARXIV.2208.03188
  * Skrylnikov et al. (2022) SS Skrylnikov, PA Posokhov, et al. 2022\.  Artificial text detection in Russian language: a BERT-based Approach. In _Dialogue_.  https://doi.org/10.28995/2075-7182-2022-21-470-476
  * Solaiman et al. (2019) Irene Solaiman, Miles Brundage, et al. 2019\.  Release strategies and the social impacts of language models.  _arXiv preprint arXiv:1908.09203_ (2019).
  * Song et al. (2019) Kaitao Song, Xu Tan, et al. 2019\.  MASS: Masked Sequence to Sequence Pre-training for Language Generation. In _ICML_. 5926–5936.
  * Stieglitz et al. (2017) Stefan Stieglitz, Florian Brachten, et al. 2017\.  Do social bots (still) act different to humans?–Comparing metrics of social bots with those of humans. In _International conference on social computing and social media_. Springer, 379–395.
  * Stiff and Johansson (2022) Harald Stiff and Fredrik Johansson. 2022.  Detecting computer-generated disinformation.  _Int. J. Data Sci. Anal._ 13, 4 (2022), 363–383.
  * Sudhakar et al. (2019) Akhilesh Sudhakar, Bhargav Upadhyay, et al. 2019\.  “Transforming” Delete, Retrieve, Generate Approach for Controlled Text Style Transfer. In _Proc. 2019 Conf. EMNLP-IJCNLP_. 3269–3279.
  * Tay et al. (2020) Yi Tay, Dara Bahri, et al. 2020\.  Reverse Engineering Configurations of Neural Text Generation Models. In _Proc. 58th Annu. Meet. ACL Sys. Demo._ 275–279.
  * TB Canada Secretariat (2021) TB Canada Secretariat. 2021\.  Directive on automated decision-making.  https://www.tbs-sct.canada.ca/pol/doc-eng.aspx?id=32592
  * Tesfagergish et al. (2021) Senait G Tesfagergish, Robertas Damaševičius, et al. 2021\.  Deep Fake Recognition in Tweets Using Text Augmentation, Word Embeddings and Deep Learning. In _International Conference on Computational Science and Its Applications_. Springer, 523–538.
  * Topal et al. (2021) M. Onat Topal, Anil Bas, et al. 2021\.  Exploring Transformers in Natural Language Generation: GPT, BERT, and XLNet.  _ArXiv_ abs/2102.08036 (2021).
  * Tourille et al. (2022) Julien Tourille, Babacar Sow, et al. 2022\.  Automatic Detection of Bot-Generated Tweets. In _Proc. 1st International Workshop on Multimedia AI against Disinformation_ _(MAD ’22)_. ACM, New York, NY, USA, 44–51.  https://doi.org/10.1145/3512732.3533584
  * Turing (1950) A. M. Turing. 1950\.  Computing Machinery and Intelligence.  _Mind_ LIX, 236 (10 1950), 433–460.  https://doi.org/10.1093/mind/LIX.236.433 arXiv:https://academic.oup.com/mind/article-pdf/LIX/236/433/30123314/lix-236-433.pdf
  * Twitter (2019) Twitter. 2019.  Twitter Elections Integrity Dataset.  https://about.twitter.com/en_us/values/elections-integrity.html.  Accessed: 2022-09-23.
  * UcedaVelez and Morana (2015) Tony UcedaVelez and Marco M Morana. 2015.  _Risk Centric Threat Modeling: process for attack simulation and threat analysis_.  John Wiley & Sons.
  * Uchendu et al. (2020) Adaku Uchendu, Thai Le, et al. 2020\.  Authorship Attribution for Neural Text Generation. In _Proc. 2020 Conf. EMNLP_. ACL, Online, 8384–8395.  https://doi.org/10.18653/v1/2020.emnlp-main.673
  * UK National Cyber Security Centre (2022) UK National Cyber Security Centre. 2022\.  Threat modelling.  https://www.ncsc.gov.uk/collection/building-a-security-operations-centre/onboarding-systems-and-log-sources/threat-modelling
  * Vaswani et al. (2017) Ashish Vaswani, Noam M. Shazeer, et al. 2017\.  Attention is All you Need.  _ArXiv_ abs/1706.03762 (2017).
  * Wang and Komatsuzaki (2021) Ben Wang and Aran Komatsuzaki. 2021.  GPT-J-6B: A 6 Billion Parameter Autoregressive Language Model.  https://github.com/kingoflolz/mesh-transformer-jax.
  * Wang et al. (2022a) Jun Wang, Mingfei Gao, et al. 2022a.  TAG: Boosting Text-VQA via Text-aware Visual Question-answer Generation.  https://doi.org/10.48550/ARXIV.2208.01813
  * Wang et al. (2022b) Jianfeng Wang, Zhengyuan Yang, et al. 2022b.  GIT: A Generative Image-to-text Transformer for Vision and Language.  _arXiv preprint arXiv:2205.14100_ (2022).
  * Wang et al. (2021) Mengqian Wang, Manhua Wang, et al. 2021\.  A systematic review of automatic text summarization for biomedical literature and EHRs.  _Journal of the American Medical Informatics Association_ 28, 10 (2021), 2287–2297.
  * Wang et al. (2019) Wenqi Wang, Benxiao Tang, et al. 2019\.  A survey on Adversarial Attacks and Defenses in Text.  _CoRR_ abs/1902.07285 (2019).  arXiv:1902.07285 http://arxiv.org/abs/1902.07285
  * Weiss (2019) Max Weiss. 2019\.  Deepfake bot submissions to federal public comment websites cannot be distinguished from human submissions.  _Technology Science_ (2019).
  * Weizenbaum (1966) Joseph Weizenbaum. 1966\.  ELIZA—a Computer Program for the Study of Natural Language Communication between Man and Machine.  _Commun. ACM_ 9, 1 (jan 1966), 36–45.  https://doi.org/10.1145/365153.365168
  * Willison (2022) Simon Willison. 2022\.  https://simonwillison.net/2022/Sep/12/prompt-injection/
  * Yu et al. (2017) Lantao Yu, Weinan Zhang, et al. 2017\.  SeqGAN: Sequence Generative Adversarial Nets with Policy Gradient. In _AAAI_.
  * Zapata (2022) Juan Pablo Ossa Zapata. 2022\.  GPT-3 Prompt Injection Example.  https://twitter.com/mkualquiera/status/1570546998104948736
  * Zellers (2019) Rowan Zellers. 2019\.  Why We Released Grover.  https://thegradient.pub/why-we-released-grover/.  _The Gradient_ (2019).
  * Zellers et al. (2019) Rowan Zellers, Ari Holtzman, et al. 2019\.  Defending against neural fake news.  _NeurIPS_ 32 (2019).
  * Zeng et al. (2021) Wei Zeng, Xiaozhe Ren, et al. 2021\.  PanGu-$\alpha$: Large-scale Autoregressive Pretrained Chinese Language Models with Auto-parallel Computation.  _CoRR_ abs/2104.12369 (2021).  arXiv:2104.12369 https://arxiv.org/abs/2104.12369
  * Zhang and Sun (2009) Li Zhang and Jian-Tao Sun. 2009.  _Text Generation_.  Springer US, Boston, MA, 3048–3051.  https://doi.org/10.1007/978-0-387-39940-9_416
  * Zhang et al. (2022) Susan Zhang, Stephen Roller, et al. 2022\.  Opt: Open pre-trained transformer language models.  _arXiv preprint arXiv:2205.01068_ (2022).
  * Zhang et al. (2020) Yizhe Zhang, Siqi Sun, et al. 2020\.  DIALOGPT: Large-Scale Generative Pre-training for Conversational Response Generation. 270–278.
  * Zhou et al. (2020) Luowei Zhou, Hamid Palangi, et al. 2020\.  Unified vision-language pre-training for image captioning and vqa. In _Proc. AAAI Conference on Artificial Intelligence_ , Vol. 34. 13041–13049.
  * Zhuang et al. (2007) Ziming Zhuang, Ergin Elmacioglu, et al. 2007\.  Measuring Conference Quality by Mining Program Committee Characteristics. In _Proc. 7th JCDL_ _(JCDL ’07)_. ACM, New York, NY, USA, 225–234.  https://doi.org/10.1145/1255175.1255220
  * Zipf (1949) George Kingsley Zipf. 1949\.  Human behavior and the principle of least effort.  (1949).


# Tensor Sandwich: Tensor Completion for Low CP-Rank Tensors via Adaptive
Random Sampling

Cullen Haselby, Santhosh Karnik, Mark Iwen  Michigan State University,
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We propose an adaptive and provably accurate tensor completion approach based
on combining matrix completion techniques (see, e.g., [1, 2, 3]) for a small
number of slices with a modified noise robust version of Jennrich’s algorithm
(see, e.g., [4, Section 3]). In the simplest case, this leads to a sampling
strategy that more densely samples two outer slices (the bread), and then more
sparsely samples additional inner slices (the bbq-braised tofu) for the final
completion. Under mild assumptions on the factor matrices, the proposed
algorithm completes an $n\times n\times n$ tensor with CP-rank $r$ with high
probability while using at most $\mathcal{O}(nr\log^{2}r)$ adaptively chosen
samples. Empirical experiments further verify that the proposed approach works
well in practice, including as a low-rank approximation method in the presence
of additive noise.

##  I Introduction

Consider a CP rank-$r$ tensor $\mathcal{T}\in\mathbb{R}^{n\times n\times n}$
where $r\leq n$ with CP-decomposition

$\mathcal{T}=\sum_{i=1}^{r}\mathbf{a}_{i}\circ\mathbf{b}_{i}\circ\mathbf{c}_{i}.$
(I.1)

Here $\mathbf{a}_{i},\mathbf{b}_{i},\mathbf{c}_{i}\in\mathbb{R}^{n}$ for all
$i\in[r]:=\\{1,\dots,r\\}$, and $\circ$ denotes the outer product so that
$\mathbf{a}_{i}\circ\mathbf{b}_{i}\circ\mathbf{c}_{i}\in\mathbb{R}^{n\times
n\times n}$ has entries
$\left(\mathbf{a}_{i}\circ\mathbf{b}_{i}\circ\mathbf{c}_{i}\right)_{h,j,k}=(\mathbf{a}_{i})_{h}(\mathbf{b}_{i})_{j}(\mathbf{c}_{i})_{k}$
for all $i\in[r]$. The tensor completion problem is to reconstruct
$\mathcal{T}$ after observing a subset of its entries $\mathcal{T}_{i,j,k}$
for $(i,j,k)\in\Omega\subset[n]^{3}$. In this paper $\Omega$ will consist of
random entries adaptively sampled in several rounds (i.e., so that the entries
observed in round $\ell+1$ are selected via a distribution that depends on the
entries observed in rounds $1$ to $\ell$). We hasten to add, however, that the
general proof approach taken herein can itself be adapted to also yield tensor
completion results based on non-adaptive sampling at the expense of further
restricting the class of tensors considered below for which the methods will
be guaranteed to succeed.

In order to define the class of tensors for which the proposed approach will
be guaranteed to succeed we need several definitions. Define the _factor
matrix_
$\boldsymbol{A}=\begin{bmatrix}\mathbf{a}_{1}&\mathbf{a}_{2}&\cdots&\mathbf{a}_{r}\end{bmatrix}\in\mathbb{R}^{n\times
r}$ to have columns given by the factor vectors ${\bf a_{j}}$ in (I.1), as
well as for $\boldsymbol{B},\boldsymbol{C}\in\mathbb{R}^{n\times r}$ with
columns arranged in the same corresponding orders. We will employ the _Khatri-
Rao product_ of two matrices; which is the matrix that results from computing
the Kronecker product of their matching columns. That is, for
$\boldsymbol{A},\boldsymbol{B}\in\mathbb{R}^{n\times r}$, their Khatri-Rao
product is the matrix
$\boldsymbol{A}\odot\boldsymbol{B}\in\mathbb{R}^{n^{2}\times r}$ defined by

$\boldsymbol{A}\odot\boldsymbol{B}:=\begin{bmatrix}\mathbf{a}_{1}\otimes\mathbf{b}_{1}&\mathbf{a}_{2}\otimes\mathbf{b}_{2}&\dots&\mathbf{a}_{n}\otimes\mathbf{b}_{n}\end{bmatrix}.$

This operation is useful when considering the matricizations or flattenings of
a rank-$r$ CP tensor (I.1). E.g. the mode-3 unfolding of $\mathcal{T}$ is
equal to
$\boldsymbol{T}_{(3)}=\boldsymbol{C}(\boldsymbol{A}\odot\boldsymbol{B})^{T}$,
see [5]. Define the _coherence_ of an $r$-dimensional subspace
$U\subset\mathbb{R}^{n}$ to be

$\mu(U):=\dfrac{n}{r}\max_{i\in[n]}\|\mathcal{P}_{U}\boldsymbol{e}_{i}\|_{2}^{2},$

where $\mathcal{P}_{U}$ is the orthogonal projection onto $U$, and where
$\boldsymbol{e}_{i}\in\mathbb{R}^{n}$ for $i\in[n]$ denotes the $i^{\rm th}$
standard basis vector. Also, the _Kruskal rank of a matrix_ is the maximum
integer $r$ such that any $r$ columns of the matrix are linearly independent.

Finally, for any positive integers $n,r,s$ with $r,s\leq n$ and any
$\mu_{0}\in[1,n/r]$, we define $\mathbb{T}(n,r,\mu_{0},s)$ to be the class of
all tensors
$\mathcal{T}=\sum_{i=1}^{r}\mathbf{a}_{i}\circ\mathbf{b}_{i}\circ\mathbf{c}_{i}\in\mathbb{R}^{n\times
n\times n}$ for which:

  1. (a)

the factor matrices $\mathbf{A},\mathbf{B}$ both have full column rank,

  2. (b)

the column space of $\mathbf{A}$ has coherence bounded above by $\mu_{0}$, and

  3. (c)

for some $s\in[n]$, every $s\times r$ submatrix of $\mathbf{C}$ has Kruskal
rank $\geq 2$.

We are now able to state our main result.

######  Theorem 1.

There exists an adaptive random sampling strategy and an associated
reconstruction algorithm (see Algorithm 2) such that for any $\delta>0$, after
observing at most $C_{1}s\mu_{0}nr\log^{2}(r^{2}/\delta)$ entries of a tensor
$\mathcal{T}\in\mathbb{T}(n,r,\mu_{0},s)$, the algorithm completes
$\mathcal{T}$ with probability at least $1-s\delta$. Here $C_{1}>0$ is
absolute constant that is independent of all other quantities.

The proof of our sandwich sampling algorithm involves three stages. First,
w.l.o.g., we pick $s$ mode-$3$ slices and then use a matrix completion
algorithm that with high probability recovers these slices and observes at
most $C^{\prime}_{1}\mu_{0}nr\log^{2}(r^{2}/\delta)$ entries in each slice.
Second, if this $n\times n\times s$ subtensor is correctly completed, we can
then use a deterministic variant of Jennrich’s Algorithm111As discussed in [6]
the work of [7] is perhaps a more accurate attribution of the method, however
we use the traditional name of Jennrich’s Algorithm in this work. on the
completed subtensor to learn the factor matrices $\mathbf{A}$ and
$\mathbf{B}$. Third, once we know the factor matrices $\mathbf{A}$ and
$\mathbf{B}$, we can deterministically find $r$ sample locations in each of
the $n$ mode-$3$ slices whose values allow a censored least squares problem to
solve for the third factor matrix $\mathbf{C}$. This three-stage procedure
uses at most $C^{\prime}_{1}s\mu_{0}nr\log^{2}(r^{2}/\delta)$ samples to
complete the $s$ initial mode-$3$ slices in order to learn $\mathbf{A}$ and
$\mathbf{B}$, and then $nr$ additional samples to learn $\mathbf{C}$
thereafter, for a total of at most
$C^{\prime}_{1}s\mu_{0}nr\log^{2}(r^{2}/\delta)+nr\leq
C_{1}s\mu_{0}nr\log^{2}(r^{2}/\delta)$ samples. See Figure 1 for a schematic
illustration of the overall sampling strategy where fibers are sampled through
the middle of the sandwich for simplicity.

We note that assumptions a and c are the necessary assumptions for the
Jennrich’s step to work with any $n\times n\times s$ subtensor. Furthermore,
if the columns of the factor matrices are drawn from any continuous
distribution, assumption c for $s=2$ holds with probability $1$. Finally,
something akin to assumption b is always required in completion problems.

Figure 1: A schematic depiction of the sampling strategy where $s=2$ slices
have been sampled relatively densely in order to compute $\mathbf{A}$ and
$\mathbf{B}$, and where additional fibers where then sampled elsewhere to help
compute $\mathbf{C}$

###  I-A Related Work

Many prior works on low-rank tensor completion use non-adaptive and uniform
sampling [8, 9, 10, 11, 12, 13, 14, 15]. While some of those works [9, 15, 13]
can handle CP-ranks up to roughly $n^{3/2}$ instead of $n$, all of them
require at least $\mathcal{O}(n^{3/2})$ samples, even when the rank is
$r=\mathcal{O}(1)$. Furthermore, [9] shows that completing an $n\times n\times
n$ rank-$r$ tensor from $n^{3/2-\epsilon}$ uniformly random samples is NP-hard
by comparison to the problem of refuting a 3-SAT formula with $n$ variables
and $n^{3/2-\epsilon}$ clauses.

In [16], the authors propose a method for completing CP-rank $r\leq n$ tensors
using adaptive sampling which, for order-$3$ tensors, requires
$\mathcal{O}(\mu_{0}^{2}nr^{5/2}\log^{2}r)$ samples. Our algorithm requires a
number of samples which has a more favorable dependence on the coherence
$\mu_{0}$ and rank $r$. Furthermore, our result only requires coherence
assumptions about $\mathbf{A}$, instead of about $\mathbf{A}$ _and_
$\mathbf{B}$. These improvements come at the expense of requiring the mild
additional assumptions a and c in our Theorem 1 related to Jennrich’s
algorithm, however.

The first step in our tensor completion algorithm involves using an adaptive
sampling algorithm to complete $s$ mode-$3$ slices of the tensor. Our tensor
completion algorithm and results are based on the adaptive matrix completion
algorithm and results in [2] which, with high probability, uses
$\mathcal{O}(\mu_{0}nr\log^{2}r)$ samples to complete a rank $r$ matrix.
However, our algorithm can be adapted to use other adaptive matrix completion
results such as, e.g., [3] with relative ease.

In the censored least squares phase of our algorithm, we can sample entire
fibers of the tensor as done in Figure 1. We note that doing so is similar in
spirit to the fiber sampling approach of Sørensen and De Lathauwer [17].
However, their work focuses on determining algebraic constraints on the factor
matrices of a low rank tensor which, when satisfied, allow the tensor to be
completed from the sampled fibers. As such, our results cannot be directly
compared with [17].

##  II Proof of Theorem 1

In this section we follow our 3 stage proof outline.

###  II-A Completing $s$ mode-$3$ slices of $\mathcal{T}$

We start by picking any subset of indices $S\subset[n]$ with $|S|=s$ elements.
For each $k\in S$, the mode-$3$ slice
$\mathcal{T}_{:,:,k}\in\mathbb{R}^{n\times n}$ satisfies

$\mathcal{T}_{:,:,k}=\sum_{i=1}^{r}\langle\mathbf{c}_{i},\mathbf{e}_{k}\rangle\mathbf{a}_{i}\mathbf{b}_{i}^{T},$

and so, $\text{col-span}(\mathcal{T}_{:,:,k})\subseteq\text{col-
span}(\mathbf{A})$. By assumption, $\text{col-span}(\mathbf{A})$ has coherence
bounded by $\mu_{0}$. Thus, the assumptions required by Theorem 1 in [2] hold.
Therefore, for each slice $T_{:,:,k}$ $k\in S$, with probability at least
$1-\delta$, the adaptive sampling procedure in Algorithm 1 uses at most
$C^{\prime}_{1}\mu_{0}nr\log^{2}(r^{2}/\delta)$ samples for some absolute
constant $C^{\prime}_{1}>0$, and completes $\mathcal{T}_{:,:,k}$.

By taking a simple union bound over each of the $s$ slices $k\in S$, we have
that with probability at least $1-s\delta$, this strategy will successfully
complete all of the $s$ slices $\mathcal{T}_{:,:,k}$ for $k\in S$ and use
fewer than $C^{\prime}_{1}s\mu_{0}nr\log^{2}(r^{2}/\delta)$ samples. Let
$\Omega_{1}=\left\\{(i,j,k)\lvert(i,j)\text{ sampled according to
\cite[cite]{[\@@bibref{}{krishnamurthy2014power}{}{}]} for slice }k\in
S\right\\}$, the set of locations of $\mathcal{T}$ sampled to complete these
$s$ slices.

###  II-B Learning mode-$1$ and $2$ factor matrices via Modified Jennrich’s
Algorithm / simultaneous diagonlization

Let $\mathbf{u},\mathbf{v}$ be random vectors uniformly drawn from the unit
sphere $\mathbb{S}^{s-1}$. Denote the sub-vector of ${\mathbf{c}}$ with
entries indexed in $S$ by $\mathbf{\tilde{c}}_{i}=(\mathbf{c}_{i})_{S}$, and
construct two auxiliary matrices $\mathbf{T}_{u},\mathbf{T}_{v}$ using the
completed slices by adding up the linear combinations of the completed slices,
weighted by the random vectors $\mathbf{u},\mathbf{v}$. In terms of the
components, we have:

$\displaystyle\mathbf{T}_{u}$
$\displaystyle=\sum_{i=1}^{r}\langle\mathbf{\tilde{c}}_{i},\mathbf{u}\rangle\mathbf{a}_{i}\mathbf{b}_{i}^{T}$
$\displaystyle\mathbf{T}_{v}$
$\displaystyle=\sum_{i=1}^{r}\langle\mathbf{\tilde{c}}_{i},\mathbf{v}\rangle\mathbf{a}_{i}\mathbf{b}_{i}^{T}$

Denote the $r\times r$ matrix $\mathbf{D}_{u}$ which has along its diagonal
entries the values $\langle\mathbf{\tilde{c}}_{i},\mathbf{u}\rangle$, and
similarly $\mathbf{D}_{v}$. Notice the following identity with the product
$\mathbf{T}_{u}(\mathbf{T}_{v})^{\dagger}$

$\displaystyle\mathbf{T}_{u}(\mathbf{T}_{v})^{\dagger}$
$\displaystyle=\mathbf{A}\mathbf{D}_{u}\mathbf{B}^{T}\left(\mathbf{A}\mathbf{D}_{v}\mathbf{B}^{T}\right)^{\dagger}$
$\displaystyle=\mathbf{A}\mathbf{D}_{u}\mathbf{D}_{v}^{-1}\mathbf{A}^{\dagger}$

Where the matrix $\mathbf{D}_{u}\mathbf{D}_{v}^{-1}$ is a diagonal matrix with
$(i,i)$-entry equal to
$\frac{\langle\mathbf{\tilde{c}}_{i},\mathbf{u}\rangle}{\langle\mathbf{\tilde{c}}_{i},\mathbf{v}\rangle}$.
Clearly the matrix $\mathbf{T}_{u}(\mathbf{T}_{v})^{\dagger}$ is
diagonalizable, and so by computing the eigen-decomposition of
$\mathbf{T}_{u}(\mathbf{T}_{v})^{\dagger}$ we recover the columns of
$\mathbf{A}$ and the eigenvlaues along the diagonal of
$\mathbf{D}_{u}\mathbf{D}_{v}^{-1}$. We can order the eigenvectors in
descending order by magnitude of their corresponding eigenvalue. Note it is
here that we employ assumption c: Since $\mathbf{C}_{S}$ (i.e., the rows of
$\mathbf{C}$ indexed by $S$) has $k$-rank at least 2, the ratios
$\frac{\langle\mathbf{\tilde{c}}_{i},\mathbf{u}\rangle}{\langle\mathbf{\tilde{c}}_{i},\mathbf{v}\rangle}$
for each $i$ will almost surely be distinct from one another, and thus the
ordering of the eigenvalues is unique.

Let $\mathbf{P}$ be the permutation matrix that interchanges the columns of
$\mathbf{A}$ so that instead of being in $\mathbf{D}_{u}\mathbf{D}_{v}^{-1}$
order, they are in $\mathbf{D}_{u}$ order (ordered greatest to least in terms
of the magnitude of $\langle\mathbf{\tilde{c}}_{i},\mathbf{u}\rangle$). Now
notice that

$\begin{split}\mathbf{A}^{\dagger}\mathbf{T}_{u}&=\mathbf{A}^{\dagger}\mathbf{A}\mathbf{P}\mathbf{D}_{u}\mathbf{B}^{T}\\\
&=\mathbf{P}\mathbf{D}_{u}\mathbf{B}^{T}\\\
&=(\mathbf{B}\mathbf{D}_{u}\mathbf{P})^{T}.\\\ \end{split}$ (II.1)

This means that the rescaled columns of $\mathbf{B}$ that are in
$\mathbf{D}_{u}$ order are now in $\mathbf{D}_{u}\mathbf{D}_{v}^{-1}$ order
after we apply the inverse $\mathbf{A}^{\dagger}$ to $\mathbf{T}_{u}$. That
is, we have found the matching components of $\mathbf{A}$ and $\mathbf{B}$ up
to a re-scaling of their outer product! This was achieved by learning the
columns of $\mathbf{A}$ from $\mathbf{T}_{u}(\mathbf{T}_{v})^{\dagger}$ and
then, crucially, the matching columns of $\mathbf{B}$ from
$\mathbf{A}^{\dagger}\mathbf{T}_{u}$. The scaling due to $\mathbf{D}_{u}$ will
be resolved in the final step of the algorithm, where we solve for the missing
third factor (i.e., $\mathbf{B},\mathbf{C}$ and
$\mathbf{BD},\mathbf{C}(\mathbf{D}^{-1})$ are both valid pairs of factors for
any diagonal matrix $\mathbf{D}$).

###  II-C Learning the mode-$3$ factor matrix

After obtaining $\mathbf{A}$ and a rescaled $\mathbf{B}$ in order to find the
remaining components, $\mathbf{C}$, we will need $\Omega_{2}$, a second set of
revealed locations of the entries of $\mathcal{T}$. We will also need the
solutions to $n$ instances of the following censored least squares problem
related to those revealed values

$(\mathbf{A}\odot\mathbf{B})_{K_{k}}\mathbf{c}=\mathbf{t}_{K_{k}}$ (II.2)

where $k\in[n]$,$\mathbf{c}=(\mathbf{C}_{k,:})^{T}$,
$\mathbf{t}=\text{vec}(\mathcal{T}_{:,:,k})^{T}$ and
$K_{k}=\left\\{i+n(j-1)|(i,j,k)\in\Omega_{2}\right\\}$. In (II.2), the term
$\mathbf{t}_{K_{k}}$ denotes the vector of length $\lvert K_{k}\rvert$ which
includes only the entries of $\mathbf{t}$ which have indicies appearing in the
set $K_{k}$. Similarly $(\mathbf{A}\odot\mathbf{B})_{K_{k}}$ is the matrix
where we restrict rows of $(\mathbf{A}\odot\mathbf{B})$ to only those which
have indices appearing in the set.

Note $(\mathbf{A}\odot\mathbf{B})$ is full rank because $\mathbf{A}$ and
$\mathbf{B}$ are assumed to be full rank (see, e.g., [18]). This implies the
uncensored system is consistent with a unique solution. The difficulty in the
censored case is that unobserved values in a particular column of the right
hand side of (II.2) could force the discarding of rows of the matrix
$(\mathbf{A}\odot\mathbf{B})$ that cause the system to become under-
determined.

That is, we must ensure that $(\mathbf{A}\odot\mathbf{B})_{K_{k}}$ has full
column rank for each $k$. If we do not vary our sampling procedure from
frontal slice to frontal slice, then this corresponds to sampling tubes of the
original tensor of the form $\mathcal{T}_{i,j,:}$ and $K_{k}=K$ for all
$k\in[n]$. In order to arrange the sampling to accomplish this, consider a
$\mathbf{QR}$ with column-pivoting factorization of
$(\mathbf{A}\odot\mathbf{B})^{T}$, see algorithm 5.4.1 in [19]). This produces
factors and a permutation matrix $\mathbf{\Pi}\in\mathbb{R}^{n^{2}\times
n^{2}}$ such that $(\mathbf{A}\odot\mathbf{B})^{T}\mathbf{\Pi}=\mathbf{QR}$,
where

$\mathbf{R}=\begin{bmatrix}\mathbf{R}_{1}&\mathbf{R}_{2}\end{bmatrix}$

and $\mathbf{R}_{1}\in\mathbb{R}^{r\times r}$ is upper-triangular and non-
singular. But this means that the first $r$ columns of $\mathbf{\Pi}$ select a
set of columns of $(\mathbf{A}\odot\mathbf{B})^{T}$ which are linearly
independent, so for each $\mathbf{\Pi}_{:,p}$, $p\in[r]$ we have that there
exists some $q\in[n^{2}]$ such that $\mathbf{e}_{q}=\mathbf{\Pi}_{:,p}$, the
corresponding column of the identity in $\mathbb{R}^{n^{2}\times n^{2}}$. Let
$i=q\mod n,j=\lfloor\frac{q}{n}\rfloor$. Define then $\Omega_{2}$ all the
tuples of the form $(i,j,:)$. That is, we can read off from $\mathbf{\Pi}$
which $r$ fibers of length $n$ to sample in order to ensure (II.2) is
consistent for each $k\in[n]$. We have specified at most $nr$ new sample
locations, and thus $\Omega=\Omega_{1}\cup\Omega_{2}$, the set of all samples
employed to complete the tensor $\mathcal{T}$ is at most
$\lvert\Omega_{1}\rvert+\lvert\Omega_{2}\rvert\leq
C^{\prime}_{1}s\mu_{0}nr\log^{2}(r^{2}/\delta)+nr\leq
C_{1}s\mu_{0}nr\log^{2}(r^{2}/\delta)$.

######  Remark 1.

Note, $\mathbf{\Pi}$ is not unique, and indeed we could use different
selections corresponding to other valid permutations from frontal slice to
frontal slice to vary the sampling pattern when finding $\mathbf{C}$.
Additionally, including more rows of $(\mathbf{A}\odot\mathbf{B})$ beyond the
first $r$ as specified by $\mathbf{\Pi}$ may be numerically advantageous when
computing $\mathbf{C}$.

Algorithm 1 Consistency Preserving Fiber Sampler

input :

$\gamma\geq 1$, over-sample parameter

$r$ rank parameter

$\mathbf{A},\mathbf{B}\in\mathbb{R}^{n\times r}$, estimates for factor
matrices

output :

$\Omega_{2}$, set of sample locations

Compute $\mathbf{QR}$ with column-pivoting,
$\mathbf{QR}=\left(\mathbf{A}\odot\mathbf{B}\right)^{T}\mathbf{\Pi}$

for  _$p\in[\gamma r]$_ do

$q\leftarrow\text{nonzero}(\mathbf{\Pi}_{:,p})$ $i\leftarrow q\mod n$
$j\leftarrow\lfloor\frac{q}{n}\rfloor$ Include $(i,j,k)$ in $\Omega_{2}$ for
all $k\in[n]$

end for

Algorithm 2 Tensor Sandwich

input :

$S\subseteq[n]$ slices to complete

output :

$\hat{T}$, completed tensor

# Slice Complete Phase

for  _$k\in S$_ do

Use, e.g., [3], or algorithm 1 in [2] to complete $\mathcal{T}_{:,:,k}$.
Algorithm 1 in [2] uses at most
$C^{\prime}_{1}\mu_{0}nr\log^{2}(r^{2}/\delta)$ adaptively chosen samples.

end for

# Jennrich Complete Phase  Generate random vectors
$\mathbf{u},\mathbf{v}\in\mathbb{S}^{s-1}$;
$\mathbf{T}_{u}\leftarrow\sum_{k\in S}u_{k}\mathbf{T}_{::k}$
$\mathbf{T}_{v}\leftarrow\sum_{k\in S}v_{k}\mathbf{T}_{::k}$ Compute eigen-
decomposition
$\mathbf{A}\mathbf{\Lambda}\mathbf{A}^{-1}=\mathbf{T}_{u}(\mathbf{T}_{u})^{\dagger}$
$\mathbf{B}\leftarrow\mathbf{A}^{-1}\mathbf{T}_{u}$ # Censored Least Squares
Phase  $\Omega_{2}\leftarrow\text{fiber
sampler}(\mathbf{A},\mathbf{B},r,\gamma$)
$\mathbf{C}^{T}\leftarrow\text{censored least squares
}((\mathbf{A}\odot\mathbf{B}),\mathcal{T}_{i,j,k}\text{ s.t.
}(i,j,k)\in\Omega_{2})$
$\mathcal{\hat{T}}\leftarrow[\\![\mathbf{A},\mathbf{B},\mathbf{C}]\\!]$

##  III Experiments

In this section, we show that tensors sampled according to our overall
strategy and completed using Algorithm (2) support our theoretical findings.
In particular we demonstrate that once sample complexity bounds are satisfied,
we can achieve very precise levels of relative error by sampling what is
overall a small percentage of the total tensor’s entries. For example, in the
rank 20 case in Figure 2, the median relative error is $0.000168$ having
sampled $\frac{94445}{8000000}\approx 1.1\%$ of the total entries. Our
experiments also verify the linear dependence on rank in the sample complexity
bound. Furthermore, in our second set of experiments we show that the method
performs useful completion even in the presence of noise. The code and results
from the numerical experiments is available at
https://github.com/cahaselby/TensorSandwich.

In all our experiments, the three modes of the tensor have length $n=200$. The
data is generated by drawing factor matrices
$\mathbf{A},\mathbf{B},\mathbf{C}\in\mathbb{R}^{n\times r}$ with i.i.d
standard Gaussian entries and then normalizing the columns. We then weight the
components using quadratically decaying weights, i.e.

$\mathcal{T}=\sum_{i=1}^{r}\left(\frac{1}{i^{2}}\right)\mathbf{a}_{i}\circ\mathbf{b}_{i}\circ\mathbf{c}_{i}.$
(III.1)

Errors are averaged over ten independent trials.

For each of our trials, $s=2$. After uniformly selecting two frontal slices to
complete, within these slices we sample per Algorithm 1 in [3] using a sample
budget of $m$ samples per slice. Slices are then completed using the SDP
formulation of the nuclear norm minimization solved via Douglas-Rachford
splitting, see [20]. Convergence is declared once the primal residual, dual
residual and duality gap are below $10^{-8}$ for each of the $s$ selected
slices, or after 2500 iterations, whichever comes first. We note that the
accuracy of this matrix completion step influences numerically what is
achievable in terms of overall accuracy for the completed tensor, and that the
error for completing these slices is compounded in the subsequent steps (even
in the absence of noise). This explains the apparent “leveling off” of the
relative error at about $10^{-4}$ even as sample complexity or signal-to-noise
ratios increase.

Following matrix completion on these frontal slices and estimation of
$\mathbf{A}$ and $\mathbf{B}$, we select $\gamma r$ rows of
$(\mathbf{A}\odot\mathbf{B})$ using Algorithm 1 and the corresponding fibers
of $\mathcal{T}$ to solve the censored least square problem. In all the
experiments in this section, $\gamma=4$. This results in at most $\gamma nr$
new entries revealed in the original tensor. Total number of entries sampled
then is always bounded by $sm+\gamma nr$ (some overlap of samples is possible
in the two slices already completed). Note that for all experiments
$0.035nr\log^{2}(n)<m<0.7nr\log^{2}(n)$.

In Figure 2, we see a phase transition of our method. For a given rank, prior
to a threshold, the error is dominated by the inability to accurately complete
the $s$ slices. Once sufficient samples are obtained within these slices,
completion reliably succeeds and accuracy approaches the limiting numerical
accuracy inherited from the initial slice completion step.

Figure 2: Median relative error (log-scaled) of completed tensors of varying
rank as sample complexity increases without noise. Each value is the median of
ten trials.

In Figure 3, we add mean-zero i.i.d. Gaussian noise to each entry in our
tensor and perform the same completion strategy on the noisy tensor as
described earlier in this section. For each trial, the noise tensor
$\mathcal{N}$ is scaled to the appropriate signal-to-noise ratio, i.e.
$\text{SNR}=10\log_{10}\tfrac{\|\mathcal{T}\|}{\|\mathcal{N}\|}$. Weights for
each of the components are again set as per (III.1). The sample complexity
proportions are fixed with respect to slice completion versus fibers sampled
to estimate $\mathbf{C}$ but do scale according to rank in order to facilitate
comparison. In all cases the total number of sampled entries is between
$0.27\%$ and $1.10\%$ of the total number of entries, depending on rank.

Figure 3: Median relative error (log-scaled) of completed tensors of varying
rank for different levels of white Gaussian noise. Sample complexity is less
than 1.1% for all trials, scaled linearly by rank.

We noticed during these experiments that using masked alternating least
squares alone (as in [21]) to complete our synthetic tensors (using either the
Tensor Sandwich sample pattern, or an equivalent proportion of uniformly drawn
samples) achieved at best relative errors of about 6%. However, the estimate
of the tensor as output by Algorithm 2, and its sample pattern can be used as
an initialization to an iterative scheme like alternating least squares to
further improve the accuracy of the completed tensor. In Figure 4, we show
three sets of related experiments: the relative error at various ranks
achieved by alternating least squares alone (AS), Tensor Sandwich alone (TS),
or alternating least squares initialized by Tensor Sandwich (TS + ALS). In
each trial, 100 iterations of alternating least squares are used, weights for
components are set to decay according to (III.1), and each of the three
variations for completing the tensor are used on the same data. We notice that
at this level of sample complexity, for either a sample mask chosen uniformly
at random or according to the adaptive scheme described in this work, ALS
alone is limited. Combined with Tensor Sandwich, however, we can see roughly
an order of magnitude improvement in relative error by performing a hundred
iterations of ALS on the TS estimate. This shows Tensor Sandwich can be useful
as an initialization strategy for other completion methods, either to save on
run time by decreasing the total number of iterations needed, or to improve
the accuracy of the final estimate.

Figure 4: Median relative error (log-scaled) of completed tensors of varying
rank for different levels of white Gaussian noise. Sample complexity is less
than 1.1% for all trials, scaled linearly by rank. Tensors are completed using
100 iterations of alternating least squares (ALS), or Tensor Sandwich (TS), or
100 iterations of ALS initialized by Tensor Sandwich (TS+ALS).

In a final set of experiments, we compare one of the existing (non-adaptive)
completion methods discussed in the Related Work section to Tensor Sandwich.
We use the same overall sample budget for Tensor Sandwich but instead use the
Algorithm in [4] which we refer to as Tensor Complete (TC). The range of total
values sampled is the same as in Figure 2. Implementation details make direct
comparisons difficult. However, the empirical findings summarized in Figure 5
suggest that Tensor Sandwich can produce better estimates for high rank
tensors than Tensor Complete can when sample budgets are limited.

Figure 5: Median relative error (log-scaled) of completed tensors of varying
rank for different total number of entries revealed. Tensors are completed
using Tensor Sandwich (TS), or Tensor Complete as described in [4] without
noise.

##  IV Conclusions and Future Work

We have presented an adaptive sampling approach for low CP-rank tensor
completion which completes a CP-rank $r$ tensor of size $n\times n\times n$
using $\mathcal{O}(nr\log^{2}r)$ samples with high probability. Our method
significantly improves on the tensor completion result in [16] while only
making a mild additional assumption on the third factor matrix. We also
provided numerical experiments to demonstrate that a version of our tensor
completion method is robust to noise empirically.

Several questions remain for future work. First, it would be interesting to
prove rigorous guarantees for a non-adaptive version of our tensor completion
algorithm using as few additional assumptions as possible. Second, it is
possible to extend our tensor completion method to higher-order tensors in
several ways. Choosing the best approach based on sampling complexity analysis
would be of value. Finally, it is always important to provide rigorous
completion guarantees for the case where the observed entries are corrupted
with some sort of noise. Very little prior work on low-rank tensor completion
provides any such theoretical guarantees making a treatment of this case an
high-value goal.

## Acknowledgements

This work was supported in part by NSF DMS 2106472.

## References

  * [1] E. Candes and B. Recht, “Exact matrix completion via convex optimization,” _Communications of the ACM_ , vol. 55, no. 6, pp. 111–119, 2012.
  * [2] A. Krishnamurthy and A. Singh, “On the power of adaptivity in matrix completion and approximation,” 2014.
  * [3] Y. Chen, S. Bhojanapalli, S. Sanghavi, and R. Ward, “Completing any low-rank matrix, provably,” _Journal of Machine Learning Research_ , vol. 16, no. 94, pp. 2999–3034, 2015. [Online]. Available: http://jmlr.org/papers/v16/chen15b.html
  * [4] A. Moitra, _Algorithmic aspects of machine learning_. Cambridge University Press, 2018.
  * [5] T. G. Kolda and B. W. Bader, “Tensor decompositions and applications,” _SIAM review_ , vol. 51, no. 3, pp. 455–500, 2009.
  * [6] T. G. Kolda, “Will the real jennrich’s algorithm please stand up?” https://www.mathsci.ai/post/jennrich/, accessed: 2023-05-23.
  * [7] S. E. Leurgans, R. T. Ross, and R. B. Abel, “A decomposition for three-way arrays,” _SIAM Journal on Matrix Analysis and Applications_ , vol. 14, no. 4, pp. 1064–1083, 1993. [Online]. Available: https://doi.org/10.1137/0614071
  * [8] P. Jain and S. Oh, “Provable tensor factorization with missing data,” _Advances in Neural Information Processing Systems_ , vol. 27, 2014.
  * [9] B. Barak and A. Moitra, “Noisy tensor completion via the sum-of-squares hierarchy,” in _Conference on Learning Theory_. PMLR, 2016, pp. 417–445.
  * [10] M. Yuan and C.-H. Zhang, “On tensor completion via nuclear norm minimization,” _Foundations of Computational Mathematics_ , vol. 16, no. 4, pp. 1031–1068, 2016.
  * [11] ——, “Incoherent tensor norms and their applications in higher order tensor completion,” _IEEE Transactions on Information Theory_ , vol. 63, no. 10, pp. 6753–6766, 2017.
  * [12] A. Potechin and D. Steurer, “Exact tensor completion with sum-of-squares,” in _Conference on Learning Theory_. PMLR, 2017, pp. 1619–1673.
  * [13] A. Montanari and N. Sun, “Spectral algorithms for tensor completion,” _Communications on Pure and Applied Mathematics_ , vol. 71, no. 11, pp. 2381–2425, 2018.
  * [14] A. Liu and A. Moitra, “Tensor completion made practical,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 18 905–18 916, 2020.
  * [15] B. Kivva and A. Potechin, “Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 sos,” _arXiv preprint arXiv:2011.09416_ , 2020.
  * [16] A. Krishnamurthy and A. Singh, “Low-rank matrix and tensor completion via adaptive sampling,” _Advances in neural information processing systems_ , vol. 26, 2013.
  * [17] M. Sørensen and L. De Lathauwer, “Fiber sampling approach to canonical polyadic decomposition and application to tensor completion,” _SIAM Journal on Matrix Analysis and Applications_ , vol. 40, no. 3, pp. 888–917, 2019\.
  * [18] T. B. JM., “The $k$-rank of a khatri–rao product,” _Unpublished Note, Heijmans Institute of Psychological Research, University of Groningen, The Netherlands._ , 2000.
  * [19] G. H. Golub and C. F. Van Loan, _Matrix Computations_ , 3rd ed. The Johns Hopkins University Press, 1996.
  * [20] B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd, “Conic optimization via operator splitting and homogeneous self-dual embedding,” _Journal of Optimization Theory and Applications_ , vol. 169, no. 3, pp. 1042–1068, June 2016\. [Online]. Available: http://stanford.edu/~boyd/papers/scs.html
  * [21] G. Tomasi and R. Bro, “Parafac and missing values,” _Chemometrics and Intelligent Laboratory Systems_ , vol. 75, no. 2, pp. 163–180, 2005. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0169743904001741