Uniform Wrappers: Bridging Concave to Quadratizable Functions in Online Optimization

Q1.

1. Could the authors provide a concise user guide for converting an OCO algorithm into an online quadratizable optimization algorithm, along with an explanation of how the regret bound proof is transformed? This should include specifying which technical parts of the paper should be applied and in what order. If the authors have already provided such part somewhere in the paper, it will be appreciate that the authors could remind me the location.

We first discuss

a concise user guide for converting an OCO algorithm into an online quadratizable optimization algorithm

The conversion of the algorithm is detailed in Meta-algorithm 1. Basically, this meta-algorithm transforms the base algorithm action using $\mathcal{W}^{\operatorname{action}}$ and the base algorithm query oracle using $\mathcal{W}^{\operatorname{query}}$.

For example, consider the Online Gradient Ascent as a base algorithm:

Input: convex set $\mathcal{K}$, $x_1 \in \mathcal{K}$, step-sizes $\eta_n$

For $t=1$ to $T$

Play $x_t$

Observe $o_t$, a sample of $\mathcal{Q}_{f_t}(x_t)$, an unbiased estimate of $\nabla f_t(x_t)$

$x_{t+1} \gets P_{\mathcal{K}}(x_t + \eta_t o_t)$

Where we use $\mathcal{Q}_{f_t}$ to denote the stochastic first order query oracle for $f_t$ which returns unbiased estimates of $\nabla f_t$.

Now, if we apply the first-order to first-order uniform wrapper $\mathcal{W}_1^{NM}$ (for non-monotone up-concave functions over general convex sets; see Appendix C.3 for additional details) according to Meta-algorithm 1, we get a first order algorithm for online optimization of non-monotone DR-submodular function over general convex sets:

Input: convex set $\mathcal{K}$, $x_1 \in \mathcal{K}$, $\underline{x} \in \mathcal{K}$, step-sizes $\eta_n$

For $t=1$ to $T$

Play $(\mathcal{W}_1^{NM})^{\operatorname{action}}(x_t) = (x_t + \underline{x})/2$

Observe $o_t$, a sample of $(\mathcal{W}_1^{NM})^{\operatorname{query}}(\mathcal{Q}_{f_t})(x_t)$

$x_{t+1} \gets P_{\mathcal{K}}(x_t + \eta_t o_t)$

By plugging in the definitions of $(\mathcal{W}_1^{NM})^{\operatorname{action}}$ and $(\mathcal{W}_1^{NM})^{\operatorname{query}}$ as per Appendix C.3, we get the following algorithm:

Input: convex set $\mathcal{K}$, $x_1 \in \mathcal{K}$, $\underline{x} \in \mathcal{K}$, step-sizes $\eta_n$

For $t=1$ to $T$

Play $(x_t + \underline{x})/2$

Sample $z$ according to $\mathcal{Z}^{NM}$ (as defined in Appendix C.3)

Observe $o_t$, a sample of $\mathcal{Q}_{f_t}(\frac{z}{2}(x_t - \underline{x}) + \underline{x})$, an unbiased estimate of $\nabla f_t(\frac{z}{2}(x_t - \underline{x}) + \underline{x})$

$x_{t+1} \gets P_{\mathcal{K}}(x_t + \eta_t o_t)$

This becomes Algorithm 1 in [Zhang et al., 2024] in the case of non-monotone functions.

We will add this example with more explanation in the Appendix to demonstrate exactly how Meta-algorithm 1 works.

an explanation of how the regret bound proof is transformed

The conversion of the regret bound is the focus of Section 6, in the form of a three-step guideline. Section 7 and Appendix D are examples of how to apply such a guideline. Since this is a guideline that depends on the structure and the details of the original proof, any explanation of the application of the guideline requires an understanding of the original proof. This is why Section 7 and Appendix D are as long as they are, we needed to go through the proof of the original regret bound, explain all the ideas there, and rewrite the proofs in order to match the guideline.

