* (64) Gamelas Sousa, R., da Rocha Neto, A. R., Barreto, G. A., Cardoso, J. S., and Coimbra, M. T. (2014a).  Reject option paradigm for the reduction of support vectors.  22nd European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, ESANN 2014 - Proceedings, pages 331–336.
  * (65) Gamelas Sousa, R., da Rocha Neto, A. R., Cardoso, J. S., and Barreto, G. A. (2014b).  Classification with Reject Option Using the Self-Organizing Map.  In Lecture Notes in Computer Science, volume 8681 LNCS, chapter Artificial, pages 105–112. Springer, Cham.
  * Gamelas Sousa et al., (2009) Gamelas Sousa, R., Mora, B., and Cardoso, J. S. (2009).  An ordinal data method for the classification with reject option.  8th International Conference on Machine Learning and Applications, ICMLA 2009, 2:746–750.
  * Gasca A. et al., (2011) Gasca A., E., Saldaña T., S., Sánchez G., J. S., Velásquez G., V., Rendón L., E., Abundez B., I. M., Valdovinos R., R. M., and Cruz R., R. (2011).  A Rejection Option for the Multilayer Perceptron Using Hyperplanes.  In Lecture Notes in Computer Science, volume 6593 LNCS, pages 51–60. Springer Berlin Heidelberg.
  * Geifman and El-Yaniv, (2017) Geifman, Y. and El-Yaniv, R. (2017).  Selective Classification for Deep Neural Networks.  In Advances in Neural Information Processing Systems, pages 4879–4888. Curran Associates, Inc.
  * Geifman and El-Yaniv, (2019) Geifman, Y. and El-Yaniv, R. (2019).  SelectiveNet: A Deep Neural Network with an Integrated Reject Option.  In International Conference on Machine Learning (ICML 2019), volume 2019-June, pages 3768–3776.
  * Golfarelli et al., (1997) Golfarelli, M., Maio, D., and Malton, D. (1997).  On the error-reject trade-off in biometric verification systems.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(7):786–796.
  * Göpfert et al., (2018) Göpfert, J. P., Hammer, B., and Wersing, H. (2018).  Mitigating concept drift via rejection.  In Lecture Notes in Computer Science, volume 11139 LNCS, pages 456–467. Springer Cham.
  * Grandvalet et al., (2009) Grandvalet, Y., Rakotomamonjy, A., Keshet, J., and Canu, S. (2009).  Support Vector Machines with a Reject Option.  In Advances in Neural Information Processing Systems 21, pages 537–544. Curran Associates, Inc.
  * Guan et al., (2020) Guan, H., Zhang, Y., Cheng, H. D., and Tang, X. (2020).  Bounded-abstaining classification for breast tumors in imbalanced ultrasound images.  International Journal of Applied Mathematics and Computer Science, 30(2):325–336.
  * Gyorfi et al., (1979) Gyorfi, L., Gyorfi, Z., and Vajda, I. (1979).  Bayesian Decision With Rejection.  Problems of control and information theory, 8(5-6):445–452.
  * Ha, (1996) Ha, T. M. (1996).  An optimum class-selective rejection rule for pattern recognition.  In Proceedings of 13th International Conference on Pattern Recognition, volume 2, pages 75–80. IEEE.
  * (76) Ha, T. M. (1997a).  Optimum tradeoff between class-selective rejection error and average number of classes.  Engineering Applications of Artificial Intelligence, 10(6):525–529.
  * (77) Ha, T. M. (1997b).  The optimum class-selective rejection rule.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(6):608–615.
  * Hamid et al., (2017) Hamid, K., Asif, A., Abbasi, W., Sabih, D., and Afsar, F. A. (2017).  Machine Learning with Abstention for Automated Liver Disease Diagnosis.  In 2017 International Conference on Frontiers of Information Technology (FIT), volume 2017-Janua, pages 356–361. IEEE.
  * Hanczar, (2019) Hanczar, B. (2019).  Performance visualization spaces for classification with rejection option.  Pattern Recognition, 96:106984.
  * Hanczar and Dougherty, (2008) Hanczar, B. and Dougherty, E. R. (2008).  Classification with reject option in gene expression data.  Bioinformatics, 24(17):1889–1895.
  * Hanczar and Sebag, (2014) Hanczar, B. and Sebag, M. (2014).  Combination of one-class support vector machines for classification with reject option.  In Machine Learning and Knowledge Discovery in Databases - Part I, pages 547–562. Springer Berlin Heidelberg.
  * Hansen et al., (1997) Hansen, L. K., Liisberg, C., and Salamon, P. (1997).  The Error-Reject Tradeoff.  Open Systems & Information Dynamics, 4(2):159–184.
  * Harshvardhan et al., (2020) Harshvardhan, G., Gourisaria, M. K., Pandey, M., and Rautaray, S. S. (2020).  A comprehensive survey and analysis of generative models in machine learning.  Computer Science Review, 38:100285.
  * Hatami and Chira, (2013) Hatami, N. and Chira, C. (2013).  Classifiers with a reject option for early time-series classification.  Proceedings of the 2013 IEEE Symposium on Computational Intelligence and Ensemble Learning, CIEL 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013, pages 9–16.
  * Hellman, (1970) Hellman, M. E. (1970).  The Nearest Neighbor Classification Rule with a Reject Option.  IEEE Transactions on Systems Science and Cybernetics, 6(3):179–185.
  * Heo et al., (2018) Heo, J., Lee, H. B., Kim, S., Lee, J., Kim, K. J., Yang, E., and Hwang, S. J. (2018).  Uncertainty-Aware Attention for Reliable Interpretation and Prediction.  In Advances in Neural Information Processing Systems, volume 31, pages 909–918, Montreal, Canada. Curran Associates, Inc.
  * Herbei and Wegkamp, (2006) Herbei, R. and Wegkamp, M. H. (2006).  Classification with reject option.  Canadian Journal of Statistics, 34(4):709–721.
  * Homenda et al., (2014) Homenda, W., Luckner, M., and Pedrycz, W. (2014).  Classification with rejection based on various SVM techniques.  In 2014 International Joint Conference on Neural Networks (IJCNN), pages 3480–3487. IEEE.
  * Homenda et al., (2016) Homenda, W., Luckner, M., and Pedrycz, W. (2016).  Classification with rejection: Concepts and evaluations.  Advances in Intelligent Systems and Computing, 364(December):413–425.
  * Horiuchi, (1998) Horiuchi, T. (1998).  Class-selective rejection rule to minimize the maximum distance between selected classes.  Pattern Recognition, 31(10):1579–1588.
  * Hosseini et al., (2017) Hosseini, H., Chen, Y., Kannan, S., Zhang, B., and Poovendran, R. (2017).  Blocking Transferability of Adversarial Examples in Black-Box Learning Systems.  arXiv preprint arXiv:1703.04318.
  * Hsu et al., (2020) Hsu, Y. C., Shen, Y., Jin, H., and Kira, Z. (2020).  Generalized ODIN: Detecting Out-of-Distribution Image without Learning from Out-of-Distribution Data.  Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 10948–10957.
  * Huang and Suen, (1995) Huang, Y. and Suen, C. (1995).  A method of combining multiple experts for the recognition of unconstrained handwritten numerals.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(1):90–94.
  * Hüllermeier and Waegeman, (2021) Hüllermeier, E. and Waegeman, W. (2021).  Aleatoric and Epistemic Uncertainty in Machine Learning: A Tutorial Introduction.  Machine Learning, 110(3):457–506.
  * Jiang et al., (2018) Jiang, H., Kim, B., Guan, M. Y., and Gupta, M. (2018).  To Trust Or Not To Trust A Classifier.  In 32nd Conference on Neural Information Processing Systems (NIPS), pages 5541–5552, Montreal, Canada.
  * Jiang et al., (2020) Jiang, W., Zhao, Y., and Wang, Z. (2020).  Risk-Controlled Selective Prediction for Regression Deep Neural Network Models.  In 2020 International Joint Conference on Neural Networks (IJCNN), pages 1–8. IEEE.
  * Jigang et al., (2006) Jigang, X., Zhengding, Q., and Jie, W. (2006).  Bootstrap methods for reject rules of fisher LDA.  Proceedings - International Conference on Pattern Recognition, 3:425–428.
  * Joana et al., (2021) Joana, K., Christian, M., and Clemens, G. (2021).  Securing Deep Learning Models with Autoencoder based Anomaly Detection.  In Proceedings of the European Conference of the PHM Society 2021, pages 221–233, Virtual event. PHM Society.
  * Kang et al., (2017) Kang, S., Cho, S., Rhee, S.-j., and Yu, K.-S. (2017).  Reliable prediction of anti-diabetic drug failure using a reject option.  Pattern Analysis and Applications, 20(3):883–891.
  * Kocak et al., (2020) Kocak, M. A., Ramirez, D., Erkip, E., and Shasha, D. (2020).  SafePredict: A Meta-Algorithm for Machine Learning That Uses Refusals to Guarantee Correctness.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(2):1–1.
  * Kompa et al., (2021) Kompa, B., Snoek, J., and Beam, A. L. (2021).  Second opinion needed: communicating uncertainty in medical machine learning.  npj Digital Medicine, 4(1):4.
  * Korycki et al., (2019) Korycki, L., Cano, A., and Krawczyk, B. (2019).  Active Learning with Abstaining Classifiers for Imbalanced Drifting Data Streams.  In 2019 IEEE International Conference on Big Data (Big Data), pages 2334–2343. IEEE.
  * Kotropoulos and Arce, (2009) Kotropoulos, C. and Arce, G. R. (2009).  Linear classifier with reject option for the detection of vocal fold paralysis and vocal fold edema.  Eurasip Journal on Advances in Signal Processing, 2009.
  * Krawczyk and Cano, (2018) Krawczyk, B. and Cano, A. (2018).  Online ensemble learning with abstaining classifiers for drifting and noisy data streams.  Applied Soft Computing, 68:677–692.
  * Kwok, (1999) Kwok, J. T. (1999).  Moderating the outputs of support vector machine classifiers.  IEEE Transactions on Neural Networks, 10(5):1018–1031.
  * Lam and Suen, (1995) Lam, L. and Suen, C. Y. (1995).  Optimal combinations of pattern classifiers.  Pattern Recognition Letters, 16(9):945–954.
  * Landgrebe et al., (2006) Landgrebe, T. C., Tax, D. M., Paclík, P., and Duin, R. P. (2006).  The interaction between classification and reject performance for distance-based reject-option classifiers.  Pattern Recognition Letters, 27(8):908–917.
  * Landgrebe et al., (2004) Landgrebe, T. C., Tax, D. M., Paclík, P., Duin, R. P., and Andrew, C. (2004).  A combining strategy for ill-defined problems.  In Proc. of the 15th Annual Symposium of the Pattern Recognition Association of South Africa, pages 57–62.
  * Laroui et al., (2021) Laroui, S., Descombes, X., Vernay, A., Villiers, F., Debreuve, E., Laroui, S., Descombes, X., Vernay, A., Villiers, F., Villalba, F., and Laroui, S. (2021).  How to define a rejection class based on model learning?  In 25th International Conference on Pattern Recogniton, Milano.
  * Le Capitaine and Frelicot, (2010) Le Capitaine, H. and Frelicot, C. (2010).  An Optimum Class-Rejective Decision Rule and Its Evaluation.  In 2010 20th International Conference on Pattern Recognition, pages 3312–3315. IEEE.
  * Le Capitaine and Frélicot, (2012) Le Capitaine, H. and Frélicot, C. (2012).  A family of measures for best top-n class-selective decision rules.  Pattern Recognition, 45(1):552–562.
  * Le Cun et al., (1990) Le Cun, Y., Matan, O., Boser, B., Denker, J., Henderson, D., Howard, R., Hubbard, W., Jacket, L., and Baird, H. (1990).  Handwritten zip code recognition with multilayer networks.  In [1990] Proceedings. 10th International Conference on Pattern Recognition, volume ii, pages 35–40. IEEE Comput. Soc. Press.
  * Lei, (2014) Lei, J. (2014).  Classification with confidence.  Biometrika, 101(4):755–769.
  * Lewicke et al., (2008) Lewicke, A., Sazonov, E. S., Corwin, M., Neuman, M., and Schuckers, S. (2008).  Sleep Versus Wake Classification From Heart Rate Variability Using Computational Intelligence: Consideration of Rejection in Classification Models.  IEEE Transactions on Biomedical Engineering, 55(1):108–118.
  * Li and Sethi, (2006) Li, M. and Sethi, I. K. (2006).  Confidence-based classifier design.  Pattern Recognition, 39(7):1230–1240.
  * Lin et al., (2018) Lin, D., Sun, L., Toh, K. A., Zhang, J. B., and Lin, Z. (2018).  Twin SVM with a reject option through ROC curve.  Journal of the Franklin Institute, 355(4):1710–1732.
  * Liu et al., (2008) Liu, F. T., Ting, K. M., and Zhou, Z. H. (2008).  Isolation forest.  Proceedings - IEEE International Conference on Data Mining, ICDM, pages 413–422.
  * Loeffel et al., (2015) Loeffel, P. X., Marsala, C., and Detyniecki, M. (2015).  Classification with a reject option under Concept Drift: The Droplets algorithm.  In Proceedings of the 2015 IEEE International Conference on Data Science and Advanced Analytics, DSAA 2015, pages 1–9.
  * Lotte et al., (2008) Lotte, F., Mouchère, H., and Lécuyer, A. (2008).  Pattern rejection strategies for the design of self-paced EEG-based brain-computer interfaces.  Proceedings - International Conference on Pattern Recognition, pages 6–10.
  * Lou et al., (1999) Lou, Z., Liu, K., Yang, J., and Suen, C. (1999).  Rejection Criteria and Pairwise Discrimination of Handwritten Numerals Based on Structural Features.  Pattern Analysis & Applications, 2(3):228–238.
  * Ma et al., (2001) Ma, C., Randolph, M. A., and Drish, J. (2001).  A support vector machines-based rejection technique for speech recognition.  ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, 1:381–384.
  * Madras et al., (2018) Madras, D., Pitassi, T., and Zemel, R. (2018).  Predict responsibly: Improving fairness and accuracy by learning to defer.  Advances in Neural Information Processing Systems, 2018-Decem(NeurIPS):6147–6157.
  * Markou and Singh, (2003) Markou, M. and Singh, S. (2003).  Novelty detection: a review—part 1: statistical approaches.  Signal Processing, 83(12):2481–2497.
  * Marrocco et al., (2007) Marrocco, C., Molinara, M., and Tortorella, F. (2007).  An empirical comparison of ideal and empirical ROC-based reject rules.  In Lecture Notes in Computer Science, volume 4571 LNAI, pages 47–60. Springer, Berlin, Heidelberg.
  * Mena et al., (2020) Mena, J., Pujol, O., and Vitria, J. (2020).  Uncertainty-Based Rejection Wrappers for Black-Box Classifiers.  IEEE Access, 8:101721–101746.
  * Merényi et al., (2016) Merényi, E., Mendenhall, M. J., and O’Driscoll, P. (2016).  Self-Adjusting Reject Options in Prototype Based Classification.  In Advances in Intelligent Systems and Computing, volume 428.
  * Mesquita et al., (2016) Mesquita, D. P., Rocha, L. S., Gomes, J. P. P., and da Rocha Neto, A. R. (2016).  Classification with reject option for software defect prediction.  Applied Soft Computing Journal, 49:1085–1093.
  * Mizutani, (1998) Mizutani, H. (1998).  Discriminative learning for minimum error and minimum reject classification.  In Proceedings. Fourteenth International Conference on Pattern Recognition (Cat. No.98EX170), volume 1, pages 136–140, Brisbane, Queensland, Australia, Australia. IEEE Comput. Soc.
  * Mozannar and Sontag, (2020) Mozannar, H. and Sontag, D. (2020).  Consistent Estimators for Learning to Defer to an Expert.  arXiv preprint arXiv:2006.01862.
  * Muzzolini et al., (1998) Muzzolini, R., Yang, Y.-H., and Pierson, R. (1998).  Classifier design with incomplete knowledge.  Pattern Recognition, 31(4):345–369.
  * Nadeem et al., (2010) Nadeem, M. S. A., Zucker, J., and Hanczar, B. (2010).  Accuracy-Rejection Curves (ARCs) for Comparing Classification Methods with a Reject Option.  Machine Learning in Systems Biology, 8:65–81.
  * Nguyen et al., (2019) Nguyen, V.-L., Destercke, S., and Hüllermeier, E. (2019).  Epistemic Uncertainty Sampling.  In International Conference On Discovery Science DS 2019, volume 11828 LNAI, pages 72–86. Springer, Cham.
  * Nguyen and Hullermeier, (2020) Nguyen, V.-L. and Hullermeier, E. (2020).  Reliable Multilabel Classification: Prediction with Partial Abstention.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5264–5271.
  * Ni et al., (2019) Ni, C., Charoenphakdee, N., Honda, J., and Sugiyama, M. (2019).  On the Calibration of Multiclass Classification with Rejection.  arXiv preprint arXiv:1901.10655, pages 1–31.
  * Pang et al., (2021) Pang, T., Zhang, H., He, D., Dong, Y., Su, H., Chen, W., Zhu, J., and Liu, T.-Y. (2021).  Adversarial Training with Rectified Rejection.  arXiv preprint arXiv:2105.14785, pages 1–23.
  * Pazzani et al., (1994) Pazzani, M. J., Murphy, P., Ali, K., and Schulenburg, D. (1994).  Tradingoff coverage for accuracy in forecasts: Applications to clinical data analysis.  In Proceedings of the AAAI Symposium on AI in Medicine, pages 100–104.
  * Perello-Nieto et al., (2017) Perello-Nieto, M., Filho, T. M., Kull, M., and Flach, P. (2017).  Background check: A general technique to build more reliable and versatile classifiers.  In Proceedings - IEEE International Conference on Data Mining, ICDM, pages 1143–1148.
  * (138) Perini, L., Galvin, C., and Vercruyssen, V. (2020a).  A Ranking Stability Measure for Quantifying the Robustness of Anomaly Detection Methods.  Communications in Computer and Information Science, 1323:397–408.
  * (139) Perini, L., Vercruyssen, V., and Davis, J. (2020b).  Quantifying the Confidence of Anomaly Detectors in Their Example-Wise Predictions.  In Proceedings of European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, Ghent, Belgium. ECML-PKDD.
  * Pietraszek, (2005) Pietraszek, T. (2005).  Optimizing abstaining classifiers using ROC analysis.  In Proceedings of the 22nd international conference on Machine learning - ICML ’05, pages 665–672, New York, New York, USA. ACM Press.
  * Pietraszek, (2007) Pietraszek, T. (2007).  On the use of ROC analysis for the optimization of abstaining classifiers.  Machine Learning, 68(2):137–169.
  * Pillai et al., (2011) Pillai, I., Fumera, G., and Roli, F. (2011).  A Classification Approach with a Reject Option for Multi-label Problems.  In Lecture Notes in Computer Science, volume 6978 LNCS, pages 98–107. Springer Berlin Heidelberg.
  * Pillai et al., (2013) Pillai, I., Fumera, G., and Roli, F. (2013).  Multi-label classification with a reject option.  Pattern Recognition, 46(8):2256–2266.
  * Pimentel et al., (2014) Pimentel, M. A., Clifton, D. A., Clifton, L., and Tarassenko, L. (2014).  A review of novelty detection.  Signal Processing, 99:215–249.
  * Prasad et al., (2009) Prasad, N. R., Almanza-Garcia, S., and Lu, T. T. (2009).  Anomaly detection.  Computers, Materials and Continua, 14(1):1–22.
  * Pudil et al., (1992) Pudil, P., Novovičova, J., Bláha, S., and Kittler, J. (1992).  Multistage pattern recognition with reject option.  In Proceedings - International Conference on Pattern Recognition, volume 2, pages 92–95.
  * Rahman and Fairhurst, (1998) Rahman, A. and Fairhurst, M. (1998).  An evaluation of multi-expert configurations for the recognition of handwritten numerals.  Pattern Recognition, 31(9):1255–1273.
  * Ramaswamy et al., (2018) Ramaswamy, H. G., Tewari, A., and Agarwal, S. (2018).  Consistent algorithms for multiclass classification with an abstain option.  Electronic Journal of Statistics, 12(1):530–554.
  * Ramaswamy et al., (2000) Ramaswamy, S., Rastogi, R., and Shim, K. (2000).  Efficient algorithms for mining outliers from large data sets.  ACM SIGMOD Record, 29:427–438.
  * Sambu Seo et al., (2000) Sambu Seo, Wallat, M., Graepel, T., and Obermayer, K. (2000).  Gaussian process regression: active data selection and test point rejection.  In Proceedings of the IEEE-INNS-ENNS International Joint Conference on Neural Networks. IJCNN 2000. Neural Computing: New Challenges and Perspectives for the New Millennium, volume 3, pages 241–246. IEEE.
  * Sansone et al., (2001) Sansone, C., Tortorella, F., and Vento, M. (2001).  A classification reliability driven reject rule for multi-expert systems.  International Journal of Pattern Recognition and Artificial Intelligence, 15(06):885–904.
  * Santos-Pereira and Pires, (2005) Santos-Pereira, C. M. and Pires, A. M. (2005).  On optimal reject rules and ROC curves.  Pattern Recognition Letters, 26(7):943–952.
  * Sayedi et al., (2010) Sayedi, A., Zadimoghaddam, M., and Blum, A. (2010).  Trading off mistakes and don’t-know predictions.  Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010, pages 1–9.
  * Schölkopf et al., (1999) Schölkopf, B., Williamson, R., Smola, A., Shawe-Taylor, J., and Piatt, J. (1999).  Support vector method for novelty detection.  Advances in Neural Information Processing Systems, 12:582–588.
  * Senge et al., (2014) Senge, R., Bösner, S., Dembczyński, K., Haasenritter, J., Hirsch, O., Donner-Banzhoff, N., and Hüllermeier, E. (2014).  Reliable classification: Learning classifiers that distinguish aleatoric and epistemic uncertainty.  Information Sciences, 255:16–29.
  * Settles, (2009) Settles, B. (2009).  Active Learning Literature Survey.
  * Shekhar et al., (2019) Shekhar, S., Ghavamzadeh, M., and Javidi, T. (2019).  Binary Classification with Bounded Abstention Rate.  arXiv preprint arXiv:1905.09561, pages 1–35.
  * Simeone et al., (2012) Simeone, P., Marrocco, C., and Tortorella, F. (2012).  Design of reject rules for ECOC classification systems.  Pattern Recognition, 45(2):863–875.
  * Singh and Markou, (2004) Singh, S. and Markou, M. (2004).  An Approach to Novelty Detection Applied to the Classification of Image Regions.  IEEE Transactions on Knowledge and Data Engineering, 16(4):396–407.
  * Sotgiu et al., (2020) Sotgiu, A., Demontis, A., Melis, M., Biggio, B., Fumera, G., Feng, X., and Roli, F. (2020).  Deep neural rejection against adversarial examples.  EURASIP Journal on Information Security, 2020(1):5.
  * Sutton and McCallum, (2011) Sutton, C. and McCallum, A. (2011).  An introduction to conditional random fields.  Foundations and Trends in Machine Learning, 4(4):267–373.
  * Sutton and Mccallum, (2019) Sutton, C. and Mccallum, A. (2019).  An Introduction to Conditional Random Fields for Relational Learning.  Introduction to Statistical Relational Learning.
  * Suutala et al., (2004) Suutala, J., Pirttikangas, S., Riekki, J., and Röning, J. (2004).  Reject-Optional LVQ-Based Two-Level Classifier to Improve Reliability in Footstep Identification.  In Lecture Notes in Computer Science, volume 3001, pages 182–187. Springer Berlin Heidelberg.
  * Tang and Sazonov, (2014) Tang, W. and Sazonov, E. S. (2014).  Highly Accurate Recognition of Human Postures and Activities Through Classification With Rejection.  IEEE Journal of Biomedical and Health Informatics, 18(1):309–315.
  * Tax and Duin, (2008) Tax, D. M. and Duin, R. P. (2008).  Growing a multi-class classifier with a reject option.  Pattern Recognition Letters, 29(10):1565–1570.
  * Thulasidasan et al., (2019) Thulasidasan, S., Bhattacharya, T., Bilmes, J., Chennupati, G., and Mohd-Yusof, J. (2019).  Combating Label Noise in Deep Learning Using Abstention.  In Proceedings of the 36 th International Conference on Machine Learning.
  * Tortorella, (2000) Tortorella, F. (2000).  An Optimal Reject Rule for Binary Classifiers.  In Lecture Notes in Computer Science, volume 1876 LNCS, pages 611–620. Springer Cham.
  * Tortorella, (2004) Tortorella, F. (2004).  Reducing the classification cost of support vector classifiers through an ROC-based reject rule.  Pattern Analysis and Applications, 7(2):128–143.
  * Tortorella, (2005) Tortorella, F. (2005).  A ROC-based reject rule for dichotomizers.  Pattern Recognition Letters, 26(2):167–180.
  * Ulmer and Cinà, (2020) Ulmer, D. and Cinà, G. (2020).  Know Your Limits: Uncertainty Estimation with ReLU Classifiers Fails at Reliable OOD Detection.  arXiv preprint arXiv:2012.05329.
  * Urahama and Furukawa, (1995) Urahama, K. and Furukawa, Y. (1995).  Gradient descent learning of nearest neighbor classifiers with outlier rejection.  Pattern Recognition, 28(5):761–768.
  * Vailaya and Jain, (2000) Vailaya, A. and Jain, A. (2000).  Reject option for VQ-based Bayesian classification.  In Proceedings 15th International Conference on Pattern Recognition. ICPR-2000, volume 2, pages 48–51. IEEE Comput. Soc.
  * Van der Plas et al., (2021) Van der Plas, D., Meert, W., Verbraecken, J., and Davis, J. (2021).  A reject option for automated sleep stage scoring.  In ICML Workshop on Interpretable Machine Learning in Healthcare, Virtual event.
  * Varshney, (2006) Varshney, K. R. (2006).  A Kernel Based Rejection Method for Supervised Classification.  International Journal of Computational Intelligence, 3(4):312–321.
  * Varshney, (2011) Varshney, K. R. (2011).  A risk bound for ensemble classification with a reject option.  In 2011 IEEE Statistical Signal Processing Workshop (SSP), pages 769–772. IEEE.
  * Vasconcelos et al., (1993) Vasconcelos, G., Fairhurst, M., and Bisset, D. (1993).  Enhanced reliability of multilayer perceptron networks through controlled pattern rejection.  Electronics Letters, 29(3):261.
  * Vasconcelos et al., (1995) Vasconcelos, G., Fairhurst, M., and Bisset, D. (1995).  Investigating feedforward neural networks with respect to the rejection of spurious patterns.  Pattern Recognition Letters, 16(2):207–212.
  * Villmann et al., (2015) Villmann, T., Kaden, M., Nebel, D., and Biehl, M. (2015).  Learning Vector Quantization with Adaptive Cost-Based Outlier-Rejection.  In Lecture Notes in Computer Science, volume 9257, pages 772–782. Springer, Cham.
  * Wang and Yiu, (2020) Wang, X. and Yiu, S. M. (2020).  Classification with Rejection: Scaling Generative Classifiers with Supervised Deep Infomax.  In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, pages 2980–2986, California. International Joint Conferences on Artificial Intelligence Organization.
  * Wegkamp, (2007) Wegkamp, M. H. (2007).  Lasso type classifiers with a reject option.  Electronic Journal of Statistics, 1:155–168.
  * Wegkamp and Yuan, (2012) Wegkamp, M. H. and Yuan, M. (2012).  Support vector machines with a reject option.  Bernoulli, 17(4):1368–1385.
  * Wu et al., (2007) Wu, Q., Jia, C., and Chen, W. (2007).  A Novel Classification-Rejection Sphere SVMs for Multi-class Classification Problems.  In Third International Conference on Natural Computation (ICNC 2007), volume 1, pages 34–38. IEEE.
  * Xu et al., (1992) Xu, L., Krzyzak, A., Suen, C. Y. C., Krzyżak, A., and Suen, C. Y. C. (1992).  Methods of Combining Multiple Classifiers and Their Applications to Handwriting Recognition.  IEEE Transactions on Systems, Man, and Cybernetics, 22(3):418–435.
  * Yuan and Wegkamp, (2010) Yuan, M. and Wegkamp, M. H. (2010).  Classification methods with reject option based on convex risk minimization.  Journal of Machine Learning Research, 11:111–130.
  * Zhang and Chaudhuri, (2014) Zhang, C. and Chaudhuri, K. (2014).  Beyond disagreement-based agnostic active learning.  Advances in Neural Information Processing Systems, 1(January):442–450.
  * Zhang et al., (2018) Zhang, C., Wang, W., and Qiao, X. (2018).  On Reject and Refine Options in Multicategory Classification.  Journal of the American Statistical Association, 113(522):730–745.
  * Zhang and Metaxas, (2006) Zhang, R. and Metaxas, D. (2006).  RO-SVM: Support Vector Machine with Reject Option for Image Categorization.  In Procedings of the British Machine Vision Conference 2006, pages 1–123. British Machine Vision Association.
  * Zheng et al., (2011) Zheng, E.-h., Zou, C., Sun, J., and Chen, L. (2011).  Cost-sensitive SVM with Error Cost and Class-dependent Reject Cost.  International Journal of Computer Theory and Engineering, 3(1):130–135.
  * Zidelmal et al., (2012) Zidelmal, Z., Amirou, A., and Belouchrani, A. (2012).  Heartbeat classifcation using support vector machines (SVMs) with an embedded reject option.  International Journal of Pattern Recognition and Artificial Intelligence, 26(01):1250001.
  * Ziyin et al., (2019) Ziyin, L., Wang, Z. T., Liang, P. P., Salakhutdinov, R., Morency, L. P., and Ueda, M. (2019).  Deep gamblers: Learning to abstain with portfolio theory.  Advances in Neural Information Processing Systems, 32(NeurIPS):1–17.
  * Zou et al., (2011) Zou, C., Zheng, E.-h., Xu, H.-w., and Chen, L. (2011).  Cost-sensitive Multi-class SVM with Reject Option: A Method for Steam Turbine Generator Fault Diagnosis.  International Journal of Computer Theory and Engineering, 3(1):77–83.


