An Ellipsoid Algorithm for Online Convex Optimization

We are grateful for your time and for your thoughtful evaluation of our work.

In Definition 2.1, I believe the correct condition for Item II should be $\langle v, u \rangle > \langle v, w \rangle$ for all $w \in \mathcal{K}$, isn't it?

We will fix this typo.

For the most-relevant prior work [17], what is the computation cost per round? Do they also incur a cost per round? My guess is not, but it would be great if the authors could clarify

The per-round cost of [17] is $\tilde{O}(d^2 + C_{\text{separation}})$, which can be slightly lower than our cost of $\tilde{O}(d^\omega + C_{\text{separation}})$, where $C_{\text{separation}}$ is the cost of performing separation. However, since the cost of performing separation typically dominates the cost of solving a $d \times d$ linear system (which we upper bound by $d^\omega$ in our analysis), the overall complexity of our method can be considered comparable to that of [17], or slightly higher.

We appreciate your careful review and the time you spent on our submission.

The paper builds closely on [17], with fairly-minor improvements in guarantees.

The regret bound in [17] scales linearly with the asphericity, which can be arbitrarily large. In contrast, our bound moves this dependence inside a logarithmic factor, which we view as a significant improvement over the guarantee in [17].

The computation cost per iteration depends on the term . It appears that this could result in significantly higher computation cost than existing methods. As such, the regret-per-computation of this method might not be better than existing methods even if the regret is lower for a given . Furthermore, it is unclear if the computation cost is less than even projection-based methods (e.g. OGD, RFTL).

The $d^\omega$ term in our computational cost comes from inverting a matrix (or solving a $d \times d$ linear system), which is required by the PoE subroutine for projecting onto the ellipsoid. Here, $\omega$ is the matrix multiplication exponent, currently estimated to be less than $2.371552$. The per-round cost of our algorithm is on the order of $d^\omega + C_{\text{separation}}$, where $C_{\text{separation}}$ is the cost of performing separation. This can be slightly higher than the per-round cost of the algorithm in [17], which is $d^2 + C_{\text{separation}}$. However, in typical optimization settings, the separation cost $C_{\text{separation}}$ dominates $d^\omega$ (the cost of solving a $d\times d$ linear system), in which case the overall computational cost of our method would be comparable to that of [17].

As for the comparison to Euclidean projection: if we could reduce the cost of Euclidean projection onto an arbitrary set to that of solving a linear system, it would represent a major breakthrough. In general, the cost of Euclidean projection can be much higher than the cost of solving a $d \times d$ linear system (i.e., $d^\omega$). In fact, given access to a separation oracle for $\mathcal{K}$, the cost of Euclidean projection onto $\mathcal{K}$ using state-of-the-art cutting plane methods is on the order of $\tilde{O}(d^3 + d \cdot C_{\text{separation}})$, which is clearly worse than $d^\omega + C_{\text{separation}}$. Moreover, the complexity of cutting plane methods often hides large multiplicative constants in the $\tilde{O}$ notation.

Table 1 (which compares the guarantees with existing work) is somewhat confusing in that it shows the number of oracle calls per a round, but doesn't compare the computation cost. This is important given that the motivation for projection-free OCO is to reduce the computation cost of classical methods.

As mentioned earlier, the separation cost typically dominates the $d^\omega$ term, which is why the table focuses on the separation oracle complexity. We will add the other computational costs to the table for completeness.

What is the term $\omega$ in the computation cost term $d^\omega$?

$\omega$ is the matrix multiplication exponent and is currently estimated to be less than $2.371552$. In our case, we use $d^\omega$ as an upper bound on the cost of solving a $d \times d$ linear system.

How does the computation cost of the method compare with the following: (a) euclidean projection in every round, (b) putting the set in isotropic position once, (c) existing projection-free methods.

Cost of Euclidean projection: $\tilde{O}(d^3+d\cdot C_{\mathrm{separation}})$ (see Lee et al., 2017 reference below). This cost is achieved using state-of-the-art cutting plane methods. We note that the $\tilde{O}$ notation can hide large constants, which often makes such methods practical only for small- to medium-sized problems. Alternatively, one could use an interior point method for Euclidean projection, but this requires a self-concordant barrier for the feasible set, which is not always available. Even when such a barrier exists, the typical cost remains greater than $d^3$.

