Discovery of new compounds from wide chemical space is attractive for materials researchers. However, theoretical prediction and validation experiments have not been systematically integrated. Here, we demonstrate that a new combined approach is powerful in significantly accelerating the discovery rate of new compounds, which should be useful for exploration of a wide chemical space in general. A recommender system for chemically relevant composition is constructed by machine learning of Inorganic Crystal Structure Database using chemical compositional descriptors. Synthesis and identification experiments are made at the chemical compositions with high recommendation scores by the single-particle diagnosis method. Two new compounds, La4Si3AlN9 and La26Si41N80O, and two new variants (isomorphic substitutions) of known compounds, La7Si6N15 and La4Si5N10O, are successfully discovered. Finally, density functional theory calculations are conducted for La4Si3AlN9 to confirm the energetic and dynamical stability and to reveal its atomic arrangement.