# No Tradeoff between Coherence and Sub-Poissonianity for Heisenberg-Limited
Lasers

L. A. Ostrowski<EMAIL_ADDRESS>T. J. Baker  S. N.
Saadatmand  H. M. Wiseman<EMAIL_ADDRESS>Centre for Quantum
Dynamics, Griffith University, Yuggera Country, Brisbane, Queensland 4111,
Australia

###### Abstract

The Heisenberg limit to laser coherence $\mathfrak{C}$—the number of photons
in the maximally populated mode of the laser beam—is the fourth power of the
number of excitations inside the laser. We generalize the previous proof of
this upper bound scaling by dropping the requirement that the beam photon
statistics be Poissonian (i.e., Mandel’s $Q=0$). We then show that the
relation between $\mathfrak{C}$ and sub-Poissonianity ($Q<0$) is win-win, not
a tradeoff. For both regular (non-Markovian) pumping with semi-unitary gain
(which allows $Q\xrightarrow{}-1$), and random (Markovian) pumping with
optimized gain, $\mathfrak{C}$ is maximized when $Q$ is minimized.

††preprint: APS/123-QED

##  I Introduction

The characteristic ability of a laser to produce optical fields with a high
degree of coherence has led to their widespread application in precision
technology. This is especially true in the quantum regime, as the ability to
access such fields has directly permitted quantum optics to flourish [1, 2, 3,
4, 5], paving the way for the advent of quantum technology [6, 7]. This
defining feature of coherence can be quantified for a continuous-wave laser by
$\mathfrak{C}$, the mean number of photons in a maximally populated mode of
the beam [8]. For a laser, unlike other light sources, this number will
typically be enormous, and may be far greater than the number of excitations
stored inside the laser itself. Considering a laser beam with “ideal”
properties—being describable by a coherent state undergoing pure phase-
diffusion [9, 10, 11]—$\mathfrak{C}$ can be intuitively expressed in terms of
the photon flux from the laser, $\mathcal{N}$, and its linewidth, $\ell$, as
$\mathfrak{C}=4\mathcal{N}/\ell$.