Putting the set in isotropic position: $\tilde{O}(d^4) \cdot C_{\text{separation}}$ (see [14]). This can be prohibitive, even if performed only once. Moreover, placing the set in isotropic position does not necessarily eliminate the dependence on asphericity in the regret bound; see the paragraph titled “Limitations of reparametrization” on Line 194 and the response to Reviewer h8Ps.

Per-round cost of existing projection-free methods: $\tilde{O}(d + C_{\text{separation}})$ for [16], and $\tilde{O}(d^2 + C_{\mathrm{separation}})$ for [17]. The dependence on $\kappa$ is linear in the regret bounds of both [16] and [17]; in [16], for example, $\kappa$ multiplies $\sqrt{T}$. Since the cost of separation typically dominates the cost of solving a $d \times d$ linear system (i.e., $d^\omega$), the overall complexity of our method can be considered comparable to that of [17], or slightly higher.

Per round cost of our approach: $\tilde{O}(d^\omega + C_{\text{separation}})$; see answer to the second comment above for a comparison with [17].

Lee, Y. T., Sidford, A., & Vempala, S. S. (2018, July). Efficient convex optimization with membership oracles. In Conference On Learning Theory (pp. 1292-1294). PMLR.

Perhaps the most relevant setting---and in some sense the best-case scenario---for which $C_{\text{sep}}$ is relatively small is when $\mathcal{K}$ is a polytope defined by $m \in \mathbb{N}$ linear constraints: \mathcal{K} := \left\\{x \in \mathbb{R}^d \mid a_i^\top x \leq b_i, \forall i \in [m] \right\\}, where $(a_i) \subset \mathbb{R}^d$ and $(b_i) \subset \mathbb{R}$. This is one of the most common setups in convex optimisation.

Separation cost.
In this case, separation reduces to membership testing, which requires computing the $m$ inner products $a_i^\top x$ for $i \in [m]$. This gives $C_{\text{sep}} = O(md).$ As soon as $m \geq d^{\omega - 1} \approx d^{1.37}$, the cost of separation dominates the cost of solving a $d \times d$ linear system, which is $O(d^\omega)$.

Projection cost. As stated in the rebuttal, projection using state-of-the-art cutting-plane methods costs $\tilde{O}(d \cdot C_{\text{sep}} + d^3) = \tilde{O}(md^2 + d^3).$ However, in the polytope setting, it is more common to use an interior-point method, since a self-concordant barrier can be constructed easily: $\phi(x) = -\sum_{i=1}^m \log(b_i - a_i^\top x),$ which is $m$-self-concordant. Using this barrier, the projection cost becomes $\tilde{O}(\sqrt{m} \cdot d^\omega).$

Side note. The polytope setting is also one where our approach is more efficient than projection-free methods based on Frank--Wolfe, which require solving a linear optimisation problem at each round. In this case, the cost of linear optimisation is comparable to that of projection using an interior-point method.

Improvements after rebuttal. We will incorporate the additional $\text{poly}(d)$ costs into Table 1 in the final version. We will also include the clarifications raised in this rebuttal regarding the cost of the different oracles.

The overall runtime to reach an $\epsilon$-average regret is indeed a good metric. As I will explain below, the cost of gradient descent combined with an interior-point method for projections can still exceed that of our proposed method when the number of constraints $m$ is larger than $d$.

Full cost of projection. The cost of Euclidean projection using an Interior-Point Method (IMP) is actually $\sqrt{m} \cdot (d^{\omega} + md^2)$; here, $\sqrt{m}$ is the number of iterations of the IPM, and $d^{\omega} + md^2$ is the per-iteration cost. The $O(md^2)$ term that I omitted in my previous comment arises from computing the Hessian of the barrier, which has $m$ terms. (The term $d^\omega$ is for inverting the Hessian.)

Cost of GD + IPM. With this corrected projection cost, the total runtime of gradient descent with interior point method is $\frac{\sqrt{m} (d^{\omega} + md^2)}{\epsilon^2}$.

Comparison with the proposed approach. This cost exceeds that of our method, which is $\frac{md^2}{\epsilon^2} + \frac{d^{\omega + 1}}{\epsilon^2}$, as soon as $m \geq d$.