In Section 7, lines 285-310 describe exactly how Theorems 1 and 2 provide an example of how to apply the guideline in this case. In Appendix D, lines 984-997, specifically the statement of Theorems 9 and 10 and the paragraph between the theorems describe how the guideline applies in this case.

Online Gradient Ascent (OGA) mentioned above is a special case of what is covered in Appendix D. For OGA specifically, we can simplify the proofs and guidelines as follows. However, in this specific case, we may simplify the proofs and the guideline in the following manner:

As per step 1 of the guideline, we first rewrite a part of the proof of the OGA, in a way that does not require concavity, but the proof of the regret bound for the concave case can be recovered using the inequality $f(y) - f(x) \leq \langle \nabla f_t(x), y - x \rangle$.

Theorem A. For any differentiable function class $\mathbf{F}$, with stochastic first-order query oracles bounded by $G$ and step-sizes $\eta_t=\frac{D}{G \sqrt{t}}$, the algorithm OGA guarantees that $\max_{x \in \mathcal{K}} \sum_{t=1}^T \mathbb{E}[ \langle \nabla f_t(x_t), x - x_t \rangle ] \leq \frac{3}{2} G D \sqrt{T}$.

The proof of this theorem is a simple rewriting of the classical results. Note that the boundedness of the stochastic first-order query oracle by $G$ implies that the gradients of functions in $\mathbf{F}$ are bounded by $G$, i.e., functions in $\mathbf{F}$ are $G$-Lipschitz continuous.

Next we want to adapt the result of Theorem A to upper-quadratizable setting.

Theorem B. If $\mathbf{F}$ is a function class over $\mathcal{K}$ that is upper-linearizable with $0 < \alpha \leq 1$ and $\beta \geq 0$ and a first-order uniform wrapper $\mathcal{W}$, then with stochastic first-order query oracles bounded by $G$ and step-sizes $\eta_t=\frac{D}{G \sqrt{t}}$, the algorithm $\mathcal{W}(OGA)$ guarantees that $\max_{x \in \mathcal{K}} \sum_{t=1}^T \mathbb{E}[ f_t(x) - f_t(\mathcal{W}^{\operatorname{action}}(x_t)) ] \leq \frac{3}{2} G D \sqrt{T}$.

At first glance, it may seem that moving from Theorem A to Theorem B might be non-trivial. However, as elaborated in Appendix A, whether we apply $\mathcal{W}(OGA)$ to an adversary $\operatorname{Adv}$ that selects functions from $\mathbf{F}$ or applying OGA to the adversary $\mathcal{W}(\operatorname{Adv})$, the sequence $x_t$ remains the same. Thus, by using Theorem A, we immediately see that $\max_{x \in \mathcal{K}} \sum_{t=1}^T \mathbb{E}[ \langle \nabla \mathcal{W}(f_t)(x_t), x - x_t \rangle ] \leq \frac{3}{2} G D \sqrt{T}$. Now we may use the definition of uniform wrappers to complete the proof of Theorem B.

We will include the discussion above in the appendix to show how our guideline may be applied to a setting that is simpler than the zeroth-order algorithm mentioned in Section 7.

2. Could the authors provide examples of potential applications for quadratizable function classes, or provide references that demonstrate the significance of this function class?

Q2. So far, the main classes of functions that are covered by quadratizable functions are concave functions and continuous DR-submodular functions (as described in the paper). However, we would like to point out that this concept has been introduced in the literature in [Pedramfar and Aggarwal, 2024a] which was published in December 2024. Thus, given more time, we expect that this concept will be better understood and more examples of quadratizable/linearizable functions will be found.

3. For the future work, could the regret lower bound proof of some OCO setting be convert to that of the online quadratizable optimization?

Q3. That is a great question. Unfortunately, we do not think our framework could be used for converting lower-bound proofs. In order to prove a lower bound, it is essential to already know the optimal approximation coefficient. (To see why, given a function class $\mathbf{F}$ with a uniform wrapper with $0 < \alpha \leq 1$, it may be possible to find another uniform wrapper with a worse approximation coefficient $0 < \alpha' < \alpha$. If an algorithm for $\mathbf{F}$ has sublinear $\alpha$-regret, then it will have negative $\alpha'$-regret.)