The foundations of laser theory was the derivation, by Schawlow and Townes, of
the laser linewidth, $\ell$ [12]. This formula sets a bound on $\ell$, and
hence $\mathfrak{C}$ in terms of an energy resource, namely,
$\mathfrak{C}_{\textrm{STL}}=\Theta(\mu^{2})$ [13]. Here, $\mu$ is the mean
number of total coherent excitations within the laser (including photons,
atomic excitations, excitons, etc). This limit was long thought to have been
an absolute limit, but recent works have shown that this may be greatly
surpassed [8, 14]. In particular, the authors of Ref. [8] considered the
Heisenberg limit (HL) for $\mathfrak{C}$, that is, the ultimate achievable
limit that is imposed by quantum mechanics, rather than by standard
technologies. They proved rigorously, under some natural conditions, that the
HL is

$\displaystyle\mathfrak{C}_{\textrm{HL}}=\Theta(\mu^{4}).$ (1)

These conditions conceive of a laser as a device that produces an output
closely approximating an ideal laser beam without restricting the processes by
which it achieves this, other than that the phase of the beam proceeds only
from the phase of the excitations stored within the device. The key to
attaining this quadratic quantum enhancement is to change both the pumping and
output coupling of the laser to be highly nonlinear, a feat that is
potentially achievable in circuit-QED [8, 14].

This letter advances the physics objectives within this field in two ways.
First, we generalize the salient result of Ref. [8], such that the HL scaling
$\mathfrak{C}=O(\mu^{4})$ is re-derived under significantly relaxed conditions
on the beam. This is motivated by the prospects of experimental realization.
The strict conditions placed on the beam given in Ref. [8] will probably not
be satisfied in the most feasible near-term experimental hardware that would
surpass the standard quantum limit for $\mathfrak{C}$ [15].

Second, this relaxation permits us study the photon statistics of Heisenberg-
limited lasers (_i.e._ , those achieving Eq. (1)). This has furnished us with
a fundamental insight to the nature of laser radiation. That is because the
more general HL derived here applies to laser beams exhibiting sub-Poissonian
photon statistics, even allowing the number fluctuations to vanish for long
counting intervals. Interest in the production of sub-Poissonian light from
lasers started in the 1980s and early 1990s [16, 17, 18, 19, 20, 21, 22, 23,
24, 25]. It has remained an active area of research since then [26, 27, 28,
29], due to the foreseeable broad application in areas such as quantum-
enhanced measurement, communication, sensing and information processing [30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41].

Among the early work within this area, several theoretical studies were
conducted to determine if a tradeoff existed between the coherence and degree
of sub-Poissonianity in standard laser beams (_i.e._ , those which achieve
$\mathfrak{C}=\Theta(\mu^{2})$ at best). It was shown that for a laser with
standard output coupling, pumping which achieves a sub-Poissonian output does
not necessarily significantly increase the phase diffusion rate [42, 43, 44,
45] (though in other models it does [22]). In this work, we extend the results
from these early studies to the extreme case, to laser models which exhibit a
phase-diffusion rate that is as small as permitted by the laws of quantum
mechanics.

We show that there is no tradeoff between coherence and the degree of sub-
Poissonianity (quantified by the Mandel-$Q$ parameter [46]) in Heisenberg-
limited laser beams. Moreover, a “win-win situation” occurs in both of the
families of laser models we introduce. These models exhibit Heisenberg-limited
coherence as well as sub-Poissonian beam photon statistics in certain
parameter regimes, and there is a perfect correlation between an increase in
the coherence and a decrease in the Mandel-$Q$ parameter of the beam. An
important point to stress here is that “external squeezing” is not an
alternative to our models. The conception of a “laser” in Refs. [8, 14] and
this work means considering the whole device, encompassing all processes that
give rise to both the coherence and the sub-Poissonianity in the beam, as a
laser. Throughout, we refer to the Companion Paper [15] for details of proofs
and much more.

##  II Beam Coherence and Sub-Poissonianity

We start with the two quantities relating to a laser beam that are the focus
of this Letter. The first of these is laser coherence, $\mathfrak{C}$, which
relates to the phase fluctuations of the beam. A unidirectional beam of light
produced by a laser can be aptly described as a scalar quantum field with the
single-parameter field annihilation operator, $\hat{b}(t)$. For such a field,
$\mathfrak{C}$ is defined as the maximally populated mode (within some
frequency band, if required) [8],

$\displaystyle\mathfrak{C}:=\max_{u\in\mathfrak{u}}\langle\hat{b}_{u}^{\dagger}\hat{b}_{u}\rangle.$
(2)

Here, $\hat{b}_{u}=(1/\sqrt{I_{u}})\int_{-\infty}^{\infty}dtu(t)\hat{b}(t)$
defines the annihilation operator for mode $u$, which is normalized such that
$I_{u}=\int_{-\infty}^{\infty}dt|u(t)|^{2}$.

We can gain intuition about this quantity by analyzing Eq. (2) under some
additional assumptions that are characteristic of an ‘ideal’ laser beam.
First, for a beam with translationally invariant statistics,
$\mathfrak{C}/2\pi$ is simply the peak of the power spectrum $P(\omega)$, the
Fourier transform of the correlation function
$\langle\hat{b}^{\dagger}(t+\tau)\hat{b}(t)\rangle$ [8]. Additionally, the
early work on laser theory during the 1960’s and 70’s [9, 10] showed that,
when technical noise is negligible, the state of a laser beam can be well-
approximated by the eigenstate

$\displaystyle\ket{\beta(t)}=\ket{\sqrt{\mathcal{N}}e^{i\sqrt{\ell}W(t)}},$
(3)

of $\hat{b}(t)$ for each $t$, where $W(t)$ represents a Wiener process. That
is, it is a coherent state undergoing pure phase-diffusion at rate $\ell$. For
such a state, the photon statistics are Poissonian [9, 47] and the power
spectrum is Lorentzian,

$\displaystyle
P(\omega)=\frac{\mathfrak{C}}{2\pi}\frac{(\ell/2)^{2}}{(\omega-\omega_{0})^{2}+(\ell/2)^{2}},$
(4)

where $\omega_{0}$ is the central frequency. Since the linewidth of this ideal
beam is entirely due to phase-diffusion, the coherence time, $1/\ell$, can be
thought of as the time for the phase of the laser to become fairly randomized.
Multiplying this by the photon flux, $\mathcal{N}=\int d\omega P(\omega)$, one
has $\mathcal{N}/\ell=\mathfrak{C}/4$. In the context of such an ideal laser,
$\mathfrak{C}$ may therefore be interpreted roughly as the number of photons
emitted into the beam with a well-defined phase relationship.

