Abstract:  Quantifying dependence between high-dimensional random variables is central to statistical learning and inference. Two classical methods are canonical correlation analysis (CCA), which identifies maximally correlated projected versions of the original variables, and Shannon’s mutual information, which is a universal dependence measure that also captures higher-order dependencies. However, CCA only accounts for linear dependence, while mutual information is often infeasible to compute/estimate in high dimensions. We propose max-sliced mutual information (mSMI), which equals the maximal mutual information between low-dimensional projections of the high-dimensional variables and enjoys the best of both worlds: capturing intricate dependencies in the data while being amenable to fast computation and scalable estimation from samples. We show that mSMI retains favorable structural properties of Shannon’s mutual information and propose an efficiently computable neural estimator, which we couple with formal non-asymptotic error bounds. We present experiments that demonstrate the utility of mSMI for several contemporary learning tasks and draw connections to fundamental problems in statistics and information theory.