Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than O(1/ )
In this paper, we develop a novel homotopy smoothing (HOPS) algorithm for solving a family of non-smooth problems that is composed of a non-smooth term with an explicit max-structure and a smooth term or a simple non-smooth term whose proximal mapping is easy to compute. The best known iteration complexity for solving such non-smooth optimization problems is O(1/ ) without any assumption on the strong convexity. In this work, we will show that the proposed HOPS achieved a lower iteration complexity ofÕ(1/ 1−θ ) 1 with θ ∈ (0, 1] capturing the local sharpness of the objective function around the optimal solutions. To the best of our knowledge, this is the lowest iteration complexity achieved so far for the considered non-smooth optimization problems without strong convexity assumption. The HOPS algorithm employs Nesterov's smoothing technique and Nesterov's accelerated gradient method and runs in stages, which gradually decreases the smoothing parameter in a stage-wise manner until it yields a sufficiently good approximation of the original function. We show that HOPS enjoys a linear convergence for many well-known non-smooth problems (e.g., empirical risk minimization with a piece-wise linear loss function and 1 norm regularizer, finding a point in a polyhedron, cone programming, etc). Experimental results verify the effectiveness of HOPS in comparison with Nesterov's smoothing algorithm and the primal-dual style of first-order methods.
The submission considers algorithms for solving a specific class of optimization problems, namely min_{x in Omega_1} F(x), where F(x) = max_{u in Omega_2} \langle Ax, u \rangle - phi(u) + g(x). Here, g is convex, Omega_1 is closed and convex, Omega_2 is closed, convex, and bounded, and the set of optimal solutions Omega_* \subset Omega_1 is convex, compact, and non-empty. The submission also assumes a proximal mapping for g can be computed efficiently.   The above framework is apparently general enough to capture a number of applications, including various natural regularized empirical loss minimization problems that arise in machine learning.   Classic work of Nesterov combined a smooth approximation technique with accelerated proximal gradient descent to converge to a solution with epsilon of optimal in O(1/epsilon) iterations. Roughly, the smoothing parameter mu controls both the quality of the smooth approximation to the original problem (smaller mu means a better approximation), and the speed of convergence (smaller mu means slower convergence). Choosing mu to balance these costs yields an eps-accurate solution in O(1/eps) iterations.  The submission shows that if F satisfies a "Local Error Bound" (LEB), then one can obtain faster convergence. Roughly, an LEB guarantees that the distance of any x from an optimal solution falls like a constant power of the distance of the value F(x) from the optimal value F(x^*). The key idea is to use Nesterov's approach, but the start with a large mu, and gradually decrease it over the course of the execution. The point is that one does not need a good approximation to the original problem at the start (since one is far from an optimal solution then anyway). But as a good solution is approached, one can afford to drop mu to get a better smooth approximation, without killing the convergence rate. A primal-dual version of the algorithm that does not require hand-tuning of parameters is also described (mostly in the supplement).  Applications to specific classes of problems are discussed, and some experimental results from 3 different application domains are provided. The experiments show significantly improved iteration complexity for small values of epsilon, compared to basic Accelerated Proximal Gradient Descent, and a first-order primal-dual method. 
This seems like a nice contribution, both in terms of the analysis (which is clean, intuitive, and apparently the first for this kind of smoothing algorithm), and the concrete efficiency as demonstrated in the experiments. (However, I am not knowledgeable enough about the area to know for certain that the algorithms experimentally compared against truly state of the art).   The class of problems considered capture a variety of important applications, and the theoretical results do seem to generalize or asymptotically improve on several directly comparable prior works.   For applications where theta=1, such as regularized empirical loss minimization with L_1-norm or L_{infty}-norm as the regularizer and a non-smooth loss function like hinge or absolute loss, the submission's algorithm will converge in O(log(epsilon_0/epsilon)) iterations, while the submission suggests that prior work would require O(1/epsilon) iterations to converge. Is this accurate? If so, then this is an exponential improvement on prior work, which seems rather impressive, and perhaps the submission should emphasize this point more.   It would be nice to see how the proposed algorithm fares against prior art for larger values of epsilon. My understanding from the experiments is that the advantage of the present algorithm is seen only at small values of epsilon. But if this is the case, why not use the other methods to quickly find a reasonably good solution, and then run the new algorithm starting from said solution?  Smaller questions: *The submission states that if L_mu is difficult to compute, one can use the "backtracking trick". Was this necessary in any of the applications considered in the experiments?   *Since the proposed primal-dual method requires operating on the dual as well as the primal, it is perhaps surprising that the experimental wall time for this version of the algorithm was best overall. Did the reported wall time account for both the time to update the primal solution and the dual?