Second, to characterize the intensity fluctuations in the beam, we employ the
Mandel-$Q$ parameter [46] defined on the output field over the duration $T$:

$\displaystyle
Q_{T}:=\frac{\langle(\Delta\hat{n}_{T})^{2}\rangle-\langle\hat{n}_{T}\rangle}{\langle\hat{n}_{T}\rangle},$
(5)

with $\hat{n}_{T}\equiv\int_{T_{0}}^{T_{0}+T}ds\hat{b}^{\dagger}(s)\hat{b}(s)$
as the number operator for the section of the beam over the interval
$(T_{0},T_{0}+T]$. Note that $Q_{T}$ does not depend on $T_{0}$ for a
stationary field. This is an affine function of the variance in the number of
photon detections made by an ideal detector monitoring the beam. It is defined
so that $Q\in[-1,0)$ implies sub-Poissonian photon statistics (a variance less
than the mean) in the beam over the interval $(T_{0},T_{0}+T]$. Here we
consider the limit of long counting intervals, $T\xrightarrow{}\infty$. That
is, the measure of beam intensity fluctuations we seek to minimize is $Q\equiv
Q_{T\xrightarrow{}\infty}$.

##  III Generalizing the Heisenberg Limit for $\mathfrak{C}$

In Ref. [8] four conditions were considered for a laser and the beam it
produces. For a device satisfying these conditions, it was shown that
$\mathfrak{C}\lesssim 2.9748\mu^{4}$, representing a Heisenberg limit for the
coherence of its beam. One of these conditions implies a beam that exhibits
$Q_{T}\approx 0$. Here we summarize these four conditions and the motivation
behind them, before showing how they can be modified such that a more general
Heisenberg limit for $\mathfrak{C}$ can be derived. This generalized limit
applies to lasers that produce a beam for which its photon statistics can have
a significant degree of sub-Poissonianity. The original four conditions are as
follows:

Condition 1, or One Dimensional Beam, states that the beam propagates away
from the laser in one direction at a constant speed, occupying a single
transverse mode and polarization. This allows the output of the device to be
described by a scalar quantum field with the annihilation operator
$\hat{b}(t)$ satisfying $[\hat{b}(s),\hat{b}^{\dagger}(t)]=\delta(s-t)$.

Condition 2, or Endogenous Phase, requires that coherence in the beam proceeds
only from within the laser. This is satisfied if a phase shift imposed on the
laser state at some time $T_{0}$ will lead, in the future, to the same phase
shift on the beam emitted after time $T_{0}$, as well as on the laser state.
When considering specific laser models in practice, this follows naturally if
the mechanisms of gain and loss of excitations in the laser correspond to
$U(1)$-covariant processes [8, 48].

Condition 3, or Stationarity, requires the laser and the beam it produces to
have a long time limit that is unique and invariant under time translation.
This means that the mean excitation number within the laser,
$\langle\hat{n}_{\rm c}\rangle$, has a unique stationary value $\mu$.

Condition 4, or Ideal Glauber(1),(2)-Coherence, states that the stationary
first- and second-order Glauber coherence functions [49] of the laser
beam—$g_{\rm laser}^{(1)}(s,t)$ and $g_{\rm
laser}^{(2)}(s,s^{\prime},t^{\prime},t)$, respectively—well-approximate those
of an ideal standard laser beam state given by Eq. (3). The motivation for
this condition is that it allows the beam to exhibit the typical properties of
an ideal laser beam to a good approximation (such as a Lorentzian power
spectrum and Poissonian beam statistics), while also allowing the upper bound
on $\mathfrak{C}$ to be obtained by the specific method of proof used in Ref
[8].

In this work, we adopt Conditions 1–3 outright as requirements for a laser to
satisfy, however Condition 4 is significantly relaxed to encompass a much more
general range of laser models. The new Condition 4 that we consider, Passably
Ideal Glauber(1),(2) Coherence, requires bounding the differences between the
Glauber coherence functions (first- and second-order) for the laser beam in
question and an ideal beam as follows:

$\displaystyle|g_{\rm laser}^{(1)}(s,t)-g^{(1)}_{\rm ideal}(s,t)|=O(1),$ (6a)
$\displaystyle|g_{\rm laser}^{(2)}(s,s^{\prime},t^{\prime},t)-g^{(2)}_{\rm
ideal}(s,s^{\prime},t^{\prime},t)|=O(\mathfrak{C}^{-1/2}),$ (6b)

for all values of the time arguments such that the difference between any two
times is $O(\sqrt{\mathfrak{C}}/\mathcal{N})$.

The original Condition 4 of Ref. [8] is the same as the one above, except for
having $o$ in place of $O$ in Eqs. (6a) and (6b). As we will show, this
revised condition now allows for models that produce highly sub-Poissonian
beams, where $Q$ approaches its minimum of $-1$, corresponding to vanishing
photon noise in the beam for long counting intervals. Specifically, this is
permitted because of the weaker constraint on $g^{(2)}_{\rm
laser}(s,s^{\prime},t^{\prime},t)$.

We note here that because $g^{(1)}_{\rm laser}(s,t)$ is relatively
unconstrained by Eq. (6a), the interpretation provided for $\mathfrak{C}$
below Eq. (4) would not generally be vaild for a laser device satisfying this
criteria. However, for the laser models presented in this work, $g^{(1)}(s,t)$
does exhibit an exponential decay characteristic of an ideal beam to a very
good approximation [15]. Thus we can still think of $\mathfrak{C}$ as the
number of photons emitted in a coherence time.

A proof for the upper bound on $\mathfrak{C}$ for a beam satisfying these more
relaxed conditions is now outlined; for details, see Ref. [15].

Theorem 1: (Generalisation of the upper bound on $\mathfrak{C}$ for sub-
Poissonian lasers). For a laser which satisfies Conditions 1–3, along with the
new Condition 4, stated above, the coherence is bounded from above:

$\displaystyle\mathfrak{C}=O(\mu^{4}),$ (7)

with $\mu$, the mean number of excitations within the laser.

The methodology applied to show this follows closely that of Ref. [8], which
boils down to comparing the precision between different methods of estimating
the optical phase of a laser. In particular, we consider a laser model
satisfying Conditions 1–3, and the Passably Ideal Glauber Coherence Condition,
operating at steady state. One observer, Effie, then encodes a random phase,
$\phi_{F}$, onto the laser state by performing a filtering heterodyne
measurement on its beam over the time interval $[T-\tau,T)$.

It is the job of a second observer, Rod, to estimate this encoded optical
phase. we consider two methods to achieve this. The first is a retrofiltering
heterodyne measurement of the beam over the interval $(T,T+\tau]$. From the
theory of heterodyne detection [50], it is possible to quantify how correlated
Rod’s retrofiltering measurement outcome, $\phi_{R}$, is with Effie’s result,
$\phi_{F}$. Considering the relative difference, in the deviations of the
estimates, between the laser model and that of an ideal beam [15], we arrive
at the expression

$\displaystyle 1-|\langle
e^{i(\phi_{R}-\phi_{F})}\rangle|^{2}=O(\mathfrak{C}^{-1/2}),$ (8)

for the choice $\tau=\Theta(\sqrt{\mathfrak{C}}/\mathcal{N})$, which minimizes
the scaling of the mean-square error (MSE) in Rod’s measurement [8]. It should
be recognized that the LHS of this equation provides a measure of phase
spread, as for small errors $\theta$, $1-|\langle
e^{i\theta}\rangle|\approx\langle\theta^{2}\rangle-\langle\theta\rangle^{2}$
represents the MSE.

Equation (8) highlights a key difference here with the result of Ref. [8];
there, a specific prefactor was able to be obtained in Eq. (8). Because of our
relaxed constraints imposed on the beam by our fourth Condition, a prefactor
for this quantity, and hence for the upper bound on $\mathfrak{C}$, is no
longer able to be attained. Regardless of this, we are still able to derive a
limit for the scaling of $\mathfrak{C}$ with $\mu$, which is sufficient to
talk of a Heisenberg limit.

To derive this, consider Rod’s second method for obtaining an estimate for
$\phi_{F}$: performing a direct phase measurement on the laser device at time
$T$. It is a known result [51] that the MSE of such an estimate, $\phi_{D}$,
is bounded below, asymptotically,

$\displaystyle 1-|\langle
e^{i(\phi_{D}-\phi_{F})}\rangle|^{2}=\Omega(\mu^{-2}).$ (9)

Finally, $\phi_{R}$ obtained via the retrofiltering measurement outlined above
cannot outperform $\phi_{D}$ as an estimate of the encoded laser phase
$\phi_{F}$ [8]. It therefore follows from Eqs. (8) and (9) that
$\mathfrak{C}=O(\mu^{4})$ represents the Heisenberg limit for any laser
satisfying the stated conditions. From our adopted method of proof, these are
the loosest requirements on the laser for which this $\mu^{4}$ scaling can be
proven to be the HL.

##  IV Sub-Poissonian, Heisenberg-Limited Laser Models

We now present two families of laser models, both satisfying our four
conditions [15], and both exhibiting Heisenberg-limited coherence with
$\mathfrak{C}=\Theta(\mu^{4})$. Fig. 1 shows the key components of these: the
laser “cavity” (a $D$-level system with the non-degenerate number operator
$\hat{n}_{c}=\sum_{n=0}^{D-1}n\outerproduct{n}{n}$) storing an average of
$\mu$ excitations at steady state, a pump that adds incoherent excitations
into the cavity, a vacuum input, which, upon reflection, becomes the beam, and
finally a sink for all excitations that leave the cavity but not in the beam.

The two families have been developed by making generalizations to the original
laser model of Ref. [8], with particular regard to the pumping mechanisms. In
a frame rotating at cavity resonance, the dynamics of the laser cavity for
this original model can be written in terms of a master equation in Lindblad
form $\dot{\rho}=\mathcal{D}[\hat{G}]\rho+\mathcal{D}[\hat{L}]\rho$, where
$\mathcal{D}[\hat{c}]\bullet:=\hat{c}\bullet\hat{c}^{\dagger}-(1/2)\\{\hat{c}^{\dagger}\hat{c},\bullet\\}$
is the usual Lindblad superoperator [50]. Here, $\hat{G}$ and $\hat{L}$ are
the single-excitation gain and loss operators, which, in the number basis,
have non-zero matrix elements $\hat{G}_{n,n-1}\propto 1$ and
$\hat{L}_{n-1,n}\propto(\rho_{n-1}/\rho_{n})^{1/2}$. Here
$\rho_{n}=\bra{n}\rho_{\rm ss}\ket{n}$ are the non-zero elements of the cavity
steady state,

$\displaystyle\rho_{n}\propto\sin^{4}\left({\pi\frac{n+1}{D+1}}\right),\quad
0\leq n\leq D-1.$ (10)

In this scenario, we say that the gain operator is quasi-isometric
($\hat{G}^{\dagger}\hat{G}=\mathds{1}-\ket{D-1}\bra{D-1}$). This laser model
produces a beam that exhibits Poissonian beam photon statistics, in accordance
with the strict Ideal Glauber(1),(2)-Coherence condition of Ref. [8]. The
ansatz for the cavity steady state (10) was suggested by numerical
optimization of $\mathfrak{C}$ based on infinite matrix product state (iMPS)
techniques [8, 52].

Figure 1:  Basic schematic of a laser showing the key components of the two
families of models discussed in the text. Top green box depicts different
statistics for the pump, applicable to the $q$-family, while the
$\lambda$-family is constrained to have Poissonian pumping statistics.

The first family of models that we introduce can be described with a master
equation in the same form as that described above, while making the
substitutions $\hat{G}\xrightarrow{}\hat{G}^{(\lambda)}$ and
$\hat{L}\xrightarrow{}\hat{L}^{(\lambda)}$. Here, the parameter
$\lambda\in\mathbb{R}$ generalizes the gain and loss operators according to

$\displaystyle
G^{(\lambda)}_{n,n-1}\propto\left(\rho_{n}/\rho_{n-1}\right)^{\lambda/2},\quad
L^{(\lambda)}_{n-1,n}\propto\left(\rho_{n-1}/\rho_{n}\right)^{(1-\lambda)/2}.$
(11)

This preserves the same ansatz for the cavity steady state (10) as in Ref.
[8], and the original model corresponds to $\lambda=0$ (flat gain [13]). This
“$\lambda$-family” of laser models generally describes a randomly-pumped gain
mechanism, which, for $\lambda\neq 0$, is non-isometric
($\hat{G}^{\dagger}\hat{G}$ is far from the identity $\mathds{1}$) [15].

The second family that we introduce instead describes a regularly pumped (non-
Markovian) gain mechanism, which is quasi-isometric. The cavity dynamics for
this “$q$-family” can be approximated as

$\displaystyle\dot{\rho}=\left(\mathcal{D}[\hat{G}^{(0)}]+\frac{q}{2}\mathcal{D}[\hat{G}^{(0)}]^{2}+\mathcal{D}[\hat{L}^{(-q/2)}]\right)\rho,$
(12)