On projection-free approaches based on linear optimization. Projection-free optimization approaches based on linear optimization are indeed very useful and practical—their dimension-free regret guarantees are particularly appealing. My earlier comment was not meant to suggest they are useless. We were simply pointing out a popular setting where, in the absence of additional structure, our approach can be more competitive. Of course, there are also settings where Frank–Wolfe outperforms ours. We view these approaches as complementary.

A more transparent comparison. As mentioned in the previous comment, we will include these discussions in the paper for a more transparent comparison. This should be relatively straightforward and would not require any major changes.

Thank you for the clarification. Still, OGD + solving the projection with the SOTA cutting plane method you mentioned above dominates the running time to reach epsilon average regret. Is this correct?

This leads me to the point: to get your complexity, couldn’t I in principle partition the rounds to blocks of length d and simply simulate the above cutting plane method within each block?

Thank you for the follow-up questions:

OGD + SOTA cutting plane for projection. Indeed, in this case, the overall cost can be slightly better than that of our approach. However, we note the following point:

• The more standard Vaidya' cutting-plane method has complexity $\tilde{O}(d \cdot C_{\text{sep}} + d^4)$ (see [1] below). Achieving a $d^3$ dependence instead of $d^4$ requires a much more involved algorithm and does not necessarily yield a practical method (see [2] below). (Cutting-plane methods are typically more theoretical in nature and often do not scale well in practice.)
• The $\tilde{O}$ in the complexity of cutting-plane methods typically hides large constants, which could partly explains why they often do not scale as well as one might expect.

Side note. Since the submission, we have found a way to improve the $d^\omega$ term in the analysis to $d^2$, which would bring the runtime for achieving $\epsilon$-average regret in line with that of OGD + state-of-the-art cutting-plane methods in the polytope setting. That said, we believe the results in the paper are already meaningful and valuable even with the $d^\omega$ cost.

Block-wise approach. Suppose we adopt a block-wise approach where the cost of projection via cutting-plane methods is amortized over a block of $B$ rounds (to be determined below).

• Since we now operate over blocks of size $B$, the per-round losses are effectively scaled by $B$, which appears linearly in the regret. The resulting regret bound takes the form $O(B G R \sqrt{T/B})$.
• The amortized cost per iteration is $\frac{C_{\text{cutting plane}}}{B} = \frac{d \cdot C_{\text{sep}} + d^3}{B}$. To match the $\tilde{O}(1)\cdot C_{\text{sep}}$ cost per round of our approach, we would need to set $B = d$. This would lead to an overall regret bound of $O(G R \sqrt{d T})$, which is in line with our guarantee. So the question ultimately becomes whether the cutting-plane approach is a practical one (see bullet points above).

References.

[1] Bubeck, Sébastien. "Convex optimization: Algorithms and complexity." Foundations and Trends® in Machine Learning 8.3-4 (2015): 231-357.

[2] Lee, Yin Tat, Aaron Sidford, and Sam Chiu-wai Wong. "A faster cutting plane method and its implications for combinatorial and convex optimization." 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 2015.

Thank you for your comments and for reviewing our paper.

Computational Overhead of Ellipsoid Updates: These updates involve operations with per-round complexity of $\mathcal{O}(d^\omega)$, where $\omega$ is the matrix multiplication exponent. Any estimation for $\omega$? Would it influence the overall computational complexity?

The $d^\omega$ term in our computational cost arises from the cost of inverting a matrix (or solving a $d \times d$ linear system). This operation is required by the PoE subroutine to project onto the ellipsoid. The exponent $\omega$ is currently estimated to be less than $2.371552$. However, even if we take $\omega = 3$, the cost $d^\omega$—that is, the cost of solving a linear $d \times d$ system—remains much smaller than the cost of Euclidean projection for many feasible sets of interest

Lack of Empirical Validation: The paper focuses entirely on theoretical contributions and does not include any empirical results. While the regret guarantees are strong, it is unclear how the algorithm performs in practice. Empirical validation—such as experiments on standard OCO benchmarks or simulations comparing runtime and regret with other projection-free methods—would significantly strengthen the paper.

We have acknowledged the lack of experiments in the limitations paragraph. Nevertheless, we believe the theoretical results we provide stand on their own.

Minor issue: It seems that you forgot to mention the full name of ONS. We will address this. Thank you for pointing this out.

Thank you for taking the time to review our work and provide your feedback.

