Submodular Function Minimization with Dueling Oracle
Authors: Kaien Sho
Shinji Ito
Venue: ICLR 2026 Poster (2026)
Keywords: submodular minimization
deling oracle
preference-based optimization
Primary area: optimization
TL;DR: We study submodular minimization with a dueling oracle giving noisy pairwise feedback.

Abstract: We consider submodular function minimization using a *dueling oracle*, a noisy pairwise comparison oracle that provides relative feedback on function values between two queried sets.
The oracle's responses are governed by a *transfer function*, which characterizes the relationship between differences in function values and the parameters of the response distribution.
For a linear transfer function, we propose an algorithm that achieves an error rate of $O(n^{\frac{3}{2}}/\sqrt{T})$, where $n$ is the size of the ground set and $T$ denotes the number of oracle calls.
We establish a lower bound: Under the constraint that differences between queried sets are bounded by a constant, any algorithm incurs an error of at least $\Omega(n^{\frac{3}{2}}/\sqrt{T})$.
Without such a constraint, the lower bound becomes $\Omega(n/\sqrt{T})$.
These results show that our algorithm is optimal up to constant factors for constrained algorithms.
For a sigmoid transfer function, we design an algorithm with an error rate of $O(n^{\frac{7}{5}}/T^{\frac{2}{5}})$,
and establish lower bounds analogous to the linear case.

Published as a conference paper at ICLR 2026
SUBMODULAR FUNCTION MINIMIZATION WITH DUELING ORACLE
Kaien Sho' Shinji Ito
'The University of Tokyo PRIKEN
tho-kaienn023eg. ecc. u-tokyo. ac. jp, shinji@mis st. i, u-tooyo,.cc ip
ABSTRACT
We consider submodular function minimization using a dueling oracle, a noisy pairwise comparison oracle that provides relative feedback on function values between two queried sets. The oracle's responses are governed by transfer function, which characterizes the relationship between differences in function values and the parameters of the response distribution. For a linear transfer function, we propose an algorithm that achieves an error rate of O /VT,, where n is the size of the ground set and T denotes the number oracle calls. We establish lower bound: Under the constraint that differences between queried sets bounded by constant, any algorithm incurs error of at least 2(n /VT). Without such constraint, the lower bound becomes (2(n/ /T). These results show that our algorithm is optimal up to constant factors for constrained algorithms. For a sigmoid transfer function, we design an algorithm with an error rate of O(n /T²), and establish lower bounds analogous to the linear case.
INTRODUCTION
Let f be set function defined on subsets of a finite set [n] {1, .n. A function f is called submodular if it satisfies f(X) + f(Y) 2 f(X UY) + f(X nY) for X,Y C [n].
Submodular functions are closely related to convex functions (Lovász) 1982 Fujishige 1991 Bach
201T) and play a significant role in numerous problems. Thus, submodular function minimization
(SFM) arises in wide range of research fields, including machine learning (Bilmes) 2022). opera-
tions research (Hochbaum Hong 1995 Qucyranne & Schulz 1995), combinatorial optimization
(Lovász] 1982 (aatmmoodds[2000000 Schrijver 2003), game theory (Shapley 1971 Topkis 1998), and
economics (Stigler & Samuelson, 1948 Topkis 1998| Vives 1999). In machine learning and artificial
intelligence, SFM has found use tasks such graphical models (Kolmogorov
Zabih 2002
Krause & Guestrin 2005), PAC-learning (Narasimhan & Bilmes 2004), clustering (Narasimhan
al. 2005 2005] Narasimhan & Bilmes 2007), and image segmentation (Kohli & Torr
2010 &
Bilmes 2011).
In optimization problems, many studies assume access to first- zero-order oracles that provide gradients or exact function values at queried points. However, in real-world scenarios, it is often impractical or unreliable obtain precise gradients function values. Instead, feedback based on relative evaluations, which determines which of two options is preferable, tends to be more feasible, efficient, and robust.
For example, in machine learning, data collection through relative evaluations not only improves reliability but also facilitates the acquisition larger datasets. Pairwise comparison queries are widely used in applications such as feedback collection for large language models (LLMs) (Liusic) ct al. 2023. Wu et al.) 2023; Jiang et al. 2023 Liu et al.) 2024) and reinforcement learning with human feedback (RLHF) (Sadigh al. 2017 Pacchiano et al. 2021 Azar al. 2024 Zhu et al. 2023).
Research on optimization problems using dueling oracle has been limited to multi-armed bandit
problems Yue et al.) 2012 Dudik et al.] [2015] (Sui et al.] 2018) (aha et al.) 20216 Saha & Gaillard
2022) and convex optimization (Saha et al. 2021a la 2025
Blum al." 2024). the context of

---

Published as a conference paper at ICLR 2026
Table 1: Upper and lower bound for submodular function minimization with a dueling oracle.
Transfer Function
Linear
Sigmoid
General
Upper Bound
O
n VT
a T
T
Lower Bound
?
f2
(with Restriction
VT
VT
vT
Lower Bound
52
?
(without Restriction
vT
VT
VT
Submodular Function Minimization (SFM), the setting in which only a dueling oracle is used without access to value oracle has not been addressed so far, making this study the first to explore it.
Existing studies on SFM assume access to oracle that provides the exact or noisy function value for a queried set. The first polynomial-timg algorithm for this problem was introduced by Grötschel et al. (98T), employing the ellipsoid method. Combinatorial strongly polynomial algorithms were developed by Iwata et al. (2000) and [Schrijver (2003). In parallel, Hazan & Kale (2012) explored online optimization for submodular functions, focusing on iterative decision making and evaluating performance through regret, defined as cumulative error during iterations. addition, Ito (2019) investigated SFM in the context of noisy function value oracles.
In this paper, we consider SFM with a dueling oracle. A dueling oracle, or a noisy pairwise comparison oracle, provides probabilistic binary feedback indicating which of two queried sets has a higher function value, without disclosing the actual function values. The algorithm can query a pair of sets, and the dueling oracle only returns probabilistic response in +1 or -1, indicating which set has the higher function value. The probability of receiving the correct response increases as the difference in function values grows, while smaller differences result in outcomes that are nearly evenly distributed. This reflects the concept of duel, where larger differences favor the stronger contender, while smaller differences introduce more uncertainty in response. This problem setting motivated by applications such as recommendation, as illustrated in Examples [ and 2 The relationship between differences in function values and parameters of the response distribution characterized by function p 1, > [-1, 1). called transfer functioon.
in Section 3
Our contribution is twofold. First, we propose efficient algorithms for SFM using a dueling oracle with linear, sigmoid, and general nonlinear transfer functions. The reason for focusing on these two concrete examples is explained in Section 3 Second, we establish lower bounds for each setting. As shown in Table 1 for the case of a linear transfer function, we develop algorithm that achieves an error bound of (n /VT) for any submodular function. For sigmoid transfer functions, propose an algorithm with an upper bound of O /T3), ). and for general nonlinear transfer functions, we provide an algorithm with an upper bound of (n / /T²).. Regarding lower bounds, we show that any algorithm satisfying the constraint that the element- wise difference between the two sets queried by the dueling oracle is of constant order must incur error of at least 2(n /VT) in hard instance. Furthermore, we prove that any algorithm, without restrictions, must suffer an error of at least ((n/VT). This result implies that, for the linear transfer function, our proposed algorithm is optimal among those satisfying the given constraint, and even with unrestricted algorithms, the error cannot be improved by more than factor of (L)v/n). We here note that, while the formulas in represen the error achievable with given number of queries T. these can also be interpreted as an evaluation of the number of queries required to achieve an error below a given threshold > O. For example, the upper bound of O(n /VT) in the table indicates that an error no greater than can be attained with T x n3/e² queries.
Our algorithm leverages the Lovász extension (Lovász 1982) which extends submodular function to a continuous convex function, and employs the stochastic gradient descent (SGD) method for convex minimization. A key property of the Lovász extension is that the minimum of the original submodular function coincides with the minimum of the extended convex function. Thus, solving the convex minimization problem via SGD yields solution to SFM. The update direction in SGD is determined by an estimator of a subgradient of the convex function. To minimize the error introduced by SGD, reducing the bias and variance of this estimator is crucial. In particular, an unbiased
2

---

Published as a conference paper at ICLR 2026
estimator, whose expectation matches the true subgradient, leads to accurate solutions. The approach using the Lovász extension and SGD has already been explored by Hazan & Kale (2012); Ito (2019)
2022). However, unlike these studies, direct access to function values is unavailable in setting. While these works construct unbiased estimators of subgradients using the responses from a function
value oracle, estimate subgradients using responses from dueling oracle.
For the linear transfer function, unbiased estimators of subgradients can be constructed by using responses from a dueling oracle. The general flow of the algorithm is similar those proposed by Ito (201)), the difference being in the construction of the unbiased estimator.
Hazan & Kale (2012)
In contrast, for the sigmoid transfer function, the construction of unbiased subgradient estimators becomes infeasible. which poses a significant challenge. Using biased estimators in SGD can cause error accumulation across iterations, resulting in considerable inaccuracies. In related work, Saha et al. 2025) addressed a similar issue in convex optimization with a dueling oracle. They considered a gradient descent-basee algorithm under similar conditions, where unbiased subgradient estimators were unavailable. Their approach relies on the assumptions of 3-smoothness and a-strong convexity of the objective function to control errors. Unfortunately, the convex function derived from the Lovász extension of general submodular function does not satisfy these properties, making Saha ct al. 2025)'s eτror control techniques inapplicable.
To overcome this difficulty, we incorporate Firth's 's method (iirhh 1993 to reduce the bias in maximum likelihood estimators (MLE). Firth's method significantly reduces bias in estimation problems related to the natural parameters of the exponential family of distributions. In this study, when the transfer function of the dueling oracle is sigmoid, the resulting model corresponds to logistic regression, making it possible to apply Firth's 's method. By incorporating Firth's method into SGD, we mitigate the impact of accumulated bias, reducing the total error, and enabling an effective optimization algorithm. To our knowledge, no existing SFM algorithm based on SGD avoids the use of unbiased subgradient estimators derived from the Lovász extension. This is the significance of this work.
The inability to use an unbiased estimator makes not only the algorithm design but also its analysis and parameter tuning considerably more challenging. In existing studies (Hazan & Kale 2012 Ito 2019), the analysis of the optimization error typically focused on two terms that increase or decrease with the learning rate 17. and choosing 1) to balance these two terms yields the desired error (or regret) bound. In contrast, in the present setting, a third term arises from the bias of the gradient estimator, and an additional parameter, the number of oracle calls & used for gradient estimation, affects these terms, resulting in a more complex analysis. In this work, we provide a new parameter- rule for 17 and & that balances all three terms so that the overall error bound is minimized.
The proof of the lower bound is based on the techniques of Ito (2019) and Auer et al. 2002). Ito (2019) establishes lower bounds for SFM, while /uuer et al. (2002) addresses lower bound for bandit problem. While the construction of the objective function follows prior work (Ito) 2019), the lower-bound analysis presents a significant challenge, as the techniques used in previous studies cannot be directly applied. This difficulty arises because the oracle and feedback structure assumed in existing models differ substantially from those considered in this work. Intuitively, prior work allows queries on single subset, whereas our setting permits queries on pairs of subsets. Since the number of feasible choices for data collection therefore much larger in our framework, proving lower bounds becomes considerably more nontrivial. In this paper, we address this challenge by extending the analysis to incorporate the probability distribution over queried pairs and by analyzing the distance between the resulting distributions.
Leveraging Yao's principle, we bound the error of randomized algorithms by the error of deterministic al algorithms under carefully chosen distribution. For deterministic algorithms, the KI. divergence of the algorithm's 's output is bounded by the KI. divergence across all input sequences. Using these results, we demonstrate that for two objective functions, the KL divergence of their respective input sequences, and consequently, the KL divergence of their output, remains small. Finally, we show that for two objective functions with different optimal solutions, any algorithm can only exhibit limited changes in its output and thus incurs a non-negligible error.
1.1 RELATED WORK
Online submodular minimization in the bandit setting
3