where $q\in(-1,\infty]$ represents the Mandel-$Q$ parameter of the pumping
statistics (see Fig. 1). This also has the steady state (10) in the limit
$D\xrightarrow{}\infty$ [15] and the loss operator in Eq. (12) is as defined
in Eq. (11). Setting $q=0$ thus reduces Eq. (12) to the model presented in
Ref. [8]. This master equation is only an approximation because it is a
Markovian equation describing a generally non-Markovian process. Regardless of
this, master equations of this form have long been employed to model
regularly-pumped lasers [16, 53, 42, 44, 36] and the results that it yields
are physically reasonable. For details, see Ref. [15].

Figures 2a–b show the scaling of $\mathfrak{C}$, for members of both the above
families, with the mean photon number $\mu=(D-1)/2$. These quantities were
numerically computed by discretizing the output beam and treating the laser as
an iMPS sequential quantum factory [54, 55]; see also Refs. [8, 15]. Fitting a
power law to each of these curves reveals $\mathfrak{C}=\Theta(\mu^{4})$ for
every choice of $\lambda$ and $q$, thus saturating the upper bound scaling of
Eq. (7). These plots also indicate that the prefactor of these power laws are
optimized by the choice $\lambda=0.5$ in the $\lambda$-family, and $q=-1$ in
the $q$-family. These prefactors are roughly, respectively, a factor of $2$
and $4$ larger than that of the model from Ref. [8].

Figure 2:  (a): iMPS calculations of beam coherence $\mathfrak{C}$ for the
$\lambda$-family of laser models as a function of average cavity excitation
number $\mu$. Circles, dots, and crosses correspond to $\lambda=0.0$, $0.25$,
and $0.5$, respectively. Solid lines depict fitted power laws to the data,
indicating a scaling of $\mathfrak{C}=\Theta(\mu^{4})$. (b): Same as (a), but
for the $q$-family of laser models, with $q=0.0$, $-0.5$, and $-1.0$,
respectively. (c,d): iMPS calculations of $\mathfrak{C}$ (normalized to
$\mathfrak{C}_{0}=\mathfrak{C}_{\lambda=0}=\mathfrak{C}_{q=0}$) and
$Q$-parameter for the $\lambda$\- and $q$-families, respectively, for a fixed
$\mu=499.5$. White overlapped curves (often appearing centered over the
numerics) are analytical formulae discussed in the text. Vertical grey lines
highlight the model parameter values which give rise to Poissonian beam photon
statistics.

This interesting detail is investigated in more depth in Figures 2d–e,
plotting $\mathfrak{C}$ and $Q$ for both families of laser models as functions
of $\lambda$ and $q$, for fixed $D=1000$. We find that increasing beam
coherence is perfectly correlated with a reduction in beam photon noise. For
the $\lambda$-family,
$\mathfrak{C}_{\lambda}\approx\mathfrak{C}_{\lambda=0}/[2(\lambda-1/2)^{2}+1/2]$,
while $Q_{\lambda}\approx 2\lambda(\lambda-1)$. For the $q$-family,
$\mathfrak{C}_{q}\approx\mathfrak{C}_{q=0}/(1+q/2)^{2}$, while $Q_{q}\approx
q$, mirroring the Mandel-$Q$ parameter of the pumping mechanism. These
formulae are indicated by the overlapped white curves and can be derived in
the asymptotic limit, where $D\xrightarrow{}\infty$ [15].

Within the $\lambda$-family, a minimum value of $Q=-0.5$ is attained when
$\lambda=0.5$, which defines the matrix elements of the gain and loss
operators as reciprocals to one another. This value for $Q$ corresponds to a
$50\%$ reduction below the shot noise limit. With the $q$-family, we instead
find that $100\%$ noise reduction in the beam is achievable by imposing a
completely regular pump with $q\xrightarrow{}-1$. Creating a sub-Poissonian
beam in this manner, by means of subjecting the laser to a pump which itself
is sub-Poissonian, is well known [36, 45]; it is also known that imposing such
a pump in an otherwise standard laser has no effect on the rate of phase
diffusion (and hence coherence) [42, 43, 44, 45]. What is interesting about
the results at hand is that the models we study exhibit a phase diffusion
vastly smaller than standard, and for both families, sub-Poissonian statistics
in the output field ensue when measures are taken to increase the coherence.
In other words, we find that there is a “win-win relationship” between
coherence and sub-Poissonianity for optimized Heisenberg-limited lasers.

In this Letter we have shown how the Heisenberg limit for laser coherence may
be generalized to encompass beams that may be highly sub-Poissonian. From this
result, we have found that reducing the photon noise for such a beam can in
fact be advantageous for a reduction in the phase noise. This marks a
generalization of past studies into sub-Poissonian lasers with standard
(linear) photon loss, to beams which exhibit phase noise that is as small as
permitted by the laws of quantum mechanics. This work could have applications
in technologies requiring minimized noise in both intensity and phase, such as
quantum information processing.

We acknowledge the support of the Griffith University eResearch Service and
Specialised Platforms Team, and the use of the High Performance Computing
Cluster “Gowonda” to complete this research. This research was funded by the
Australian Government through the through the Australian Research Council’s
Discovery Projects funding scheme (project DP220101602), and an Australian
Government Research Training Program (RTP) Scholarship.

## References

  * [1] D. Leibfried, R. Blatt, C. Monroe, and D. Wineland, Quantum dynamics of single trapped ions, Rev. Mod. Phys. 75, 281 (2003).
  * [2] I. Bloch, Quantum Coherence and Entanglement with Ultracold Atoms in Optical Lattices, Nature (London) 453, 1016 (2008).
  * [3] S. Deléglise, I. Dotsenko, C. Sayrin, J. Bernu, M. Brune, J.-M. Raimond, and S. Haroche, Reconstruction of non-classical cavity field states with snapshots of their decoherence, Nature (London) 455, 510 (2008).
  * [4] B. Hensen _i.e._ , Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres, Nature (London) 526, 682 (2015).
  * [5] Z. K. Minev, S. O. Mundhada, S. Shankar, P. Reinhold, R. Gutierrez-Jauregui, R. J. Schoelkopf, M. Mirrahimi, H. J. Carmichael, and M. H. Devoret, To Catch and Reverse a Quantum Jump Mid-Flight, Nature (London) 570, 200 (2019).
  * [6] J. I. Cirac and P. Zoller, Quantum Computations with Cold Trapped Ions, Phys. Rev. Lett. 74, 4091 (1995).
  * [7] D. Browne, S. Bose, F. Mintert and M.S. Kim, From quantum optics to quantum technologies, Progress in Quantum Electronics 54, 2 (2017).
  * [8] T. Baker, S. Saadatmand, D. Berry and H. Wiseman, The Heisenberg Limit for Laser Coherence, Nat. Phys. 17, 179 (2021).
  * [9] M. Sargent, M. O. Scully, and W. Lamb, Laser Physics (Addison-Wesley, Reading Mass., 1974).
  * [10] W. H. Louisell, Quantum Statistical Properties of Radiation (John Wiley & Sons, New York, 1973).
  * [11] H. Carmichael, Statistical Methods in Quantum Optics 1: Master Equations and Fokker-Planck Equations (Springer, Berlin, 1999).
  * [12] A. Schawlow and C. Townes, Infrared and Optical Masers, Phys. Rev. 112, 1940 (1958).
  * [13] H. Wiseman, Light Amplification without Stimulated Emission: Beyond the Standard Quantum Limit to the Laser Linewidth, Phys. Rev. A 60, 4083 (1999).
  * [14] C. Liu, M. Mucci, X. Cao, G. Dutt, M. Hatridge and D. Pekker, Proposal for a Continuous Wave Laser with Linewidth Well Below the Standard Quantum Limit, Nat. Commun. 12, 5620 (2021).
  * [15] L. A. Ostrowski, T. J. Baker, S. N. Saadatmand, and H. M. Wiseman, arXiv:2208.14082 [quant-ph] (2022).
  * [16] Y. M. Golubev and I. V. Sokolov, Photon antibunching in a coherent light source and suppression of the photorecording noise, Sov. Phys. JETP 60, 234 (1984).
  * [17] Y. Yamamoto, S. Machida and O. Nilsson, Amplitude squeezing in a pump-noise-suppressed laser oscillator, Phys. Rev. A 34, 4025 (1986).
  * [18] S. Machida, Y. Yamamoto and Y. Itaya, Observation of Amplitude Squeezing in a Constant-Current-Driven Semiconductor Laser, Phys. Rev. Lett. 58, 1000 (1987).
  * [19] J. Bergou, L. Davidovitch, M. Orszag, C. Benkert, M. Hillery and M. Scully, Influence of the Pumping Statistics in Lasers and Masers, Opt. Commun. 72, 82 (1989).
  * [20] W. Richardson and R. Shelby, Nonclassical Light from a Semiconductor Laser Operating at 4K, Phys. Rev. Lett. 64, 400 (1990).
  * [21] D. Walls, M. Collett and A. Lane, Amplitude-Noise Reduction in Lasers with Intracavity Nonlinear Elements, Phys. Rev. A 42, 4366 (1990).
  * [22] H. M. Wiseman, and G. J. Milburn, Noise reduction in a laser by nonlinear damping, Phys. Rev. A 44, 7815 (1991).
  * [23] T. Ralph and C. Savage, Squeezed Light from Conventionally Pumped Multilevel Lasers, Opt. Lett. 16, 1113 (1991).
  * [24] T. Ralph and C. Savage, Squeezed Light a Coherently Pumped Four-Level Laser, Phys. Rev. A 44, 7809 (1991).
  * [25] Y. Yamamoto, S. Machida and W. Richardson, Photon Number Squeezed States in Semiconductor Lasers, Science 255, 1219 (1992).
  * [26] W. Choi, J. Lee, K. An, C. Fang-Yen, R. Dasari and M. Feld, Observation of Sub-Poissonian Photon Statistics in the Cavity-QED Microlaser, Phys. Rev. Lett. 96, 093603 (2006).
  * [27] M. Koppenhöfer, M. Marthaler, Creation of a Squeezed Photon Distribution using Artificial Atoms with Broken Inversion Symmetry, Phys. Rev. A 93, 023831 (2016).
  * [28] M. Koppenhöfer, J. Leppäkangas and M. Marthaler, Creating Photon-Number Squeezed Strong Microwave Fields by a Cooper-Pair Injection Laser, Phys. Rev. B 95, 134515 (2017).
  * [29] V. Canela and H. Carmichael, Bright Sub-Poissonian Light through Intrinsic Feedback and External Control, Phys. Rev. Lett. 124, 063604 (2020).
  * [30] M. Kolobov and I. Sokolov, Interference of Light Waves Possessing Sub-Poissonian Statistics and the Sensitivity of Laser Gravitational Observations, Zh. Eksp. Teor. Fiz 90, 1889 (1986).
  * [31] Y. Yamamoto and H. Haus, Preparation, Measurement and Information Capacity of Optical Quantum States, Rev. Mod. Phys. 58, 1001 (1986).
  * [32] E. Polzik, J. Carri and H. Kimble, Spectroscopy with Squeezed Light, Phys. Rev. Lett. 68, 3020 (1992).
  * [33] T. Ralph and H. Bachor, Noiseless Amplification of the Coherent Amplitude of Bright Squeezed Light using a Standard Laser Amplifier, Opt. Commun. 119, 301 (1995).
  * [34] L. Davidovitch, Sub-Poissonian processes in quantum optics, Rev. Mod. Phys. 68, 127 (1996).
  * [35] T. Golubeva, D. Ivanov and Y. Golubev, Broadband Squeezed Light from Phase-Locked Single-Mode Sub-Poissonian Lasers, Phys. Rev. A 77, 052316 (2008).
  * [36] D. F. Walls and G. J. Milburn, Quantum Optics (Springer, Berlin, Heidelberg 2008).
  * [37] S. Korolev, A. Dobrotvorskaia, T. Golubeva and Y. Golubev, Quantum Computations on the Ensemble of Two-Node Cluster States Obtained by Sub-Poissonian Lasers, Laser Phys. Lett. 16, 075204 (2019).
  * [38] J. Mork and K. Yvind, Squeezing of Intensity Noise in Nanolasers and NonoLEDs with Extreme Dielectric Confinement, Optica 7, 1641 (2020).
  * [39] A. Goldberg and A. Steinberg, Transcoherent States: Optical States for Maximal Generation of Atomic Coherence, PRX Quantum 1, 020306 (2020).
  * [40] N. Hosseinidehaj, M. Winnel and T. Ralph, Simple and Loss-Tolerant Free-Space Quantum Key Distribution using a Squeezed Laser, Phys. Rev. A 105, 032602 (2022).
  * [41] S. Zhao and F. Grillot, Modeling of Amplitude Squeezing in a Pump-Noise-Suppressed Interband Cascade Laser, IEEE Photon. J. 14, 1 (2022).
  * [42] J. Bergou, L. Davidovich, M. Orszag, C. Benkert, M. Hillery, and M. O. Scully, “Role of pumping statistics in maser and laser dynamics: Density-matrix approach”, Phys. Rev. A 40, 5073 (1989)
  * [43] C. Benkert, M. O. Scully, J. Bergou, L. Davidovich, M. Hillery, and M. Orszag, “Role of pumping statistics in laser dynamics: Quantum Langevin approach” Phys. Rev. A 41, 2756 (1990).
  * [44] H. Wiseman, Stochastic Quantum Dynamics of a Continuously Monitored Laser, Phys. Rev. A 47, 5180 (1993).
  * [45] T. Ralph, Squeezing from Lasers—Quantum Squeezing, edited by P. Drummond and Z. Ficek (Springer Berlin 2004), pp. 141-170.
  * [46] L. Mandel, Sub-poissonian photon statistics in resonance fluorescence, Opt. Lett. 4, 205 (1979).
  * [47] F. T. Arecchi, Measurement of the Statistical Distribution of Gaussian and Laser Sources, Phys. Rev. Lett. 15, 912 (1965).
  * [48] S. D. Bartlett, T. Rudolph, and R. W. Spekkens, Reference frames, superselection rules, and quantum information, Rev. Mod. Phys. 79, 555 (2007).
  * [49] R. Glauber, The Quantum Theory of Optical Coherence, Phys. Rev. 130, 2529 (1963).
  * [50] H. Wiseman and G. Milburn, Quantum Measurement and Control, Cambridge University Press (2009).
  * [51] A. Bandilla, H. Paul and H. Ritze, Realistic Quantum States of Light with Minimum Phase Uncertainty, Quantum Optics: Journal of the European Optical Society Part B 3, 267 (1991).
  * [52] S. N. Saadatmand, Finding the ground states of symmetric infinite dimensional Hamiltonians: explicit constrained optimizations of tensor networks, J. Phys.: Condens. Matter 32, 355901 (2020).
  * [53] F. Haake, S. Tan and D. Walls, Photon Noise Reduction in Lasers, Phys. Rev. A 40, 7121 (1989).
  * [54] C. Schön, E. Solano, F. Verstraete, I. Cirac and M. Wolf, Sequential generation of entangled multiqubit states, Phys. Rev. Lett. 95, 110503 (2005).
  * [55] C. Schön, K. Hammerer, M. Wolf, I. Cirac and E. Solano, Sequential generation of matrix-product states in cavity qed, Phys. Rev. A 75, 032311 (2007).


