This paper considers the problem of estimating the information leakage of a\nsystem in the black-box scenario. It is assumed that the system's internals are\nunknown to the learner, or anyway too complicated to analyze, and the only\navailable information are pairs of input-output data samples, possibly obtained\nby submitting queries to the system or provided by a third party. Previous\nresearch has mainly focused on counting the frequencies to estimate the\ninput-output conditional probabilities (referred to as frequentist approach),\nhowever this method is not accurate when the domain of possible outputs is\nlarge. To overcome this difficulty, the estimation of the Bayes error of the\nideal classifier was recently investigated using Machine Learning (ML) models\nand it has been shown to be more accurate thanks to the ability of those models\nto learn the input-output correspondence. However, the Bayes vulnerability is\nonly suitable to describe one-try attacks. A more general and flexible measure\nof leakage is the g-vulnerability, which encompasses several different types of\nadversaries, with different goals and capabilities. In this paper, we propose a\nnovel approach to perform black-box estimation of the g-vulnerability using ML.\nA feature of our approach is that it does not require to estimate the\nconditional probabilities, and that it is suitable for a large class of ML\nalgorithms. First, we formally show the learnability for all data\ndistributions. Then, we evaluate the performance via various experiments using\nk-Nearest Neighbors and Neural Networks. Our results outperform the frequentist\napproach when the observables domain is large.\n