---

Published as a conference paper at ICLR 2026
The online submodular minimization introduced by Hazan & Kale (2012) is closely related to our algorithm. In this setting, an online decision maker iteratively selects a subset St S [na] over t = 1. .T. After each selection, the decision maker incurs loss of f((S),, where each fa is a submodular function. The performance the algorithm is evaluated by the regrer defined as Regret, = Σx= f(() min Σi= f(()..
In the bandit setting, only the loss f((S,) for the chosen subset St is observed, and no other in- formation is available. The algorithm proposed by Hazan & Kale (20T2) is based the Online Gradient Descent algorithm of oinkiene 22003), using unbiased subgradient estimators derived from the Lovász extension extension of the submodular functions. The key idea of this algorithm is to dynamically adjust the probabilities of choosing subset and use just one sample for both exploration and exploitation. The regret achieved by this algorithm is (n(T3) ). which translates to an error of
(n/T3) when applied directly to SFM.
Submodular function minimization with noisy oracles
Our work also influenced by the study of SFM using a noisy zero-order oracle by Ito (2019); Lattimore (2024). In their work, each step 1,... ,T, subset S, is chosen, and noisy observation (S,) of the submodular objective function f is obtained, where f satisfies Bff f(S) for all S S [n] and t = 1, ... ,T
The algorithm their research is also based on SGD, with the final solution obtained as the average of the iterations over T steps. Their approach achieves emrrr of O (n //T) which improves to O (n/VT) under the assumption that each noisy observation fe also submodular.
Furthermore, their approach also influences the proof of the lower bound for SFM in our study. They constructed distribution of objective functions that serves hard instance, showing that even when a distribution is perturbed, the observed values change slightly, making it challenging for any algorithm distinguish between distributions. This was demonstrated using KL divergences of distributions.
Convex optimization with dueling oracle
Convex optimization using dueling oracles has been explored in Saha et al. (202 la) and Saha et al. (2025), which consider transfer functions P with specific properties. In Saha et (2021a), P is assumed to be sign function, while Saha et al. (2025) considers function that satisfies p (x) 2 (pp|x|/-11 for all E (-r,r), where p 2 1, r > O, and Cp > 0. Both studies propose Gradient Descent-based algorithms; however, unbiased estimators of subgradients cannot be constructed from the information ducling oracles.
To address this difficulty, Saha et al. (2021a) determined the descent direction using the normalized subgradient vf(x)//lV f(x) I.. and demonstrates that the algorithm produces an approximate solution. Mcanwhile, Saha et al. (025 introduces a scaled gradient approach using V fx) [[ [[ and shows that an approximate solution exists within the sequence of points generated by the algorithm.
Both approaches rely the assumptions of 8-smoothness and a-strong convexity of the objective function, which enable the analysis of convergence and approximation guarantees.
PRELIMINARIES
2.1 SUBMODULAR FUNCTIONS
Let be a positive integer and let [n] (1, 21,2, .1. Denote by 2 the power set of [m], i.c. the set
of all subsets of (n). We consider function : 2 [0, 1] defined in the decision space 2|el.
A function f 2 + [0, is submodular if and only if for all sets X,Y Y E 2/d such that X C Y and
for all elements i E [x] \ Y, we have:
S(XU (1) f(x) J( S(Y).
(1)
4

---

Published as a conference paper at ICLR 2026
2.2 LOvÁsz EXTENSION
The Lovász extension a fundamental technique in designing algorithms for submodular function minimization. Although submodular function f is originally defined in the decision space 2 can regarded as the vertices of the hypercube K. = [o. 1| The Lovász extension f provides a continuous extension of submodular function to the whole interior of K.
The Lovász extension is constructed by dividing the hypercube K. into n! regions and defining f as piecewise linear function that interpolates between the values of the function at the vertices of K.
Definition 1. Given function 2 + [0. 1]. the Lovász extension f K. [0. 1] is defined as follows; for w E K, order the components in decreasing order wx(1) 2 ... 2 (n(n) where :: [n] + [n] is a permutation. Let (x(0) = 1, B, = {I(1),.... m(i) for E [n]] and Bo = Ø. The value of the Lovász extension f(w) is defined as:
n-1 Σ f(B))(w=)) - + f([n)). (2)
f(w) Σ (=(olf(B.) f(B--)(BBBBB f(0)
An alternative equivalent expression for the Lovász extension is also utilized construct our algo- rithms.
Proposition 1. Let f be a Lovász extension of a function f 2 + [0, 1]. For any w E K, the following equations hold:
f(w)= - [(Ei =3)dd= Em [[( w; 2 =})]-
The following theorem provides connection between submodular function minimization and convex function minimization.
Theorem 1. Fujishige 1991 )) A function f 2 + [0, 1] submodular if and only if its Lovász extension f KC + [0. 1] is convex. For a submodular function f :22l + [o, 1] and its Lovász extension J:K + [0, 1]. we have minx f(X) minnw f(w) min fww).
When analyzing the minimization of the convex function f. is notable that f is piecewise linear. Therefore, its subgradient constant within each region of linearity, formally stated in the following proposition.
Let ff be submodular function. For w E K, let π be a permutation that orders the components of w in decreasing order, and let be the inverse permutation of Then, subgradient g of f at given as follows:
Proposition 2.
9x(1) (BB) f(B:.)) or, equivalently,
9: -BBB()))((BB)) f(Br
2.3 STOCHASTIC GRADIENT DESCENT
By Theorem D submodular minimization can be reformulated convex minimization. Therefore, our algorithm is based on the stochastic gradient descent (SGD) method for convex minimization.
The algorithm initializes (1) } K. For each iteration
1,2. .,....TTTT, ,T the point (()) is updated to (+++)) using information about the objective function f obtained through oracle queries. At each update, an estimator 9, of subgradient of f at u((t) is constructed, and the update rule is given by: ()+++)) (l - n9:), where 1 O is a learning rate parameter that can be arbitrarily chosen. Here, IIx R + KC represents the Euclidean projection onto X,, defined as: [e(()) = arg min,ex |/v w|l2. Since K. = [0. 1]", the projection is computationally efficient. For any v Ra, the projection w = (v) can implemented by clipping each component of the interval [0, 1]: w; min m0 m:)).
For the sequence of points [ generated by this procedure, the average point to + Dr ((()) satisfies the following error bound, stated in Hazan & Kale (2012 Lemma 11).

---

Published as a conference paper at ICLR 2026
Theorem 2. Les K - [0,1]
be convex function in the hypercube K. [0, Let
w(,, w(2), ..... ,...,,(?? w( be defined by w()) = 1 1 and w(t-1) -lx(w(()) -inmmngp ngt). When ف1. 92. .2...... 9r are unbiased estimators of subgradients, i.e.. Elg. w(th) = 9t. where gr is a subgradient of f at w(t), then w = T EE= w(t) satisfies H[f(w)) min EK f(ww) S 1
1
x2
+ 1
8n
3 PROBLEM STATEMENT
We address the problem of minimizing a submodular function f: 2 - [0, 1. In this setting, the exact values of f are not directly accessible; instead, we rely dueling oracle, in other words, a noisy comparison oracle of two points. The dueling oracle provides a random binary response o E }+1} for a pair of subsets (S,5") E 2 x 2 Note that, as in prior works on dueling bandits and dueling convex optimization (Saha al., 202 a), all outputs from the dueling oracle are assumed to be independent. Therefore, even if the same pair is queried multiple times, the outputs are not necessarily identical. The probability of the response given as: Pr(o = +1)
+ {((((()) - f(S")). Pr(o -1) = 2 (f((() f(S"), where p [-1, - [-1, is fixed transfer function that maps the difference in function values to the distribution parameter.
Our goal is to design algorithms that minimize additive error Er == f($) min f(S), where
S the algorithm output. The algorithm is given the decision set 2 the number available oracle calls T, and the transfer function p. At each iteration t 1, 2,2,.... T, the algorithm chooses pair of subsets (S,, St) and observes a response E {+1} from the dueling oracle. After T iterations, the algorithm outputs a subset $ E 2
This problem motivated by the following applications:
Example 1 (recommendation system). Let us consider recommendation systems, in which we want to find a collection of items S _ [n]] that maximizes a user's satisfaction f(S). based on feedback obtained after presenting S to various users. In practice, users rarely provide reliable cardinal scores but can often express pairwise preferences between presented collections; such comparative feedback is naturally modeled by dueling oracle. Under certain conditions the resulting optimization cast as submodular minimization. Let x E {0, 112h be the indicator of S and suppose user utility S(S) has the quadratic form ((S) = Σi=1 0,3; Eisisjen bij.r If bij 0 for all j.j. which models complementary interactions like camera and lens, then f is supermodular (Nemhauser et al., 1978 Boros & Hammer 2002). Hence, maximizing f is equivalent to minimizing -f. which is submodular, and thus the problem covered by our dueling-oracle SFM framework. Note that the quadratic form above is only illustrative; our approach applies to general supermodular maximization problems. More broadly. any selection task defined on a ground set, such as choosing keywords or response components for a chatbot, can be addressed by the same framework.
be
Example (multi-product price optimization). Consider price optimization over a set of products to maximize total revenue. As shown in (Ito & Fujimaki, 2016), the total revenue function can be formulated as a supermodular function under suitable assumptions, which means that the problem is an instance of submodular minimization. In this setting. relative evaluations- such as pairwise comparisons between pricing vectors-are are often less sensitive to external factors like weather or seasonality than absolute measurements, and thus more accurately capture the effect of price changes.
Following prior work on dueling convex optimization (Saha et al. 2021a 2025). we consider a transfer function p that satisfies the following properties:
1. Strictly monotonically increasing function: p(x:) > ply) if y.
2. Odd function: p(-z) = -p(z) for all x E [-1, In particular, p(0) = 0.
In partieular, this study focuses on the following two examples of p:
Sigmoid transfer function: p(x) 1o - 1, b> 0.
Linear transfer function: p(x) az, 0<a5L 1.
Our primary motivation for considering the sigmoid transfer function is that it is both natural and important, particularly due to its connection with the Bradley-Terry model (Bradley & Terry 1952).

---

When Published as a conference paper at ICLR 2026
The Bradley-Tere model has long been used of the most standard models for pairwise comparisons, and ability to fit wide range empirical data has been well documented (David 1988; Cattelan 2012). Its practical usefulness has been demonstrated across diverse applications, including ranking systems, search engine click modeling (Joachims 2002), preference estimation in recommender and information-retriewee systems (Chen al.1) and preference modeling for post-training large language models (Stiennon et 2020 Rafailov et al. 2023). This models the probability that item i is preferred over item Pr(i >
where 3,, 93 E IR are parameters associated with the items. Now, suppose that for each subset S, the corresponding parameter 3s is proportional to the utility- -f()), i.e., A3 = (S) for some b > O. In this case, the output of dueling oracle based on a sigmoid transfer function is consistent with the Bradley-Terry model as Pr(o- = +1) = + (S' - ((S) = I+exp(-b +xXp(=b((3)-
exp(P:)
+
exp(0g))
exp( -
This model has been widely used as standard tool for modeling preferences based on pairwise comparisons, and appears various domains such as sports ranking, consumer behavior, and AI-based decision-making. Moreover, the Bradley-Terry model can also be interpreted probabilistically example, as the probability that a random variable drawn from an exponential distribution associated with item i exceeds that of item j. This interpretation further supports its relevance as a model for real-world phenomena.
The linear transfer function is important for two main reasons. First, any smooth transfer function can be approximated by a linear function in a small neighborhood around zero. Therefore, even if the true underlying transfer function is nonlinear, the linear case becomes relevant when the exploration restricted to regions where the difference in values is small. In such settings, approaches developed for the linear case are expected to remain effective. Numerical results supporting this hypothesis to some extent are provided in Section [B.2 of the appendix. Second, the linear case is the simplest from the perspective of algorithm design and analysis. thus serves as a natural starting point for investigating our new problem setting.
4 LINEAR TRANSFER FUNCTION
In this section, we present an algorithm for submodular minimization using ducling oracle with linear transfer function. The proposed algorithm is based on the Stochastic Gradient Descent on the
Lovász extension f of the submodular function f. It achieves an additive error bound of O a Furthermore, we prove that, under the condition that the difference between the elements in the two queried sets is bounded by constant order, any algorithm suffers error of least Ω n (VTT there are no restrictions on queries, the lower bound remains 22 avT).
4.1 ALGORITTM
Our algorithm is based on the SGD method. To construct subgradient estimators in SGD, we use information using a ducling oracle. When the transfer function p of the ducling oracle linear, we can construct unbiased estimators of subgradients by the definition of the dueling oracle. From Proposition 2 querying (Br(i). -1)))1) provides o that corresponds to the i-th component of the subgradient y. By the linearity of expectation, we have E = -
- ((Br(0-1)
= 9t-
From Proposition the optimal value of the submodular function f over 2 is equivalent to the optimal value of its Lovász extension ff over K. Using this equivalence, the algorithm performs SGD to find solution to E IC with a small error relative to the optimal solution of f. Finally, leveraging the representation of the Lovász extension in equation the algorithm outputs set S7 such that E[f(Sz)) = f(w).
This algorithm is simple extension of the algorithms proposed by Hazan & Kale 2012) and Ito (2019). In these prior works, the algorithms rely querying sets to obtain function values, which then used to construct unbiased estimators of the subgradients. contrast, this algorithm leverages the properties of the dueling oracle perform SGD without directly using function values.
7

---

Published as a conference paper at ICLR 2026
Algorithm 1 Submodular Stochastic Gradient Descent for linear transfer function
Input: The size n 2 1 of the ground set, the number T 2 1 of oracle calls and the coefficient
< a S
the transfer function p(ar) = az.
1: Set the initial point w T"
1, the learning rate 1) = 2/n7 and the number of steps T T
2: fort = 1, 1,, do
3: Find permutation æ corresponding w(t), i.e. u (1)
w
and its
x(1)
x(x)"
inverse permutation T.
4:
Define B; = (=())...., (i)) for i [n] and Bo Ø3
5: for i = 2,
do
6: Query the ducling oracle with (B+(1), B1()-1) and receive the feedback On
7: Compute an unbiased estimator 9ti- 2is
8: end for
9: Update w (1+++) [x((w)) ng()-
10: end for
T" 11: Set w 75 =1= to(() and choose a threshold = E [0, uniformly at random.
12:
return Sz {il W7 2 2].
4.2 UPPER BOUND
We prove that Algorithm achieves an error bound of n
for any submodular objective
avT
function f. Similar proofs are given in Hazan & Kale 2012 and Ito (011)).
Theorem 3. Let f be a submodular fumction. Let n. T and a be the input of Algoritlum L Then,
Algorithm with parameter 1l = 2V1T achieves the following error bound: E[Er] = avT
The expectation is taken with regard the randomness of the oracle responses o,, and the internal randomness of the algorithm.
5 SIGMOID TRANSFER FUNCTION
In this section, we present an algorithm for submodular minimization using dueling oracle when the transfer function is sigmoidal. This algorithm is similar Algorithm| T and performs SGD on the Lovász extension.
However, when the transfer function nonlinear, not possible construct an unbiased estimator of the subgradient of the Lovász extension from responses of the dueling oracle. To reduce the error necessary to design an estimator with small bias for the subgradient. We employ Firth's 's method to construct a small-bias estimator when the transfer function is sigmoidal, thereby mitigating the estimation error.
introduced by SGD,
Firth (1993) has shown that in regular parametric problems, the first-order term of the asymptotic bias of the maximum likelihood estimates can be eliminated by penalizing the log likelihood. In particular, if 0 is the canonical parameter of exponential family model, the penalized log likelihood becomes 00 log L(0) ae log [(6)), where I(6) denotes the Fisher information evaluated at 6.
Proposition Consider a logistic regression model:
1 Pr(X; = +1 01) 1 18. = - - +1
e-b8 69
++e" -0
{+1} denoting the binary outcome variable and b being a positive constant. The penalized maximum likelihood estimator @- for the regression parameter [[1, 1] can be
with i i k. X;
written as: 0- 1 log
k ) where k4 = Hi
X; = +1H and k_ = Hi X; = -1
Then, the bias of
θ- satisfies:
[B 0 <
2p
+
Here, i is a constant and
24b (1 (1-
R
K3
IT. We denote the coefficient of Fz by C(b)
2
8

---

Published as a conference paper at ICLR 2026
Algorithm 2
Submodular Stochastic Gradient Descent for sigmoid transfer function
Input:
The size 2 1 of the ground set, the number T 2 1 of oracle calls and the constant of
the transfer function p(x) = 2/ b-b)--
Set the initial point w1(1) 1/2 1,
the constant & 1/(1 + e 6) and C(b) 12 1)/(2466 +3)) the learning rate 7/ - 6 C(b) f T
the number of steps T T /ntbéC(()
and the number of query repetitions -=C( /nt.
2:
for = 1,2,.... do
3: Find a permutation æ corresponding to (f) ie., w (1)
x(1) 2 ... 2 w x(x)' and its
inverse permutation T.
4:
Define B; (=())....,<( x(i) for i [n] and Bg Ø.
5: for = 1,2, ... do
Repeatedly query the dueling oracle with (B+(i), (i))) for k times and receive feed-
back.
7:
Let k+ and k_ be the number of times +1 and -1 are returned. 8: Compute estimator of the subgradient 9r: log k++1
A k +2
9: end for
Update ((++1) 11x(((()) n()))
11: end for
Set W
T" T" Ei=1 (t)) and choose a threshold E [0, 1] uniformly at random.
13: return ST = {i W. 2 2)
5.1 ALGORITIIM
When the transfer function sigmoidal, querying (Br(s) (+))-)) produces dueling oracle response following a logistic regression model with parameter gi- From Proposition estimating with Firth's 's method enables obtain low-bias estimators of subgradients. This algorithm can efficiently perform SGD even unbiased estimators of subgradients cannot be constructed.
5.2
UPPER BOUND
In this subsection, we prove that Algorithm 2 achieves an eπrоr bound ET = O
C(M
n
for
6
T
any submodular objective function f. The proof structure closely follows that Theorem with necessary adjustments to account for the sigmoid transfer function.
Theorem 4. Let be submodular function. Let n, T and b be the input of Algorithm Then,
C(b)
Algorithm achieves the following error bound: E[Er] =
The expectation is taken with regard to the randomness of the oracle responses on and the internal randomness of the algorithm.
b3
T
C(b) The factor diverges to +o0, as + +0 or + +oo. Therefore, this algorithm cannot limit
68 the error when b takes extreme values.
6 LOWER BOUND
This section establishes lower bounds for the submodular minimization problem using a dueling oracle with linear or sigmoid transfer functions. Specifically, we analyze the following two scenarios.
1. A lower bound for algorithms that satisfy the following Restriction
2. A general lower bound for any algorithm.

---

Published as a conference paper at ICLR 2026
Restriction 1.
The symmetric difference between the nwo in each query remains constant order.
Specifically, for any query (St. St), the condition |SAAS]| = (SA))) u (S)) = O(1) holds.
Algorithms and satisfy this restriction. In fact, the pairs queried in the algorithms restricted to those of the form (Br()) -1))) and by the definition of B, and T, we have [B(s)) AB) =
K+H = 1.
We prove that for algorithms that satisfy Restriction I there exists instance of the problem where
#
the error is at least 5
Additionally, for algorithms without any restrictions, we construct
an instance where the error lower bound is Ω Since Algorithm satisfies Restriction is optimal up to a constant factor among algorithms restricted by this condition.
Theorem 5. In SFM using dueling oracle with linear sigmoid transfer functions, there exists an instance for which algorithms that satisfy Restriction suffer an error of: E| = In addition, there is an instance for which algorithms without any restrictions suffer an error of: B[FT] = Ω (- The expectation is taken with regard to the randomness of the instance f and oracles on, and the internal randonmess of the algorithm.
CONCLUSION AND OPEN QUESTIONS
We have presented algorithms with upper bounds and lower bounds for submodular function mini- mization using dueling oracles with linear or sigmoid transfer functions. In the case of linear transfer functions, the upper and lower bounds coincide in their dependence on T, establishing algorithmic optimality. By contrast, for nonlinear transfer functions, there remains gap between the upper and lower bounds in terms of 7 -epeedenee leaving room for improvement; we conjecture that the upper believe that more detailed investigation into the dependence on n in the linear case is also important direction for future research. Relaxing the assumption that the transfer function is known is also important direction for future work, and techniques in dueling convex optimization (Saha et al. (025) and derivative-free optimization (Jamieson al., 2012) might provide effective approach to this issue. Furthermore, while the algorithm in this paper is designed via an extension to continuous space, is possible that a combinatorial approach, i.e., one that does not rely on continuous relaxations such as FTPL-basedd algorithms by Hazan & Kale (2012), may lead to a more efficient method. Exploring such alternative approaches constitutes another interesting direction for future research.
bound can be tightened to O (.)). which we leave as future work. Furthermore,
Reproducibility statement The code necessary to reproduce the numerical experiments reported in Appendix B included in the supplementary material. For the theoretical results, all claims without external references are accompanied by complete proofs provided either in the main text or in the appendix. These materials, together with the descriptions of assumptions and algorithmic details in the paper, are intended to ensure the reproducibility of our results.
ACKNOWLEDGMENTS
We thank Takeru Matsuda for pointing us to the literature on Firth's method. SI was supported by JSPS KAKENHI Grant Number JP25K03188 184 and by JST PRESTO, Japan, Grant Number JPMJPR2511.
REFERENCES
Peter Auer, Nicolò Desa-Bianchi, Yoav Freund, and Robert E. Schapire The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32:48-771 77, 2002.
Mohammad Gheshlaghi Azar, Zhaohan Daniel Guo, Bilal Piot, Remi Munos, Mark Rowland, Michal Valko, and Daniele Calandriello. A general theoretical paradigm understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics, pp- 4447-4455. PMLR, 2024.
10

---

Published as a conference paper at ICLR 2026
Francis R. Bach. Learning with submodular functions: A convex optimization perspective. Found. Trends Mach. Learn., 6:145-373, 2011.
Jeff A. Bilmes. Submodularity in machine learning and artificial intelligence. ArXiv, abs/2202.00132. 2022.
Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj. Aadirupa Saha, and Yuanyuan Yang. Dueling optimization with a monotone adversary. In International Conference on Algorithmic Learning Theory, pp. 221-242 PMLR, 2024.
Endre Boros and Peter L Hammer. Pscudo-boolean optimization. Discrete applied mathematics, 123 (L-3):155-225, 2002.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-355, 1952.
Manuela Cattelan. Models for paired comparison data: A review with emphasis on dependent data. Statistical science, 27(3):412 433,,122-33.. 2012.
Xi Chen, Paul N Bennett, Kevyn Thoniss,, and Eric Horvitz. Pairwise ranking aggregation in a crowdsourced setting. In Proceedings of the sixth ACM international conference on Web search and data mining, pp. 193-202 2013.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. 2005.
D.R. Cox and E.J. Snell. Analysis of Binary Data, Second Edition. Chapman and Hall/CRC Mono- graphs on Statisties and Applied Probability. Taylor and Francis, 1989. ISBN 97804 12306204.
Herbert A. David. The Method of Paired Comparisons, volume 41 of Griffin's 's Statistical Monographs & Courses. C. Griffin, London, 2nd edition, 1988.
Miroslav Dudík, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. In Conference on Learning Theory, pp. 563-587. PMLR, 2015.
Jack Edmonds. Submodular functions, matroids, and certain polyhedra. Combinatorial Optimiza- tion, 2001.
David Firth. Bias reduction of maximum likelihood estimates. Biometrika, 80:27-38, 1993.
Satoru Fujishige. Submodular functtioss and optimization. 1991.
Martin Grötschel, László Miklós Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169-197, 1981.
Flad Hazan and Satyen Kale. Online submodular minimization. J. Mach. Learn. Res., 13:2903-2922. 2012.
Dorit S. Hochbaum and Sung-Pil Hong. About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Mathematical Progranming, 69:269-309, 1995.
Shinji Ito. Submodular function minimization with noisy evaluation oracle. In Neural Information Processing Systems, 2019.
Shinji Ito. Revisiting online submodular minimization: Cap-dependent regret bounds, best of both worlds and adversarial robustness. In International Conference on Machine Learning, pp. 9678-9694, PMLR, 2022.
Shinji Ito and Ryohei Fujimaki. Large-scale price optimization via network flow. Neural Information Processing Systems, 2016.
Satoru Iwata, Lisa Fleischer, and Satoru Fujishige. A combinatorial, strongly polynomial-tine algorithm for minimizing submodular functions. In Symposium on the Theory of Computing, 2000.
Kevin G Jamieson, Robert Nowak, and Ben Recht. Query complexity of derivative-free optimization. Advances in Neural Information Processing Systems, 25, 2012.
11

---

Published as a conference paper at ICLR 2026
Stefanie Jegelka and Jeff A. Bilmes. Submodularity beyond submodular energies: Coupling edges in graph cuts. CVPR 2011, pp. 1897-1904, 2011.
Dongfu Jiang, Xiang Ren, and Bill Yuchen Lin. Lim-blender: Ensembling large language models with pairwise ranking and generative fusion. In Annual Meeting of the Association for Computational Linguistics, 2023.
Thorsten Joachims. Optimizing search engines using clickthrough data. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 133-142, 2002.
Pushmeet Kohli and Philip H. S. Torr. Dynamic graph cuts and their applications in computer vision. In Computer Vision: Detection, Recognition and Reconstruction, 2010.
Vladimir Kolmogorov and Ramin Zabih. What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence, 26:144 16:147- 2002.
Andreas Krause and Carlos Guestrin. Near-optimal nonmyopic value of information in graphical models. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, pp. 324-331, 2005.
Tor Lattimore. Bandit convex optimisation. arXiv preprint arXiv:2402.006533 2024.
Yinhong Liu, Han Zhou, Zhijiang Guo, Ehsan Shareghi, Ivan Vulić, Anna Korhonen, and Nigel Collier. Aligning with human judgement: The role of pairwise preference in large language model evaluators. In First Conference on Language Modeling. 2024.
Adian Liusie, Potsawee Manakul, and Mark John Francis Gales. Llm comparative assessment: Zero- shot nlg evaluation through pairwise comparisons using large language models. In Conference of the European Chapter of the Association for Computational Linguistics, 2023.
László Miklós Lovász. Submodular functions and convexity. In International Symposium Mathematical Programming, 1982.
Mukund Narasimhan and Jeff A. Bilmes. Pac-leamning bounded tree-width graphical models. In Conference on Uncertainty Artificial Intelligence, 2004.
Mukund Narasimhan and Jeff A. Bilmes. Local search for balanced submodular clusterings. In International Joint Conference on Artificial Intelligence, 2007.
Mukund Narasimhan, Nebojsa Jojic, and Jeff A. Bilmes. Q-clustering. In Neural Information Processing Systems, 2005.
George Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions Mathematical programming, 14(1):265-295 2944, 1978.
Aldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling Reinforcement learning with trajectory preferences. In International Conference on Artificial Intelligence and Statistics, 2021.
Maurice Queyranne and Andreas S. Schulz. Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds. In Conference on Integer Programming and Combinatorial Optimization, 1995.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in neural information processing systems, 06:53728-53741 2023.
Dorsa Sadigh, Anca D. Dragan, S. Shankar Sastry, and Sanjit A. Seshia. Active preference-based learning of reward functions. In Robotics: Science and Systems, 2017.
Aadirupa Saha and Pierre Gaillard. Versatile ducling bandits: Best-of-both world analyses for learning from relative preferences. In International Conference on Machine Learning, pp. 1901 19011-19026. PMLR, 2022.
12

---

Published as a conference paper at ICLR 2026
Aadirupa Saha, Tomer Koren, and Yishay Mansour. Dueling convex optimization. In International Conference on Machine Learning, 2021a.
Aadirupa Saha, Tomer Koren, and Yishay Mansour. Adversarial dueling bandits. In International Conference Machine Learning, pp. 9235-9244. PMLR, 2021b.
Aadirupa Saha, Tomer Koren, and Yishay Mansour. Dueling convex optimization with general preferences. In Forty-second International Conference on Machine Learning, 2025.
Alexander Schrijver. Combinatorial optimization. Polyhedra and efficiency. 2003.
Lloyd S. Shapley. Cores of convex games. International Journal of Game Theory, 1:11-26, 1971.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. Advances in neural information processing systems, 33:3008-3021 2020.
George Joseph Stigler and Paul A. Samuelson. Foundations of economic analysis. Journal of the American Statistical Association, 43:497, 1948.
Yanan Sui, Masrour Zoghi, Katja Hofmann, and Yisong Yuc. Advancements in dueling bandits. In IJCAI, pp. 5502-5510, 2018.
Donald M. Topkis. Supermodularity and Complementarity. 1998.
Xavier Vives. Oligopoly Pricing: Old Ideas and New Tools. 1999.
Tianhao Wu, Banghua Zhu, Ruoyu Zhang, Zhaojin Wen, Kannan Ramchandran, and Jiantao Jiao. Pairwise proximal policy optimization: Harnessing relative feedback for I1m alignment. ArXiv, abs/23 10.02220. 2023.
Yisong Yue, Josef Broder, Robert D. Kleinherg, and Thorsten Joachims. The k-armed dueling bandits problem. J. Comput. Syst. Sci., 78:1538-1553 2012.
Banghua Zhu, Jiantao Jiao, and Michael I. Jordan. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. ArXiv, abs/2301. 12270, 2023.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference Machine Learning, 2003.
13

---

Published as a conference paper at ICLR 2026
APPENDIX
A OMITTED PROOFS
Proposition 1. Let f be a Lovász extension of a function f 2 + [0, 1]. For any w K, the following equations hold:
f(w) 1/' f({i) w/ 2 2))dz
= =Es-Unir(((.1)) [f(fi () we 2 =])]-
Since the permutation π is defined so that (1 2 (1))() 2 ... 2 (n(n) 0), the following equations follow:
Proof.
[ f((w 2 =})dz
(e(n))
s([w 2 2})dz + +.. f
J(ww 2 2})dz + ...
s([w 2 z})dz
=[([))((x(()) 0) +... [(=(((),..,,()())))))))))))))))) wx(++1) +... f(2) -.x()))
Σ [((=(1),....)
(1))) (((=(),...,=())))) f(w).
(x(++1) ((z)) + ((0)(1
-x-1))))))
2 is chosen uniformly at random from [0. 1]. the probability density function of a random variable
is 1. Then, we have:
=}}] /' f(tw 2})ldz
E Un=0
f(w).
Theorem 1. Fujjshhie 1991 A function f 2 + [0, 1] is submodular if and only if its Lovász
extension f K. + [0, is convex. For submodular function f 2 - [0, 1] and its Lovász
extension f i:K. K. [0, 1}. have:
min f(X) min f(w) min f(w). X
wE(0,11
wE(0.1]
To begin with, we prove the first part Theorem which states that function is submodular and only if its Lovász extension is convex. To prove this, we first define the submodular polyhedron in IR. We then consider linear programming problem (LP) over the submodular polyhedron and apply the strong duality theorem to this LP. For xx R",, we use the notation (xx); = 1(i e X}.
Definition 2. Let f be a submodular function. The submodular polyhedron P(f) is defined as:
P(f) {s E IR" VX E 2 s xx {(X)).
Theorem 6 (Strong Duality Theorem). Let 1,C R", y. E R" E Rmxn Consider the following primal problem and its corresponding dual problem in linear programming:
Primal Problem:
maximize bTy subject to A y S
14

---

Published as a conference paper at ICLR 2026
Dual Problem:
minimize
c
subject to Ar = b 2
For these problems, if either the primal or dual problem has an optimal solution, then the optimal values of both problems are equal. That is,
max (b" A y 2 c)
min(c"a x Ar = b, 2 0}.
The following proposition, given in Bach (001 Proposition 3.2), serves key building block for proof the first part of Theorem
Proposition 4. Let f be a submodular function. Let w E IC, π [n| + [n] be a permutation that orders the components of in decreasing order, and define 8x(1) (1) ior E 2, and xx11) f((T(1))) - f()). Then P(f) and,
arg max
=EP())
f(w) f(0) max w
P()
Proof. We consider the LP:
max w s. PEP())
By the definition of P(f), the primal problem can be explicitly written as:
maximize
w
subject to
x S f(X) for all X E 2!d)
Let Ax be real number for all X E 20r) The dual problem corresponding to this primal problem
can be written as:
minimize
Σ Axf(X)
XE2
subject to
Σ AxXx= =
Xea
Ax 2 0
for all X E 2
constant vector, where each component is min x xee X |X| belongs to P(f), ensuring that
f(X)
P(f) is non-empty and the primal problem has an optimal solution. Therefore, by the strong duality (Theorem 6), the optimal values of both problems are equal.
define as:
(f((((1))) - f(0)
(ifi= 1), (if E {2, (2....,m))
8x(())
- ((())))((((()......))))) -(i- 1)H) (if x (a(1),..., (1)) for e 1}), X
(x(()
(x(++1)
Ax
W|m]
0
(otherwise),
15

---

Published as a conference paper at ICLR 2026
and show that they feasible solutions of primal and dual problems. Then, show that they achieve the same objective value and are optimal solutions. Without loss generality, we assume that rkk) k for all & [n]] For any set X, we have:
xx Σ
(x
Σ (xx.) kb)) f(f1...... -
--1]] by the submodularity of f.
Eir(x (L..........)) f(Xn 13)1
k=1
=(())
Thus, 8 E P(J), i.e., 8 is feasible solution of the primal problem. Ax are non-negative according to the definition of and satisfy the constraint Exe2d Axxx Therefore, Ax are feasible solutions of the dual problem. Since
W (
(=()) ((<()) (i(( 1)))
2=
+ ( -
f(w) f(Ø).
Σ Axf(X)= Σ f(Im())..... (i)))( w=(++1)
XE2
i=1
+ [[n])) -
f(w) S(0).
both the primal and dual problems achieve the value f(w) f(Ø). Thus, by strong duality, this is the optimal solution of both problems and 8, Ax are the optimal solutions for the primal and dual problems, respectively.
L
Then, we prove the first part of Theorem T usiin this proposition.
Proof. If f a submodular function, from Proposition for all w KC, f(w) f(Ø) a maximum of linear functions, and hence f(w) fØ) convex function, i.c., f(w) a convex function. Conversely, suppose that the Lovász extension f of f is convex function. By definition, f is positively homogeneous function, i.e., f(Arr = >f for any X (0, 1]. For any X,Y Y 2
16 + (xr) = / /xxx,,x + (xxnr)
=f(xxxur) + f(xxmr)
1
fxxx,))) 2 [xxmx))
((xu)))++ s(XN).
16