$g(x)^{-\frac{1}{2}}A^{\top}(Ag(x)^{-1}A^{\top})^{-1}Ag(x)^{-\frac{1}{2}}=g(x)^{-\frac{1}{2}}U_{r}(U_{r}^{\top}g(x)^{-1}U_{r})^{-1}U_{r}^{\top}g(x)^{-\frac{1}{2}}.$

Therefore,

$\displaystyle\overline{g}(y)^{-1}$
$\displaystyle=U_{k}^{\top}\left(g(x)^{-1}-g(x)^{-1}A^{\top}(Ag(x)^{-1}A^{\top})^{-1}Ag(x)^{-1}\right)U_{k}$
$\displaystyle=U_{k}^{\top}\left(g(x)^{-\frac{1}{2}}\left(I-g(x)^{-\frac{1}{2}}A^{\top}(Ag(x)^{-1}A^{\top})^{-1}Ag(x)^{-\frac{1}{2}}\right)g(x)^{-\frac{1}{2}}\right)U_{k}$
$\displaystyle=U_{k}^{\top}\left(g(x)^{-\frac{1}{2}}(I-P(x))g(x)^{-\frac{1}{2}}\right)U_{k}$
$\displaystyle=U_{k}^{\top}W(x)U_{k}.$

∎

We can now view the ideal CRHMC with the metric $M(x)$ as the ideal RHMC with
the metric $\overline{g}$ on the $k$-dimensional manifold. Note that we have
to ensure that the local metric $\overline{g}$ is also induced by the Hessian
of a logarithmic barrier, in order to refer to results from it.

######  Lemma 17.

Let $\overline{A^{\prime}}=A^{\prime}U_{k}$ and $\psi(y)$ be the logarithmic
barrier of the $k$-dimensional polytope defined by
$\\{y\in\mathbb{R}^{k}:\overline{A^{\prime}}y\leq b^{\prime}\\}$. Then
$\nabla^{2}_{y}\psi(y)=\overline{g}(y)$.

###### Proof.

Observe that $\\{y\in\mathbb{R}^{k}:\overline{A^{\prime}}y\geq b^{\prime}\\}$
is the new representation of
$\mathbb{\mathcal{M}}=\\{x\in\mathbb{R}^{n}:A^{\prime}x\geq
b^{\prime},Ax=0\\}$ in the $y$-coordinate system. Due to
$\overline{A^{\prime}}y=Ax$, we have
$S_{x}=\mathrm{Diag}(A^{\prime}x-b^{\prime})=\mathrm{Diag}(\overline{A^{\prime}}y-b)=S_{y}$.
For the logarithmic barrier $\phi(x)$ of
$\\{x\in\mathbb{R}^{n}:A^{\prime}x\geq b\\}$, direct computation results in

$\displaystyle\nabla^{2}_{y}\psi(y)$
$\displaystyle=\overline{A^{\prime}}^{\top}S_{y}^{-2}\overline{A^{\prime}}=U_{k}^{\top}A^{\prime\top}S_{x}^{-2}A^{\prime}U_{k}=U_{k}^{\top}\nabla^{2}_{x}\phi(x)U_{k}$
$\displaystyle=U_{k}^{\top}g(x)U_{k}=\overline{g}(y),$

where we used $\nabla_{x}^{2}\phi(x)=A^{\prime\top}S_{x}^{-2}A^{\prime}$ in
the third equality and Lemma 16 in the last equality. ∎

Most importantly, we prove that this ideal RHMC on the $k$-dimensional
manifold with the metric $\overline{g}(y)$ is equivalent to the ideal CRHMC
with the metric $M(x)$.

######  Lemma 18.

The dynamics $(x,v)$ and $(y,u)$ of the ideal CRHMC in $\mathbb{R}^{n}$ and
the ideal RHMC in $\mathbb{R}^{k}$ are equivalent in a sense that the
Hamiltonian equations for $(x,v)$ can be obtained by lifting up the
Hamiltonian equations for $(y,u)$ from $\mathbb{R}^{k}$ to $\mathbb{R}^{n}$
via multiplying $U_{k}$. That is, when we lift up the dynamics $(y,u)$ in
$\mathbb{R}^{k}$ to the dynamics $(\overline{x},\overline{v})$ in
$\mathbb{R}^{n}$ defined by $\overline{x}=U_{k}y$ and $\overline{v}=U_{k}u$,
it follows that

$\displaystyle\frac{dx}{dt}=\frac{d\overline{x}}{dt},\,\frac{dv}{dt}=\frac{d\overline{v}}{dt}\text{
and }v,\overline{v}\sim\mathcal{N}(0,M(x)).$

###### Proof.

We first recall from the proof of Lemma 4 that the Hamiltonian equations of
$(x,v)$ are

$\displaystyle\frac{dx}{dt}$ $\displaystyle=W(x)v,$
$\displaystyle\frac{dv}{dt}$
$\displaystyle=-\nabla_{x}f(x)-\frac{1}{2}\mathrm{Tr}\left[W(x)Dg(x)\right]+\frac{1}{2}Dg(x)\left[\frac{dx}{dt},\frac{dx}{dt}\right]-A^{\top}\lambda(x,v)$
$\displaystyle=-\nabla_{x}f(x)-\frac{1}{2}\mathrm{Tr}\left[W(x)Dg(x)\right]+\frac{1}{2}Dg(x)\left[\frac{dx}{dt},\frac{dx}{dt}\right]$
$\displaystyle\leavevmode\nobreak\
-A^{\top}\left(AA^{\top}\right)^{-1}A\left(-\nabla_{x}f(x)-\frac{1}{2}\mathrm{Tr}\left[W(x)Dg(x)\right]+\frac{1}{2}Dg(x)\left[\frac{dx}{dt},\frac{dx}{dt}\right]\right)$
$\displaystyle=(I-A^{\top}\left(AA^{\top}\right)^{-1}A)\left(-\nabla_{x}f(x)-\frac{1}{2}\mathrm{Tr}\left[W(x)Dg(x)\right]+\frac{1}{2}Dg(x)\left[\frac{dx}{dt},\frac{dx}{dt}\right]\right)$
$\displaystyle=U_{k}U_{k}^{\top}\left(-\nabla_{x}f(x)-\frac{1}{2}\mathrm{Tr}\left[W(x)Dg(x)\right]+\frac{1}{2}Dg(x)\left[\frac{dx}{dt},\frac{dx}{dt}\right]\right),$

where the last equality follows from that $U_{k}U_{k}^{\top}$ is the
orthogonal projection to the null space of $A$.

From Lemma 7 of [31], the Hamiltonian equations of $(y,u)$ are

$\displaystyle\frac{dy}{dt}$ $\displaystyle=\overline{g}(y)^{-1}u,$
$\displaystyle\frac{du}{dt}$
$\displaystyle=-\nabla_{y}f(U_{k}y)-\frac{1}{2}\mathrm{Tr}\left[\overline{g}(y)^{-1}D\overline{g}(y)\right]+\frac{1}{2}D\overline{g}(y)\left[\frac{dy}{dt},\frac{dy}{dt}\right].$

From the definitions of $(\overline{x},\overline{v})$, we have

$\displaystyle\frac{d\overline{x}}{dt}$
$\displaystyle=U_{k}\overline{g}(y)^{-1}u=U_{k}U_{k}^{\top}W(\overline{x})U_{k}u=U_{k}U_{k}^{\top}W(\overline{x})\overline{v}$
$\displaystyle\underset{(*)}{=}W(\overline{x})\overline{v},$
$\displaystyle\frac{d\overline{v}}{dt}$
$\displaystyle=U_{k}\left(-\nabla_{y}f(U_{k}y)-\frac{1}{2}\mathrm{Tr}\left[\overline{g}(y)^{-1}D\overline{g}(y)\right]+\frac{1}{2}D\overline{g}(y)\left[\frac{dy}{dt},\frac{dy}{dt}\right]\right),$

where $(*)$ follows from that $W(x)\overline{v}$ is already in the constrained
space (i.e., the null space of $A$). Let us examine each term in
$d\overline{v}/dt$ separately.

$\displaystyle\nabla_{y}f(U_{k}y)$
$\displaystyle=U_{k}^{\top}\nabla_{\overline{x}}f(\overline{x}),$
$\displaystyle\mathrm{Tr}\left[\overline{g}(y)^{-1}D_{y}\overline{g}(y)\right]$
$\displaystyle=\mathrm{Tr}\left[U_{k}^{\top}W(\overline{x})U_{k}\cdot
D_{y}\left(U_{k}^{\top}g(U_{k}y)U_{k}\right)\right]$
$\displaystyle=\mathrm{Tr}\left[U_{k}U_{k}^{\top}W(\overline{x})U_{k}U_{k}^{\top}(U_{k}^{\top}D_{\overline{x}}g(\overline{x}))\right]$
$\displaystyle=\mathrm{Tr}\left[W(\overline{x})U_{k}U_{k}^{\top}(U_{k}^{\top}D_{\overline{x}}g(\overline{x}))\right]$
$\displaystyle=\mathrm{Tr}\left[(U_{k}U_{k}^{\top}W(\overline{x}))^{\top}(U_{k}^{\top}D_{\overline{x}}g(\overline{x}))\right]$
$\displaystyle=\mathrm{Tr}\left[W(\overline{x})(U_{k}^{\top}D_{\overline{x}}g(\overline{x}))\right]$
$\displaystyle=U_{k}^{\top}\mathrm{Tr}\left[W(\overline{x})D_{\overline{x}}g(\overline{x})\right],$
$\displaystyle D_{y}\overline{g}(y)\left[\frac{dy}{dt},\frac{dy}{dt}\right]$
$\displaystyle=U_{k}^{\top}(U_{k}^{\top}D_{\overline{x}}g(\overline{x}))U_{k}\left[\frac{dy}{dt},\frac{dy}{dt}\right]$
$\displaystyle=\left(\overline{v}^{\top}W(\overline{x})U_{k}\right)U_{k}^{\top}(U_{k}^{\top}D_{\overline{x}}g(\overline{x}))U_{k}\left(U_{k}^{\top}W(\overline{x})\overline{v}\right)$
$\displaystyle=\overline{v}^{\top}W(\overline{x})(U_{k}^{\top}D_{\overline{x}}g(\overline{x}))W(\overline{x})\overline{v}$
$\displaystyle=U_{k}^{\top}D_{\overline{x}}g(\overline{x})\left[\frac{d\overline{x}}{dt},\frac{d\overline{x}}{dt}\right].$

Putting all these together, the Hamiltonian equations of
$(\overline{x},\overline{v})$ can be written as

