Uniform Wrappers: Bridging Concave to Quadratizable Functions in Online Optimization

Authors: Mohammad Pedramfar, Christopher John Quinn, Vaneet Aggarwal
Primary area: optimization
Keywords: DR-submodular Optimization, Convex Optimization

Abstract:
This paper presents novel contributions to the field of online optimization, particularly focusing on the adaptation of algorithms from concave optimization to more challenging classes of functions. Key contributions include the introduction of uniform wrappers, establishing a vital link between upper-quadratizable functions and algorithmic conversions. Through this framework, the paper demonstrates superior regret guarantees for various classes of up-concave functions under zeroth-order feedback. Furthermore, the paper extends zeroth-order online algorithms to bandit feedback counterparts and offline counterparts, achieving a notable improvement in regret/sample complexity compared to existing approaches.

Decision: reject
Reviewer scores: 5, 3, 3

Reviews and discussion:
<thread>
creation date:
1730189672142

thread_type:
official_review

<thread_object>
creator: reviewer_e3zd

<content>
summary:
This article develops a general framework for transferring the algorithms and their regret guarantees from online convex/concave optimization to online quadratizable optimization. Within this framework, the authors employ a variant of Follow-the-Regularized-Leader (FTRL) from [1] to enhance the regret guarantees for several classes of weakly DR-submodular functions under zeroth-order and bandit feedback.

[1] Ankan Saha and Ambuj Tewari. Improved regret guarantees for online smooth convex optimization with bandit feedback. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 636–642. JMLR Workshop and Conference Proceedings, 2011.”

strengths:
1.The authors have improved the regret bound for online optimization problems across three function classes under zeroth-order feedback, from $\tilde{O}(T^{3/4})$ to $\tilde{O}(T^{2/3})$.

2.The authors have enhanced the regret bound for online optimization problems across three function classes under bandit feedback, improving it from $\tilde{O}(T^{4/5})$ to $\tilde{O}(T^{3/4})$.

weaknesses:
1.The technical contribution is quite limited. Although the upper quadratizable function is highly non-convex, many previous articles, especially [2], have shown that this upper quadratizable function satisfies a first-order variational inequality similar to that of a convex function (Lemma 1, 2, 3). Therefore, we can consider the upper quadratizable function as a special type of "quasi-concave" function. Consequently, it is quite natural for this paper to use a variant of FTRL [1] to improve the regret bounds in zero-order and bandit scenarios.

2.This paper lacks an in-depth discussion of the applications of the upper quadratizable function and a practical evaluation of the newly introduced algorithms. This statement may make readers feel that the authors are merely exploring a new function without clarifying its relevance or impact on the machine learning community.

3.From the full text and Definition 2, it appears that the primary purpose of introducing the upper quadratizable function is to study $\gamma$-weakly continuous DR-submodular functions. So, why not focus on "$\gamma$-weakly continuous DR-submodular functions" as the main subject of the paper? Can the authors provide examples of applications where the target function is upper quadratizable but not $\gamma$-weakly continuous DR-submodular functions?


[1] Ankan Saha and Ambuj Tewari. Improved regret guarantees for online smooth convex optimization with bandit feedback. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 636–642. JMLR Workshop and Conference Proceedings, 2011.

[2]Mohammad Pedramfar and Vaneet Aggarwal. From linear to linearizable optimization: A novel framework with applications to stationary and non-stationary DR-submodular optimization. arXiv preprint arXiv:2405.00065, 2024a.

questions:
1. Could the authors provide a detailed personal perspective on how their technical contributions differ from those in references [1] and [2]?
2. Could you provide a detailed explanation of the applications of upper quadratizable functions and conduct an empirical evaluation of the newly proposed algorithms?  
3. Can the authors provide examples of applications where the target function is upper quadratizable but not $\gamma$-weakly continuous DR-submodular functions? 
4. Why not focus on "$\gamma$-weakly continuous DR-submodular functions" as the main subject of the paper?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730675838373

thread_type:
official_review

<thread_object>
creator: reviewer_orvx

<content>
summary:
This work gives a framework that reduces the problem of online optimization with quadratizable functions (Pedramar & Aggarwal, 2024a) to OCO. This results in state-of-the-art guarantees in several settings and improvements in some others.

