A Stochastic Subgradient Method for Nonsmooth Nonconvex Multi-Level\n Composition Optimization

We propose a single time-scale stochastic subgradient method for constrained\noptimization of a composition of several nonsmooth and nonconvex functions. The\nfunctions are assumed to be locally Lipschitz and differentiable in a\ngeneralized sense. Only stochastic estimates of the values and generalized\nderivatives of the functions are used. The method is parameter-free. We prove\nconvergence with probability one of the method, by associating with it a system\nof differential inclusions and devising a nondifferentiable Lyapunov function\nfor this system. For problems with functions having Lipschitz continuous\nderivatives, the method finds a point satisfying an optimality measure with\nerror of order $1/\\sqrt{N}$, after executing $N$ iterations with constant\nstepsize.\n