$\displaystyle\frac{d\overline{x}}{dt}$
$\displaystyle=W(\overline{x})\overline{v},$
$\displaystyle\frac{d\overline{v}}{dt}$
$\displaystyle=U_{k}U_{k}^{\top}\left(-\nabla
f(\overline{x})-\frac{1}{2}\mathrm{Tr}\left[W(\overline{x})Dg(\overline{x})\right]+\frac{1}{2}Dg(\overline{x})\left[\frac{d\overline{x}}{dt},\frac{d\overline{x}}{dt}\right]\right).$

Therefore, the Hamiltonian equations of $(x,v)$ and
$(\overline{x},\overline{v})$ are exactly the same. In addition,
$\overline{v}=U_{k}u$ leads to
$\overline{v}\sim\mathcal{N}(0,U_{k}\overline{g}(y)U_{k}^{\top})=\mathcal{N}(0,M(x))$.
∎

Using these three lemmas, we conclude that the dynamics of the ideal CRHMC on
the constrained space is equivalent to that of the ideal RHMC on the
corresponding $k$-dimensional polytope. Therefore, Theorem 14 immediately
follows from Corollary 3 in [28].

######  Corollary.

Let $\pi$ be a target distribution on a polytope with $m$ constraints in
$\mathbb{R}^{n}$ such that $\frac{d\pi}{dx}\sim e^{-\alpha^{\top}x}$ for
$\alpha\in\mathbb{R}^{n}$. Let $\mathbb{\mathcal{M}}$ be the Hessian manifold
of the polytope induced by the logarithmic barrier of the polytope. Let
$\Lambda=\sup_{S\subset\mathbb{\mathcal{M}}}\frac{\pi_{0}(S)}{\pi(S)}$ be the
warmness of the initial distribution $\pi_{0}$. Let $\pi_{T}$ be the
distribution obtained after $T$ iterations of the ideal RHMC on
$\mathbb{\mathcal{M}}$. For any $\varepsilon>0$ and step size
$h=O\left(\frac{1}{n^{7/12}\log^{1/2}\frac{\Lambda}{\varepsilon}}\right)$,
there exists $T=O\left(mn^{7/6}\log^{2}\frac{\Lambda}{\varepsilon}\right)$
such that $\left\|\pi_{T}-\pi\right\|_{TV}\leq\varepsilon$.

###  D.2 Convergence rate of discretized CRHMC

We attempt to demonstrate a similar reduction of the discretized CRHMC.
However, it is trickier than that of the ideal RHMC, since Algorithm 2 uses
the simplified Hamiltonian, which omits the Lagrangian term
$c(x)^{\top}\lambda(x,v)$, in place of the full Hamiltonian.

We look into the reduction in two steps. First of all, we show in Section
D.2.1 that the dynamics of $x$ is the same under the discretized CRHMC via IMM
with the simplified Hamiltonian, and the discretized CRHMC via IMM with the
full Hamiltonian, and that the acceptance probabilities are the same as well.
Next in Section D.2.2, we show a correspondence between the discretized CRHMC
via IMM and the discretized RHMC via IMM, just as we did for the ideal case in
Section D.1.

####  D.2.1 Simplified Hamiltonian and full Hamiltonian in constrained space

We recall that the simplified Hamiltonian $\overline{H}(x,v)$ is the sum of
two parts defined by

$\displaystyle\overline{H}_{1}(x,v)$
$\displaystyle=f(x)+\frac{1}{2}\log\mathrm{pdet}M(x)$
$\displaystyle=f(x)+\frac{1}{2}\left(\log\det g(x)+\log\det
Ag(x)^{-1}A^{\top}-\log\det AA^{\top}\right),$
$\displaystyle\overline{H}_{2}(x,v)$ $\displaystyle=\frac{1}{2}v^{\top}W(x)v.$

The full Hamiltonian $H(x,v)$ with the Lagrangian term
$c(x)^{\top}\lambda(x,v)$ can be also written as the sum of two parts defined
by

$\displaystyle H_{1}(x,v)$ $\displaystyle=f(x)+\frac{1}{2}\left(\log\det
g(x)+\log\det Ag(x)^{-1}A^{\top}-\log\det AA^{\top}\right)$
$\displaystyle\quad-x^{\top}A^{\top}(AA^{\top})^{-1}A\left(\nabla
f(x)+\frac{1}{2}\mathrm{Tr}\left[W(x)Dg(x)\right]\right),$ $\displaystyle
H_{2}(x,v)$
$\displaystyle=\frac{1}{2}v^{\top}W(x)v+\frac{1}{2}x^{\top}A^{\top}(AA^{\top})^{-1}ADg(x)\left[\frac{dx}{dt},\frac{dx}{dt}\right],$

and IMM with this Hamiltonian is implemented as in (C.1). We note from the
proof of Lemma 18 that

$\displaystyle\frac{\partial H_{1}}{\partial
x}(x,v)=U_{k}U_{k}^{\top}\frac{\partial\overline{H}_{1}}{\partial x}(x,v),$
$\displaystyle\frac{\partial H_{2}}{\partial
x}(x,v)=U_{k}U_{k}^{\top}\frac{\partial\overline{H}_{2}}{\partial x}(x,v),$
$\displaystyle\frac{\partial H_{2}}{\partial
v}(x,v)=U_{k}U_{k}^{\top}\frac{\partial\overline{H}_{2}}{\partial v}(x,v).$

######  Lemma 19.

For step size $h$, let $(\overline{x},\overline{v})$ and $(x,v)$ be the
outputs of IMM with the simplified Hamiltonian and with the full Hamiltonian
starting from $(x_{0},v_{0})$, respectively. Then $\overline{x}=x$, and
$\frac{e^{-\overline{H}(\overline{x},\overline{v})}}{e^{-\overline{H}(x_{0},v_{0})}}=\frac{e^{-H(x,v)}}{e^{-H(x_{0},v_{0})}}$.

###### Proof.

We use $x_{\frac{1}{3}}(=x_{0}),x_{\frac{2}{3}}(=x)$ and
$v_{\frac{1}{3}},v_{\frac{2}{3}},v$ to denote the points obtained during one
step of IMM with the full Hamiltonian. We similarly define $\overline{x}_{i}$
and $\overline{v}_{i}$ for $i=\frac{1}{3},\frac{2}{3}$. As $(x_{0},v_{0})$ is
a starting point, $U_{k}U_{k}^{\top}x_{0}=x_{0}$ and
$U_{k}U_{k}^{\top}v_{0}=v_{0}$. Due to $\mathrm{Null}(W(x))=\text{row}(A)$, we
have that $W(z)U_{k}U_{k}^{\top}w=W(z)w$. By comparing the first step of IMM
for each Hamiltonian,

$U_{k}U_{k}^{\top}\overline{v}_{\frac{1}{3}}=v_{0}-\frac{h}{2}U_{k}U_{k}^{\top}\frac{\partial\overline{H}_{1}}{\partial
x}(x_{0},v_{0})=v_{0}-\frac{h}{2}\frac{\partial H_{1}}{\partial
x}(x_{0},v_{0})=v_{\frac{1}{3}},$

and thus $U_{k}U_{k}^{\top}\overline{v}_{\frac{1}{3}}=v_{\frac{1}{3}}$.

From the second step of IMM, $\overline{x}_{\frac{2}{3}}$ is already in the
null space of $A$. For
$x_{\frac{1}{3}}=\overline{x}_{\frac{1}{3}}=x_{0},\overline{x}_{\text{mid}}=(\overline{x}_{\frac{1}{3}}+\overline{x}_{\frac{2}{3}})/2$
and
$\overline{v}_{\text{mid}}=(\overline{v}_{\frac{1}{3}}+\overline{v}_{\frac{2}{3}})/2$,
the second step of IMM with the simplified Hamiltonian is

$\displaystyle\overline{x}_{\frac{2}{3}}$
$\displaystyle=x_{\frac{1}{3}}+hU_{k}U_{k}^{\top}\frac{\partial\overline{H}_{2}}{\partial
v}(\overline{x}_{\text{mid}},\overline{v}_{\text{mid}})=x_{\frac{1}{3}}+hU_{k}U_{k}^{\top}W(\overline{x}_{\text{mid}})\overline{v}_{\text{mid}}$
$\displaystyle=x_{\frac{1}{3}}+hU_{k}U_{k}^{\top}W(\overline{x}_{\text{mid}})U_{k}U_{k}^{\top}\overline{v}_{\text{mid}}=x_{\frac{1}{3}}+hU_{k}U_{k}^{\top}\frac{\partial\overline{H}_{2}}{\partial
v}(\overline{x}_{\text{mid}},U_{k}U_{k}^{\top}\overline{v}_{\text{mid}})$
$\displaystyle=x_{\frac{1}{3}}+h\frac{\partial H_{2}}{\partial
v}(\overline{x}_{\text{mid}},U_{k}U_{k}^{\top}\overline{v}_{\text{mid}}),$
$\displaystyle U_{k}U_{k}^{\top}\overline{v}_{\frac{2}{3}}$
$\displaystyle=v_{\frac{1}{3}}+hU_{k}U_{k}^{\top}\frac{\partial\overline{H}_{2}}{\partial
x}(\overline{x}_{\text{mid}},\overline{v}_{\text{mid}})$
$\displaystyle=v_{\frac{1}{3}}+hU_{k}U_{k}^{\top}\left(-\frac{1}{2}Dg(\overline{x}_{\text{mid}})\left[W(\overline{x}_{\text{mid}})\overline{v}_{\text{mid}},W(\overline{x}_{\text{mid}})\overline{v}_{\text{mid}}\right]\right)$
$\displaystyle=v_{\frac{1}{3}}+hU_{k}U_{k}^{\top}\left(-\frac{1}{2}Dg(\overline{x}_{\text{mid}})\left[W(\overline{x}_{\text{mid}})U_{k}U_{k}^{\top}\overline{v}_{\text{mid}},W(\overline{x}_{\text{mid}})U_{k}U_{k}^{\top}\overline{v}_{\text{mid}}\right]\right)$
$\displaystyle=v_{\frac{1}{3}}+hU_{k}U_{k}^{\top}\frac{\partial\overline{H}_{2}}{\partial
x}(\overline{x}_{\text{mid}},U_{k}U_{k}^{\top}\overline{v}_{\text{mid}})$
$\displaystyle=v_{\frac{1}{3}}+h\frac{\partial H_{2}}{\partial
x}(\overline{x}_{\text{mid}},U_{k}U_{k}^{\top}\overline{v}_{\text{mid}}).$

Note that
$U_{k}U_{k}^{\top}\overline{v}_{\text{mid}}=(U_{k}U_{k}^{\top}\overline{v}_{\frac{2}{3}}+v_{\frac{1}{3}})/2$
and
$\overline{x}_{\text{mid}}=(\overline{x}_{\frac{2}{3}}+x_{\frac{1}{3}})/2$.
Since the solution of this second step is characterized as a unique fixed-
point, it follows that
$(\overline{x}_{\frac{2}{3}},U_{k}U_{k}^{\top}\overline{v}_{\frac{2}{3}})=(x_{\frac{2}{3}},v_{\frac{2}{3}})$
and so $\overline{x}=x$. In the same way we analyzed
$\overline{v}_{\frac{2}{3}}$, we can obtain that
$U_{k}U_{k}^{\top}\overline{v}=v$.

We now compare the acceptance probabilities. We clearly have
$\overline{H}(x_{0},v_{0})=H(x_{0},v_{0})$ due to $c(x_{0})=0$ and have
$\overline{H}_{1}(\overline{x},\overline{v})=H_{1}(x,v)$ due to
$\overline{x}=x$. For $\overline{H}_{2}$,

$\displaystyle\overline{v}^{\top}W(\overline{x})\overline{v}=\overline{v}^{\top}U_{k}U_{k}^{\top}W(x)U_{k}U_{k}^{\top}\overline{v}=v^{\top}W(x)v,$

and so $\overline{H}_{2}(\overline{x},\overline{v})=H_{2}(x,v)$. ∎

####  D.2.2 CRHMC and RHMC discretized by IMM

In this section, we show that there is a correspondence between the dynamics
of CRHMC discretized by IMM and that of RHMC discretized by IMM.

######  Lemma 20.

The discretized CRHMC via IMM in $\mathbb{R}^{n}$ and the discretized RHMC via
IMM in $\mathbb{R}^{k}$ are equivalent. That is, the output $(x_{1},v_{1})$
given by the discretized CRHMC starting from $(x,v)$ is the same with
$(U_{k}y_{1},U_{k}u_{1})$, where $(y_{1},u_{1})$ is the output of the
discretized RHMC starting from $(y,u)$ satisfying $(x,v)=(U_{k}y,U_{k}u)$.
Moreover, the acceptance probabilities are the same due to

$\frac{e^{-H^{c}(x_{1},v_{1})}}{e^{-H^{c}(x,v)}}=\frac{e^{-H^{r}(y_{1},u_{1})}}{e^{-H^{r}(y,u)}},$

where $H^{c}(x,v)$ and $H^{r}(y,u)$ are the Hamiltonians of CRHMC and RHMC
respectively.

###### Proof.

We first recall that $H^{c}(x,v)$ can be rewritten as the sum of two parts
defined by

