- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies zeroth-order continuous DR-submodular maximization over polyhedral constraints. The authors propose State-aware Direct Search (SDS), which exploits local constraint geometry to construct feasible polling directions in nondegenerate states and resorts to zeroth-order gradient estimation in degenerate states. By combining SDS with existing non-oblivious objectives, the paper establishes approximation guarantees of , , and for three problem settings, together with expected iteration complexity. The corresponding value-oracle complexities are and under exact and stochastic oracles, respectively.
Critical strengths
The paper develops a state-aware zeroth-order framework that exploits local polyhedral geometry to obtain feasible search directions without explicit gradient estimation in nondegenerate states. It provides a unified analysis establishing approximation guarantees and expected iteration and value-oracle complexity bounds across several DR-submodular maximization settings.
Critical weaknesses
The main technical ingredients, including direct search, positive-generating sets, and non-oblivious approximation guarantees, are largely based on existing results.
Although the state-aware mechanism provides an alternative to gradient estimation, its independent theoretical contribution remains unclear. In particular, the proposed method does not establish a general improvement in value-oracle complexity, while the dependence on the geometry and conditioning of the polyhedral constraints is not sufficiently characterized.
It is also unclear under what conditions the proposed mechanism is more efficient than existing zeroth-order methods. Moreover, the experiments do not adequately isolate the contribution of state-aware switching.
Questions for authors
-
What new theoretical insight does the state-aware mechanism provide beyond combining existing direct-search techniques and non-oblivious approximation guarantees? In particular, can the authors establish a geometry-dependent oracle complexity bound that characterizes the effects of constraint conditioning, polling-set size, and degenerate states, thereby clarifying when the proposed method offers a genuine advantage?
-
Under what conditions is direct polling more efficient than standard zeroth-order projected-gradient methods? Since direct polling also requires function-value evaluations, can the authors provide a rigorous comparison under the same auxiliary objective and oracle model?
-
Table 1 classifies Lian et al. (2024) under the exact value-oracle model, whereas the original CG-ZOSA and RG-ZOSA results are established for finite-sum stochastic function-value oracles, with complexity bounds depending on both the dimension and the number of components. Could the authors clarify which result is being cited and justify the oracle classification and complexity comparison?
-
Can the authors compare SDS with always-gradient and pure direct-search variants under the same objective and oracle budget to isolate the benefits of state-aware switching, particularly in degenerate settings?