Finding the optimal approximation coefficient is highly non-trivial. For example, for non-monotone DR-submodular functions over downward-closed convex sets, the optimal approximation coefficient is still unknown.

Thanks for the detailed responses. These examples will increase the clarity of the presentation. I noticed the author's response to another reviewer happened to address the question I intended to ask about 'how to construct a suitable wrapper'. Therefore, I have no further questions.

The paper is purely theoretical. No simulations is provided to demonstrate practical performance of the meta-algorithms

The reason we have not added simulations is two-fold.

First, given the theoretical nature of our work and the extensive coverage of difference scenarios, it is not clear what experiments could support our main contributions. An experiment for the zeroth-order algorithm in one of the settings will only demonstrate that, in that setting, that algorithm is performant. Such an experiment only marginally supports our main contribution, which is Meta-algorithm 1 and the guideline described in Section 6.

Second, it is common for papers that are theoretical like this to not have experiments.

For many practical functions, how should we construct a suitable wrapper W? Are there heuristics or automatable steps, especially for less structured non-convex functions?

Given the difficulty of non-convex optimization, finding a uniform wrapper for a single function class is a powerful result. In general, even for offline optimization, there are few families of non-convex functions where global convergence results are currently known. Thus, any heuristic that could be applied to a general family of function classes would be an immensly powerful breakthrough, as it would result in global convergence guarantees for online optimization of the all the function classes in that family.

In order to construct a uniform wrapper $\mathcal{W}$, we need to specify $\mathcal{W}^{\operatorname{action}}$, $\mathcal{W}^{\operatorname{function}}$, and $\mathcal{W}^{\operatorname{query}}$.

So far, except for the identity wrapper which applies to both concave functions and monotone up-concave functions over general convex sets, the examples of uniform wrappers fit into the following framework:

There is a random variable $\mathcal{Z}$ taking values in $[0, 1]$ and a parametrized family of functions $h_z : \mathcal{K} \to \mathcal{K}$ for $z \in [0, 1]$, such that, for some $\alpha \in (0, 1]$ and $\beta, \mu \geq 0$, we have

$\alpha f(y) - f(x) \leq \beta \left( \langle \nabla F(x), y-x \rangle - \frac{\mu}{2}\| y - x \|^2 \right)$,

where $F(x) = \mathbb{E}_{z \sim \mathcal{Z}} [f(h_z(x)) - f(h_0(x))]$.

In this case we define $\mathcal{W}^{\operatorname{action}} = h_1$, and $\mathcal{W}^{\operatorname{function}}(f) = F$. We also define $\mathcal{W}^{\operatorname{query}}(Q_f)$ such that it converts a query oracle for $f$ into a query oracle for $F$ using the following equality:

$\\nabla F = \mathbb{E}\_{z \sim \mathcal{Z}} [\\nabla f(h_z(x)) J_{h_{z}}(x) - \\nabla f(h_z(x)) J_{h_{0}}(x)]$,

We will add a discussion on these lines in the final version.

We thank the reviewer for their review and suggestions.

Clarity: ... substantial space is devoted to presenting results, leaving limited room for presenting and explaining the approach.

The main concepts and ideas are explained in Sections 4, 5, and 6 in the main text and Appendices A and C. The core ideas are mathematically complete, but somewhat abstract, which makes them difficult to explain and understand without examples. This is why we have devoted Sections 7 and 8 to examples and applications of our method, which takes a total of 2.5 pages. However, there is a tradeoff between the simplicity of the example and the significance of its application. In Section 7, we have chosen an example that would allow us to obtain novel results.

We believe that, given the abstract nature of the ideas, the best way to increase clarity might be to add a simpler example. In the response to reviewer ESFd, we have detailed how our guideline may be applied to a simpler base algorithm, namely Online Gradient Ascent. The resulting algorithms are not novel, but the procedure will increase the clarity of our presentation. We will include this example in the final version in the main text to further clarify the main ideas.

