CONGO: Compressive Online Gradient Optimization
Authors: Jeremy Carleton
Prathik Vijaykumar
Divyanshu Saxena
Dheeraj Narasimha
Srinivas Shakkottai
Aditya Akella
Venue: ICLR 2025 Poster (2025)
Keywords: online convex optimization
compressive sensing
regret analysis
Primary area: optimization
TL;DR: A compressive sensing based approach to online convex optimization and its application to the optimization of queueing networks

Abstract: We address the challenge of zeroth-order online convex optimization where the objective function's gradient exhibits sparsity, indicating that only a small number of dimensions possess non-zero gradients. Our aim is to leverage this sparsity to obtain useful estimates of the objective function's gradient even when the only information available is a limited number of function samples. Our motivation stems from the optimization of large-scale queueing networks that process time-sensitive jobs. Here, a job must be processed by potentially many queues in sequence to produce an output, and the service time at any queue is a function of the resources allocated to that queue. Since resources are costly, the end-to-end latency for jobs must be balanced with the overall cost of the resources used. While the number of queues is substantial, the latency function primarily reacts to resource changes in only a few, rendering the gradient sparse. We tackle this problem by introducing the Compressive Online Gradient Optimization framework which allows compressive sensing methods previously applied to stochastic optimization to achieve regret bounds with an optimal dependence on the time horizon without the full problem dimension appearing in the bound. For specific algorithms, we reduce the samples required per gradient estimate to scale with the gradient's sparsity factor rather than its full dimensionality. Numerical simulations and real-world microservices benchmarks demonstrate CONGO's superiority over gradient descent approaches that do not account for sparsity.

Published as a conference paper at ICLR 2025
CONGO:
COMPRESSIVE ONLINE GRADIENT OPTIMIZATION
Jeremy Carleton' Prathik Vijaykumar' Divyanshu Saxena²
Dheeraj Narasimha'
Srinivas Shakkottai"
Aditya Akella?
Texas A&M University, The University of Texas at Austin, 3 Inria
ABSTRACT
We address the challenge of zeroth-order online convex optimization where the objective function's gradient exhibits sparsity, indicating that only a small number of dimensions possess non-zero gradients. Our aim is to leverage this sparsity to obtain useful estimates of the objective function's 's gradient even when the only information available is a limited number function samples. Our motivation stems from the optimization of large-scale queueing networks that process time- sensitive jobs. Here, a job must be processed by potentially many queues in sequence to produce an output, and the service time at any queue is function of the resources allocated to that queue. Since resources are costly, the end-to-end latency for jobs must be balanced with the overall cost of the resources used. While the number of queues is substantial, the latency function primarily reacts to resource changes in only few, rendering the gradient sparse. We tackle this problem by introducing the Compressive Online Gradient Optimization framework which allows compressive sensing methods previously applied to stochastic optimization to achieve regret bounds with an optimal dependence on the time horizon without the full problem dimension appearing in the bound. For specific algorithms, we reduce the samples required per gradient estimate scale with the gradient's s sparsity factor rather than its full dimensionality. Numerical simulations and real- world microservices benchmarks demonstrate CONGO's 's superiority over gradient descent approaches that do not account for sparsity.
INTRODUCTION
Online convex optimization (OCO) plays an important role in managing distributed applications like web caching, advertisement placement, portfolio selection, and recommendation systems. These applications involve an unknown, time-varying convex system cost function f((2)). dependent on d-dimensional control æg, which the user selects in online manner. Of particular interest systems with the following key characteristics: (i) fr(-) and its gradient are unknown, and obtaining measurements for any control æ, is costly; (ii) the gradient of f+(-) is sparse, where only few dimensions of 2e significantly affect fe()): and (iii) fe(-) evolves slowly, allowing for multiple measurements between updates to æt. These features arise in many real-world settings, such in queueing systems in communication, manufacturing, and distributed computing, where only a few bottlenecks exist any given time and they must be identified through only a few measurements. Our goal is to develop efficient online gradient descent algorithms tailored to such scenarios.
core challenge in OCO is that both the objective function and its gradient are usually unavailable in closed form. Thus, we must perform zeroth-order OCO, where gradients are estimated from objective function observations at specific points close to the current input. We will show that when gradients exhibit sparsity (see Definition 1), efficient gradient estimation is possible by combining simultancous perturbation stochastic approximation (SPSA; Spall (1992)) and compressive sensing, achieving cumension-independeee sub-linear regret scaling in OCO problems.
"Corresponding author; jcarleton @ @tamu.ddu Code available https//gituaaccom///ceemyyCCCCo

---

