Se propone un método eficiente y robusto para problemas de regresión con salidas múltiples usando distancias y vecinos más próximos. Para ello se aprende una función de distancia en el espacio de entrada reformulándolo como un problema de optimización con margen máximo. En concreto, se aplica el método de descenso por gradiente estocástico al problema primal y se proponen diversas heurísticas para preservar una cierta relación de orden entre los valores de entrada y los de salida en entornos locales de los elementos del conjunto de entrenamiento. La experimentación sugiere que el método resultante es robusto y eficiente y podría ser extendido para ser aplicado sobre volúmenes de datos a gran escala en el contexto de BigData.