CONGO: Compressive Online Gradient Optimization

We thank the reviewer for their careful review and consideration. We hope that our responses below provide clarification and are ready to discuss these points further as needed.

[Weakness 0] [Formatting issue] We apologize for this oversight on our part. The formatting on the submission has been corrected.

[Weakness 1/Question 1] [Discussion on parameter choices] Numerical simulations have proved CONGO-Z and CONGO-E to be reasonably robust to the choice of $s$ and $m$. To augment our original results in Appendix F discussing the robustness of CONGO-E to the value of $m$, we have added empirical results on the impact of assuming a value for $s$ that is inaccurate (see Section F.2). Some parameters like $\delta$ and the learning rate are necessarily problem-dependent, with the optimal values depending on things like the presence of noise in function evaluations and the smoothness of the objective function.

[Weakness 2] [Efficiency of CONGO-B versus other CONGO variants] The CONGO framework can generate a variety of algorithms, and not all of them will necessarily be equally effective. Our intention was to display multiple design choices that fit the CONGO framework while proving that there exist some CONGO algorithms that are highly efficient. Thus, we do not view the particular weaknesses of CONGO-B as weaknesses of the CONGO framework as a whole. We have added a remark to Section 4 (page 6) which clarifies this.

[Weakness 3] [Restrictiveness of assumptions] As we acknowledged in our response to Reviewer qS2T, the assumption of exact gradient sparsity seems to be necessary for an algorithm explicitly using sparse gradient estimates to achieve sublinear regret in the adversarial setting. There is a limit to how close a sparse gradient estimate can get to a non-sparse true gradient, and if the average error in the gradient estimate cannot be made to decrease continually as $T$ increases then linear regret is inevitable. In terms of empirical performance, however, we have added new experiments in section F.2 which show the impact of weakening the exact gradient sparsity assumption.

Furthermore, our assumption that the algorithm can make several measurements on each round seems reasonable for the applications we consider in our paper, and has been used in previous work on zeroth-order online convex optimization. The slow evolution of the objective function for autoscaling microservices has been observed in [1], where it was found that in 55% of the microservice application deployments studied, the load did not change by more than 10% over a five minute interval. In our autoscaling experiment in Section 7.2, that would give more than enough time to do a full gradient estimate. The other assumptions we make on the objective function in Section 2 are standard in the constrained OCO literature.

[1] Luo, S.; Xu, H.; Lu, C.; Ye, K.; Xu, G.; Zhang, L.; Ding, Y.; He, J.; Xu, C. Characterizing microservice dependency and performance: Alibaba trace analysis. In Proceedings of the ACM Symposium on Cloud Computing, Seattle, WA, USA, 1–4 November 2021

[Question 2] [Adaptive strategies for sparsity parameter] An adaptive strategy motivated by the one proposed by Cai et. al. [2] could be applied by starting with an optimistic estimate of $s$ and then adding on measurements if the error is believed to be large. We believe this could be integrated into CONGO-Z or CONGO-E without major computational overhead to reduce the difficulty of choosing the $s$ parameter. We have added a discussion on this matter to pages 24-25.

[2] HanQin Cai, Daniel McKenzie, Wotao Yin, and Zhenliang Zhang. Zeroth-order regularized optimization (zoro): Approximately sparse gradients and adaptive sampling. SIAM Journal on Optimization, 32(2):687–714, April 2022.

We thank the reviewer for their extensive analysis and hope that our responses below provide clarification. We are ready to discuss these points further as needed.

[Weakness 1/Question 1] [The need for exact gradient sparsity] The assumption of exact gradient sparsity is necessary in the adversarial setting to enable an algorithm which uses sparse gradient estimates to achieve sublinear online regret. Without that assumption, there would be a lower bound on the gradient error at each round which would lead to a linear increase in the regret so long as the value of the gradient along more than $s$ dimensions does not decay with $T$. The purpose for applying our algorithm in realistic scenarios like the microservice autoscaling problem is to show that empirically the assumption of exact gradient sparsity is not required for CONGO-style algorithms to outperform algorithms which do not exploit sparsity. To make this more clear, we have added the results from new numerical experiments in Section F.2 of the appendix which demonstrate the robustness of CONGO-Z and CONGO-E to a misspecification in the value of $s$ given to the algorithm and their robustness when the ratio $\frac{d}{s}$ is smaller than what we considered before.

[Weakness 2/Question 3] [Comparisons are mostly with respect to methods that do not leverage sparsity] We note that, to the best of our knowledge, there is no prior work on OCO which is explicitly designed to exploit sparse gradients, which is why we have mostly compared different versions of CONGO to evaluate their relative merits. Part of our rationale for introducing multiple CONGO variants is to show that the CONGO variant which we believe to be most effective, CONGO-E, indeed uses the most efficient sparse gradient estimation scheme for OCO (rather than the one introduced in [1], for example, which is the inspiration for CONGO-B). Please also see our response to reviewer LC7u's Weakness 1, which addresses a similar concern.