In the final version, we will expand Section 6 further to clarify the ideas. We will also add examples of pseudo-codes for application of the specific uniform wrappers we consider to the base algorithm mentioned in Section 7.

Significance: ... However, it is worth noting that the approach only beats the SOTA in a limited number of cases. This means that the approach does not contain too many substantial insights that can break the barrier for online up-concave optimization. This paper may be regarded as an interim summary in some sense.

As discussed in the paper, and in the Online Gradient Ascent example in our response to reviewer ESFd, even though the changes to the original algorithm and proof could be very minor, one can not simply claim that the original proof could be adapted to the format we require without justification. Thus, applying our guideline requires an almost complete rewriting of the proof of the original regret bound.

In this work, we provide an example for zeroth-order case. However, this is merely because of limited space. Our technique is general enough that, a priori, it is not possible to rule out any algorithm for online concave optimization as a base algorithm. The result of [Pedramfar and Aggarwal, 2024a] covers base algorithms that are deterministic and require first order feedback. However, there are first order algorithms that are not deterministic. For example, all Follow-The-Perturbed-Leader type algorithms are by definition stochastic as they require perturbation. Similarly, the SOTA projection-free online concave optimization algorithm using membership oracles is also stochastic (See [1]). On the other hand, the results of [Pedramfar and Aggarwal, 2024a] do not cover any base algorithm that is not first order. Thus none of the zeroth-order or second-order (e.g. Newton method) feedback algorithms are directly covered by [Pedramfar and Aggarwal, 2024a]. While it is possible to add more results in this paper, by considering more base algorithms, we would need to introduce the notation, ideas, and proofs of those results in entirety in order to do so. The paper [1] is 77 pages. Even if adapting this result using our framework increases our page count by only 30 pages, it would still result in an overly lengthy paper and reduce the clarity of the presentation. Moreover, none of the ideas used in [1], or in second-order algorithms, or even in the zeroth-order algorithm that we have discussed in Section 7, are directly relevant to the main contribution of our work.

[1] Efficient Projection-Free Online Convex Optimization with Membership Oracle - Mhammedi - 35th Annual Conference on Learning Theory - 2022

We thank the reviewer for their review and positive assessment of our work.

... Earlier work by Pedramfar and Aggarwal (who also introduced the class of quadratizable functions) provided a method to automatically translate between these two regimes, but their method is somewhat more lossy than the method presented in this paper (in the zeroth-order FTRL application mentioned above, the algorithm of Pedramfar and Aggarwal results in suboptimal $T^{3/4}$ rates)

We note that the result of [Pedramfar and Aggarwal, 2024a] for the zeroth order case is obtained by transforming a first-order algorithm and then converting the resulting first-order algorithm into a zeroth-order algorithm using one-point gradient estimators (a la [Flaxman et al., 2005]). Specifically, they require the base algorithm to be first-order and their result cannot be directly applied to a zeroth-order base algorithm.

... it would have been helpful to have a bit more exposition explaining which of the new results in Table 1 arethe most significant improvements over the existing state-of-the-art algorithms. (Right now my impression is that the improvements largely are limited to previously not-well-studied domains, e.g. stochastic-within-a-cone queries, but there are many results and I could have missed some important ones).

The most significant improvements are for previously studied oracle types. Note that a deterministic oracle is a special case of stochastic-within-a-cone oracle. Thus, when considering either deterministic or fully stochastic query oracles, we obtain superior regret guarantees for 3 settings. Specifically, for online or offline zeroth order feedback, we improve the SOTA for monotone up-concave functions over general convex sets and for bandit feedback, we improve the SOTA for non-monotone up-concave functions over general convex sets. (See Tables 1 and 2)

However, we note that the results in Tables are by no means the only applications of our work. We have only considered the zeroth-order algorithm of [Saha and Tewari, 2011] due to the limited space in the paper. We refer to our response to reviewer ALb7 for more details on other possible applications.