A Service System with On-Demand Agents, Stochastic Gradient Algorithms and the SARAH Algorithm

Abstract We consider a system, where a random flow of customers is served by agents invited on-demand. Each invited agent arrives into the system after a random time, and leaves it with some probability after each service completion. Customers and/or agents may be impatient. The objective is to design a real-time adaptive invitation scheme that minimizes customer and agent waiting times.We study some aspects of the SGD method with a fixed, large learning rate and propose a novel assumption of the objective function, under which this method has improved convergence rates. We also propose a convergence analysis of SGD within a diminishing learning rate regime without bounded gradient assumption in the strongly convex case.We propose the SARAH algorithm for solving finite-sum minimization problems in the strongly convex, convex, and nonconvex cases. We also consider a general stochastic optimization problem by using the SARAH algorithm with inexactness.