[1] Vivek S. Borkar, Vikranth R. Dwaracherla, and Neeraja Sahasrabudhe. Gradient estimation with simultaneous perturbation and compressive sensing. Journal of Machine Learning Research, 18(161):1–27, 2018

[Question 2] [Practical implications of logarithmic growth of sample complexity with dimension] We have added numerical experiments for very high-dimensional cases (up to $d = 5000$) in Section F.3 of the appendix. These experiments test what happens if the dimension $d$ increases without increasing the number of samples per round to compensate, and we find that CONGO-E is able to maintain similar performance to gradient descent with full gradient information despite not using the theoretically correct number of samples. This suggests that the sample complexity actually required for good performance will not become prohibitively large in very high-dimensional settings as long as gradients are appropriately sparse. Note that it is not practical for us to consider such high-dimensional problems for the Jackson network and microservice autoscaling experiments due to limited computational resources.

We thank the reviewer for their praise and insightful comments, and we hope to hear their thoughts about our responses below.

[Weakness 1/Question 1] [Clarifying our contributions with respect to the results from AISTATS'18] The gradient estimation procedure used in the AISTATS'18 paper does not exactly match any of the methods we consider, and its theoretical guarantees appear to be inferior to those which CONGO-Z and CONGO-E enjoy. We have added a discussion of this to Appendix A. More importantly, the fundamental differences between their problem setting and ours make it so that the algorithms proposed in that paper are not directly suitable for the goal of achieving sublinear OCO regret in a sample-efficient way. On one hand, the successive component selection algorithm (Algorithm 2) is not applicable to OCO at all. It relies on the assumption that the value of the objective function will never depend on most of the dimensions of the input. The mirror descent algorithm (Algorithm 3), on the other hand, assumes that each gradient is being taken using $\Theta(\sqrt{T})$ samples, which makes it much less reasonable to assume that the objective function remains fixed throughout the sampling process. Furthermore, it is not obvious that the probability of failure for their gradient estimation method can be made to decrease as $T$ increases, which we have shown is necessary to achieve a sublinear expected regret.

[Question 2] [Phase transition for convergence rate in terms of number of measurements] In Appendix F (particularly Figure 6) we showed the effect of reducing $m$ (the number of measurements for CONGO-E) on the error in the gradient estimate. In that case, we had observed that setting $m = 24$ gave very good results, but it could be reduced to 21 without much of a loss in accuracy. However, once $m$ reached about 2/3 of the starting value, the error began to increase dramatically. This seems indicative of such a phase transition.

We thank the reviewer for their feedback and invite them to continue to discuss these points based on our responses below.

[Weakness 1] [Main challenges and positioning of results] The main theoretical challenge in applying compressive sensing to online convex optimization is ensuring that the error due to compressive sensing failures does not accumulate over $T$ (which would lead to a large regret). The main challenge in the practical implementation of CONGO within the framework from section 4 is finding the best choices for the measurement matrix and recovery algorithm to achieve good speed and performance. We believe that we found superior choices in CONGO-E, which does not exactly match any existing gradient estimation method (though it is inspired by multiple).

[Weakness 2] [CONGO-B gradient recovery requires solving an LP] This is one of the reasons why we consider CoSaMP to be the better choice of recovery algorithm for other CONGO variants; however, to better show the range of possible options under the CONGO framework, we used basis pursuit for CONGO-B which aligns with the choice in Borkar et. al. for the stochastic optimization setting.

[Weakness 3] [Compressive sensing usually requires knowledge of the sparsity] This is indeed true. However, we have now included empirical results demonstrating that under the appropriate sampling strategy (used in CONGO-Z and CONGO-E), the approach is robust to an inaccurate estimate of the sparsity in the sense that it will still perform better than Spall's SPSA even if $s$ is much larger than the predicted value (see Section F.2 on pages 23-25). In fact, those results show that even when there is a 50% error in the estimate of $s$, the performance will not be too much worse that gradient descent with full information.

[Question 1] [High probability equivalents of Theorems 2 and 3] One could derive high-probability bounds in much the same way as the bounds in expectation for a version of the algorithms in which a single measurement matrix is drawn at the beginning and reused at every round. In such a case, the law of total expectation would no longer be applied because we would only be considering outcomes where the gradient estimation error is bounded as in Lemma 2. The probability with which the bound holds would be equal to epsilon in Lemma 2, which could be chosen freely as long as m is set appropriately. Thus, it would not be necessary for $m$ to depend on $T$. However, as stated in Appendix D, we opt to resample on every round for practical reasons (to ensure that no single trajectory experiences a very large number of failures), and so we did not include theorems for the high-probability bounds.