Predicción óptima distribuida en línea utilizando mini-lotes

Los métodos de predicción en línea se presentan típicamente como algoritmos seriales que se ejecutan en un único procesador. Sin embargo, en la era de los problemas de predicción a gran escala en la web, es cada vez más común encontrar situaciones donde un solo procesador no puede mantener el ritmo con la alta tasa a la que llegan las entradas. En este trabajo, presentamos el algoritmo de mini-lotes distribuido, un método para convertir muchos algoritmos de predicción en línea basados en gradientes en algoritmos distribuidos. Probamos un límite de arrepentimiento para este método que es asintóticamente óptimo para funciones de pérdida convexas suaves y entradas estocásticas. Además, nuestro análisis toma en cuenta explícitamente las latencias de comunicación entre nodos en el entorno distribuido. Mostramos cómo nuestro método puede utilizarse para resolver el problema de optimización estocástica distribuido, logrando una aceleración asintóticamente lineal sobre múltiples procesadores. Finalmente, demostramos los méritos de nuestro enfoque en un problema de predicción en línea a gran escala.