---

Published as a conference paper at ICLR 2026
The second equation holds because the components of each vector 2XXUY + 2xxnx , Xxxy and XXUY can be ordered in the same sequence and can share the same permutation л. Furthermore, since f a convex function, we also have:
n6xx (xx) / [xxx 1 (
2 (() + + +
Therefore, f is submodular function.
Next, establish the second part of Theorem 1 which states that the minimum value of submodular function is equal to the minimum value of its Lovász extension.
Proof. Since f is an extension from {0, 11" to [0. 1|" and satisfies f(X) f(xx) for all X 2!d follows that me2x f(X) = minwe (0,1) f f(w) 2 min fww). Next, we prove the reverse inequality. From equation 2 the following holds for any w E [0,
f(w) = Σ f((=(1), (((()))..,,(()))))() (10))((0(()) - (x(++1)) - f(mi))u -(x)))))
+ f(2) - mx(1))
min [(X)(x>() wa(e+1)) + min J(X) + min S(X)( (x((1))
X
Xe2
Xe2
t=1
min f(X)
Xe2in
Let J be submodular function. For w E Kc, let x be a permutation that orders the components of w in decreasing order, and let be the inverse permutation of Then, sub subgradient g of at given as follows:
Proposition 2.
(x()) [(B,) [(B(11) 9: f(B f(Br(0)-1
Proof. From equation the expression for subgradient is immediately obtained.
Theorem 2. Let IC + 10 be convex function in the hypercube K. = 10, 11a. Ler
((1), w,(,,,., (T) be defined by w()) = 1 and ((t-1) = [l.((w()) - n(t). When 91, . gr are unbiased estimators of subgradients such that Elge w(()]= = 9t. where ge is subgradient of f w(t), the average point u Σ w(() satisfies:
min f(ww) < [[f(w)]
+
or ek
8nj
Proof. Let (t+1) (t) 79.. that (t+1) = (lx(((((1)). By expanding the squared norm, have:
(+++))) w/ 113 = ||w w0112 2ng (wi( w²) ) + +1 11 19
Rearranging terms, we obtain:
1 g.t (w w²)
(1| w/ 112 [|](++1]] w" 11 1
2n
Using the non-expansiveness property of Euclidean projections onto convex sets,
[1+1+ w" [|(((+ w =1
17

---

Published as a conference paper at ICLR 2026
further obtain:
De (w(() w²) - 21 [1 ==1 11
12 -=] + "
"11baa 12:
Summing this inequality over t - ...... T, we have:
ge (w w0)
|| (w( w0 11
[w(
w
7
2 -1.0-112
27
t=1
T
7
19e12
811
since || w"
w²113 113 - " (lwe w7 - for all i [n] since w = 2 1 and w" E [0, 1)*). Next,
since Elge w gt. subgradient of f (t)), have:
Elg, (w w') wl = ge (w w²) 2 (w - f(w"),
where the inequality follows from the convexity f. Taking the expectation over the choice of w(()) we have:
Elge (w w² -
f(w").
Summing over 1. 1,..., T.
have:
T Σ [0]]
T
T
Σ f(w") S
3e (w w²)l
T
71
E 0l
81
2
1=1
Finally, since f is convex, we can apply Jensen's 's inequality to obtain the expected error bound as follows:
1
B(((T)) - f(w=) = R(f(
Σ
w (0)) - -((w")
T
1=1
(()(w(())) - -s(w")
(By Jensen's inequality)
-
Σ
E (1)
> f(w*))
T
$ T
Bilba 12
8m
2
Theorem 3. Let f be a submodular function. Let n. and be the input of Algorithm Then, Algorithm 7 with parameter 1)
2//x achieves the following error bound:
nz
B[Er|= 0
avT
The expectation is taken with regard the randomness of the oracle responses o,, and the internal randomness of the algorithm.
Proof. Since in Algorithm 1 is an unbiased estimator of the subgradient gr, by Theorem 2 the following inequality holds:
Elf(w)] min f(ww) e
Σ
Billg l
T 8n
==1
18

---

Published as a conference paper at ICLR 2026
Moreover, since ge n. o and l a2, we have:
n²T
Σ
a
Then, we obtain:
T
1
E [[](w]] min f(w=)
E8
T
811
2 t=1
1712"
8T/T
2a
n 3
4a
/T
where the last equality follows by setting 17 2/07 have the error bound:
Finally, from equation 3 and Theorem we
E[Er]
[[(((Tr)
min ((S)
Se2l
-]f((0] min f(w")
EX
n
4avT
Proposition 3. Consider logistic regression model:
69
Pr(X, = = I+e-w0 -0 -1(X==1)==1-P((A +1 1
with = 1....., k. X; { denoting the binary outcome variable and being a positive constant.
The penalized maximum likelihood estimator 0" for the regression parameter E [-11,]] 1] can be written as:
1 k
O" = log
k- +
where k4 = -18 X; +1}| and k_ 11 X; -1}
Then, the bias of 0* satisfies:
2Φ 1
[B 01 <
+0
24b +)
A
Here, v is a constant and ap
1 We denote the coefficient of 12 by C(b) =
26-1
(1
First, we derive the form of the penalized maximum likelihood estimator, which constitutes the first part of this proposition.
Proof. The log likelihood function and its partial derivative with respect are
log L(0)
Σ log
1 e- X,60
1
= s4t log
k- k-1log
11 (1+ch0)
1 1te 50
① 0g
be -b
- -b
log L(Ø) k:4 o
11 c00)
(1 + e h0j2
(1 + c022
= k44 b
k
1 60
19

---

Published as a conference paper at ICLR 2026
The Fisher information is
0
T(0) = El-
log [(0) 0]
002
e0
Blk 6²
k-
0
(1 + ebog2
(1+ (1+e-b0y 60
e-
kb?
(1 + e e-b b0y2
since Elk+ 10
Ite-br and [Kk 0)
I. Therefore, the modified score function is
0 00
(+)
log L(0)
log I(0)
00
1
b
be
k
- --b
+
1 + c6
+ c- 60
2
1 + c
b
(1k+ + 2)
60 - (k- + 2
1
)
Ite
Finally, we obtain the solution /":
16
k= +
7
k4 +
2
k +
- -00-
log
h+ +
1
h4 +
0-
log
b
k
Next, we establish the second part of Proposition 3 which demonstrates the bias of 0- Our proof is based on the method outlined in Cox Snell 1989 $2.1.6). Although their work showed that the leading bias term, proportional to n can be eliminated, we extend this approach to derive terms to I
Proof. Let 1 Tee-5a, the probability of X, = +1. The parameter 0 can be expressed as #+ log -- Define function h [0, 1] R as M(x) log I-ot
Then, Ô- h h(*#),
Considering the Taylor expansion of h (L) with respect to di we have:
0- hh( k+
h+ +)+ + h" h0)
k+
h(0) + N'(O)(
6)2
k
k
1
b+
1
h+
(p)
-b)0 +
h
TM (x)
6)
(5)
6
24
k:
20

---

Published as a conference paper at ICLR 2026
By the definition of k+, = o. Therefore, E[[ o) is the r-th central moment of binomial distribution. Taking expectation of equation [S] we obtain:
BBL0"
bn (() + [())
Φ) +
1 h" (0)) +b + nM [+]
+)
1 + 24
h+
h nM (o)
0) + +
0 1
1
-2
1
-2
Φ(1
=log
+
o+ +
Φ + 2k
2
2k
2k
-3
1
-3
6(1 Φ) 22)
+
+
+
++
2k
2k
1
1
3 (1 x)²
+
6
1
o
24
2k
2h
h2
Φ(1 Φ) (1
6Φ(1 x))
k3
1
1
1
log
2Ípk
8022
2(1 6)h
8(1
6)2122
+
1
1
1
1
}
66(1
1
62
ok
(1 Φ)²
(1
5)k
1
1
1
6(1 6) - 2Φ)
Φ)3
12
1
1
2 6)² 1
+
+0
Φ1
(1
12
1
1
1 Φ
1
1
1
10
2Φ
2(1 Φ)
2Φ
211
Φ)
5 1
862
+
8(1 3)
+
2Φ²
(1
(1 20)
6( 2Φ)
3(1
6) 2
30 2
+
2(1
6)²
302
3(1
6)²
4Ø2
4(1
+)2
1
(By the Taylor expansion of log(1
+ x) and (1 + x))
-)
26-
60 + 24 6)2
+0
122
Thus, the bias 0+ can be written as:
2Φ 1
E 0 24bo
61- 6)2
13
Considering o as a function of 0 and b as a function of (00) and 6, the relationship between ø and 8, and the relationship between the cocfficient of the term 1 and o are illustrated in Figure I and Figure [ For all b > O, the coefficient reaches its maximum with = 1 (or 0 = -1). Therefore, the coefficient can be bounded using 1/ 1
2Φ 1
2 - 1
S
-C(b.
24 0)2
24b
Theorem 4. Let f be a submodular function. Let n, and be the input of Algorithm 2 Then, Algorithm achiiees the following error bound:
C(6)&
n
E Eyyl 0
T
21

---

Published as a conference paper at ICLR 2026
-2.0
-2.2
-4.0
-0.2
0.30
025
130
3.7
1.0
3.5
68
1.
0
Figure 1: Relationship between & and 0.
Figure 2: Relationship between
((2
(24bg) (1 )) and Φ
The expectation is taken with regard to the randomness of the oracle responses or, and the internal
randomness of the algorithm.
Proof. Let w" be a minimizer of in K.
T
(f(w((t)) - {(w0))
De (w(( - -w*))
0f (w) - "w²) + (9p 9. (w)()))))))))))))))))))))))))) - w²))
T"
T'
71
Σ
11 +
Σ (oT 9. (20(0)) w²)
(By equation 4
87
2
t=1
17
Σ
11
Σ
l1 0. |1 (1|lo(()) w" 100
81)
(By Hölder's inequality)
11 T
T
10
+
Σ l
9. 111
8n
2
The last inequality holds since (1) w" E K. By the definition of ge. we have:
1 <
n
flog(2k 2 + 1))2, ll.. 9. nC
b2
k22
Then, the following inequality follows by taking expectations and using Jensen's inequality:
T >
Blf(w)]
min f(ww) <
1
n
+
1
11
1l
g. Tll1))
ex
T
8n
1=1
t=1
<<
(log(2k + 1)}² + nC
81'n
25
kz
n²2k
nm
(log(2k: + nC(b)0
8Tn
21
1.2
Setting 77 by C(b) n
and le be C(b) T
we have:
nb
C(6) (C(6))
n
B[f(w)
min f(w") 0
b T
22

---

Published as a conference paper at ICLR 2026
Finally, from equation and Theorem
| have the enror bound:
E[Er] = [[S(ST)] - min S(S)
SE2
Blf(ū)]
min f(w") eK
C(b)
n
b8 T
L
Theorem 5. In SFM using dueling oracle with linear or sigmoid transfer,unctions, there exists an instance for which algorithms that satisfy Restriction 7 suffer an error of:
n
B
min f(s)] = SE2
VT
In addition, there is an instance for which algorithms without any restrictions suffer an error of:
E[Er] E(
min f(S)] -2 (17))
SE2M
The expectation is taken with regard the randomness of the instance f and oracles ob and the internal randommess of the algorithm.
Before presenting the proof of the lower bound, we introduce Yao's principle, powerful tool for analyzing lower bounds randomized algorithms. This principle allows to derive lower bounds by analyzing the expected performance of deterministic algorithms over a chosen distribution of problem instances.
To begin with, we prove the lower bound for the linear transfer function.
Proposition 4 (Yao's principle). The worst-case error of any randomized algorithm is at least the error of the best deterministic algorithm under specific distribution D. That is, let the error Er be expressed as function Er(A,z), x). where A is algorithm (deterministic randomized) and represents the input (including the objective function f. oracle response ot). Define A as the set of all deterministic algorithms. R as the set of all randomized algorithmss, X as the set all possible inputs, and D as a specific input distribution. Then, the following inequality holds:
min EEND BERDDEET(A,, (A, < max E (R, AEA
N
Proof. For simplicity, this proof considers the objective function to be submodular function 20 + [1. Since submodular functions remain submodular under scaling by constant or adding/subbracting a constant, this proof is applicable to the problem setting as well.
First, we consider the where the algorithm satisfies Restriction T By Proposition to establish a lower bound, we construct an objective function in which any deterministic algorithm (satisfies
Restriction incurs an error of Ω
RVT
Fix subset 5 E 20d) and a positive real value e E [0, 1]. Define a submodular function f 2 -> [-1,1] f(X)= 2n (1x""_"1111XX"-"" When new element is added to subset, the increment in the function value only depends on whether is included in S*. Hence, as equation hholds, defined above is a submodular function. It is obvious that f achieves its minimum value of < S at S" Thus, the error of the output Sp is given by the following expression:
2n
f($r) - f(5*) = (1$r)5511 ST (- (- (SS (
2n
2n
E
1TAAS
2n
23

---

Published as a conference paper at ICLR 2026
According to the restriction, the query at iteration t is given by (S, + St) (i S.). Based on the definition of f, the result or of the dueling oracle follows the probability distribution:
(-aam) i O2 Ber (am))
Since the output or does not depend on S, but only depends on ie let i represent the query in iteration I.
Since we consider deterministic algorithms, the query in iteration determined by (4.. 0,) 0,)=== and the output ST is determined by (éx, ( Therefore, if 5* is fixed, the output Sy can be considered being sampled from a probability distribution that depends S*
To simplify the proof, we define = Xš, and x= = Xs- Then, the error can be expressed using
w:|. Given that follows probability distribution D,- determined by x², we consider the error as a function of x². Specifically, we define:
and x² as 2n ST 2n Ei=1 و
Er(x*) EEND..
Σ
First, we bound the KL divergence between the probability distributions followed by ST when and 5" (i) are respectively given. By the definition of 4 and x", consider the KI. divergence between the distribution Da', which è follows when x is given, and the distribution D', At])- which
follows when x² (i) given. By the chain rule for KL divergence [Cover Thomas 20055
Theorem 2.5.3)I, we have:
DDr (()))))) DKL( (102-14)))
S DKu((ir, ot) lz (1 oz) 1z
DKI (1) n- (1 0.) ((t1)
+ + (DLL( (DL 11(rr or))a-
(By the chain rule)
= DDai T-1 x |1 1e 9)) 1-1
(a ) | (-a c ))
+ +Binn) fir 1) DKL (Ber
2n
2n
-KLL(Gi, a. (1 0x) 1 1(-)(1))
+ 2m
+ Pr. (br ia 2n log(
2m
(By the definition of KL divergence)
T
1 a 2n log(
$ Pra- (ie = ()
2n
2n
The last inequality holds by applying the chain rule repeatedly. Since Ei ΣT Pr. (1e we have the following inequality:
1) =T,
1 a 2m
D (Dr. < Ta
log(
2n
1
0m
log 3
2T
(6)
2
n²
The last inequality holds, since z log(
1+
<
lng 3 2 for 0 < x <
and 0 <
< 1
24

---

Published as a conference paper at ICLR 2026
Next, define (1(2)) = Dg [At] and e,(x*) 11x(x")) - 2/1. since a; only takes values in {0, 1), the error Er (x") can be expressed as:
ET
BEN 18; z/
BB Dz- [5i] 271
2n
(1=( - =11
2n
cx(x").
2n
By Pinsker's inequality, the following inequality holds:
S SV Da.De-lDDDa)))))
Then, we have:
n
1 DKL (D=-11D;xAA())
lu(x") A(i)ll
S
n
n
DKL (Dx- (())
2
log
3
a2
2
Therefore,
((x")+e((x" A(i)) lux x31 + 1v. A(1)) (1- 2!)
2 11 (xx - 1z - 11(x" +1-)))(1=2)))
2 |1 2x 11,(x)) - vx(x"\(i))
= 1 lu, V1(x (-(x=(((())) (
Then, obtain the following inequality by setting Vlog3" n
evT
Σ +e,"")) >
Σ (1 l1r(x*) v-(x=' ((i))
log 3 a²T
2
2
(By equation 7
n
(8)
2
25

---

Published as a conference paper at ICLR 2026
Finally, if 5* is chosen uniformly at random from 2 x²' also follows uniform distribution (we denote x= Unif). Then, we obtain the lower bound in Theorem 5
B[ UunrrLn (T(=) (z")]
6 Faz Unif
ex(x")
2n
Nnitl
(c((*)+ + +G(''((1)))
4n
Ex
Unid
2
(By equation S)
4n
n
8 av
The second equality follows from the fact that if x" follows the uniform distribution, then x. A1) also follows the uniform distribution for any i [n].
For algorithms without any restrictions, the following inequality holds instead of equation 6
log 3 a a²T 2.
Σ DKL((x-IlDarpp))
2
Then, by setting c Ving avT we have the same inequality equation & Finally, we obtain the lower bound:
n
E[ET| 2 8 3 avT
Next, we establish the lower bound for the sigmoid transfer function. The overall proof follows the same structure as in the linear case, with the differences stated as the following lemma. Lemma 1. Let p(z) T
and let the other definitions follow those used in the proof of Theorem 3 For any algorithm that satisfies Restriction 1 the KL divergence between two distributions Dr- and Dr A(S) satisfies the following inequality:
bT
DKL 1I (())) S
2
4n
For any algorithm without any restrictions, the following inequality holds:
b²T
DKL (D. a(1))
4n
Proof. By the chain rule for KL divergence, we have:
DKL(Dz-1 DD D2=
< ((t( |( ot) la- (11)))))
+ E (1,,o) T- [1(ir = DKL (pl
D)]lBer+ (p(- _ )))
2n
2n be
DKI o - ([ ) lx- A(1)) Pr,- (ir = 1)( 2n 2n
pl _))
(By the definition of KI. divergence and p(x:))
T
pl 6 =))-
Pr (ie = i)( 2n 2n
When the algorithm satisfics Restriction I it holds ET Pra. (is i) T. Therefore, have the following inequality:
(Dr (D24111))) < TT be
pl
2n
2n
6T
2
(:' p(x) S be for all x 0).
4n
26

---

Published as a conference paper at ICLR 2026
Moreover, for algorithms without any restrictions, it follows Ex= Et= Pr. (ét i) =nI. Therefore, we obtain:
62T 4n
DeL DKr a(1))
c
B NUMERICAL EXPERIMENT
B. DEPENDENCE OPTIMIZATION ERROR ON THE PROBLEM PARAMETERS
In this section, we investigate, through numerical experiments, how the emror achieved by the algorithm varies with the problem parameters (T' and ni), and verify that the empirical behavior is consistent with the theoretical analysis. We implemented the algorithm with linear and sigmoid transfer functions and investigated the dependence of the error on the number of oracle calls T and the dependence of the eπror on the size of the ground set Fig 3 together with the upper and lower bounds derived in this paper. As objective functions, used nontrivial submodular functions derived from cut functions, so that neither the empty set nor the full set is necessarily minimizer.
display the empirical results
The experimental settings are as follows. The linear transfer parameter a and the sigmoid transfer parameter were both to Algorithmic parameters are as specified in and For the experiments on the dependence of the error on the number of oracle calls T, we fixed the size of the ground set at n = 5 and ran the algorithms with T {500, 1000, 1500, 2000, 2500}. For the experiments on the dependence of the елгог the size of the ground set we fixed the number of oracle calls at = 2000 and varied n E {4, 6, 8, 10, 12, 14).
For each objective function, the algorithm's output and the optimal solution. This procedure was repeated for 100 randomly generated objective functions; the plots report the mean across these functions together with the corresponding standard deviations.
the algorithm 100 times and recorded the average error between
Upper Bound
Lower Bound
data with error bars
10-1
Error
60
-
3x10-2
10a
Figure 3: Dependence of the error the number of oracle calls T under the linear transfer function.
27

---

Published as a conference paper at ICLR 2026
Upper Bound
Lower Bound
data with error bars
10-1
Error
10-2
3x
4x109
6 6x
101
n
Figure 4: Dependence of the error on the size of the ground set n under the linear transfer function.
100
Error
-0
Upper Bound
Lower Bound
data with error bars
10a
Figure 5: Dependence of the error the number of oracle calls T under the sigmoid transfer function.
28

---

Published as a conference paper at ICLR 2026
Upper Bound
Lower Bound
100
data with error bars
Error
10-1
3 3x
4x10
6 10
101
n
Figure Dependence of the error on the size of the ground set under the sigmoid transfer function.
B.2 EXPERIMENTS UNDER MISSPECIFIED TRANSFER FUNCTIONS
In this section, we evaluate the performance the proposed algorithm through numerical experiments in misspecified transfer-function setting, i.e., when the transfer function assumed in the algorithm design does not match the actual transfer function that governs the behavior the ducling oracle. Such misspecification commonly arises in practical applications, where there often exists gap between the real-world problem and the mathematical model used for algorithm design; therefore, robustness this type of misspecification is practically important. We also note that Section B. focused on the correctly specified setting, where the dueling oracle indeed follows the assumed linear sigmoid transfer function.
In the experiments, we used the following two transfer functions: the clipped linear function Pelip and the cubic function Peubie defined
Palip (x) min max(-
Poubio (x) 2x x²
Using the ducling oracle induced by each transfer function, we evaluate whether the algorithm
designed for the linear transfer function (Algorithm [ still achieves vanishing error. We set and plot in Figure 7 how the error behaves as T increases over {100, 200, 400, 800, 1600, 3200]. All other experimental settings are identical to those in Section B.1
From Figure 7 we observe that the error approaches zero as T increases for both transfer functions. Moreover, the convergence rate appears comparable that in Section B.T where the correct transfer function was used. This suggests that the proposed algorithm is reasonably robust to misspecification of the transfer function. In other words, the algorithm expected to perform well even more realistic scenarios where the comparison outcomes do not strictly satisfy the assumed model.
Although we are currently unable to provide a mathematically rigorous explanation for why the algo- rithm continues to perform well under such misspecified settings, the phenomenon can be intuitively understood through the interpretation discussed in the last paragraph transfer functions used in this section not strictly linear, but they can be well approximated by linear function in a neighborhood around zero. Therefore, when the difference in the function values used by the dueling oracle is sufficiently small (e.g., in regions close to the optimal solution), the
Section 3 Specifically, the
29

---

Published as a conference paper at ICLR 2026
1x
Emrr
Error
10n²
10-1
60
107
10t
10"
(a) Case of Polip
(b) Case of Peabie
Figure Performance Algorithm Jnder misspecified transfer functions.
behavior of the oracle becomes nearly indistinguishable from that of linear transfer function. This explains why Algorithm [ which assumes a linear transfer function, still performs reasonably well. Developing a theoretical framework analyze and characterize this phenomenon is an interesting direction for future work.
30


Reviews:
[{"review_id": "kZXHMVcbbT", "reviewer": "Reviewer_2Y67", "summary": "**Main contribution:**\nThis paper presents the first study of submodular function minimization (SFM) using only a dueling oracle, which provides noisy pairwise comparisons rather than exact function values. The authors propose and analyze algorithms for this setting, establishing error bounds for both linear and sigmoid oracle transfer functions.\n\n**Problem formulation:**\nThe objective is to minimize a submodular function $f:2^{[n]}\\rightarrow[0,1]$, which is a set function satisfying $f(X)+f(Y)\\ge f(X\\cup Y)+f(X\\cap Y)$ for all $X, Y\\subseteq[n]$. Access to the function is restricted to a dueling oracle, which, when queried with two sets $(S,S^{\\prime})$, returns a random binary response $o\\in\\{\\pm1\\}$. The probability of the response is governed by a transfer function $\\rho$ based on the value difference, e.g., $Pr(o=+1)=\\frac{1}{2}+\\frac{1}{2}\\rho(f(S)-f(S^{\\prime}))$. The goal is to minimize the additive error $E_{T}:=f(\\hat{S})-min_{S\\in2^{[n]}}f(S)$ after $T$ oracle calls.\n\n**Main results**\nFor a linear transfer function, the paper provides an algorithm with an error rate of $O(n^{\\frac{3}{2}}/\\sqrt{T})$, which is proven to be optimal for constrained algorithms by a matching lower bound. For a sigmoid transfer function, the authors design an algorithm with an error rate of $O(n^{\\frac{7}{5}}/T^{\\frac{2}{5}})$.\n\n**Technique/algorithm summary:**\nThe algorithms are based on applying Stochastic Gradient Descent (SGD) to the Lovász extention, which is a continuous convex relaxation of the submodular function. In the linear case, an unbiased subgradient estimator for SGD is constructed directly from the dueling oracle's response. Because unbiased estimation is infeasible for the sigmoid function, that algorithm instead employs Firth's method (Firth, 1993) to create a low-bias estimator from the logistic regression model, thereby mitigating error accumulation.\n\n**Experiment summar **\nThe paper includes numerical experiments that implement the proposed algorithms for both linear and sigmoid transfer functions on submodular cut functions. The result empirically validate the theoretical findings by plotting the error's dependence on the number of oracle calls ($T$) and the ground set size ($n$), showing the data falls between the derived upper and lower bounds.", "questions": ".", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The theoretical results are solid.", "weaknesses": "Even though this is mainly a theoretical paper, the paper also provides some experimental supports. However, it would be good to provide experiments on some real world data than just numerical experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IOgmGJ2gCX", "reviewer": "Reviewer_BQte", "summary": "This work studies submodular function minimization (SMF) with a *dueling oracle* (i.e., an oracle that takes two sets $S$ and $S'$, and\nprobabilistically returns which set has the higher value with probability $\\frac{1}{2} + \\frac{1}{2} \\rho( f(S) - f(S'))$ for\na fixed *transfer function* $\\rho : [-1, 1] \\rightarrow [-1, 1]$. A dueling oracle has been used for multi-armed bandit problems\nin the context of convex optimization (e.g., [Saha et al., ICML 2021] and [Saha et al., ICML 2025]), but this work is the first to study them for SMF.\nThe authors give strong upper and lower bounds for the following transfer functions: linear, sigmoid, and general (see Table 1).\nOverall, this is a nice and very well written theoretical paper.", "questions": "- [264] How does the randomness of the dueling oracle work? Does it give the\n  same noisy response for any given pair of subsets $S$ and $S'$, or are there\n  independent coin flips each time the oracle is called?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Good classification of upper and lower bounds for SMF for different transfer functions in Table 1.\n- Combines a nice set of tools: Lovasz extension (continuous methods), Yao's principle for analysis\n- Very well written introduction with motivating applied ML examples in Example 1 and Example 2", "weaknesses": "- Lack of experiments\n- Submodular function minimization isn't the strongest fit for ICLR, but there is precidence", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mUB734jpN7", "reviewer": "Reviewer_eqdV", "summary": "This work studies submodular function maximization under a new setting where the algorithm does not observe the function values, but only pairwise noisy preferences returned by an oracle. This paper formalizes how duelling responses depend on difference function values through a transfer function (linear, sigmoid etc). For the linear case, the authors propose an SGD-based algorithm using Lvasz extension and show provable optimality, For the sigmoid case, the authors use Firth's bias-correction technique to obtain a theoretical guarantee.", "questions": "Please see the weakness.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The introduction of the problem.\nThe hardness of theoretical results is also provided the algorithms are provably optimal. Experimental results give insights are how errors depend on n and T", "weaknesses": "The algorithms heavily rely on continuous extensions. Thus,a concern is overall efficiency of the algorithms could be limited compared to the discrete methods. Is it possible to design algorithms without using the continuous extensions?\n\nThe analysis largely adopts techniques from earlier works. How do proof techniques differ>\n\nPresentation could be improved: Adding brief description showing why Algorithm 1 naturally satisfies Restriction 1 could be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "14lx6sDvWY", "reviewer": "Reviewer_qsMZ", "summary": "This paper studies the problem of submodular function minimization under the noisy dueling oracle setting, where the algorithm receives noisy pairwise comparisons between subsets rather than direct function evaluations, and the oracle's response is further determined by a transfer function. The authors establish both upper and lower bounds on the achievable error rate. In particular, they proposed algorithms that achieve an error rate of $O(n^{3/2}/\\sqrt{T})$ and $O(n^{7/5}/{T}^{2/5})$, respectively for linear and sigmoid transfer functions. In particular, the achieved error rate under the case of a linear transfer function matches the result of the lower bound.", "questions": "1. Compared to existing work, the main distinguishing feature is the transfer function. Do these assumptions introduce specific technical challenges that must be addressed in the analysis? What are the novel elements in the proofs that arise from these assumptions?\n\n2. For the sigmoid and linear transfer functions, could the authors clarify why these assumptions are reasonable and important in the examples provided? In particular, the linear transfer function appears somewhat impractical, and additional explanation regarding its relevance would be helpful.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The problem of submodular optimization under the i.i.d. bandit feedback setting has been extensively studied in prior work and has broad applications across various machine learning tasks. In this regard, the paper addresses an important and timely problem of clear relevance to the ICLR community.\n\n2. The authors present a thorough theoretical analysis, deriving both upper and lower bounds on the error rate for the considered setting.\n \n3. The proposed algorithm attains the optimal regret bound in the special case of a linear transfer function.", "weaknesses": "1. The problem of submodular optimization under the i.i.d. bandit feedback setting has been studied in many previous works. Compared with existing works, the key assumption is the existence of the transfer function. While the authors provide several motivating examples related to submodular optimization with noisy dueling bandit feedback, it remains unclear how the proposed transfer function appropriately models those scenarios.\n\n 2. The paper does not clearly articulate its technical contributions. It would be helpful for the authors to explicitly emphasize the novel aspects of their analysis. In particular, highlighting the key distinctions from prior work and elaborating on the specific technical challenges addressed would make the theoretical contributions more compelling and substantial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)