Published as a conference paper at ICLR 2025
Related Work on Compressive Sensing for Stochastic Optimization: Introduced by Candes and Tao (2006), compressive sensing is widely used in signal processing for sparse signal recovery (Eldar and Kutyniok, 2012). Its value lies in requiring only logarithmic measurements relative to the vector's dimension to approximate an s-sparse vector; see Foucart and Rauhut (2013) for details.
To apply compressive sensing techniques, gradient measurements must be taken at randomly perturbed points, similar to SPSA. This idea was explored in (Borkar et al., 2018) in the context of stochastic optimization for single unchanging objective function. Here, the gradient is measured as A V fxx)= e, with A being a Gaussian matrix and an error term due to interference from other dimensions and high order terms in the Taylor approximation evaluations suffice per measurement, though the error requires averaging over multiple perturbations to ensure an acceptable level of accuracy of the gradient estimate.
the perturbed function value. Two function
Other significant work that leverages compressive sensing for stochastic optimization of given objective function is (Cai et al., 2022), which introduces the Zeroth-Order Regularized Optimization (ZORO) algorithm. ZORO uses a Bernoulli measurement matrix and applies only one row of the matrix at a time. This method reduces the noise in gradient estimation, enabling accurate gradient estimates with fewer function evaluations.
More details of related work are presented in Appendix A.
Our Contributions - CONGO: We introduce the Compressive Online Gradient Optimization
(CONGO) framework, applying compressive sensing methods to OCO for estimating gradients using limited number of function evaluations at each online optimization step. Our goals for CONGO in the sparse OCO problem are: (i) develop a sample-efficien its regret over finite time, and (iii) empirically validate it in a general setting, and specifically for real-world use case in a containerized microservice application.
gradient estimation approach, (ii) analyze
We propose three CONGO variants: CONGO-B (leveraging ideas from Borkar et al. (2018)), CONGO-Z (leveraging ideas from the ZORO approach of Cai et al. (2022)), and a more effective sampling approach using Gaussian measurement matrix, which we name CONGO-E. One of our key analytical results is to allow for a bound on the expected regret to be proven in spite of the chance for compressive sensing to fail to recover the gradient with low error. We prove that CONGO-Z and CONGO-E have a better sample complexity than CONGO-B -B for generating gradient estimates, and we derive a dimension inmeesioonindeeendeen O ((VT) regret bound over T time steps for these algorithms. For CONGO-Z and CONGO-E, the (s log (=)) samples per gradient estimate greatly improves upon the d samples required for algorithms that do not consider sparse gradients (Agarwal et al., 2010).
We validate CONGO in three settings: (i) fully stochastic setting where a new high-dimensional random objective function is sampled after each gradient descent step (Section 6); (ii) a a queueing system (under the Jackson network model), where resource allocations are chosen to balance pro- cessing time and resource cost (Section 7.1); and (iii) a real-world mieroservice autoscaler, where CPU resources are allocated to containers of a benchmark application (Gan et al., 2019) (Section 7.2). In setting (i), CONGO-E and CONGO-Z perform similar to gradient descent with full gradient information, thus matching expectations from the theoretical results. In settings (ii) and (iii), CONGO-E outperforms standard SPSA in most cases even in -iwddimeniional settings, with its performance improving as sparsity increases. In the microservice setting, CONGO-E approaches the performance of an optimal reinforcement learning (RI. baseline even under variable loads. We conclude that CONGO enables algorithms which effectively exploit sparsity.
PROBLEM FORMULATION
System model and sequence of events: We consider an online learning problem over T rounds indexed from 1 to T. At the start of each round f, the controller must choose a a d-dimensional control TG E KC where K. C IRd is known. We are specifically interested the high dimensional regime such that d is large value. Next, adversary chooses a differentiable convex function ft d + I and the controller incurs the cost (zz)) The controller is unaware of the function ft. however, we may acquire samples of fi in local vicinity of f(()). It is assumed that these samples are costly to obtain, or that there is a limit to how many can be taken, such that we desire an algorithm to be as sample-efficient as possible. Note that in our constrained optimization setting, we permit the samples
2

---

Published as a conference paper at ICLR 2025
used for gathering information fa,) to lie outside of IC so long they remain close to æ; in expectation.
Control strategy: In this work, will examine online projected gradient descent algorithm where the samples retrieved are used to estimate a noisy gradient. In particular, at the end round t, we use the samples taken to compute an estimate V ft()), The online gradient descent algorithm dictates that should use
1t+1 argmin]
x (xt 7/ (((x))l)
aEK
as the control for our next time step. Here 1t is predetermined step-size chosen by the controller.
Assumptions: Our setting uses two key assumptions the constraint set K. and the observed functions. Assumption 1 (Constraint Set Properties). The set K. C. IRd satisfies the properties: (i) KC is compact and convex; and (ii) sup||>/|2 2012 R. =ek
An important way in which our setting differs from standard online convex optimization is that we make an assumption about the sparsity of fc. We define sparsity follows:
Definition (Sparsity). The support of vector x E Rd is: supp(ær) == (j E We call vector s-sparse (sup xx)
d} J # #0}.
Our overall constraints on the set of functions the adversary can choose from are summarized below:
Assumption 2 (Function Properties). Let F denote the set of all functions I which satisfy the properties: (i) f is convex, Ly-Lipschitz, and L-smooth; and (ïi) V fx)) ) is s-sparse Vo K. For each time E [1, T). we assume our functions Je are chosen such that Jt E
As mentioned Section 1, the significance of the sparsity assumption is that an algorithm may be able to exploit this sparsity such that the number of samples requires and the overall regret has little or no dependence on d. The challenge, course, that we do not know a priori which dimensions of V fz are nonzero
current control point, and this change every round.
Performance Metric: Our performance metric of interest is the adversarial regret at the end of T rounds, which measures the difference in the cost accumulated over the T rounds with that of the best fixed control point xx in hindsight. In what follows we shall formally define the adversarial regret. Definition 2 (Adversarial Regret). Given a sequence of convex functions {fr) satisfying As- sumption 2, our objective is to minimize the following quantity which we call the regret:
T
R(T)= =
max
Σ f((
minn 26"
Σ f((aa)
3 MOTIVATING EXAMPLE
The Jackson network control problem is one possible application of CONGO and relates to the real-world problem of autoscaling microservices. In Jackson network (Srikant and Ying, 2014), jobs enter set of interconnected queues. When de-queued, jobs are processed by a server and then may re-enter the queue, jump to another, or exit the system. The (end-to-end) latency is the delay between job arrival and completion and is affected by the service rates of the servers. Our goal is minimize the average latency while balancing resource costs, which grow linearly with increased resource allocation. The average service time in a Jackson network a convex, non-increasing function of allocated resources; meanwhile, the workload changes over time, making this an OCO problem.
Let L(>e; (x)) denote the expected end-to-end latency for a given workload X and allocation æ; The objective function (total cost) that we wish to minimize is:
f((x,) L(>,, 2x) + w
where w is the price per unit of allocated resources (assumed uniform across queues). Note that each element of the gradient of T. T.( corresponds to different queue. We can only sample latencies
3

---

Published as a conference paper at ICLR 2025
for finite number of jobs to limit measurement overhead, and these samples are used to estimate the gradient. The service cost is known, so only the gradient of L(),, ) needs to be estimated. If the system is bottlenecked only at few queues, the problem will be sparse. with only few large gradients, which we must identify using a limited number of measurements.
Such sparsity is observed in large-scale heterogeneous microservices applications. Similar to the Jackson network model, requests in microservice applications queue at multiple microservices before completion (Gan al., 2019). Resource allocation to microservices, e.g. CPU resources, must be carefully managed to achieve tight latency targets. Appendix A includes a review of microservice literature and the challenges of resource allocation, particularly the curse of dimensionality arising from numerous services and flows (production microservice graphs may have up to 100s of mi- croservices (Huye et al., 2023)). Typically, only a few microservices are bottlenecks, and adjusting resources for any microservice which is not a bottleneck will not significantly impact T.(>,, zx) (Qiu al., 2020), leading to an approximately sparse gradient as per Definition 1, which we have confirmed experimentally (see Fig. 1). This sparse bottleneck phenomenon has been observed in other offline-trained autoscalers (Qiu et al., 2020; Sachidananda and Sivaraman, 2024; Wang et al., 2024) that identify specific microservice instances that bottlenecks and adjust their allocations. We also observe that L is convex in both its arguments (Fig. 1). Thus, a scheme like CONGO can be expected to perform well online resource management for microservice applications.
Loud Latieny
Labenay us allccation
deerage Nurmel dcross Containe's
13.5
0.00
11.5
200 400
1200 1900 Leoz Eindueet der Gecond)
CHU of Coll1
1.0
2307
Figure 1: -Lett: Convexity of latency vs. CPU allocated to the nginx-thrift container in the SocialNetwork benchmark. Center: Convexity of latency arrival rate for compose-pon requests. Right: Sparsity of average relative gradients of end-to-end latency for 26 containers under different offered workloads. Only a few show large (negative) gradients for each workload, making them good targets for increased CPU allocation.
4 CONGO FRAMEWORK AND ALGORIHTM
The CONGO framework characterizes class of online convex optimization algorithms that consist of four steps: (i) a measurement matrix generation step, (ii) a step where measurements are collected, (iii) constrained gradient recovery step, and (iv) gradient descent update step. CONGO algorithms can be broken into an inner loop that estimates the gradient (steps (i)-(ii)) and an outer loop that performs gradient descent (step (iv)). Since no existing OCO approach utilizes compressive sensing, we make decisions for each of the above steps, leveraging insights from work on stochastic optimization with a fixed objective. As we do so, we present variants CONGO-B and CONGO-Z, which are motivated by Borkar et al. (2018) and Cai et al. (2022), along with a more efficient variant, CONGO-E. Some of the design choices we made for the OCO setting are explained in greater detail in Appendix D.
To obtain the gradient approximation (w)), we first obtain "compressed" measurements of the form y = AV f(x) + e (where the range space of A is of lower dimension than the domain space). We apply the theory of compressive sensing to guide our choice for the matrix A used in the simultaneous perturbation step (step (ii). The recovery guarantees we use require A to satisfy the 2h or th restricted isometry property (RIP) as defined in Appendix A. This property approximately preserves the notion of distance in the domain and range of the transformation represented by the matrix A for sufficiently sparse vectors. Since we will eventually create V (ax) from the measurements (step iii), we need A to such that the information in V fx) can be recovered from A (z).
(i) Measurement Matrix Generation Method:
is known (Foucart and Rauhut, 2013) that matrices drawn from dense random distributions like Gaussian matrices (with (O, 1) entries) and Bernoulli matrices (with Rademacher entries) give the best guarantees for satisfying the RIP, so those matrices are used in the CONGO-style algorithms we consider. Since these matrices may fail to satisfy the RIP (with small probability), CONGO-style algorithms resample the measurement matrix at each iteration to ensure that compressive sensing failures are limited to single iterations.
4

---

Published as a conference paper at ICLR 2025
(ii) Measurement Procedure: The measurements of the form (Vx + are obtained using variants of the simultaneous perturbation stochastic approximation (SPSA). The original idea for SPSA is credited to Spall (1992). We introduce it here with more details in Appendix A. First, generate a sequence of i.i.d. Rademacher random variables, (Az}}=ı- Next, generate, a perturbation vector
A :
E Σラ= ú where u, is the unit vector along the ith dimension. Then we compute gradient estimates along each dimension:
f(e + و2) - ((x)
af(x)
0f(x) A dz, A;
(5)
j
dr:
These measurements combine to give an estimate of V (xx). When applying compressive sensing, seek measurements which form vector approximately equal to A (V) where A E Rmxd with m << d. This requires us to form perturbations using the rows of A, either by replacing A with a row a, and repeating m times by replacing A with A A to form linear combination. While the latter method only requires two function evaluations, it introduces a noise term due to interference between measurements for different rows; this was observed previously by Borkar al. (2018).
To see how these methods give us an approximation of V (ae), note that since f is differentiable, the Taylor approximation for f(x + 8A) with x as the reference point is as shown in equation 6 after cancelling out terms:
(6) where represents the Lagrange remainder of the first-order Taylor approximation. In particular, have the bound
f (x ره) f(x) + (Vf(=), -
1 v f
s < 2
Thus, (f + 5A) - f())) (5 (Vf(z), A + O(8).
Composition of y from measurements: If A a, then the first term is exactly want want for y:- However, if A = ATA, then we can divide by A, to isolate (Vf(x), a.), but there will be other terms of the form A, (V (x), م,ay) left (if the elements A are Rademacher random variables, then these terms will have zero mean). Since any difference between y; and (Z)()) a.) adds to the error in the final estimate of fxx). algorithms using the second method may need to repeat the process several times with different random draws of A and average over the measurements to control this interference between measurements. In either case, the CONGO framework also requires replacing 8 by |||اه
cancel out the factor of A in the Lagrange remainder. This is important because if factor of A 12 is left in the eгror term, its expectation will be present in the regret bound, and hence the regret bound will no longer be paweensionnindeendeen
The difference between the two measurement schemes is made clear in the following lemma, which bounds the overall measurement error (prior to any potential averaging):
Lemma 1. Given a matrix A E pmmxd, 8> O, and a function f which is convex, Lipsschhi,,, and L-smooth, if a vector of measurements y is constructed as
5
||
= [(x
a.) f(x)
vi = [m].
a 11
8
then
y AV)(z) te
where |lell < v 2/ S Lmmm If instead, y is constructed as
||ATII
f(x
A AT
f(x)
Vi E [m].
ATA
SA,
where A E Ipm is vector of Rademacher random variables independent from the entries of A, then
y f
e1 +
with |e2|l2 < 101l < 2/2 f and
A
(V az)
[e:)
A
5

---

Published as a conference paper at ICLR 2025
(iii) Constrained Gradient Recovery: Many recovery methods are available that estimate sparse vector v given measurements of the form Aute under suitable conditions on A. Two of these already have well-studied guarantees: (i) Basis Pursuit (Chen et al., 1998) and (ii) Compressive Sampling Matching Pursuit (CoSaMP) (Needell and Tropp, 2008). See Appendix A for an introduction. Note that the recovery guarantees
in Section 5 require to scale A and y by /m where is the number rows of before performing the recovery. Regardless which method is used, the CONGO framework requires that f((x)) be explicitly bounded over all rounds, and to ensure this either introduce explicit constraint (in the case of basis pursuit) perform post-processing the recovery procedure fails to return a vector satisfying the expected bound, we replace with the zero vector. Although the choice of the zero vector is not critical to the regret bound, it makes some practical sense since avoids the risk of unexpectedly moving to a much worse control point.
(iv) Gradient Descent Update Step In this paper, consider constrained OCO (see Assumption 1). Thus, our gradient descent update takes the form of equation
4.1 CONSTRUCTION OF CONGO VARIANTS
We construct three variants of CONGO based some of the choices that make for each step.
CONGO-B uses a Gaussian mcasurement matrix and a combination of the rows of the measurement matrix for each perturbation. Averaging is applied to mitigate the effect of interference between measurements. Basis pursuit is applied to obtain the gradient estimate. The pseudocode for this algorithm is presented in Appendix B.
CONGO-Z uses a Bernoulli measurement matrix and single-row perturbations resulting in exactly m + 1 function evaluations per gradient estimate (since averaging is applied). CoSaMP used to obtain the gradient estimate. Due to the similarity between CONGO-Z. and CONGO-E, we do not include the pseudocode for CONGO-Z here.
CONGO-E modifies CONGO-Z by using a Gaussian measurement matrix, which we find leads to performance improvements across all of our experiments. We chose to stick with single-row perturbations to avoid the interference between measurements, since our analytical results show that this is necessary in order to obtain the desired regret bound with an efficient number of samples. We maintain CoSaMP as the recovory method for practical reasons; see Appendix E. The pseudocode for CONGO-E is provided in Algorithm
Remark 1. As alluded to above, the gradient estimation procedure used for CONGO-B introduces additional error due to interference since the measurements for every row of A are being compressed into a single sample. We have found that this leads to weaker theoretical results and worse empirical performance (even with averaging) than CONGO-ZJE. Our intention with CONGO-B is to illustrate the importance of certain design choices by comparing it to CONGO-ZEE.
THEORETICAL RESULTS
In this section, we first present the general theorem used to prove CONGO regret bounds. Then, we state the bounds achieved by CONGO-B, CONGO-Z and CONGO-E. We establish that all three algorithms achieve the optimal regret scaling of O(VT) without dependence on the dimension. For CONGO-Z and CONGO-E in particular, this only requires O(s (log (9) ) + log(2T)) samples per round. In the non-sparse case it has been shown (Agarwal et al., 2010) that this can be achieved using + samples per round, but by taking advantage of the sparsity we are able to do so using number of samples that depends only logarithmically on d. All proofs are postponed to Appendix C.
The following the key theorem for the CONGO framework:
Theorem 1. Let assumptions 1 and 2 hold, and further assume that Vt E [T]:
-)(f((=)) - (x < M8 with probability at least
1
T
/1/((2))) M8 T

---

Published as a conference paper at ICLR 2025
Algorithm 1 CONGO-E: Compressive Online Gradient Optimization Efficient Version
Require: Constraint set K. Horizon T, sparsity s, Lipschitz constant L, Smoothness parameter L,
Parameters (m) (m=){= 6, m, Initialization point æ
for 1 1,2,-.. T do
A <- randomly drawn m x d matrix with (0, 1) entries
D Generate measurement matrix
Query f((2:))
for i = 1.2g ...,m do
|| a
Query fe + A)
IA (fe( + A) f(()))) قااا
Construct from measurements
end for
fa..)) CoSaMP(
1 A vm U,
Constrained gradient recovery
if ftxa))l > Lg + 7.21 L5 then
fx, +-
end if
D++1 + argmin| x (a: - - m Ve(x)))) #EK
> Gradient descent update
end for Incur regret Et= (x,,) fe(x*)
where M 2 0 is independent T' Then with LIVT Vt and 5 = MT. the regret of an algorithm running projected gradient descent using the estimated gradient f(x.) after T rounds scales as O(DD + + L, (.yT)) where R is as Assumption and D sup x y11 (see proof for ø.yek
1
the full expression).
The following lemma uses known guarantees the restricted isometry constants (RICs) for Gaussian and Bernoulli random matrices to establish recovery guarantees. In turn, this will be used to show conditions under which CONGO-style algorithms satisfy the assumptions of Theorem 1.
Lemma 2. On any round f, Given Gaussian or Bernoulli random matrix A' and measurements y A (xx) + e, if A and y are first rescaled by io then under Assumption 1, the gradient estimate V (x)) returned by CoSaMP or basis pursuit satisfies
[[V - ve((x))ll S C1|eel2
with probability at least - so long as
ed
+ log(2e 12)
2 C'
Ki Ksslog
188
where C, C', and are constants depending on the type of measurement matrix used and the recovery algorithm (but not on d or ). In particular, one can use C = 3 and k = 2 2.ror basis pursuit and C' 7.21 and for CoSaMP; see Remark for note on the value of C².
Based on Lemma 2 and Theorem 1, must depend logarithmically on T to ensure the guarantee. While this dependence is weak, adjusting the number samples as the problem horizon increases is undesirable. Fortunately, in all our experiments, we could omit the T T-dependent term in m and still achieve strong performance.
We now give the theoretical result for CONGO-B (Algorithm 2), and then show how it is improved upon by CONGO-Z Z and CONGO-E in terms of the number of function evaluations per round.
Theorem
assumptions and hold. Then CONGO-B with 17 I L [C (2s log ( (#)) + log(4T))) (for a constant C independent of s, d, and T' has an expected regret, which, after T rounds, scales O(D R 4B LLy)). Furthermore, the average number of samples which the algorithm must take on a round to achieve this is no greater than 36d(m 2)2 1.2, (og(2m))))( +2. 2.
at., m
L,
7

---

Published as a conference paper at ICLR 2025
GDSP
CONGO B
CONGO 2
CONGO_ _
30, 5, m 24, Notseless
50, 5, 24,
0.00)
1000, 5,
00000
150
Recumasene Cna
ACCU MEMAMAAAOE Coost
ACCUPLEENN Cast
130
-00
50-
60
300
20
60
80
100
20
40
60
20
150
Round
Sound
Round
Figure 2: Comparison of accumulated costs, where GD represents gradient descent with full gradient information. Left: Noiseless function evaluations with 50. Center: Noisy evaluations with d 50. Right: Noisy evaluations with 100. represents the noise standard deviation. Even with noise, CONGO-Z and CONGO-E perform closely to the GD baseline.
Clearly, the number of samples which CONGO-B demands for this guarantee is not realistic for practical scenarios. However, it should be noted that due to the loose upper bounds used to obtain this value, the situation appears much worse than it actually is. Indeed, in the numerical experiments of Section we find that when the number of samples taken is only cm for a small constant c, the performance from CONGO-B is still significantly better than the SPSA algorithm that does not account for sparsity. Nonetheless, we would like to have an algorithm which can give the desired regret bound with a reasonable number of samples which is significantly less than d. The following result shows that CONGO-Z. and CONGO-F, which only require m samples, suit this purpose.
Theorem 3. Let assumptions I and hold. Then CONGO-Z and CONGO-E with n L,VT' 5 = 7.2FT. m = |C' (4s log (4) + +og((T)) (for constant C independent of s, d, and T') have an expected regret which after T rounds scales as O(DD +
2
LgVT).
4B Ly
6 BENEFITS OF COMPRESSIVE SENSING
In what follows, we empirically demonstrate the superiority of the compressive sensing approach to standard SPSA (GDSP denotes the algorithm which performs gradient descent using standard SPSA) in the online setting. We also include projected gradient descent with full gradient information (denoted GD) optimal baseline. In the numerical results presented in this section, restrict the class of functions which the adversary can choose from to quadratic functions of the form
((x) xx" Dr: + bT a' +
(8)
where D a diagonal matrix. Importantly, the vectors diag(D) and are both s-sparse with identical support. This ensures that the gradient V fx(x)= 2D + b is s-sparse. The nonzero entries of b are sampled from a Gaussian distribution with a mean -1 and standard deviation 1, and the nonzero entries of D are sampled from the same distribution with the absolute value taken to ensure that D is positive semidefinite. The value of c is sampled from a folded normal distribution so that 2 0. The constraint set is Fuclidean ball centered on the origin with radius R. In the experiments for Fig. 2, we set R R 100.
Fig. 2 shows the results for three experiments with moderately high level of sparsity. These plots are averaged over 50 random seeds, and the standard deviations are indicated with the shaded areas. CONGO-Z, CONGO-E, and GDSP all use m m++1 samples per gradient estimate, but CONGO-B uses 3m and 6m for d = 50 and d = 100, respectively. We first considered the case where function evaluations are noiseless, and set 6 1e - As expected, the CONGO-Z and CONGO-E algorithms achieved almost the same performance as exact gradient descent, while CONGO-B did worse since the amount of averaging was not enough to counteract the interference between dimensions. All of the CONGO-stya algorithms outperformed GDSP. In the second and third experiments, we considered the case where noise from a (0,0, 0.001) distribution was added to the function evaluations and found that CONGO-Z and CONGO-E still did not perform much worse than exact gradient descent. For CONGO-B, we had to increase the number of samples averaged over for it to maintain a similar performance. We performed several additional experiments in this setting to investigate robustness; the results can be found in Appendix More details on the parameters used in the numerical simulations are given in Appendix G.
8

---

Published as a conference paper at ICLR 2025
NEGD
SCDSP
CONGO-8
CONGO-Z
CONGD-E
15 Queues, Foxed Workload
15 Queues, Variable job Type
15 Queues, Varisble Arrival Rate
140
100
120
100
Cost
80-
40
20
100
20
40
60
80
100
100
50 Queues, Foxed Workload
50 Queues, Variable
50 Queues, Varieble Arriall Rate
350
200
325
300
300
275
250
125
250
100
0
20
40
60
80
100
20
40
60
80
100
20
40
80
100
Round
Round
Round
Figure 3: Jackson network simulations while varying the number of queues, workload, job types and
arrival rates. The CONGO algorithms, especially CONGO-E, reduce cost faster than the baselines.
7 AUTOSCALING OF CONTAINERIZEI MICROSERVICES
We now discuss the application of CONGO to the use-cases introduced in Section 3. In Section 7.1, we simulate Jackson networks under job distributions with unique routes, showing that the benefits of compressive sensing can be reaped in many scenarios. Then, in Section 7.2, we deploy our CONGO algorithms on a real-world microservice benchmark and demonstrate their practical benefits.
7.1 JACKSON NETWORK SIMULATION
Methodology: In the following experiments, simulate the Jackson Network model introduced in Section 3. In the simulation, the service time experienced by jobs at queue is inversely related to the allocation for that queue: given allocation æ the service time the ith queue is .;+0.. For simplicity,
in equation 4. We consider two different Jackson network layouts 15 and one with 50 microservices. Details can be found in Appendix G. We conduct experiments for the two Jackson network layouts with three types of workloads: (i) fixed workload, (ii) fixed arrival rate with variable job distribution, and (iii) variable arrival rate with fixed job distribution.
with
Baselines: We compare the three CONGO-style algorithms with each other and two gradient-descent baselines to concretize the benefits of compressive sensing observed for this application. The first, Naive Stochastic Gradient Descent (NSGD), takes the naive approach of estimating the partial gradient along each dimension in isolation (thus requiring d + samples per round). The second is the GDSP algorithm mentioned in Section (now denoted SGDSP since it is applied stochastic gradient descent). See Appendix G for the implementation details of the algorithms, including hyperparameters. The results for each of these algorithms are averaged over five random seeds.
The results are shown in Fig. 3. First, we note that NSGD, despite using more samples on each round than the other algorithms, shows poor performance in every scenario; this is evidence for the effectiveness of simultancous perturbation. We also note that while SGDSP eventually reaches a cost on par with that of CONGO-E in each scenario, it consistently takes much longer to reach significantly higher regret. In general, CONGÔ-E's advantage from quickly
Results:
that cost, leading lowering its cost in the early rounds is amplified when there are more queues. We see that CONGO-B performs well in the limited-sparsipg regime with only 15 queues, while in the high-dimensional regime it fails to outperform SGDSP (likely owing to greater interference). CONGO-Z performs poorly in many scenarios, which we believe is due the Bernoulli random matrix being less effective for sparse recovery than the Gaussian random matrix for the same number of measurements.
7.2 REAL-WORLD MICROSERVICE BENCHMARK DEPLOYMENT
Methodology: We test the ability of CONGO-style algorithms to converge to an efficient resource allocation when autoscaling from the DeathStarBench suite (Gan et al., 2019) which represents a small-scale social media platform with various request types such as "compose-post" readd-user-tmmeline and 'read-home time--e---
real-world benchmark. We utilize the SocialNetwork application

---

Published as a conference paper at ICLR 2025
1600
SCOSP
COMSO
COM60-2
CONOOV
190
Fixed workloac
Veriable job type
Variable arrival
150
180
160
200
140
160
120
140
0
100
120
100
100
50
50
1000 2000 3000 4000 5000 6000 7000 8000 Time lin seconds)
1000 2000 3000 4000 5000 6000 7000 8000 Time (in seconds)
0
2000
4000 6000
8003 10000 12000 Time (in seconos)
Figure 4: Overall costs in a microservice benchmark application under different workload patterns. CONGO-E consistently outperforms the baselines and overall performs better than CONGO-B B and CONGO-7, and it approaches the performance of a policy pre-trained for each scenario via PPO.
As with the experiments in Section 7.1, three scenarios are considered: (i) fixed workload, (ii) fixed arrival rate with variable job types, and (iii) variable arrival rate with fixed job types. As before, use a combination of the end-to-end latency and a cost associated with CPU allocations as the overall cost function. If (-s-) denotes the sample mean of the end-to-end latency, the cost is calculated as:
f((z)) ( (L(A,, 21) W
[rc]
Note that for the purposes of minimizing the cost function, the introduction of the latency weight d has the same effect on the optimal solution as rescaling w by its inverse. In these experiments, we set v = 0.001 and w = 0.1. Unlike in Section 7.1, we plot wall-clock time the x-axis since everything happens in real-time but the time elapsed per round is not consistent across all algorithms.
These experiments compare CONGO B, 7, and E against the same NSGD and SGDSP baselines used in Section 7. along with PPO as a representative pretrained RL method. We include compete with a pretrained model since most intelligent autoscaling methods rely on pretraining (see Appendix A). Results are averaged over four runs.
Baselines:
PPO to test whether our algorithm
Results: As seen in Fig. 4, CONGO-E always performs better than the gradient descent baselines, and it is able to make progress towards the optimal cost given by PPO, reducing its cost by close to 45% average for the fixed workload and variable job type cases and 20% for the variable arrival rate case a matter of just over two hours. Furthermore, CONGO-E reaches a lower cost faster than CONGO-Z for the FW and VAR cases, demonstrating the superiority of the Gaussian distribution for measurement matrices. On the other hand, CONGO-B shows poorer performance though it still maintains lower cost than the gradient descent baselines most times; we attribute this the extra noise which the algorithm suffers from as explained in Section 4.
CONCLUSION AND LIMITATIONS
In this paper, we introduced a framework that brings the benefits from compressive sensing into the OCO setting. We proved that in the sparse gradient setting, number of samples only logarithmic in d is sufficient to guarantee O(TT') regret. Furthermore, we showed that these benefits extend to practical applications. Overall, we found that CONGO-Z allows for strong theoretical guarantees with relatively few samples while CONGO-B offers poor theoretical guarantees but performs better in scenarios where observations are highly noisy, and CONGO-E provides the best of both worlds.
The assumption of exactly sparse gradients in our theoretical analysis may not hold in complex systems, but our experiments in Section 7 show that near-sparsity suffices for the benefits of compressive sensing to be seen. As noted in Section 5, our algorithm assumes that bounds on several quantities are known; however, it is acceptable for the bounds on Ly and L to be quite loose we are mainly concerned about the scaling of I' and d. Our treatment of the Jackson network optimization problem (and hence the microservice autoscaling problem) as an OCO problem depends upon the assumption of stability (i.e., job arrival rates do not exceed service rates for prolonged periods), and in our experiments we took measures to ensure that stability was not violated in a way that prevented the algorithms from recovering. Measures ensure stability are detailed in Appendix G.
Limitations:
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
Research was funded in part by NSF grants CNS 2312978 and CISE Expeditions in Computing CCF-2326576. All opinions expressed are those of the authors, and need not represent those of the sponsoring agencies.
REFERENCES
Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Annual Conference Computational Learning Theary, 2010. URL https: /api. semant i cacholar. wtt.ooorgr/opouueeeee ID: ID:1 83 4530.
Krishnakumar Balasubramanian and Saced Ghadimi. Zeroth-order nonconvex stochastic optimization: Handling constraints, high dimensionality, and saddle points. Foundations of Computational Mathematicx, 22:35 76,
2018. URL https:: /api...... wemant cwc.nicccccl.r........oo.. org/ Corpus ID: 58004708.
S.. Bhatnagar, HL Prasad, and LA Prashanth. Stochastic Recursive Algorithms for Optimization: Simultaneous Perturbation Methods. Springer, 2013.
Vivek S. Borkar, Vikranth R. Dwaracherla, and Neeraja Sahasrabudhe. Gradient estimation with simultaneous perturbation and compressive sensing. Joumal of Machine Learning Research, 18(161):1-27, 2018. URI.
http:// htnt:://mmm...e wrg. wtt. wwwprr///pppp/////eeeeee/eeee 5
5- 59m.mmmtl..
Sébastien Bubeck, Ofer Dekel, and Tomer Koren. Bandit convex optimization: VTT) regret in one dimension.
In Annual Conference Computational Learning Theory, 2015. URL https://api semanticscholos
org/CorpusIID:11e 11: 14672274.
HanQin Cai, Daniel McKenzie, Wotao Yin, and Zhenliang Zhang. Zeroth-order regularized optimization (zoro); Approximately sparse gradients and adaptive sampling. SIAM Journal Optimization, 32(2):687-714, April 2022. ISSN 1095-7189. doi: 10.1137/21m139266. URL ht //t:://dxxx// doi. http:/xxddooo..rgggo/. 292139.966.
Emmanuel Candes and Terence Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE transactions on information theory, 52(11):5406 5044554066555,,000 2006.
Emmanuel J. Candès. The restricted ismmett property and implications for compressed sensing. Comptes Ren-
dus Mathematique, Maahhemaiique,344669583338-----3 34669)599--9922 2008. 2008. ISSN 1631-073X. doi:
00.0114. URL https:ttps..... www. http::/wwciinnnereettt...cc com http://weeeeeeeeeeeeeeeeeeeeeeee http:///t......c.......aaaaaaaaa
Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders. Atomic dccomposition by basis pursuit,
SIAM Journal on Scientific Computing, 20(1))33-61, 1998. doi: 10. 10.1137//100444755666000000 URL
https: /tc./cciic/// wwt.crgg////. 1t1.//1104427396300000
Varsha Dani, Sham M Kakade, and Thomas Hayes. The price of bandit information for online optimization. In Platt, D. Koller, Y. Singer, and S. Roweis, editors. Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007. URL /tttps://ppoooee /ttp://ecoocccesseeeee neurips ce/ papper.... files/ /ailes//pper/20011 http:/2000///ieeee// http///eeeeeeeee/eeeeeeeee 68ca4 6b wtw.eeeaaaa....eeeeeeeeeeeaeaee. bdaleeaabbbeeeeelaaaaaaaaee Paper. paf.
Yonina Eldar and Gitta Kutyniok. Compressed sensing: theory and applications. Cambridge university press, 2012.
Abraham D. Flaxman, Adam Tauman Kalai, and Н. B. McMahan. Online convex optimization bandit setting: gradient descent without a gradient. ArXiv, cs.LG/0408007. 2004. URL https:
//api. semant inaaniicson icscholar org Irg/CorpusID: 32:4:3224230
Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Birkhäuser New York, NY, 2013. doi: 10.1007/978 00----8811
Yu Gan, Yanqi Zhang, Dailun Cheng, Ankitha Shetty, Priyal Rathi, Nayan Katarki, Ariana Bruno, Justin Hu, Brian Ritcheen, Brendon Jackson, Kelvin Hu, Meghna Pancholi, Yuan He, Brett Clancy, Chris Colen, Fukang Wen, Catherine Leung, Siyuan Wang, Leon Zaruvinsky, Mateo Espinosa, Rick Lin, Zhongling Liu, Jake Padilla, and Christina Delimitrou. serdware-softwarr implications for cloud edge systems. In Proceedings of the Twenty-Foou International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '19, page 3-18, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450362405. doi: 328183297788.28 3304013.
open-source benchmark suite for microservices and their
10. 011.5/229788.334000 URL https: /oii http:////oooooo....eeeeo
11

---

Published as a conference paper at ICLR 2025
Elad Hazan al. Introduction to online optimization. Foundations and Trends in Optimization, 2(3-4); 157-325, 2016.
Sherif Hosny, M. Watheq El-Kharashi, and Amr TT Abdel-Hamid. Survey on compressed sensing over the past two decades. Memories Materials, Devices, Circuits and Systems, 4: 4:10066, 2023. ISSN 2773- 0646. doi: https://boi..or///00001/// wwt.:///.....mmmmm.......... 100060. science/articler paieeleeppii/S/e (ttp/////2776242322232222 62300433
com/
Xiaowei Hu, Prashanth L. A., András György, and Csaba Szepesvári. (bandit) convex optimization with biased
noisy gradient oracles, 2020.
Darby Huye, Yuri Shkuro, and Raja R. Samhasivan. Lifting the veil on Meta's microservice architecture: Analyses of topology and request workflows. In 2023 USENIX Annual Technical Conference (USENIX ATC 23), pages 419-432, Boston, MA, July 2023. USENIX Association. ISBN 978-1-939113-35599 URL
https:/ /tl:://wwwww /www. usenix wwtgg//oofeeeneeeeeeeeeeeeeeeeee http://teeeeeeeeeeeeeeeppeaaaaaa
Shinji Ito. An optimal algorithm for bandit couvex optimization with strongly-oovvr and smooth loss. In International Conference on Artificial Intelligence and Statistics, 2020. URL https://api. semanti cschclar arg/Corpus
ID:20009525
Daniel Jordon. Queueing-tool: a queueing network simulator, June 2023. URL URt.https://gtthubbb
tool. License: MIT.
Tor Lattimore. Improved regret for zeroth-order adversarial bandit convex optimisation. ArXiv, abs/2006.00475. 2020. URL https: / app. semant icscholar worpsooororrrrrroooooooooooo ortg///orrpsssi122111221111
Tor Lattimore and András György. A second-order method for stochastic bandit convex optimisation. In Annual Conference Computational Learning Theory, 2023. URL ht
iaschnncccccccra. org/
Corpus ID: 256808773
Shutian Luo, Huanle Xu, Kejiang Ye, Guoyao Xu, Liping Zhang. Jian He, Guodong Yang, and Chengzhong Xu. Erms: Efficient resource management for shared microservices with sla guarantees. ASPLOS 2023, page 62-77, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450399159. doi:
10.1145/3569555.366777
URL https: dol org/10l/////0 /11145//569555 3467964.
D. Needell and J. A. Tropp. Cosamp: Iterative signal recovery from incomplete and inaccurate samples, 2008.
URL https: /ttp/varvvvvvvvvv////v//eee///vv wttgg/abb/0800..0
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19149 doi: 10.1137/ 070704277.
Haoran Qiu, Subho S. Banerjee, Saurabh Jha, Zbigniew Kalbarczyk, and Ravishankar Iyer. FIRM: An intelligent fine-grained resource management framework for SI.O-Oriented microservices. 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 805-825. USENIX Associa- tion, November 2020. ISBN 978-1-938 11-199933-311999 URL https:t::/ /www. usenii org conference// osdi20 presentation. /
Vighnesh Sachidananda and Anirudh Sivaraman. Erlang: Application-aware autoscaling for cloud microservices. In Proceedings of the Nineteenth European Conference Computer Systems, EuroSys '24, page 888-923. New York, NY, USA, 2024, Association for Computing Machinery. ISBN 9798400704376. doi: 10. 1445/
3027703.3650084 URL https: /oo. http://i..oooooo//// 1111111133330 3555/66277333 3650084.
Ankan Saha and Ambuj Tewari. Improved regret guarantees for online smooth convex optimization with bandit feedback. In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 636-642, Fort Lauderdale, FL, USA, 11-13 Apr 2011. PMLR. URL https: / http///eccccccccccceeeeeeec
wtwp:cceeeinng.......ee.... mlr. press v//////55/aaallla saaallal.... hht..
James C. Spall. Multivariate stochastic approximation using simultancous perturbation gradient approximation.
IEEE Transactions on Automatic Control, 37(3)3332-341 1992 doi: 10.19 119632.
Rayadurgam Srikant and Lei Ying. Communication Nenworks: An Optimization, Control and Stochastic Networks Perspective. Cambridge University Press, USA, 2014, ISBN 1107036054.
Yining Wang. Simon Du, Sivaraman Balakrishnan, and Aarti Singh. Stochastic zeroth order optimization in high dimensions. In Amos Storkey and Fernando Perez- Cruz, editors. Proceedings of the Twenty- International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1356-1365. PMI.R, 09-11 Apr 2018. URI. https: /ttp::////rccec//p//p ngs. big..n ml press/ / v84 wang1 8e. html.
12

---

Published as a conference paper at ICLR 2025
Zibo Wang, Pinghe Li. Chieh-Jan Mike Liang. Feng Wu, and Francis Y. Yan. Autothrottle: A practical Bi- Level approach resource management for SLO-Targeted microservices. In 21 USENIX Symposium on Nenworked Systems Design and Implementation (NSDI 24), pages 199-165, Santa Clara, CA, April 2024. USENIX Association. ISBN 978- 1-939133-399 URL ht / /www, uswnix. org/ cccfcrrncccr heti2///peeentatioo wwa.iiioo/wwnnggnnee wttp//anngg-aaaaa
Yanqi Zhang, Weizhe Hua, Zhuangzhuang Zhou, G. Edward Suh, and Christina Delimitrou. Sinan: MI-hased and qos-aware resource management for cloud microservices. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '21, page 167-181, New York, NY. USA, 2021. Association for Computing Machinery. ISBN 9781433383172. doi: 10.11445/3445144444460060
URL httpstpppp. /ttp:///o/..../////////// 0
22114444484444444999 3446693.
Yun-Bin Zhao and Zhi Quan Luo. Improved rip- bap-based bounds for guaranteed performance of two compressed sensing algorithms, 2020. https: /tapsi///////.//// org/ /ttpg/aa////..... 01451.
A RELATED WORKS
Zeroth-Order Online Convex Optimization: Online Convex Optimization (OCO) game in which an online player iteratively makes decisions drawn from a convex set. Upon committing to decision, the player incurs a loss, which is possibly advesarially chosen convex function of the possible decisions and is unknown beforehand. The performance metric for this problem is typically the static regret based on the best action in hindsight, see Hazan et al. (2016) for a good introduction to the topic. In this setting, there are different levels of information that learning algorithm may have access to. The first is full information, where the full objective function chosen by the adversary is revealed after the corresponding cost is incurred. If the objective function is also smooth, then regret which scales as /T is achievable by simply running a gradient descent algorithm on the gradients of the revealed functions. Another level of information is bandit information (Dani et al., 2007: Saha and Tewari, 2011) 1), where only the loss is revealed; in this case it is common to rely on zeroth-order methods for gradient estimation. Several works have not only been able to characterize information theoretic minimax regret bounds under bandit feedback (see for example Lattimore (2020); Bubeck et al. (2015)) but have also provided algorithms that can achieve these bounds ( Flaxman et al. (2004); Balasubramanian and Ghadimi (2018); Ito (2020); Saha and Tewari (2011); Lattimore and György (2023) to name a few). An intermediate setting between these two extremes allows the algorithm to collect a limited number of samples from the objective function after incurring the loss, which opens up more options for zeroth-ordee gradient estimation procedures. Our work belongs to this setting. A general oracle framework for zeroth- gradient estimation procedures using one or more samples in the OCO context is developed in (Hu et al., 2020).
Related Work:
Simultaneous Perturbation Stochastic Approximation: The most basic form of SPSA, due to (Spall, 1992), is a method for computing an estimate of (xx))) using only zeroth-order information with only two evaluations of the objective function regardless of the dimension of æ. Naively, one may compute an approximate measurement of the gradient at x along one dimension using the finite difference:
0f(x) f(x + de,) - f(x)
(9)
Or;
8
Where e; is the unit vector in direction i, and is the smoothing parameter which controls the bias. However, for a high-dimensional problem this requires least d measurements in addition to f f(x) to estimate the full gradient which might be infeasible due to the time or effort required to take a measurement. The alternative provided by SPSA is as follows: First, generate a sequence of i.i.d. Rademacher random variables, [ Next, generate, a perturbation vector A = Ej= eyAj. Finally, we may compute our gradient estimate as follows:
f(x - 8 - f(Ø) 0f(x) رA,
0f(x) A:
dx.
Oz, A
When the expectation is taken over the randomness in A, the terms in the summation are eliminated and hence this method gives an approximately unbiased estimate of fz for appropriately small be reduced by repeating the process for different random draws 8. The variance in the estimate of A and averaging over the results. The SPSA method provides a way to handle figg--immnssioall problems when the number of available measurements is limited, but it does not directly exploit the
13

---

Published as a conference paper at ICLR 2025
sparsity of fx))). For further details about the qualities of the SPSA method, see Bhatnagar et al. (2013).
Results in compressive sensing (Foucart and Rauhut, 2013; Candès, 2008) state that given mcasurements of the form y = Ax e where æ is a sparse vector, A is an m x d matrix (called the measurement matrix) satisfying the restricted isometry property (RIP) appropriate to the sparsity of æ, and e is bounded measurement noise, an approximation & can be obtained through various recovery methods such that || æ æ||2 is bounded by a quantity proportional ||e| 2- In this context, vn is called the number of measurements; in most practical situations one wants m to be as small as possible. The recovery step can be formulated as the nonconvex optimization problem
Compressive Sensing:
min ll subj. to ||Aæ y112 S ||e|2z
(10)
which must be relaxed or approximated in practice. For measurement matrix A and integer one may define the Athh restricted isometry constant (RIC) (A) that preserves the RIP property for any k-sparse vector. Concretely, for any k-sparse vector x, we need to ensure
(1-64) [ S A (1+ 6
Loosely speaking, we say that A satisfies the RIP for a given & if 6g is small (how small we need it depends the use case). It turns out that a measurement matrix with sufficiently small cs RIC with e being a small scalar (dependent upon the recovery method) will allow the recovery of any 5-sparse vector. Furthermore, it is known that increasing m increases the likelihood with which A will satisfy the RIP for a given RIC. However, current guarantees for deterministic measurement matrices require m scale (ss²) while for random matrices superior Oss log )z)) scaling is achievable (though there will necessarily be a probability of failure) (Foucart and Rauhut, 2013). The available recovery methods can be broadly grouped into those based on greedy algorithms and those based on convex relaxations of equation 10 (Hosny et al., 2023). One example of a greedy algorithm is Compressive Sampling Matching Pursuit (CoSaMP) from Needell and Tropp (2008), and one example of a convex relaxation is basis pursuit (first introduced by Chen et al. (1998)). The general approach of CoSaMP is to iteratively construct a sparse vector which is as close as possible to the target vector; the goodness of the estimate on each iteration is estimated using least squares. Basis pursuit, on the other hand, replaces the O-norm in equation 10 with the 1-norm which is convex. Solutions to the convex optimization problem can then be approximated using various possible solvers.
Regularized Gradient Estimation: In the zeroth-order stochastic optimization setting, where noisy samples from a static convex objective function are used to iteratively approach the function's 's minimum value, prior works have considered gradient estimation techniques which exploit sparsity in the objective function gradient. Among these is Wang et al. (2018) which uses the Lasso method to recover the gradient from set of measurements taken in the same fashion as in SPSA. An important distinction between this technique and other gradient estimators which take multiple samples is that the value of the objective function the current control is not used by the estimator, but rather is estimated from the data. Lemma in that paper indicates that the sample complexity required to achieve bound on the gradient estimation error is on the order of s², while the compressive sensing schemes underlying CONGO-Z and CONGO-E only require number of samples linear in This suggests that the Lasso method is less sample efficient (at least in the noiseless case which is more commonly analyzed in the OCO setting). We have not seen any work up to this point which has attempted to apply the same technique to the OCO setting.
Microservice Autoscaling: Prior approaches have tried to use several variants of learned models as controllers for the task of allocating resources to microservices. At a high-level, all prior works either rely on heavy complex training regimes, which can be infeasible in practice or make simplifying assumptions as they do not exploit the sparsity in gradients. We briefly summarize several such approaches here.
Many prior works (Qiu et al., 2020; Zhang er al., 2021; Luo et al., 2022) rely on complex and heavy offline training mechanisms. This is especially challenging in the microservice setting where frequent re-training might be necessary because applications are regularly updated leading to changes in microservice behavior and even application graphs (Huye et al., 2023).
FIRM (Qiu et al., 2020) first uses an SVM model to identify the critical bottlenecked service, and then uses an offline-trained DDPG-based model to change the resources for the critical service. A
14

---

Published as a conference paper at ICLR 2025
key drawback of this technique is that training FIRM requires anomalies to be injected by artificially inducing resource bottlenecks in the system which can be either impossible or too expensive in many cases. Injecting resource constraints might be infeasible if the application is run a third- party cloud provider. On the other hand, it can be expensive if the application undergoes frequent changes/updates.
Sinan (Zhang et al., 2021) predicts a given resource allocation set for a microservice application can lead latency violations. Using the predictions, it then relies on a heuristic choose the next control action. Sinan has two drawbacks, First, training the latency violation predictor requires extensive data on various resource allocation and workload combinations, which again impractical. Second, the heuristic to change resource allocations might not be general enough for all applications.
Erms (Luo al., 2022) approximates the latency-throughpue curve for each microservice as piecewise linear function and employs techniques to prioritize latency-critical services at shared mi- croservices. The assumption piecewise linear function can be too simplistic for most microservices. Especially, at the inflection points, when a small change in the request rate causes high changes in the latencies, even small error in the piecewise linear estimation can lead drastically bad performance.
Autothrottle (Wang et al., 2024) uses online RL mechanism using contextual bandits and thus, alleviates the problem of offline training to great extent. However, because Autothrottle does not exploit the sparsity in gradients of microservices, it is forced make simplifying assumption by clustering all services into just two clusters, leading to the same action for all services in the same class. This would imply that even if one microservice is the bottleneck, in expectation, it could lead to more resources being allocated for roughly half of all the services!
Erlang (Sachidananda and Sivaraman, 2024) is another such online RL-based system for microservice autoscaling, that uses a multi-armed bandit algorithm to choose the right resource allocation, given congested microservice. However, Erlang relies microservice in the first place. The heuristic is to just use the service which has the highest change in CPU utilization. This heuristic may hold in many cases, for example, when the CPU utilization of microservice may be high because it is continuously polling on downstream microservice (Gan al., 2019).
simple heuristic to choose the congested
B DESCRIPTION OF CONGO-B ALGORITTH
In this section we give details for the CONGO-B algorithm, including the pseudocode in Algorithm CONGO-B -BB takes inspiration from Algorithm 1 in Borkar et al. (2018). The functional differences between that algorithm and the gradient estimation procedure used in CONGO-B are summarized below:
We scale the perturbation by |A AlI
We rescale A' and y by / right before the recovery step
We introduce an additional constraint to the basis pursuit /1 /1-minimization problem to ensure a specific bound on the gradient estimates used for gradient descent steps
We emphasize that the inclusion of the additional constraint does not affect the applicability of the recovery result used in the proof of Lemma 2. To see this, note that under any outcome where the solution to the /1-minimization problem without the second constraint satisfies || (V)()))((())) S 3LS. we also have fe < 3LS + [|Vf((z;)ll < 3L8 + Ly by the triangle inequality. and hence the second constraint is immediately satisfied.
15

---

Published as a conference paper at ICLR 2025
Algorithm 2 CONGO-B: Compressive Online Gradient Optimization Borkar Version
Require: Constraint set K. Horizon T, Lipschitz constant y, Smoothness parameter L, Parameters (m-)==1 8, m, Initialization point 2
for 1,2,.... T do
A <- randomly drawn x d matrix with (0,, 1) entries
D Generate measurement matrix
Query f((2t)
for | = 1,2,
do A' < random m-dimensional vector of Rademacher random variables
Query at point at + ō||A ||2 AA A' to get (a + 6 2 A 0| 2 AA T
3 [x(
A [xx))
for = 1,2, ... , do
1/ 81A4115'
Construct from measurements
end for end for y (
E vi. Etn wim
Average over observations
Rescale A' and by mm if There exists feasible solution x" for min ||||| subj. to || 2/112 s 3L0 and |||||2 S Lg 31.
Constrained gradient recovery
then
V (xx,) 2²
else
V fi (xx) t
end if
1t++
argmin| =EK
[ac (zz: 77 (a)))))
Gradient descent update
end for Incur regret
Σt f((x))) f+(x*)
C PROOFS
C.1 PROOF LEMMA
Proof. We begin with the case where
||a:||3
1/4
f(x
|all
a.)
f(x)
vi
[m]]
Applying the Taylor approximation given in equation 6 and the bound given in equation 7, the expression simplifies follows:
|a;
2
|
1
(x(x).
y/
||a
8
6
2
a 2
(V](z)) ad) +
|a
||a
5
L
< (VI(x), +
It follows that = (z) + where each element of e is bounded by 4.8. Since e E R" we have |/el|2 < /
Now we turn to the case where
8 AT
|ATAI 13
31 f(x +
f(x))
Vi E [m]
ATAI
16

---

Published as a conference paper at ICLR 2025
Simplifying as before gives:
|ATAI
I
1/1
V
A
ATA
AA,
+
S4,
m
LI
|A
|ATA
2 2
8
j=1
(Vf(2), a.)
(Vf(z), ay) +
A
336
we let [ei]: Ejqi ( and [02], = IIAT 13 A.
62. we have y = AVf(z) +e + e2 as
desired, and as before we have | S 5
C.2 PROOF OF THEOREM 1
C.2.1 ADDITIONAL LEMMA FOR THE PROOF OF THEOREM
The proof of Theorem I requires the following lemma from (Nemirovski et al., 2009) expressed in our notation below.
Lemma (Lemma 2.1 of (Nemirovski et al., 2009)). Let V.(...) be the Bregman Distance the a-strongly convex distance generating function w. and let Pz() ) be the proximal mapping associated
(.)
with w. Then for every u E K, x E K', and y Rd,, has
1
V=(Pa()), u) S VI) + (v, x)
20
Using x Tr and y T/. fx,,). we ger
m (2 u, f((x))) S Valar, (z(41,
[ff(()))11
2a
This result applies generally to mirror descent algorithms, but since projected gradient descent can be viewed as a special case this in the Euclidean setting, we simplify to equation 11 (This form appears in equation 2.6 of (Nemirovski et al., 2009), where the expectation is taken over all of the terms).
(V.i(x)), u)
1 ( M
1
2x112
2
11u xe+ 113
Tht "IVV[(
(11)
C.2.2 ASSUMPTIONS
The following must hold for all t [T]:
[)))()))) fi(a))) M8 with probability at least for some M independent of T
|IVA( S M6 Ly
C.2.3
PROOF THEOREM
Proof. First, we apply the law of total expectation and the above assumptions to derive a bound on f...))) fe(r.)) [|]]
The second assumption implies that with probability 1,
[,,,) v.f. < M8 + Ly (x:))l < M6 + 2Lg
Let E denote the event fxx V=(((=))] M8 and E its complement. By the law of total expectation.
Vf((z;) - vf((z
-| = || f((z)) - vi(wx))
E PP (E)
E ((((z) v.(((e))
E P(E))
1
< M8 + (M6 + 2L,) -
17

---

Published as a conference paper at ICLR 2025
where the bound P (E) < 1.
Now, informed by the approach in Section 7.2 of (Hu et al., 2020), we seek to show that on each round the regret of our algorithm compared to any arbitrary point, which includes mill ΣT-1 fi(x"), is sufficiently small. We begin by applying the convexity of fe:
T
IE
Σ f((x)) - Σn(t) f(()
S E
(e(( xe -
t=1
T
(f(((z)) - V.(((t)) -z))
E
(2te())), x4- +
-
S E
(Vi(())) xx)
E ||| [ &li 1koee 2112
< E
(1)) -x)
E 2R V
+ 2RT M6 + (M6 -2 +
E
(V - x)
Focusing the remaining term, apply Lemma 3 in the form given by equation 11, where let 2 x. Thus, by telescoping.
T
T
(m:
E
fe(x))) 24 - x))
SE
E
||
rel13
2 211x0 x2+1113 + m
2
1=1
D
E
TT- -1
where
sup 11100 - u1l.. Now, we are assuming that [(>x(() S M6 Ly, and hence a.yEk
D+
D
R(M5 L
E
Σ
(fi(aa)) - 2))
Σ
17-1
t=1
Putting things together, we have
D
R(M5 + L,)
E
f((z))
Σ f(()) <
Σ
Tn-
1=1
t=1
(12)
M6 + (MS + 2L,) 1
+ 2RT
Plugging in 7) = 1 and choosing 8 = 1 MT gives us
LsVT
E
((((8))
-
-E f((x) DDDTT VT
T
R(
2T.
+
+R +
2R
T
+ ARLs
R
R
RLTVT
2R
DLLVVT
+2R +
ARL
2L
VT
2
For large T', the terms which dominate are those which scale VT. Isolating those terms gives us the asymptotic regret of O(D + R LyyTT))
C.3 PROOFS OF THEOREM AND THEOREM
C.3.1 PROOF OF LEMMA 2
Proof. All of the existing results used in this proof come from Foucart and Rauhut (2013). We use several of their results to determine how large must be guarantee recovery with sufficiently
18

---

Published as a conference paper at ICLR 2025
high probability. In this context, for the measurement matrix A and integer ie one may define the kth restricted isometry constant 6x [A) as the smallest such value for which A satisfies the RIP property. Concretely, for any k S-sparee vector æ. need to ensure
(1 - 6x || I || I (1+ +6))1=111
Indeed, Corollary 9.3, which applies to both Gaussian and Bernoulli random matrices, gives lower bound on the probability with which the matrix will satisfy the 6x-RIP for some integer k:
eed"
(6 8) 2 if C'5-2
Io
A: log((c
Note that the values of and required by different recovery methods differ. We will be interested & 2s for basis pursuit and = 4s for CoSaMP. Theorem 6.12 states that sufficient to have d2. < 0.6246 when basis pursuit is used, while Theorem 6.27 states that it is sufficient to have dis < 0.4782 when CoSaMP used. (This requirement has been improved upon more recently (Zhao and Luo, 2020), but do not focus optimizing constants here). In the case of basis pursuit, when the RIP holds we get the following bound on the recovery error:
CBP
[[a;)) (m())ll2 S
[V/((a))) + CBP mm ||e|2
Vs
where e = y - A f((;)) is the measurement error before rescaling by 7m and CT and C are constants depending only on 02g. In the case of CoSaMP, we instead get the following bound:
_
[V;)) (a,))) |= fi(a))ssl
CoSSaMP mm
A (A' + ell2
where 1, is the number of iterations of the CoSaMP algorithm, and C'SSaMP is constant
depending only on dis-
Under the assumption that fa,;) is s-sparse, f(((x)s fz(,) and Vf(w)) 0 so the bound for basis pursuit becomes
(x;) ff(x))l S C
|ella
Furthermore, if we assume n is sufficiently large that the pa1 | fe term vanishes on every round, then the bound for CoSaMP becomes
f((x)) fi(xx))la S C CoSuMP
|ell
Vm
Thus in this specific case, both basis pursuit and CoSaMP give recovery error proportional to ||e/ l- For CONGO-Z and CONGO-E to be implementable practice, necessary to give bounds on CRPP and CCSMMP From the proofs of Theorems 4.22 and 6. we can deduce that
(Vi 82 22
V1 + 82.
BP < 4
4 82 fu 823
(VI Ozs faz)
One can easily verify that 82. 0.6246 implies CBP For CoSaMP, from the proof of Theorem 6.27 we find that
2(1 + 362 2 das
CoSaMP =
1
81s
and one can easily verify that 52s 0.4782 implies CosSaM
7.21.
Remark 2. According Section 9.3 of Foucart and Rauhut (2013). for Gaussian matrices the best known lower bound for C" that allows these results to hold generally is around 80; but when d is sufficiently large this be improved considerably. Much like Cai et al. (2022), we ignored this large theoretical constant in our experiments and still achieved good performance.
C.3.2 PROOF OF THEOREM 2
Proof. We first find M such that the assumptions for Theorem I hold for CONGO-B. Our analysis begins a similar fashion to the proof of Theorem in Borkar et al. (2018), but due to our modifications the gradient estimation procedure and the recovery guarantee from compressive
19

---

Published as a conference paper at ICLR 2025
sensing used able obtain different bound that is suitable for purposes. By Lemma 1, the vector y of measurements collected on round t satisfies
y = (Vi( aL) +
1 ke
Σ
cef + +c)
where -efl=Ej Σjji (((()))))))))) and ||e/|2 s 50.m vi E [Kr] To bound the overall error, we A will use the averaging over i to control the magnitude ej and ignore the averaging on e2 since we can use ò to control its magnitude instead. Define 7 ddmm We wish to set ky such that
(V af))
P
(13)
A
m
2mT
i=1
which, via union bound, will ensure that ||el
e2 la S
2y with probability at least 2T We
( A
and Ejji ()(1112))))))
apply Hoeffding's inequality, noting that E
S
A
(m 1) max, (V fa at) s (m L)L,G, where we introduce the notation G = max; ||
This gives us the following:
-2k?
IP
exp
A
vm
m(m - 1)3((s))
Thus we must solve the following to find the desired value for ky:
2
exp
m(m - 1)>(L))
2mT
The solution is
m(m - (1)
k 2
log(2mT)
272
(14)
4(m (1
l2g()
I2202
We round up this value ensure hs is integer. We can apply Lemma 2, which gives the following guarantee:
(x.)) (((x))) S 6y 3L8
which holds with probability at least ( + E) as long as
m 2 (".66444)) -2 s slog
+ log
Setting = 2T ensures that assumption of Theorem is satisfied. Assumption 2 is also satisfied because replace (xx)) with the zero vector when it exceeds 3L5 + Ly. The desired bound on the expected regret follows from Theorem with M = 3L.
As requirement of Theorem I, must set 8 377' 3LT Note that G found in the expression for k; a random variable which is only known once A f drawn, hence the reason why the number of samples to average over varies for different rounds. we finish by bounding the expected value of ke (which is the same on every round since A drawn the same way on every round). To do so, we
20

---

Published as a conference paper at ICLR 2025
must bound E [G²]
max; || Let Y max; |a
and observe that
exp
tE [Y) < E exp (tY)
m
exp
|
11
1=1
E
exp
(d|la)1B)
eexp (+]
m(1 21)-
$ 11 E (0,
Where we apply the moment generating function of x (d) distribution. Taking the logarithm of both sides and dividing by f gives us
B 2t
log
m
1 2t
Choosing = 1 yields
G = E YJ s 2d log
Plugging these values into the expected value of Kg as
E [kg] 36d(m 1)² L3 12m(2m) yT log log(2ml))
C.3.3 PROOF THEEREM
Proof. As in the proof of Theorem 2, we first find M such that the assumptions for Theorem hold. Lemma tells us that the error must account for in the recovery process is bounded by S f which after rescaling becomes 48. Lemma 2 tells us that M 1.21 L sufficient if we have
m 2 (0.047782 <log
+ log(22
Note that the value of C' is different for CONGO-Z and CONGO-E due the different measurement matrices (this is in fact the only difference the proofs for these algorithms). We set + to satisfy
Assumption 1. Assumption 2 is also satisfied because we replace f((z) with the zero vector when exceeds 7.21 Lő + Ly (respectively " Lö + Ly in the case of basis pursuit). Applying Theorem 2 finishes the proof.
D MOVING FROM STOCHASTIC OPTIMIZATION TO ONLINE CONVEX OPTIMIZATION
Here we further discuss the rationale behind some elements the CONGO framework. We mention in Section 4 that it is necessary to enforce limit the magnitude of any gradient estimate that is applied as a gradient descent step. This requirement arises from the use of Lemma when we bound the cumulative regret in Theorem 1, which introduces a term involving //V (xx:)) Without a bound on the magnitude of the gradient estimates that holds with probability one, it becomes difficult to deal with this term in the regret bound. Note that an analysis like the one for stochastic optimization setting in Cai et al. (2022) which yields high probability bound by conditioning matrix being "good" does not have to worry about issues like this because it can rely on a recovery guarantee holding. Now, if we know bound L, on the norm of the true gradient, then it makes sense to enforce a bound on the estimated gradient equal to Lg plus the maximum error we are willing to tolerate, since know that any estimate which does not satisfy this bound is not useful
the measurement
Since
21

---

Published as a conference paper at ICLR 2025
this is rare event (as proven in Lemma 2). we can afford to skip the gradient descent step to avoid making a very large step which may be in a bad direction. An example of this in practice is given in Fig. 7. Note that consequence, it is necessary to know a bound on Ly in order for the theoretical guarantee to hold.
As also mentioned at the end of Section 4, under the CONGO framework we sample new mea- surement matrix on each round. In the ZORO algorithm, a single measurement matrix is sampled the start and reused for every gradient estimate. This makes sense when the goal is obtain nigh-probability sample complexity bound since one only needs to bound the probability of a single event rather than a separate event for each round. However, when the goal is to prove bound on the expected regret as in our case, it becomes irrelevant whether the matrix is drawn once overall or on each round. This because applying the law of total expectation on the entire cumulative regret leads to the same result as applying it to the gradient estimation error does. We choose to re-sample the measurement matrix on each round to eliminate the possibility of a single "bad" measurement matrix ruining all of the rounds, and hence we apply the law of total expectation to the gradient estimation error alone. The fact that we are pursuing a bound on the regret in expectation also influences how we choose After applying the law of total expectation, it remains necessary bound the gradient error when compressive sensing recovery fails which necessarily introduces a term that does not scale with 6; to compensate for this we need the probability of failure to decrease as T increases. This is why our choice of m for the theoretical results depends logarithmically on while in Cai et al. (2022) it does not. On the other hand, if one simply wants bound on the regret which holds with a high probability independent of I' then the method of sampling a single measurement matrix at the start could be adopted, in which case could be the desired probability instead of 7 since the magnitude of regret when the high probability event does not occur no longer matters.
E PRACTICAL IMPLEMENTATION OF RECOVERY METHODS
Here we justify our choice of the CoSaMP algorithm for CONGO-E based on practical considerations. Basis pursuit is in theory a good candidate for recovery algorithm because it allows for fewer measurements to be used than methods like CoSaMP and Iterative Hard Thresholding (this can be seen by comparing the requirements on the restricted isometry constant for each algorithm; see Chapter 6 of Foucart and Rauhut (2013)). However, the practical implementations of basis pursuit have poor runtime guarantees compared to greedy methods like CoSaMP (Hosny et al., 2023). Empirically, we have observed that for the same tolerance level and limit the number of iterations, the implementation of basis pursuit using Chambolle and Pock's 's primal-dual algorithm (see Section 15.2 of Foucart and Rauhut (2013) for the pseudocode) is indeed slower than CoSaMP. Fig. 5 compares the CDF of the execution time for the two methods; observe that the curve for the primal-dual algorithm stays the right of the curve for CoSaMP. Furthermore, using basis pursuit for robust recovery requires one to have a bound on ||el|2 which will hold with high probability whereas CoSaMP only requires an estimate of the sparsity level (Needell and Tropp. 2008). Based on these considerations, we rely on the CoSaMP algorithm for the implementations of CONGO-Z and CONGO-E used in our experiments, For CONGO-B, we use basis pursuit to remain faithful to the method proposed by Borkar et al. (2018). Note that both CoSaMP and basis pursuit have additional hyperparameters which determine the tolerance and maximum number of iterations to run; the exact values used are given in Appendix G.
F ADDITIONAL NUMERICAL SIMULATION RESULTS
F.1 ANALYSIS OF THE IMPACT OF DIFFERENT CHOICES FOR mI
In our numerical simulation environment, we ran experiments to test how the quality of the gradient estimate from CONGO-E with CoSaMP changes as varies, and to see if the value of 2s log (3) prescribed in the theoretical results (ignoring the log(T') term) is in fact good choice in practice. First, we set d = 50, s = and R = 50 and ran CONGO-E for each of the values of m in the range [6,24] on the same environment with the same 50 random seeds. We computed || fz:;)) - f(2)))) on each round for each algorithm and averaged over all the measurements at the end. Fig. 6 shows bar graph of the average errors for the different values of m. Note how the error rapidly drops after
m 15; in this case, 2s log ( 23.026 so would be 24 after rounding up. This is clearly in the
22

---

Published as a conference paper at ICLR 2025
CoSas
mariice [ic)
Figure 5: Comparison of the CDFs for execution time of basis pursuit and CoSaMP over 1000 exccutions.
trad vs, seb and dego
Effect of Enforing Gredient Limit for
2000
Enforcer
Accumuatedd Cod
Limit Not Enforced
1500
500
00
00
100
Boand
Figure 7: Comparison of the the cumulative cost with and without enforcing limit on the gradients used for online gradient descent in the case where m is insufficiently large
Figure 6: Bar graph showing how error in the gradient estimate changes more samples are used.
region where the gradient error is very small and so there no need increase m further. Note that we also ran the GDSP algorithm under the same conditions with total of 26 samples per gradient estimate (including the sample for (xx)) and found that the average norm of the gradient error was 31.64, far higher than CONGO with even just 16 samples per gradient estimate. Surprisingly, however, we observe a very sharp spike in gradient error for m = 13, 14, and 15. This is accompanied by abnormally large values in the gradient estimates. Further investigation found that this was not simply caused by poorly conditioned measurement matrix, since the maximum and minimum eigenvalues of A were not outside the ordinary range when these highly erroneous gradient estimates were made. The anomaly occurs both for basis pursuit and CoSaMP. While we do not know the exact cause of this behavior, the implication is that allowing m be significantly smaller than the prescribed value runs the risk of very poor performance. Of course, due to the constraint on the magnitude of the gradient estimate, when this anomaly occurs its contribution the cumulative regret will be limited. To illustrate this, we compared the cumulative regret for certain value of m with and without enforcing the gradient limit (see Fig. 7) and observed that for m significant amount of regret could be avoided.
F.2 ANALYSIS OF ROBUSTNESS SPARSITY LEVEL
To demonstrate that CONGO-style algorithms (particularly CONGO-Z and CONGO-E) can still be useful in scenarios where (i) is not significantly smaller than d, (ii) the gradient is not exactly s-sparse but s dimensions are much larger than the rest, or (iii) the true value of s is unknown and must be guessed with some level of eгror, ran additional numerical simulations for each of these cases using setup similar to the experiments of Section 6.
In the left plot of Fig. 8, consider the noiseless case where d = 50 and test We also set с = in equation to ensure that the cumulative costs come out positive. In this experiment, we allow CONGO-B to three times many samples per round as the other algorithms. We plot the excess cost that each algorithm accumulates over T 100 rounds compared to exact gradient descent. We find that while GDSP and CONGO-B do progressively worse compared to
{5, 10, 15, 20).
23

---

Published as a conference paper at ICLR 2025
Testing Increasing with d= 50 fixed
Approximately Sparse Case with d = 100, =
cumulative Cost (in Excess GD)
500
200
GDSP
400
CONGO-2
CONGO-B
Accumulated Cost
150
GDSP
CONGO
CONGO-E
300
CONGO_Z
100
CONGO_E
200
50
100
12.5
20.0
20 40 60 80
100
Figure 8: Left: Cumulative costs incurred beyond that of exact gradient descent over 100 rounds when s increases while is fixed. The performance of CONGO-Z and CONGO-E is not significantly different from that of exact gradient descent even in low-sparsity situations. Right: Cumulative cost trajectories in a scenario where gradients are only approximately sparse. The CONGO-style algorithms continue to perform much better than GDSP.
Testing for Misspecified s When True s is 10
Cumulative Cost Excess GD)
200
175
150
125
100
75
50
25
0-
4
8
10
12
14
S Given to Algorithm
Figure 9: Cumulative costs incurred beyond that of exact gradient descent over 100 rounds when the value s assumed by the algorithm differs from the true value. CONGO-Z and CONGO-E achieve low excess cost compared to exact gradient descent even when the assumed value of is less than the true value of 10.
exact gradient descent as increases, CONGO-Z and CONGO-E remain relatively stable when using the prescribed number of samples.
In the right plot of Fig. 8, we set d = 100 and s but in this case, the elements of b and the main diagonal of D in equation 8 outside of the "significant" dimensions are scaled by J rather than being set to zero. Thus the objective function on each round is only approximately sparse. Here we set and allow CONGO-B use 3m samples per round as before. One can see that although the performance of CONGO-Z and CONGO-E does not match that of exact gradient descent (as it does in the first experiment of Section 6), is not too much worse. The results support our claim that the assumption of exact gradient sparsity is not required for CONGO-style algorithms to outperform algorithms which do not exploit sparsity.
In Fig. 9, we consider the case where d = 100 and 10 but the value of which the algorithm uses varies. In this experiment we set e and allow CONGO-B to use 3m samples per round (where m is calculated based on the value of available to the algorithm). Furthermore, we allow GDSP to use m 57 samples per round, which corresponds to s = 15, across all comparisons. We plot the excess cost that each algorithm accumulates over T' 100 rounds compared to exact gradient descent. We find that although the performance of CONGO-Z and CONGO-E is poor when the given s less than half the true their performance quickly approaches that of the baseline and does not deviate significantly as the given value of s continues to increase. Thus we see that under the appropriate sampling strategy, the approach is robust to inaccurate estimate of the sparsity. For CONGO-B,
24

---

Published as a conference paper at ICLR 2025
Varying d for Fixed Number of Samples
300
Cumulative Cost
250
200
GDSP
150
CONGO-E
100
1000
2000
3000
4000
5000
Figure 10: Cumulative costs incurred over 100 rounds for different values of with fixed at 5 and fixed 24. Note how the cumulative cost of CONGO-E closely follows the cumulative cost of exact gradient descent, which represents the best we can hope to do.
the performance degrades more significantly as the given value of increases beyond the true value because larger value of m actually introduces greater noise into the gradient estimates which the greater averaging is not able to compensate for.
While there may not be much of a cost in performance for overestimating the value of there is still a cost in algorithm runtime due to taking more samples per round than is really needed. However, there is potential for one adaptively choose the number of measurements such that desired level of accuracy in the gradient estimate is maintained without using many more samples than necessary. Cai et al. (2022) describes method for adapting to the sparsity level designed for the stochastic optimization setting where the gradient in a previous round can provide useful information about the current gradient. This is not in the online convex optimization setting, but similar adaptive strategy could still be applied by starting with an optimistic estimate of and then adding on measurements if the error is believed be large. Furthermore, the adaptation method relies on a proxy
for the true gradient error, specifically (, which will not necessarily be minimized by 11
the true gradient since A fi 2x, V However, by making 8 suitably small we can mitigate that issue. This suggests that the adaptive method would remain useful in the OCO setting and reduce the difficulty of choosing the parameter for both CONGO-Z and CONGO-E (the sampling method used by CONGO-B is not compatible with this method). We leave the full analysis of this method in the OCO setting for future work.
F.3 IMPACT OF LARGE PROBLEM DIMENSION UNDER A CONSTRAINED NUMBER OF SAMPLES
Although compressive sensing allows us to reduce the sample complexity for gradient estimation merely logarithmic dependence d, for extremely high-dimensional problems it may remain problematic to continuously scale up the number of samples as d increases. Here, we test whether d can be increased without increasing m for CONGO-E without seriously degrading the performance. We fix m = 24 which is the standard value we have used for d = 50 and 5, but let d increase up to 5000. If we were to scale m with d, this would require m increase up 70. The results in Fig. 10 suggest that little is lost in terms of the empirical performance of CONGO-E relative to exact gradient descent when increases. Note however that this depends on 8 remaining constant. also show GDSP with the same number of samples for reference.
G DETAILS OF EXPERIMENTAL SETUP
G. ALGORITHM IMPLEMENTATION DETAILS
In this section, we provide implementation details for both the CONGO-style algorithms and the baselines used in our experiments. Note that for the baselines, distinguish between the instances
25

---

Published as a conference paper at ICLR 2025
used for stochastic gradient descent latency function (Section 7) from those used for gradient descent on the quadratic functions (Section 6) since in the SGD case we opt to normalize gradients before taking the gradient descent step to improve stability. In the case of the CONGO-style algorithms, we use the same name for both to avoid confusion although this difference is present in their implementations well. Finally, note that there additional hyperparameters for each of the algorithms used on the real system, which are defined in Table 6. The code used to implement the algorithms can be found in the supplementary materials (or, in the case of CONGO-Z and CoSaMP, in the Github repository at
Gradient Descent: Since we have closed form for the true gradient of the quadratic functions
considered in Section 6, we implement a standard projected gradient descent algorithm as an optimal baseline.
This zeroth-order algorithm applies a perturbation to each dimension of 2 one at a time and uses the finite difference approximation (as in equation 9) to estimate the gradient on per-dimension basis. This means that the number of samples for this algorithm is always + 1.
Naive Stochastic Gradient Descent:
Gradient Descent/Stochastic Gradient Descent with Simultancous Perturbations: This is an implementation Spall's SPSA (see Appendix A for details). Since this algorithm is able to estimate the full gradient after just two function evaluations, average over several estimates that the total number of samples matches that of the CONGO-style algorithms for a fair comparison.
RL Agent Using Proximal Policy Optimization: Proximal Policy Optimization (PPO) is a trust region based policy gradient algorithm that maximizes the following objective function
TT(a s) Too (a 8)
Te(a () Tep (a 8)
L (8, a, Oz, 0) min
A A (s,a), clip
1 e, 1 11 A (3..a) (15)
This objective function ensures that the policy updates are not too drastic. Specifically, the gradient of the objective goes to zero if the ratio of the new policy probability to the old policy probability for any given state-action pair deviates more than e away from 1. The PPO agent is trained on the DeathStarBenchmark Social Media environment (we do not use it in the Jackson network simulations) for 30 iterations to learn the impact of different CPU allocations on system performance. It is then tested for an additional 30 iterations evaluate its effectiveness, which is what compare the other algorithms. PPO was chosen as a baseline to demonstrate the performance of an algorithm with prior system knowledge, unlike gradient descent approaches.
CONGO-B: In the numerical experiments for Section 6, we set h; = 3m of kz 6m depending on the value of d to ensure sufficient averaging. In the experiments for Section 7, we fix k m such that CONGO-B uses the same number of samples as CONGO-Z/E and GDSP/SGDSP. To implement the basis pursuit recovery method, we use Chambolle and Pock's primal-dual algorithm (see (Foucart and Rauhut, 2013), Section 15.2) for the Numerical and Jackson network experiments and the Sequential Least Squares Quadratic Programming (SLSQP) solver from the scipy optimize Python package for tests the DeatthStareenchmakk
The code used to implement CONGO-Z comes directly from the code base for the paper which introduced ZORO (Cai et al., 2022). The only file that we needed to modify was optimizers.py. but the files Cosamp.py and base.py are also required.
CONGO-Z:
CONGO-E: We provided our implementation of CONGO-E, although it uses the same code for the CoSaMP algorithm as CONGO-Z does. The implementation is based on the pseudocode for Algorithm 1.
G.2 NUMERICAL EXPERIMENTS FOR ONLINE OPTIMIZATION OF QUADRATIC FUNCTIONS
For all of the numerical simulation experiments, we used T 100. Where applicable, the algorithms used the same hyperparameters. The value of provided to the algorithms was the exact value s. These hyperparameters are listed in Table 1.
26

---

Published as a conference paper at ICLR 2025
Table 1: Hyperparameters for Numerical Experiments
Name
Description
Value
learning rate
0.1
le
8
smoothing parameter
0.05,
=
0.001
171
# rows in A
[2slog( e)
Recovery tolerance
Used for basis pursuit and CoSaMP
0.005
Recovery max iterations
Used for basis pursuit and CoSaMP
50
Since the CONGO-style algorithms require bounds on LF 2 ||V/el and L 2 //V2/, we compute then for a given quadratic function as follows:
Ly = Rv 2og () +2
= Vogg((
These are bounds in expectation; The value of L comes from bounding ||De| |2 + ||6||2, where recall that the radius of the constraint set (in this case centered on 0) and hence the maximum value that any entry of x can take. The value of L comes from bounding the maximum of standard normal random variables in expectation since the eigenvalues of diagonal matrix correspond the diagonal entries.
For performing computations, the main Python package we use is Numpy full list of the packages required is available with the code). The seeds we used to obtain our results are 0-49. When creating our plots, we plot the average over the trajectories from the different seeds and also plot a shaded area representing + one standard deviation away from the mean. The computation of the mean and standard deviation is done using functions provided by Numpy. The pyproximal package is also required by the code used for CONGO-Z.
G.2.1 SPECIFICATIONS OF MACHINE USED
The numerical simulations were run on machine with an Intel core i7 processor and an NVIDIA GeForce RTX 3050 Ti Laptop GPU, We found that each overall experiment with d = 50 did not take longer than two minutes to run.
G.3 SIMULATION EXPERIMENTS FOR ONLINE OPTIMIZATION OF JACKSON NETWORKS
The following information concerns Section 7.1. We first provide a description of the layout of the Jackson networks and briefly explain how they are implemented. then describe the simulated workloads used, and finally provide the hyperparameter settings for the algorithm. Any additional information needed to setup and reproduce the experiments provided with the code.
G.3.1 JACKSON NETWORK LAYOUT
To simulate Jackson networks, we use the Python package queueing-tool (Jordon, 2023). Our simulation experiments use two different layouts, one which we call the complex environment and one which we call the large-scale environment. The first contains 15 queues and the second contains 50. For each layout we define set of jobs, each of which defined by an ordered sequence of queues which that job must be processed by. The length of this sequence varies from I to 7. All jobs share a single entry point which we label as "A". While the queueing-tood package comes with all the functionality needed to simulate generic Jackson network, we found the need to implement subclass of the Agent class to implement jobs with paths randomly chosen from a fixed set. However, this did not involve modifying the source code of the package.
visual representation of the complex environment is given in 11. This environment has eight possible job types, named Job1 through Job8. The sequence of microservices that each type must visit is specified in the yaml configuration files corresponding to the complex environment. The large-scale environment has simpler structure; there are 10 job types, and after being processed by
27

---

Published as a conference paper at ICLR 2025
E
M
B
F
G
A
N
C
D
H
K
J
Figure 11: Visual representation the connections between microservices for the 15-microservice environment. The labeled boxes correspond to microservices, the black arrows correspond to the entry point and the connections between microservices, and the blue arrows correspond to exit points. Each of the 8 possible jobs different exit point.
the entry-point microservice each job moves through a unique sequence of four or five microservices before exiting the system. Hence, in the large-scale environment the job paths only overlap the entry point.
In the queueing-tor tool framework, each microservice is represented pair of nodes with queue edge inbetween. When a job leaves a microservice's queue, it instantaneously moves from the exit node of that microservice the entry node of the next and is enqueued Using the functionality provided by the queueing-tool package, we generate arrivals according to Poisson process. Each time a job arrival occurs, the new job has a job type assigned to it according to the workload distribution. The service times, and hence the measured latencies, are based on the Jackson network's simulation time. We advance the simulation time only when the algorithm incurs its cost for the round or takes one of its samples (thus nothing changes in the simulation while the algorithm is performing computations). When the average latency is measured, we first advance the simulation for 30 seconds to bring it to steady state and then advance it for another 10 seconds while measuring the end-to-end latencies experienced by all jobs which leave the system during that period. the clear() function provided by queueing socueinngtool to reset the Jackson
the next microservice's queue.
At the end of round, network to its initial state. We found this necessary because otherwise the Python object simulating the network would accumulate much logged data which would make obtaining latency for newly processed jobs prohibitively slow. Running the simulation so that reaches steady state hefore taking any measurements compensates for this, since the network is allowed reach approximately the same state that it would have had under the new allocation without the reset.
G.3.2 PROTECTING AGAINST INSTABILITY
To ensure that any algorithm has valid latency measurements to use when forming a gradient estimate. we monitor whether or not any jobs leave the system during measurement period and if none do, we assume that the stability of the Jackson network has been violated. Regardless of which algorithm is use, when this occurs we increase the allocation to every microservice by small amount called the correction factor and proceed to the next round. This ensures that the algorithm is able to eventually recover from the instability even it cannot form a gradient estimate. The choice of correction factor depends on the scenario; for the complex environment with fixed workload it is 1, for the complex environment with variable job type or arrival rate it is 0.5, and for all large-scale environment scenarios it is O.II.
28

---

Published as a conference paper at ICLR 2025
Besides the workload, there are few other parameters which determine the environment that the algorithms operate in. These are the initial allocations for the microservices, the range of allowable allocations, and the resource weight (referred to w in the paper). For all experiments, the resource weight is set to and the range of allowable allocations is the set [1, 60). The initial allocations vary based the experiment since in cases where the workload will change, want the algorithms to have a chance to converge before the change becomes significant, forcing them to adjust. For simplicity, we keep this value uniform for all but the entry microservice (which requires higher initial allocation to ensure stability in some cases).
Table 2: Initial Allocation by Configuration
Configuration
For Entry Microservice
For Others
Complex, Fixed Workload
10
10
Complex, Variable Arrival Rate
10
10
Complex, Variable Job Type
10
7
Large-Scale, Fixed Workload
Large-Scale, Variable Arrival Rate
Large-Scale, Variable Job Type
10
G.3.3 DESCRIPTION OF WORKLOADS
The three workload types tested mimic the different workload types used our experiments on the DeathStarBench Social Network Application. The first type is the fixed workload where both the average arrival rate and the job distribution remain constant for all rounds. The second type is variable arrival rate where the average arrival rate changes periodically while the job distribution remains constant. This forces the algorithm to adapt its allocation over time without directly changing the set of queues which process jobs. The third type is variable job type where the job distribution incrementally switches between two fixed distributions over a certain number of rounds; outside of those rounds, the job distribution is constant. This forces the algorithm adapt a change in which microservices require resources and involves a change in the sparsity during the transition period. In the following tables, we specify the parameters defining the workload used in each plot of 3.
Table 3: Parameters for Fixed Workloads
Environment
Arrival Rate
Job Distribution
Complex
5/s
Jobs 1,3,4,6,7,8: 2% Jobs 2,5: 44%
Large-scale
5/s
Job6: 100%
G.3.4 HYPERPARAMETERS
Learning Rate Schedules Since our goal to show that CONGO-E produces better gradient estimates than other algorithms under sparse conditions, we ensure that all algorithms use the same learning rate schedule so that no algorithm has a clear advantage in that respect. For both environment types we use the same initial learning rate of 1 for fixed workload and variable arrival rate scenarios, while for variable job type scenarios the initial learning rate 0.7. For the the complex environment we decay the learning rate every 25 rounds (with a factor of 0.7 for the fixed workload and variable arrival rate scenarios, and a factor of 0.5 for the variable job type scenario).
Other Hyperparameters For all algorithms we set 0.5 since making it too much smaller would cause noise to overwhelm the measurements; this applies equally for both the baselines and the CONGO-style algorithms since they all depend measuring the difference in the function's value at two points, and if the noise in the function evaluations is larger than that difference then gradient estimation becomes ineffective. For the SGDSP and CONGO-B algorithms which only require two function evaluations to get a gradient estimate but average over many to reduce noise, we set the sample size for the average the value of m used by the CONGO-stype algorithms since this ensures
29

---

Published as a conference paper at ICLR 2025
Table 4: Parameters for Variable Arrival Rate Workloads
Environment
Arrival Rate
Job Distribution
Complex
Rounds 1-25: 5/s
Job6: 100%
Rounds 26-50: 5.5/s
Rounds 51-75: 6/s
Rounds 76- 100: 5.5/s
Large-scale
Rounds 1-10: 4.5/s
Job2: 100%
Rounds 11-20: 4.75/s
Rounds 21-30: 5/s
Rounds 31-40: 5.25/s
Rounds 41-50: 5.5/s
Rounds 51-60: 5.25/s
Rounds 61-70: 5/s
Rounds 71-80: 4.75/s
Rounds 81-90: 4.5/s
Rounds 91-100: 4.75/s
Table 5: Parameters for Variable Job Type Workloads
Environment
Arrival Rate
Initial Distribution
Final Distribution
Transition Rounds
Complex
5/s
Job 2: 50% Job 3: 30%
Job 2: 10%
40-90
Job 5: 50%
Job 6: 60%
Lcrge-scale
4/s
Job 1: 50%
Job1: 30%
40-90
Job 3: 50%
Job3: 30%
Job6: 20%
Job8: 20%
that they use the same number of samples as CONGO-Z and CONGO-E on each round. For the complex environment use = 6 and m 8, while for the large-scale environment we use s = 10 and m 17. For the primal-dual algorithm which implements basis pursuit as well as the CoSaMP algorithm, set the tolerance to 0,005 and the maximum number of iterations to 50,
G.3.5 SPECIFICATIONS OF MACHINE USED
Note that these simulations did not require the use of GPUs.
Operating System: Ubuntu 22.04.3 LTS (Jammy)
Kernel Version: 6.5.0-28-generte
CPU: AMD Ryzen Threadripper 3960X 24-Core Processor
Architecture: x86_64
Cores: 12
Threads: 24
Max Frequency: 3.8 GHz
Memory:
Total Memory: 96 GiB
Swapp 31 GiB
30

---

Published as a conference paper at ICLR 2025
G.4 DEATHSTARBENCH SOCIAL NETWORK APPLICATION
OVERVIEW
The DeathStarBench suite includes a social network application designed to evaluate microservices' performance. This application simulates real-world social network activities, providing robust environment for benchmarking.
TESTING METHODOLOGG
The wrk2 tool is utilized to generate workloads for the microservice application. This application consists of multiple containers, each hosting different microservice. Integrated within these containers are Jaeger clients, which continuously record service-level metrics, specifically latency, in the background. These metrics periodically sent the Jaeger Collector.
The collected metrics serve as key performance indicators (KPIs) to assess the system's performance. The KPIs are then used calculate the gradient, which informs the adjustments needed for CPU allocations. These adjustments are applied to the system's 's containers through Docker commands.
The specific methods for calculating the gradient and implementing CPU allocation modifications algorihhn-dependen. This adaptive approach ensures optimal resource allocation, thereby enhancing the overall efficiency and performance the microservice application. 12 illustrates how algorithms interact with the social network application in our experiments.
Microservice Application
eecroservie
microservio
jagar
jagarr
jargrr clent
janger cllent
cieni
Janger
Lagend
Calorlate
CPU
Docker
Algorithm Platform
Figure 12: visual representation of the application of algorithms within microservice architecture, demonstrating how CPU allocations are adjusted to achieve optimal performance thresholds.
Workloads: We used the WRK2 tool to generate workloads for experiments. We run the workload for duration of hours, with client connections. We executed the benchmark against the following workloads:
Fixed Workload with fixed job types: Request per second = Fixed 2000 req/sec
Job type = compose-poss
Fixed Workload with variable job types:
Request per second Fixed 2000 reg/sec
read-hometimeline, read-usertimeline requests Job type composition of compose-pon
Variable Arrival Rate with fixed job types:
Request per second = follows this pattern [2000, 1900, 1500, 1600, 1800]
Job type = compose-post
31

---

Published as a conference paper at ICLR 2025
G.4.1 HYPERPARAMETERS
Each algorithm tested with specific set of hyperparameters assess their performance under different conditions. Table presents the glossary of the hyperparameters used for the various algorithms and Tables 8, 9, 10,11, provide the exact hyperparameters used for NSGD, SGDSP, PPO, CONGO-B, CONGO-Z and CONGO-E respectively.
Table 6: Glossary of Hyperparameters for Deathstar Bench Trials
Hyperparameter
Definition
epu period
Parameter for Docker change CPU allocation (100000
for all)
max iterations
Maximum number of iterations for the algorithm (20 for all)
FACTOR latency_weige
Cost factor for CPU usage
Weight assigned to latency in the cost function
8
Small value for CPU allocation adjustments
initial learning rate
Starting rate for updating CPU allocation
learning rate decay factor update step limit
Multiplier to reduce learning rate each iteration
Max step size for CPU allocation updates
current cpu bounds significance threshold for change learning rate decay schedule
Range for allowable CPU usage
Min threshold for significant CPU allocation changes Formula decrease learning rate over time Iterations for Bayesian Optimization Function to select next hyperparameters in BO Maximum allowable latency for operations Parameter accelerate gradient vectors
number of calls (BO)
acquisition function (BO) latency threshold
momentum
exploration factor
Balance between exploring and exploiting strategies Number steps per environment update in PPO Discount factor in PPO Learning rate in PPO Controls bias-variance trade-off in advantage estimation (PPO)
n_steps
"PPo
learning rate GAE Lambda (gae_lambda)
Entropy Coefficient (ent_coef)
Encourages exploration by penalizing deterministic poli- cies (PPO)
Value Function Coefficient (vf_coef)
Weight for the value function's error during training (PPO)
Max Gradient Norm
Threshold for gradient clipping to prevent explosion (PPO)
(max grad norm)
/1 11-minimization error constraint (CONGO)
scale (sigmoid adjustment)
Scaling factor for sigmoid function to adjust CPU alloca- tions (CONGO)
Table 7: NSGD Hyperparameters for Deathstar Bench Trial
Hyperparameter
Value
(gradient estimation)
0.05
initial learning rate update step limit current cpu bounds
0.01
0.1
0.1 to 1.0
significance threshold for change
0.00009
learning rate decay schedule
1.0 (1.0 socca_ffctorr iteration)
CPU CPU_ COST_FACTOOR weincyyweight
10.0
1.0
32

---

Published as a conference paper at ICLR 2025
Table SGDSP Hyperparameters for Deathstar Bench Trial
Hyperparameter
Value
8
0.02
learning rate
(1.0/ (1.0 steps))
CPU_COST DEL_CCOSTFATTTO FACTOR
10.0
latency_
1.0
Table 9: Proximal Policy Optimization (PPO) for Deathstar Bench Trial
Hyperparameter
Value
0.05
max iterations
60 (30- training, 30 -test)
n n_steps
2048
"PPO
0.99
learning_rate
0.015
gae_lambda
0.95
ent_coef
0,01
vf_coef
0.5
max grra_ggaadg_gg norm
0.5
CPU CPU_COST FACTOR
10.0
evency_weightt
1.0
G.4.2 SPECIFICATIONS OF MACHINE USED
Operating System: Ubuntu 22.04.3 LTS (Jammy)
Kernel Version: 6.5.0-28-generic
CPU: Intel(R) Core(TM) 19-9940X CPU @ 3.30GHz
Architecture: x86
Cores: 14
Threads: 28
Max Frequency: 4.5 GHz
Memory:
Totaa Memory: 62 GiB
Swap: 31 GiB
GPU:
NVIDIA GeForce RTX 2080 Ti
33

---

Published as a conference paper at ICLR 2025
Table 10: CONGO Hyperparameters for Deathstar Bench Trial
Hyperparameter
Value
number of measurements (m)
12
6
0.2 max perturbation value
7
0.2 (1 + iteration 0.05)
learning_rat rate
0.6/ (1 iteration 0.5)
scale (sigmoid adjustment)
5
CPU_COST FSSTORR
10.0
latency_weight
1.0
Table CONGO Hyperparameters for Deathstar Bench Trial
Hyperparameter
Value
(perturbation size)
0.1
learning rate
0.15
sparsity (s)
number of measurements (m)
10
latency weight
1.0
CPU allocation weight
10.0
Table 12: CONGO E Hyperparameters for Deathstar Bench Trial
Hyperparameter
Value
(perturbation size)
0.1
learning rate
starts 0.1. decreases 0.1/(1 + iteration 0.1)
sparsity (s)
number of measurements (m)
initial CPU allocation
0.35
latency weight
1.0
CPU allocation weight
10.0
34


Reviews:
[{"review_id": "oo5cfujKxK", "reviewer": "Reviewer_YSr4", "summary": "The paper studies zeroth-order online convex optimization, where the gradient of the objective function is assumed to be sparse. The proposed algorithms, CONGO, combine the (projected) gradient descent algorithm for online convex optimization, with a gradient estimation procedure using compressive sensing technique. The regret is proven to be O(\\sqrt(T)) and does not depend on the dimension of the problem, and the per-iteration sampling complexity scales with the sparsity level of the gradient. Experiments confirm the effectiveness of the algorithms.", "questions": "The regrets in Theorem 2 and 3 holds in expectation, but if understanding is correct, they also hold with high probability?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is overall well written, and presents the setup, results, and proof clearly. The algorithms proposed appear efficient in terms of the regret and the sampling complexity.", "weaknesses": "-- One might argue that the results are not too surprising: the regret follows from the regret of online gradient descent, while the sampling complexity follows from the compressive sensing results. \n\n-- In CONGO-B, line 827 – 829, gradient recovery requires solving an LP, which can be computationally inefficient, especially in high-dimensional setting. In addition, compressive sensing usually requires knowledge of the sparsity level before setting the number of samples. If such knowledge is lacking or inaccurate, compressive sensing might fail completely [1]. \n\n[1] Amelunxen, Dennis et al. “Living on the edge: phase transitions in convex programs with random data.” Information and Inference: A Journal of the IMA 3 (2013): 224-294.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jwADoKj1uN", "reviewer": "Reviewer_LC7U", "summary": "This paper proposed a framework for online zeroth-order optimization leveraging the techniques and insights from compressed sensing. The authors provide several schemes for efficiently sampling the objective functions values and estimate the gradients, alongside with theoretical convergence proofs revealing the fast convergence rates. The numerical results demonstrate this approach's superior performance over state-of-the-art baselines.", "questions": "Could the authors clarify the fundamental difference between the proposed method and AISTATS'18 paper mentioned above? Please highlight the advantages of the proposed method.\n\nIn the numerical experiments, did you observe any phase transition on the number of measurements to the convergence speed of the proposed algorithms?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a well-written paper in general, the idea of introducing compressed sensing for estimating the gradients is very inspiring. The numerical performance of the proposed scheme is excellent. The presentation of the paper is very clear and easy to read.", "weaknesses": "The novelty of the proposed scheme may be potentially limited (rebuttal against this point is welcomed as the reviewer is not familiar with zeroth-order optimization literature). The reviewer has seen similar approach been proposed in Wang et al, \"Stochastic zeroth-order optimization in high dimensions\" AISTATS'18, where they utilized a very similar idea but used LASSO (L_1) instead of CoSAMP (L_0). The numerical study did not considered this AISTATS'18 paper as a baseline, although being cited in the reference.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fylXB1YLu0", "reviewer": "Reviewer_qS2T", "summary": "This paper introduces a framework designed for zeroth-order online convex optimization (OCO) in environments where gradients are often sparse. The core idea is to combine compressive sensing techniques with online optimization to take advantage of this sparsity, which allows for efficient high-dimensional optimization with fewer samples. \n\nThe authors propose three variations—CONGO-B, CONGO-Z, and CONGO-E—that utilize different compressive sensing approaches and gradient estimation methods. They back up their approach with theoretical guarantees, showing sublinear regret bounds, and validate the framework through experiments on both synthetic and real-world tasks (like microservice autoscaling).", "questions": "1. The theoretical analysis assumes exact gradient sparsity, which may not hold in all practical scenarios. Could the authors discuss potential extensions of their theoretical analysis to approximately sparse gradients, or provide insights on how performance changes as the level of sparsity decreases? This could help clarify the framework's robustness and practical applicability.\n\n2. While the regret bounds are dimension-independent, sample complexity grows logarithmically with dimension. In very high-dimensional settings, how does this sample complexity impact practical performance?\n\n3. The framework is compared to standard SPSA-based methods, but how does it compare to other advanced sparse optimization or regularized gradient estimation techniques?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The use of compressive sensing within an OCO framework is a fresh and well-motivated idea. By focusing on sparse gradients, the authors address both sample efficiency and dimensionality reduction, which are critical in high-dimensional settings. \n\n2. The authors provide rigorous theoretical analysis, establishing regret bounds that demonstrate sublinear scaling with respect to the problem horizon, independent of the problem dimension.\n\n3. The three algorithmic variants, CONGO-B, CONGO-Z, and CONGO-E, offer a nice balance of performance and complexity. For instance, CONGO-E uses Gaussian matrices and CoSaMP for enhanced performance, while CONGO-Z is more sample-efficient.", "weaknesses": "1. The theoretical analysis assumes exact gradient sparsity, which may not be realistic for all real-world problems.\n\n2. While CONGO outperforms standard gradient descent with SPSA, it’s mostly compared against methods that don’t leverage sparsity. A more comprehensive comparison with advanced sparse optimization techniques or regularized gradient estimators would help here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bTG0xjrdVs", "reviewer": "Reviewer_zPCR", "summary": "The paper introduced the compreesive online gradient optimization framework (CONGO) for solving sparse online convex optimization problems based on motivating examples in real world application. Three variants using simultaneous perturbation and compressive sensing are proposed based on different inspiration. The proposed algorithms were validated both theoretically and experimentally.", "questions": "1. How sensitive is the proposed algorithm to sparsity? What would happen if the sparsity measure $s$ is large, will the performance still be comparable to other existing methods?\n\n2. Could adaptive strategies be used for the sparsity?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The idea of using compressing sensing to estimate gradients more efficiently is novel. From the theory provided, the total cost of function value evaluation is reduced which makes it suitable for problems of large dimension.\n\n2. Based on the specific setting and the measurements used, three different variants are proposed, which makes the framework flexible.\n\n3. The paper presents theory on the regret bound and validate the theory with experiments.", "weaknesses": "While the paper is generally interesting and the idea is novel, the reviewer wants to point out that the paper contains *formatting errors*, specifically, the heading \"Under review as a conference paper at ICLR 2025\" is missing at each page.\n\n1. It seems to the reviewer that the proposed method needs careful tuning of the parameters, such as the step size and the sparsity, which may require additional information which makes the proposed algorithm less practical. \n\n2. CONGO-B seems to be less efficient and more unstable compare to the other variants, this is not explained in theory.\n\n3. The proposed assumptions are a little restrictive in reality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)