acceptodds
Withdrawn from ICLR 2027

State-Aware Zeroth-Order Search for DR-Submodular Maximization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We study zeroth-order continuous DR-submodular maximization over polyhedral constraints and introduce *state-aware direct search* (SDS), a new zeroth-order search paradigm in which local polyhedral geometry determines how search directions are obtained. On nondegenerate iterations, SDS directly polls feasible directions generated from the local geometry, while gradient estimation is used only in degenerate states. We develop a unified analysis framework that extends SDS to non-oblivious objectives whose stationarity yields approximation guarantees. For monotone and nonmonotone maximization over general polytopes, and nonmonotone maximization over down-closed polytopes, SDS achieves approximation factors , , and , respectively, with expected iterations in all three settings. Under exact and stochastic value oracles, the corresponding worst-case expected value-oracle complexities are and , respectively. This matches the best known iteration dependence for general polytopes and improves the zeroth-order iteration complexity for the guarantee in nonmonotone down-closed maximization from to . Numerical experiments demonstrate the practical effectiveness of SDS, with degenerate states rarely encountered in practice.

Primary area:
optimization
Keywords:
DR-submodular maximization, zeroth-order optimization, direct search

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_yWDbOpenReview ↗
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 1−1/e1-1/e, (1−h)/4(1-h)/4, and 1/e1/e for three problem settings, together with O(ϵ−2)O(\epsilon^{-2}) expected iteration complexity. The corresponding value-oracle complexities are O(rϵ−3)O(r\epsilon^{-3}) and O(r2ϵ−4)O(r^2\epsilon^{-4}) 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
  1. 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?

  2. 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?

  3. 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?

  4. 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?

Reviewer_EBBzOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies continuous DR-submodular maximization over explicit polytopes when only function values are available. The proposed state-aware direct search (SDS) algorithm chooses how to search according to the local constraint geometry. It polls feasible directions in nondegenerate states and estimates a reduced gradient in degenerate states. By applying this procedure to existing non-oblivious auxiliary objectives, the authors obtain approximation factors 1−1/e1-1/e, (1−h)/4(1-h)/4, and 1/e1/e for the three settings considered. They prove an O(ε−2)O(\varepsilon^{-2}) expected time to reach approximate stationarity. The corresponding worst-case expected query costs are O(ε−3)O(\varepsilon^{-3}) with exact values and O(ε−4)O(\varepsilon^{-4}) under the stochastic oracle, suppressing dependence on dimension, geometry, and regularity. Experiments examine query use and how often the algorithm encounters degenerate states.

Critical strengths

SDS has a sensible way of adapting to the constraint geometry. It avoids reconstructing a full gradient on nondegenerate steps, while gradient estimation in degenerate states avoids enumerating a potentially difficult set of directions. This could be useful in practice, and the experiments provide evidence of query savings on the tested instances.

Critical weaknesses
  1. Algorithm 1 does not specify a stopping rule or explain which iterate should be returned. Theorem 3.5 establishes approximation at XTεX_{T_\varepsilon}, but TεT_\varepsilon depends on the unknown true gradient of the auxiliary objective. Theorem 4.1 then counts queries up to this time. Since the algorithm cannot identify TεT_\varepsilon, these results do not yet show how to return a solution with the claimed approximation and query cost. An observable certificate or a finite-budget output guarantee would address this concern. I consider this a fixable but material omission.
  2. My main concern is the limited novelty of the theoretical contribution. The approximation factors follow from existing non-oblivious objectives, and the ε−2\varepsilon^{-2} stationarity dependence builds on established direct-search analysis. The improved iteration bound in the down-closed setting does not improve the ε−3\varepsilon^{-3} value-query complexity, while the stochastic comparisons involve different oracle assumptions. The main new ingredient therefore appears to be the switch between polling and gradient estimation according to local geometry. Although this is a reasonable design and may reduce queries in practice, I am not convinced that the current results establish a sufficiently substantial advance over existing methods.
Questions for authors
  1. The approximation guarantee in Theorem 3.5 concerns XTεX_{T_\varepsilon}, but TεT_\varepsilon depends on the unknown gradient of the auxiliary objective. How should Algorithm 1 stop or select an output using only the available information? Please explain whether the resulting output preserves the stated approximation guarantee within the query bound of Theorem 4.1.
  2. Could the authors clarify what advantage the state-dependent switch provides over projected ascent using the same auxiliary objectives and value-based gradient estimators? The approximation factors are inherited, and the improved iteration bound in the down-closed setting does not improve the value-query exponent. Is there a theoretical advantage under comparable oracle assumptions that is not apparent from the current bounds, or is the main benefit the query savings observed in the experiments?
Reviewer_F8hAOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes state-aware direct search (SDS) for zeroth-order continuous DR-submodular maximization over polytopes. SDS polls feasible directions in non-degenerate states and estimates reduced gradients only when degenerate, using non-oblivious objectives across monotone/general/down-closed settings. It shows the expected number of iterations and improved value-oracle bounds. Experiments on quadratic, finite-sum, and coverage benchmarks show efficiency vs. baselines.

Critical strengths

S1. This paper handles monotone, nonmonotone general, and down-closed polytopes with one algorithm and an iteration guarantee.

S2. SDS avoids full gradient estimation in nondegenerate states, yielding improved oracle-complexity bounds and consistent gains.

Critical weaknesses

W1. The iteration complexity merely matches existing bounds, and improvements are incremental polynomial-factor gains.

W2. Experiments rely on synthetic quadratic/coverage instances, and no real-world problems are considered.

W3: The rank test, active-set construction, and positive-generator computation are not included in complexity accounting; these costs may dominate the claimed oracle savings.

W4: Conditional information reliability, smoothness, bounded paired noise, and unspecified constants are assumed rather than validated.

W5: SDS combines existing non-oblivious objectives, direct search, and subspace polling with a state switch; the core mechanism is engineering rather than a fundamentally new idea, and no lower bound shows the state-aware design is necessary.

Questions for authors

See Critical Weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.