Learning from multi-label data in an interactive framework is a challenging problem as algorithms must withstand some additional constraints: in particular, learning from few training examples in a limited time. A recent study of multi-label classifier behaviors in this context has identified the potential of the ensemble method “Random Forest of Predictive Clustering Trees” (RF-PCT). However, RF-PCT has shown a degraded performance in terms of computation time for large feature spaces. To overcome this limit, this paper proposes a new hybrid multi-label learning approach IDSR-RF (Independent Dual Space Reduction with RF-PCT) which first reduces the data dimension and then learns a predictive regression model in the reduced spaces with RF-PCT. The feature and the label spaces are independently reduced using the fast matrix factorization algorithm Gravity. The experimental results on nine high-dimensional datasets show that IDSR-RF significantly reduces the computation time without deteriorating the learning performances. To the best of our knowledge, it is currently the most promising learning approach for an interactive multi-label learning system.