$\displaystyle H^{c}_{1}(x,v)$
$\displaystyle=f(x)+\frac{1}{2}\log\mathrm{pdet}M(x)$
$\displaystyle\quad-x^{\top}A^{\top}(AA^{\top})^{-1}A\left(\nabla
f(x)+\frac{1}{2}\mathrm{Tr}\left[W(x)Dg(x)\right]\right),$ $\displaystyle
H^{c}_{2}(x,v)$
$\displaystyle=\frac{1}{2}v^{\top}W(x)v+\frac{1}{2}x^{\top}A^{\top}(AA^{\top})^{-1}ADg(x)\left[\frac{dx}{dt},\frac{dx}{dt}\right].$

Similarly for $H^{r}$, we can represent it by the sum of two parts defined by

$\displaystyle H^{r}_{1}(y,u)$
$\displaystyle=f(U_{k}y)+\frac{1}{2}\log\det\overline{g}(y),$ $\displaystyle
H^{r}_{2}(y,u)$ $\displaystyle=\frac{1}{2}u^{\top}\overline{g}(y)^{-1}u.$

For the first claim, we need to show that each step of IMM for RHMC and CRHMC
is equivalent, thus it suffices to check that for any
$(y,u)\in\mathbb{R}^{k}\times\mathbb{R}^{k}$

$\displaystyle\frac{\partial H^{c}_{1}(U_{k}y,U_{k}u)}{\partial x}$
$\displaystyle=U_{k}\frac{\partial H^{r}_{1}(y,u)}{\partial y},$
$\displaystyle\frac{\partial H^{c}_{2}(U_{k}y,U_{k}u)}{\partial x}$
$\displaystyle=U_{k}\frac{\partial H^{r}_{2}(y,u)}{\partial y},$
$\displaystyle\frac{\partial H^{c}_{2}(U_{k}y,U_{k}u)}{\partial v}$
$\displaystyle=U_{k}\frac{\partial H^{r}_{2}(y,u)}{\partial u}.$

These computations were already checked in the proof of Lemma 18.

For the second claim, we note that the Lagrangian term vanishes due to
$c(x)=c(U_{k}y)=0$. Then the second claim follows from

$\displaystyle\log\det\overline{g}(y^{\prime})$ $\displaystyle=\log\det
U_{k}^{\top}M(U_{k}y^{\prime})U_{k}\quad(\text{Lemma\leavevmode\nobreak\
\ref{lem:bg_relationship}})$
$\displaystyle=\log\mathrm{pdet}M(U_{k}y^{\prime}),$ $\displaystyle
u^{\prime\top}\overline{g}(y^{\prime})^{-1}u^{\prime}$
$\displaystyle=u^{\prime\top}U_{k}^{\top}W(U_{k}y^{\prime})U_{k}u^{\prime}.\quad(\text{Lemma\leavevmode\nobreak\
\ref{lem:bg_relationship}})$

∎

The previous two lemmas imply that the dynamics of the discretized CRHMC via
IMM on the constrained space is equivalent to that of the discretized RHMC via
IMM on the corresponding k-dimensional polytope. Therefore, Theorem 15 follows
from Corollary 4 in [28].

######  Corollary.

Let $\pi$ be a target distribution on a polytope with $m$ constraints in
$\mathbb{R}^{n}$ such that $\frac{d\pi}{dx}\sim e^{-\alpha^{\top}x}$ for
$\alpha\in\mathbb{R}^{n}$. Let $\mathcal{M}$ be the Hessian manifold of the
polytope induced by the logarithmic barrier of the polytope. Let
$\Lambda=\sup_{S\subset\mathcal{M}}\frac{\pi_{0}(S)}{\pi(S)}$ be the warmness
of the initial distribution $\pi_{0}$. Let $\pi_{T}$ be the distribution
obtained after $T$ iterations of RHMC discretized by IMM on $\mathcal{M}$. For
any $\varepsilon>0$ and step size
$h=O\left(\frac{1}{n^{3/2}\log\frac{\Lambda}{\varepsilon}}\right)$, there
exists $T=O\left(mn^{3}\log^{3}\frac{\Lambda}{\varepsilon}\right)$ such that
$\left\|\pi_{T}-\pi\right\|_{TV}\leq\varepsilon$.

##  Appendix E Missing Notations and Definitions

###  E.1 Notations

  * •

We use $\mathcal{N}(\mu,\Sigma)$ to denote Gaussian distribution with mean
$\mu$ and covariance $\Sigma$.

  * •

We use $\text{Null}(A)$ and $\mathrm{Range}(A)$ to denote the null space and
image space of a matrix or linear operator $A$.

  * •

We use $\nabla^{2}f\in\mathbb{R}^{n\times n}$ to denote the Hessian of a
function $f:\mathbb{R}^{n}\to\mathbb{R}$.

  * •

We use $\left\|\cdot\right\|$ to denote $\ell_{2}$-norm unless specified
otherwise, and define $\left\|x\right\|_{A}:=\sqrt{x^{\top}Ax}$ for a vector
$x\in\mathbb{R}^{n}$ and a matrix $A\in\mathbb{R}^{n\times n}$.

  * •

We use $\partial K$ to denote the boundary of the set $K$.

  * •

For a matrix $g(x)$ with $x\in\mathbb{R}^{n}$, we use $Dg(x)$ to denote the
derivative of $g(x)$ with respect to $x$. This can be thought of as the
$n\times n\times n$ tensor such that
$(Dg(x))(i,j,k)=\frac{\partial(g(x))_{ij}}{\partial x_{k}}$. In other words,
$(Dg(x))(\cdot,\cdot,k)$ is the matrix, each of entries is the derivative of
$g(x)$ with respect to $x_{k}$. In addition, for a vector
$v\in\mathbb{R}^{n}$, $Dg(x)[v,v]$ is a vector in $\mathbb{R}^{n}$ such that
$(Dg(x)[v,v])_{i}=v^{\top}Dg(x)(\cdot,\cdot,i)v$.

  * •

For a matrix $A$ of size $n\times n$, we use $A\cdot Dg(x)$ to denote a
$n\times n\times n$ tensor such that $(A\cdot
Dg(x))(\cdot,\cdot,i)=A\cdot(Dg(x))(\cdot,\cdot,i)$. We use
$\mathrm{Tr}(A\cdot Dg(x))$ to denote a vector in $\mathbb{R}^{n}$ such that
$(\mathrm{Tr}(A\cdot Dg(x)))_{i}=\mathrm{Tr}((A\cdot Dg(x))(\cdot,\cdot,i))$.

###  E.2 Definitions

##### Convex body.

A convex body is a compact and convex set.

##### Isotropy.

A random variable $X$ is said to be in isotropic position if $\mathbb{E}X=0$
and $\mathbb{E}XX^{\top}=I$.

##### Pseudo-inverse.

For a matrix $A\in\mathbb{R}^{m\times n}$, it is well known that there always
exists the unique pseudo-inverse matrix $A^{\dagger}$ that satisfies the
following conditions:

  1. 1.

$A^{\dagger}AA^{\dagger}=A^{\dagger}$.

  2. 2.

$AA^{\dagger}A=A$.

  3. 3.

$AA^{\dagger}$ and $A^{\dagger}A$ are symmetric.

It is also well known that
$\mathrm{Null}(A^{\dagger})=\mathrm{Null}(A^{\top})$ and
$\mathrm{Range}(A^{\dagger})=\mathrm{Range}(A^{\top})$.

##### Pseudo-determinant.

For a square matrix $A$, its pseudo-determinant $\mathrm{pdet}(A)$ is defined
as the product of non-zero eigenvalues of $A$.

##### Leverage score.

For a matrix $A\in\mathbb{R}^{m\times n}$, the leverage score of the $i^{th}$
row is $(A(A^{\top}A)^{\dagger}A^{\top})_{ii}$ for $i\in[m]$. When $A$ is
full-rank, it is simply $(A(A^{\top}A)^{-1}A^{\top})_{ii}$.

##### Log-barrier & Dikin ellipsoid.

For a polytope $P=\\{x\in\mathbb{R}^{n}:Ax\leq b\\}$ where
$A\in\mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^{m}$, let us denote the
$i^{th}$ row of $A$ by $a_{i}$ and the $i^{th}$ row of $b$ by $b_{i}$. The
log-barrier of $P$ is defined by

$\phi(x)=-\sum_{i=1}^{m}\log(b_{i}-a_{i}^{\top}x).$

For $x\in P$, the Dikin ellipsoid at $x$ is defined by
$D(x):=\\{y\in\mathbb{R}^{n}:(y-x)^{\top}\nabla^{2}\phi(x)(y-x)\leq 1\\}$. The
Dikin ellipsoid is always contained in $P$.

##### Analytic center.

The analytic center $x_{ac}$ of the polytope $P$ is the point minimizing the
log-barrier (i.e., $x_{ac}=\arg\min\phi(x)$).

##### Self-concordant function.

A function $f:\mathbb{R}^{n}\to\mathbb{R}$ is self-concordant if it satisfies
$\left|D^{3}f(x)[h,h,h]\right|\leq 2\left(D^{2}f(x)[h,h]\right)^{3/2}$ for all
$h\in\mathbb{R}^{n}$ and $x\in\mathbb{R}^{n}$.

##### Highly self-concordant function.

A barrier $\phi$ is called _highly self-concordant_ if it satisfies for all
$h\in\mathbb{R}^{d}$ and $x\in\mathbb{R}^{d}$

$\left|D^{3}\phi(x)[h,h,h]\right|\leq
2\left(D^{2}\phi(x)[h,h]\right)^{3/2}\quad\textrm{and}\quad\left|D^{4}\phi(x)[h,h,h,h]\right|\leq
6\left(D^{2}\phi(x)[h,h]\right)^{2}.$

##### Total variation.

For two probability distributions $P$ and $Q$ on support $K$, the total
variation distance of $P$ and $Q$ is

$\left\|P-Q\right\|_{\mathrm{TV}}\stackrel{{\scriptstyle\mathrm{{\scriptscriptstyle
def}}}}{{=}}\sup_{A\subseteq K}(P(A)-Q(A)).$

###  E.3 Details

##### Inverse and Determinant of block matrix.

For a square matrix $M=\left[\begin{array}[]{cc}A&B\\\ C&D\end{array}\right]$
with blocks $A,B,C,D$ of same size, if $D$ and $A-BD^{-1}C$ are invertible,
then its inverse and determinant can be computed by

$\displaystyle M^{-1}$
$\displaystyle=\left[\begin{array}[]{cc}(A-BD^{-1}C)^{-1}&-(A-BD^{-1}C)^{-1}BD^{-1}\\\
-D^{-1}C(A-BD^{-1}C)^{-1}&D^{-1}+D^{-1}C(A-BD^{-1}C)^{-1}BD^{-1}\end{array}\right],$
$\displaystyle\det(M)$ $\displaystyle=\det(D)\det(A-BD^{-1}C).$

##### Orthogonal projection.

Let $S=\\{x\in\mathbb{R}^{n}:Ax=b\\}$ for $A\in\mathbb{R}^{m\times n}$ and
$b\in\mathbb{R}^{m}$, and $x_{0}$ be a point in $S$. Thus $S-x_{0}$ is the
null space of $A$, due to $A(x-x_{0})=0$. The orthogonal projection $P$ to
this null space is

$P=I-A^{\top}(AA^{\top})^{-1}A.$

Note that the range of $P$ always lies in the null space because

$A(Pv)=A(I-A^{\top}(AA^{\top})^{-1}A)v=Av-AA^{\top}(AA^{\top})^{-1}Av=Av-
Av=0.$

$I-P$ is also an orthogonal projection matrix, and eigenvalues of orthogonal
projection matrices are either $0$ or $1$.

##### Matrix calculus.

Let $U(x)$ be a $n\times n$ matrix with a parameter $x\in\mathbb{R}^{n}$.

$\frac{\partial U^{-1}(x)}{\partial x_{i}}=-U(x)\frac{\partial U(x)}{\partial
x_{i}}U(x).$

Hence using the notation $Dg$, we can write in a more compact way as

$DU^{-1}(x)=-U(x)DU(x)U(x).$

For $\log\det$,

$\frac{\partial\log\det U(x)}{\partial
x_{i}}=\mathrm{Tr}\left(U^{-1}(x)\frac{\partial U(x)}{\partial x_{i}}\right).$

In other words,

$D(\log\det U(x))=\mathrm{Tr}(U^{-1}(x)DU(x)).$

##### Cholesky decomposition.

For a symmetric positive definite matrix $A$, there exists a lower triangular
matrix $L$ such that $LL^{\top}=A$.

##### Newton’s method.

For $f$ convex and twice differentiable in $\mathbb{R}^{n}$, consider an
unconstrained convex optimization $\min_{x}f(x)$. Given a starting point
$x_{0}\in\mathbb{R}^{n}$, the Newton’s method repeats

$x_{i}=x_{i-1}-(\nabla^{2}f(x_{i-1}))^{-1}\nabla f(x_{i-1})\quad\forall
i\in\mathbb{N}$

to solve the optimization problem.