Identifying a potentially large number of simultaneous line outages in power transmission networks in real time is a computationally hard problem. This is because the number of hypotheses grows exponentially with the network size. A new "Learning-to-Infer" method is developed for efficient inference of every line status in the network. Optimizing the line outage detector is transformed to and solved as a discriminative learning problem based on Monte Carlo samples generated with power flow simulations. A major advantage of the developed Learning-to-Infer method is that the labeled data used for training can be generated in an arbitrarily large amount rapidly and at very little cost. As a result, the power of offline training is fully exploited to learn very complex classifiers for effective real-time multi-line outage identification. The proposed methods are evaluated in the IEEE 30, 118 and 300 bus systems. Excellent performance in identifying multi-line outages in real time is achieved with a reasonably small amount of data.