strengths:
- The framework provides improvements in the state-of-the-art regret bounds in several settings.
- The presentation is sufficiently clear.

weaknesses:
Although there might be some small improvements in the analysis of Pedramar & Aggarwal (2024a), the framework appears to be nearly identical to that in Pedramar & Aggarwal (2024a). Nearly every technical result in the paper is due to Pedramar & Aggarwal (2024a), e.g. Lemma 1, Lemma 2, Lemma 3, ... I do not see any novelty in techniques or approach.

questions:
What is the technical novelty with respect to Pedramar & Aggarwal (2024a)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730775298646

thread_type:
official_review

<thread_object>
creator: reviewer_pu29

<content>
summary:
This paper provides an in-depth exploration of advanced techniques for online optimization, particularly focusing on transitioning algorithms from concave optimization to more complex classes. This work contributes by introducing "uniform wrappers," a framework for adapting standard online convex optimization (OCO) algorithms to handle non-convex, quadratizable functions while preserving sublinear regret bounds.

strengths:
- The paper considers a challenging and important problem in online optimization, namely, how to extend algorithms from the convex to the non-convex setting.
- The core idea of uniform wrappers allows traditional OCO algorithms to handle quadratizable functions by converting feedback and actions within a structured wrapper framework. This wrapper effectively bridges the gap between simpler convex optimization and more complex quadratizable function classes. Moreover, this framework is general and can be applied to a wide range of function classes.
- This paper obtains or matches the state of the art algorithm in several online optimization settings considered. For classes such as weakly DR-submodular functions under
zeroth order feedback, the framework provides superior regret guarantees, surpassing prior results in the field.

weaknesses:
- The paper is quite dense and difficult to follow. The theoretical framework is complex, with multiple layers of definitions (e.g., quadratizability, up-super-gradients, and uniform wrappers) that might limit accessibility for a broader audience. While this complexity is necessary to cover a broad class of functions, it risks making the approach difficult to understand for readers unfamiliar with the field. The presentation could be improved by providing more intuition and examples to help readers understand the core ideas and contributions. 
- The paper cites and builds upon prior work in DR-submodular and up-concave optimization (e.g., Pedramfar & Aggarwal, 2024), but it lacks a clear differentiation of its unique contributions. The proposed framework appears to be an incremental improvement rather than a groundbreaking advance. I suggest the authors to clarify the novelty and significance of their work compared to existing methods in the field.
- I am quite confused about the necessity of the uniform wrappers. The paper does not provide a clear motivation for why uniform wrappers are needed or how they improve upon existing methods. A more detailed discussion on the limitations of current approaches and how uniform wrappers address these limitations would be beneficial.

questions:
- I wonder the significance of the upper quadratizable/linear functions. Why are these functions important, and how do they relate to real-world applications? It would be helpful to provide more context on the motivation behind this class of functions and why they are relevant in practice.
- What are the conditions under which uniform wrappers can be applied? Are there any limitations that restrict the applicability of this framework to certain function classes or settings?
- I am interested in the regret defined in Line 203. Can the results reduce to the dynamic regret and adaptive regret? If so, how do they compare to existing methods in these settings?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732090104167

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Here we respond to some common comments and clarify some aspects of our contributions.

**Comparison with previous works**

The core question this paper addresses is
*When and how can we adapt algorithms from the (simpler) setup of online convex optimization into algorithms for online optimization over linearizable functions?*

Consider the following classes of online algorithms for convex/concave optimization:  
I. Deterministic algorithms with deterministic first-order semi-bandit feedback.  
II. All algorithms that *have* a proof which can be adapted using steps 0-2 detailed in Section 6.  
III. All algorithms.  
In (Pedramfar \& Aggarwal, 2024a) the notion of linearizable function classes are defined and a meta-algorithm is proposed for the class I above.
This meta-algorithm, namely OMBQ, can only be applied to class I and Theorem 1 in that paper shows that the guarantees for the original algorithm carry over to the linearizable case.
However, this class is quite limited.
For example, the requirement of first-order semi-bandit feedback rules out all zeroth order or bandit algorithms.
Or the requirement that the algorithm should be deterministic rules out algorithms such as Follow-The-Perturbed-Leader.

