Three Operator Splitting with Subgradients, Stochastic Gradients, and\n Adaptive Learning Rates

Three Operator Splitting (TOS) (Davis & Yin, 2017) can minimize the sum of\nmultiple convex functions effectively when an efficient gradient oracle or\nproximal operator is available for each term. This requirement often fails in\nmachine learning applications: (i) instead of full gradients only stochastic\ngradients may be available; and (ii) instead of proximal operators, using\nsubgradients to handle complex penalty functions may be more efficient and\nrealistic. Motivated by these concerns, we analyze three potentially valuable\nextensions of TOS. The first two permit using subgradients and stochastic\ngradients, and are shown to ensure a $\\mathcal{O}(1/\\sqrt{t})$ convergence\nrate. The third extension AdapTOS endows TOS with adaptive step-sizes. For the\nimportant setting of optimizing a convex loss over the intersection of convex\nsets AdapTOS attains universal convergence rates, i.e., the rate adapts to the\nunknown smoothness degree of the objective. We compare our proposed methods\nwith competing methods on various applications.\n