Time-Data Tradeoffs by Aggressive Smoothing
This paper proposes a tradeoff between sample complexity and computation time that applies to statistical estimators based on convex optimization. As the amount of data increases, we can smooth optimization problems more and more aggressively to achieve accurate estimates more quickly. This work provides theoretical and experimental evidence of this tradeoff for a class of regularized linear inverse problems.
In regularized linear inverse problems, the sample complexity for recovering the true signal has recently been well understood. This paper agues that excess observations than needed in the sample complexity bound can be used to reduce the computational cost. This is achieved through carefully smoothing the original nonsmooth regularizer (such as the ell_1 norm) hence reducing computational iterations,  and without violating the sample complexity bound for recovery. The paper is clearly written and the idea seems interesting, however, there are several practical issues that perhaps should have been addressed.The reviewer found the idea to squeeze more smoothing from excess observations quite interesting, however, this is at the expense of potentially compromising the recovery probability (eta in Fact 2.3, in particular the success recovery bound). A bit disappointingly, in the experiments the authors did not simulate the probability of "exact" recovery at all; instead, only some predefined "closedness" to the true signal is used to declare victory of the algorithm. The authors did decrease the smoothing parameter by a factor of 4 to hedge against failure, but this is adhoc and insufficient. It would be very interesting (in some sense also necessary) to see whether or not, or to what extent, does the aggressive smoothing affect the (exact) recovery probability. Judging from the bound (Fact 2.3), there should be another tradeoff. The experiments can be improved. The reviewer expected to see the following comparison: When we compare against some constant smoothing parameter, say mu = 0.1, we can compute the number of samples needed for high probability recovery, call it m_mu, which is smaller than the number of available samples m. Then we just randomly throw away m - m_mu samples. This way one also reduces the computational cost by reducing the size of the problem. In the reviewer's opinion, this should be the "conventional" constant smoothing algorithm to compare to. Right now, the authors seem to let the competitor run on all available samples, putting it in a disadvantageous position. The two strategies (throwing away redundant data or aggressively smoothing) are really two blades of the same sword: both aim at maintaining the recovery bound in the minimal sense. But the first approach is even more appealing: it certainly requires less memory. The reviewer strongly recommends the authors to perform a serious comparison and report the relative strengths and weaknesses.Another issue the reviewer would like to see addressed is practicality: so far the analysis and experiments are done with prior knowledge of the true signal. In practice this is not available. How could one still be able to apply the aggressive smoothing without being too aggressive? On the other hand, it all appears to "tune" the smoothing parameter, which is what is done in practice anyways. From a fully practical aspect, what is new and different here then? If the new message (as argued in line 325) is that the smoothing parameter needs to depend on the sample size, then how can this be implemented without too much prior knowledge of the true signal?