On the other hand, in this paper we propose meta-algorithms that could be applied to *any* algorithm.
Uniform wrappers can wrap any algorithm and propose new algorithms for linearizable optimization.
The regret guarantees do not necessarily carry over for any algorithm imaginable.
However, the guideline described in Section 6 shows how to obtain regret guarantees for algorithms belonging to class II.

To summarize, while the meta-algorithm OMBQ proposed in (Pedramfar \& Aggarwal, 2024a) applies to class I above, we propose uniform wrappers which can wrap *any* algorithm.
When it comes to regret guarantees, while Theorem 1 in (Pedramfar \& Aggarwal, 2024a) again applies to class I above, our guideline applies to class II which is significantly larger.

We achieved this by going through and gaining a deeper understanding of the existing algorithms and proofs and identifying exactly what makes them work, abstracting it away and condensing it into meta-algorithms (i.e., uniform wrappers) and the guideline detailed in Section 6.
In particular, the OMBQ meta-algorithm may be seen as an application of our guideline to Theorem 2 in (Pedramfar \& Aggarwal, 2024b) using a special case, namely 1st-order-to-1st-order case, of the uniform wrappers described in Section 7. 
However, this is only a special case, while our framework is much more general. 


Note that all results in Tables 1 and 2 that are marked with a blue (*) are results that fit into our framework and could be seen as an application of uniform wrappers. (The same could be said of every result of (Pedramfar \& Aggarwal, 2024a), even those that we didn't mention in Table 1.)
Moreover, the proofs of all those results also fit within our framework and can be seen as application of the guideline specified in Section 6.
Furthermore, to demonstrate the generality of our framework, besides recovering previous results, we also obtain 9 new results, all of which are SOTA within the respective setting.

In other words, we are not just proving a single result. We are demonstrating how many results in the literature (most of which are SOTA in their respective settings) can be obtained via a single framework and when and how one might go about obtaining more results.


**Specific new results**

As specific applications of our framework, we obtain 9 new results.

1. We improved the regret bound for online optimization problems across three function classes under zeroth-order feedback, detailed in Theorem 6, from $O(T^{3/4})$ to $O(T^{2/3})$.

2. We enhanced the regret bound for online optimization problems across three function classes under bandit feedback, detailed in Theorem 7, improving it from $O(T^{4/5})$ to $O(T^{3/4})$.

3. We improved the sample complexity for offline optimization problems across three function classes under zeroth order feedback, detailed in Theorem 8, improving it from $O(\epsilon^{-4})$ to $O(\epsilon^{-3})$.

There are many examples in the literature, published in top ML venues, where the authors obtain a single result in similar settings.
These applications alone are significant contributions to this field.

However, these results are merely special applications of our framework.
Specifically, Theorem 2 is an application of our framework and all the above results are applications of Theorem 2.
We will change the title of the sections to reflect this fact.

To the best of our knowledge, in all cases considered in Tables 1 and 2, i.e., both in online and offline case, whether projection-free or not, (and also in all non-stationary cases that are discussed in (Pedramfar \& Aggarwal, 2024a)), our framework obtains or matches the SOTA in DR-submodular optimization.
</content>
</thread_object>

</thread>
<thread>
creation date:
1768524514202

thread_type:
public_comment

<thread_object>
creator: ~mohammad_pedramfar1

<content>
comment:
Please see the revised version of the paper, published in NeurIPS, at https://openreview.net/forum?id=dgQRSJdo6a
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces the notion of "uniform wrappers", an algorithmic meta-framework intended to provide regret guarantees for various classes of functions under zeroth-order feedback. The class of functions considered are essentially "quadratizable" in the sense of Pedramfar and Aggarwal (2024), which implies that its optimum points satisfy a first-order variational inequality similar to (pseudo-) convexity. The authors provide a meta-analysis based on these wrappers, which allows them to extract regret guarantees from algorithms with known performance in online convex optimization.

The reviewers raised several concerns about this paper, namely that it is densely written, difficult to follow, and incremental relative to the work of Pedramfar and Aggarwal (2024). The reviewers were unanimous in their evaluation that the paper does not clear the (admittedly high) bar for ICLR and the authors' responses did not convince them otherwise, so it was decided to make a reject recommendation.