Adaptive SVRG Methods under Error Bound Conditions with Unknown Growth Parameter
Error bound, an inherent property of an optimization problem, has recently revived in the development of algorithms with improved global convergence without strong convexity. The most studied error bound is the quadratic error bound, which generalizes strong convexity and is satisfied by a large family of machine learning problems. Quadratic error bound have been leveraged to achieve linear convergence in many first-order methods including the stochastic variance reduced gradient (SVRG) method, which is one of the most important stochastic optimization methods in machine learning. However, the studies along this direction face the critical issue that the algorithms must depend on an unknown growth parameter (a generalization of strong convexity modulus) in the error bound. This parameter is difficult to estimate exactly and the algorithms choosing this parameter heuristically do not have theoretical convergence guarantee. To address this issue, we propose novel SVRG methods that automatically search for this unknown parameter on the fly of optimization while still obtain almost the same convergence rate as when this parameter is known. We also analyze the convergence property of SVRG methods under Hölderian error bound, which generalizes the quadratic error bound.
This paper introduces a restarting scheme for SVRG specialised to the case where the underlying problem satisfies the quadratic error bound (QEB) condition, a weaker condition than strong convexity that still allows for linear convergence. The algorithm solves the problem of having to know the value c of the QEB constant before hand.
The restarting scheme applies full SVRG repeatedly in a loop. If after the application of SVRG the resulting iterate is less than a 25% relative improvement (according to a particular notion of solution quality they state), the value of c is increased by \sqrt{2}, so that the next run of SVRG uses double the number of iterations in it's inner loop (T propto c^2).
The use of doubling schemes for estimating constants in optimisation algorithms is a very standard technique. It's use with SVRG feels like only an incremental improvement. A particular problem with such techniques is setting the initial value of the constant. Too small a value will result in 5-10 wasted epochs, where as too large a value results in very slow convergence.
The experiments section is well-explained, with standard test problems used. I do have some issues with the number of steps shown on the plots. The x axis #grad/n goes to 1000 on each, which is unrealistically large. It masks the performance of the algorithm during the early iterations. In the SVRG and SAGA papers the x axis spans from 0 to 30-100 of #grad/n, since this represents the range where the loss bottoms out on held-out tests sets. It's hard to tell from the plots as they are at the moment if the algorithm works well where it matters. This would be much clearer if error on a test set was shown as well.
On the first plot, a comparison is made against SVRG with a fixed number of inner iterations T, for a variety of T. The largest T tried had the best performance, I would suggest adding larger values to the plot to make clear that using too large a value results in worse performance (i.e. there is a sweet spot). I would remove the T=100 from the plot to make room.
In terms of language, the paper is ok, although in a number of places the language is a little informal. There are a moderate number of grammatical issues. The paper does require additional proof reading to get it up to standard.