Samir M. Perlaza | INRIA | Permanent Member of the Scientific Staff

Inria
2004, route des Lucioles BP 93, 06902 Sophia Antipolis Cedex
Équipe NEO, Bâtiment Lagrange, Office: L137
samir.perlaza@inria.fr

An Upper Bound on the Error Induced by Saddlepoint Approximations—Applications to Wireless Communications

• Dates:

  • March 8, 2023. Workshop on “Performance Guarantees in Wireless Networks”. Laboratory for Information, Networking and Communication Sciences (LINCS), Palaiseau, France. Host: Prof. Francois Baccelli and Prof. Jean-Marie Gorce.

• Abstract
  In this talk, an upper bound on the absolute difference between: (a) the cumulative distribution function (CDF) of the sum of a finite number of independent and identically distributed random variables with finite absolute third moment; and (b) a saddlepoint approximation of such CDF is introduced. This upper bound, which is particularly precise in the regime of large deviations, is used to study the dependence testing (DT) bound and the meta converse (MC) bound on the decoding error probability (DEP) in point-to-point memoryless channels. Often, these bounds cannot be analytically calculated and thus lower and upper bounds become particularly useful. Within this context, the main results include, respectively, new upper and lower bounds on the DT and MC bounds. A numerical experimentation of these bounds is presented in the case of the binary symmetric channel, the additive white Gaussian noise channel, and the additive symmetric alpha-stable noise channel. The same type of result is also presented for the case of finite sums of real-valued independent and identically distributed random vectors. In such a case, the approximation error is upper bounded and thus, as a byproduct, an upper bound and a lower bound on the CDF of the sum are obtained.

• Slides are available in PDF.

• Video available here.

• References

  • Dadja Anade, Samir M. Perlaza, Jean-Marie Gorce, and Philippe Mary, ‘‘An upper bound on the error induced by saddlepoint approximations - Applications to information theory’’. Entropy, vol. 22, no. 6, 690, pp. 1-39, Jun., 2020.

  • Dadja Anade, Jean-Marie Gorce, and Philippe Mary, and Samir M. Perlaza, ‘‘Saddlepoint Approximations of Cumulative Distribution Functions of Sums of Random Vectors’’. Research Report, INRIA, No. RR-9388, Lyon, France, Feb., 2021..

Empirical Risk Minimization and Zero-Sum Games with Noisy Observations

• Dates:

  • December 12, 2022. Conservatoire national des arts et métiers (CNAM), Paris, France. Host: Prof. Stefano Secci.

  • November 9, 2022. Industrial Engineering and Operations Research Department. Indian Institute of Technology at Bombay (IITB), Mumbai, India. Host: Prof. Manjesh Hanawal.

• Abstract
  This talk introduces a new formulation of zero-sum games (ZSG), which is particularly suited for studying the Empirical Risk Minimization (ERM) problem and ERM-based machine learning algorithms. More specifically, ZSG are studied under the following assumptions: (1) One of the players (the leader) publicly and irrevocably commits to choose its actions by sampling a given probability measure (strategy); (2) The leader announces its action, which is observed by its opponent (the follower) subject to noise; and (3) the follower chooses its strategy based on the knowledge of the leader's strategy and the noisy observation of the leader's action. Under these conditions, the equilibrium is shown to always exist and be often different from the Nash and Stackelberg equilibria in mixed strategies and pure strategies. Even subject to noise, observing the actions of the leader is either beneficial or immaterial to the follower for all possible commitments. When the commitment is observed subject to a distortion, the equilibrium does not necessarily exist. Nonetheless, the leader might still obtain some benefit in some specific cases subject to equilibrium refinements. For instance, epsilon-equilibria might exist in which the leader commits to suboptimal strategies that allow unequivocally predicting the best response of its opponent. The optimal strategies for the leader at epsilon-equilibria are shown to be solutions to an ERM with relative entropy regularization (ERM-RER) problem.

• Slides are available in PDF.

• References

  • Ke Sun, and Samir M. Perlaza, and Alain Jean-Marie. ‘‘Zero-Sum Games with Noisy Observations’’. Preprint.

The Role of Relative Entropy in Supervised Machine Learning

• Dates

  • July 28, 2022 Electrical and Computer Engineering Department and Center for Statistics and Machine learning at Princeton University, Princeton NJ USA. Host: Prof. H. Vincent Poor

  • July 26, 2022 Electrical and Computer Engineering Department at Rensselaer Polytechnic Institute, Troy NY USA. Host: Prof. Ali Tajer.

  • July 6, 2022 Laboratoire Traitement et Communication de l'Information (LTCI), TelecomParis, Saclay, France. Host: Prof. Michèle Wigger.

• Abstract
  In this talk, recent results on various aspects of the Empirical Risk Minimization (ERM) problem with Relative Entropy Regularization (ERM-RER) are presented. The regularization is with respect to a sigma-finite measure, instead of a probability measure, which provides a larger flexibility for including prior knowledge on the models. Special cases of this general formulation include the ERM problem with (discrete or differential) entropy regularization and the information-risk minimization problem. Three results are discussed. First, it is shown that the empirical risk observed when models are sampled from the ERM-RER optimal probability measure is a sub-Gaussian random variable that exhibits a probably-approximately-correct (PAC) guarantee for the ERM problem. Second, the sensitivity of the expected empirical risk to deviations from the ERM-RER-optimal measure is characterized. Finally, using the notion of sensitivity, the impact of data aggregation on the generalization capabilities of machine learning algorithms based on the ERM-RER is studied. Interestingly, none of these results relies on statistical assumptions on the datasets, and thus, cases in which datasets exhibit different statistical properties can also be studied within this framework.
  

• Slides are available in PDF.

• References

  • Research Report, INRIA, No. RR-9454, Sophia Antipolis, France, Feb., 2022.
    ‘‘Empirical Risk Minimization with Generalized Relative Entropy Regularizations’’.

  • Research Report, INRIA, No. RR-9474, Sophia Antipolis, France, Jun., 2022.
    ‘‘Sensitivity of the Gibbs Algorithm to Data Aggregation in Supervised Machine Learning’’.