Minimal Learning Machine (MLM) is a distance-based supervised machine learning method for classification and regression problems. Its main advances are simple formulation and fast learning. Computing the MLM prediction in regression requires a solution to the optimization problem, which is determined by the input and output distance matrix mappings. In this paper, we propose to use the Newton method for solving this optimization problem in multi-output regression and compare the performance of this algorithm with the most popular Levenberg–Marquardt method. According to our knowledge, MLM has not been previously studied in the context of multi-output regression in the literature. In addition, we propose new initialization methods to speed up the local search of the second-order methods.