While the regret performance achieved by the proposed algorithm is order-wise larger than the sample-optimal gradient-based algorithms, they can also be order-wise larger compared to separation-based algorithms in prior works in certain regimes, e.g. when dimension d is large, due to the additional d factors in the stated upper bounds.

There are regimes where our regret bound is worse than that of previous separation-based algorithms, such as when $\kappa$ is already small. For this reason, our approach can be seen as complementary to existing methods.

As a side note, it is possible to design an algorithm that achieves a regret matching the best of the bounds obtained by our method and those in [16] and [17]. One such approach would aggregate the outputs of the individual algorithms using exponential weights; see, for example, reference [1] below.

As elaborated in the weakness section, we recommend the authors to revise the manuscript to correct typos in problem formulation and clarify the dependencies of all parameters when comparing regrets in related works.

We will correct the typo in the definition of the separation oracle. All the regret bounds—both ours and those we cite—depend linearly on the product RG, which is why we omitted it. This is generally the case for OCO algorithms, as their outputs are typically equivariant to the input scales R and G. The exception is algorithms that adapt to R and G, which is beyond the scope of this paper.

The authors presents a natural extension to stochastic optimization on page 9, however, it is not clear what is the oracle model considered here. We recommend the authors to clarify the oracle model, as well as providing a brief overview of the best know results in different settings (e.g., zeroth order, first order, or having access to both).

We consider the standard stochastic optimization setting with access to a first-order stochastic gradient oracle. Some details specific to the stochastic setting were moved to Appendix F due to space constraints. We will restore more of this material to the main text thanks to the additional page that is allowed for the camera ready.

The asphericity of the action set is often not a fundamental constraint in the sense that a hyperelliposid action set could have large asphericity, but it is trivial to achieve the optimal O(\sqrt{T}) regret by operating in a linearly transformed space where the action set is a hyperball while constraint parameters G and R remain the same. Could the authors provide an example where the dependency of asphericity can not be resolved by extending [16][7] through this approach.

This is not always true, and here is why. Let $W \in \mathbb{R}^{d \times d}$ be a positive-definite matrix, and let $\mathcal{E} = \\{x \in \mathbb{R}^d \mid x^\top W^{-1} x \leq 1\\}$ be an ellipsoid. Assume that $\lambda_{\min}(W) \geq 1$, so that $\mathcal{E} \subseteq \mathbb{B}(1)$. Suppose we are in the OCO setting, where $\mathcal{E}$ is the feasible set and the losses $f_t$ are $G$-Lipschitz over $\mathcal{E}$; that is, $\\|\nabla f_t(x)\\| \leq G$ for all $x \in \mathcal{E}$.

Now, if we apply a reparametrization to work on the Euclidean ball instead, the reparametrized losses we work with are $\tilde{f}_t: \mathbb{B}(1) \rightarrow \mathbb{R}$ given by $\tilde{f}_t(y) = f_t(W^{1/2} y)$. By the chain rule, the gradients of $\tilde{f}_t$ satisfy $\nabla \tilde{f}_t(y) = W^{1/2} \nabla f_t(W^{1/2} y)$ (assuming $f_t$ is differentiable for simplicity). Therefore, the Lipschitz constant of $\tilde{f}_t$ in the reparametrized problem can be as large as $\sqrt{\lambda{\max}(W)} G$, which can be arbitrarily larger than $G$ for ill-conditioned $\mathcal{E}$. Here, $\sqrt{\lambda{\max}(W)}$ is a measure of the asphericity of $\mathcal{E}$.

Since the regret bound scales linearly with the Lipschitz constant of the losses (see the answer to the first question), working with the reparametrized losses in this way can introduce a dependence on the asphericity in the regret bound. This issue with reparametrization holds more broadly (beyond the ellipsoid setting), as we discuss in the paragraph titled “Limitations of reparametrization” on Line 194.

[1] Dylan J Foster, Satyen Kale, Mehryar Mohri, and Karthik Sridharan. Parameter-free online learning via model selection. In Advances in Neural Information Processing Systems, pages 6020–6030, 2017.

That is a fair point. Given the closing deadline for the author response, we’d like to end on the following point: while computing the appropriate reparametrization for the ellipsoid was cheap, doing it for general sets can cost O(d^4) calls to a separation oracle, making it prohibitive even if done once. (We mention this in the paper on line 194)