Bandit and Delayed Feedback in Online Structured Prediction
Authors: Yuki Shibukawa
Taira Tsuchiya
Shinsaku Sakaue
Kenji Yamanishi
Venue: NeurIPS 2025 poster ()
Keywords: online learning
structured prediction
bandit feedback
delayed feedback
Primary area: theory
TL;DR: We present surrogate regret upper bounds for online structured prediction with bandit and delayed feedback.

Abstract: Online structured prediction is a task of sequentially predicting outputs with complex structures based on inputs and past observations, encompassing online classification. Recent studies showed that in the full-information setting, we can achieve finite bounds on the *surrogate regret*, *i.e.,* the extra target loss relative to the best possible surrogate loss. In practice, however, full-information feedback is often unrealistic as it requires immediate access to the whole structure of complex outputs. Motivated by this, we propose algorithms that work with less demanding feedback, *bandit* and *delayed* feedback. For bandit feedback, by using a standard inverse-weighted gradient estimator, we achieve a surrogate regret bound of $O(\sqrt{KT})$ for the time horizon $T$ and the size of the output set $K$. However, $K$ can be extremely large when outputs are highly complex, resulting in an undesirable bound. To address this issue, we propose another algorithm that achieves a surrogate regret bound of $O(T^{2/3})$, which is independent of $K$. This is achieved with a carefully designed pseudo-inverse matrix estimator. Furthermore, we numerically compare the performance of these algorithms, as well as existing ones. Regarding delayed feedback, we provide algorithms and regret analyses that cover various scenarios, including full-information and bandit feedback, as well as fixed and variable delays.

Bandit and Delayed Feedback in Online Structured Prediction
Yuki Shibukawa
Taira Tsuchiya
The University of Tokyo
The University of Tokyo and RIKEN AIP Tokyo, Japan
Tokyo, Japan
shibu-yu7620g. ecc. w-t.uuo.ooo.ac..ppp.
tsuchiya@mist.c w.t....oo....... ac.
Shinsaku Sakaue*
Kenji Yamanishi
CyberAgent Tokyo, Japan shinsaku. wak.ue@gmail.ccom com
The University of Tokyo
Tokyo, Japan
yamanishi@g. ecc. u u-tokyo.ac. ac.
Abstract
Online structured prediction is task of sequentially predicting outputs with com- plex structures based on inputs and past observations, encompassing online classifi- cation. Recent studies showed that in the full-information setting, we can achieve finite bounds on the surrogate regret, i.e, the extra target loss relative to the best possible surrogate loss. In practice, however, full-information feedback is often un- realistic as it requires immediate access to the whole structure of complex outputs. Motivated by this, propose algorithms that work with less demanding feedback, bandit and delayed feedback. For bandit feedback, by using a standard inverse- weighted gradient estimator, we achieve a surrogate regret bound of (VKKT) for the time horizon T and the size of the output set K. However, K can be extremely large when outputs are highly complex, resulting in an undesirable bound. To address this issue, propose another algorithm that achieves surrogate regret bound of ( which is independent of K. This is achieved with carefully designed pseudo-inverse matrix estimator. Furthermore, we numerically compare the performance of these algorithms, well existing ones. Regarding delayed feedback, we provide algorithms and regret analyses that cover various scenar- ios, including null-information and bandit feedback, well fixed and variable delays.
1 Introduction
In many machine learning problems, given an input vector from set X' of input vectors, we aim to predict a vector in finite output space y. Multiclass classification is one of the simplest examples, while in other cases, output spaces may have more complex structures. Structured prediction refers to such a class of problems with structured output spaces, including multiclass classification, multilabel classification, ranking, and ordinal regression, and has applications in various fields, ranging from natural language processing to bioinformatics [2, 43]. In structured prediction, training models that directly predict outputs in complex discrete output spaces is typically challenging. Therefore, we often adopt the surrogate loss frumework defie an intermediate space of score vectors and train models that estimate score vectors from inputs based on surrogate loss functions. Examples of
"This work was primarily conducted during period when was affiliated with the University Tokyo and RIKEN AIP.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Upper and lower bounds the surrogate regret in online multiclass classification and OSP. Here, T is the time horizon, K = | is the size of the output space, and D is the fixed-delay time. Delayed feedback is considered only when "Delayed" appears in the feedback column, In the target loss column, "SELF*" means SELF that satisfies Assumption 3.5. Note that the O(T2/33 bounds for SELF* in lines 6 and 9 do not explicitly depend on K but on d; in the case of multiclass classification with the 0-1 loss, the dependence on K appears as d K.
Setting
Reference
Feedback
Target loss
Surrogate regret bound
Binary classification
Van der Hoeven ct al. [45, Cor. 1]
Graph bandit
0-1 loss
((vT) (d
Multiclass
Van der Hoeven [44, Thm.
Bandit
0-1 loss
O(KTT)
classification
Van der Hoeven al. [45, Thm. 1]
Bandit
0-1 loss
O(KVT)
Structured
Sukaue et [41, Thms. and 8]
Full-info
SELF
0(1)
prediction
This work (Theorems 3.4 and D.2)
Bandit
SELF
O(vRT)
This work (Theorem 3.6)
Bandit
SELF
O(T47)
This work (Theorems 4.3 and E.3)
Full-info & Delayed
SELF
O(D* 1)
This work (Theorems 4.4 and E.4)
Full-info & Delayed
SELF
O
This work (Theorem 4.5)
Full-info & Delayed
SELF
Q
This work (Theorem 5.1)
Bandit & Delayed
SELF
O(y(K DJT)
This work (Theorem 5.2)
Bandit & Delayed
SELF*
O(D4/11//)
surrogate losses include squared, logistic, and hinge losses, and general framework encompassing them is the Fenchel-Young loss [7], which we rely on in this study.
Structured prediction can be naturally extended to the online setting, called Online Structured Pre- diction (OSP) [41]. In OSP, at each round = 1,..., T, an environment selects an input-output pair (æt, 3/) E X x V. A learner then predicts ÿt E )' based on the input 2; and incurs loss L(T yt). where L: y + R2 is the target loss function. Following prior work [41, 44, 45], we focus on the simple yet fundamental case where the learner's 's model for estimating score vectors is linear.
The goal of the learner is to minimize the cumulative loss ET, L yr). On the other hand, the best the learner can do in the surrogate loss framework is to minimize the cumulative surrogate loss, namely Ei= S(U ; yr), where U: X' + Rd is the best offline linear estimator and S: Rdd x y - R22 is a surrogate loss, which measures the discrepancy between the score vector Uz E Rd and y: E V. Given this, natural performance measure of the learner's predictions is the surrogate regret, Rr, de- fined by Σ T(0r V/)) = - S(Ua;;; yı) ) RRr. It has recently attracted increasing attention fol- lowing the seminal work by Van der Hoeven [44] on online classification. The surrogate regret is an ap- pealing, data-dependent performance measure, it can provide better bounds on the target loss when the surrogate loss of the best offline estimator, Σ SUUx,;; y.), smaller. Further background and a comparison with the standard regret are provided in Appendix C. Of particular relevance to our work, Sakaue et al. [41] recently obtained a finite surrogate regret bound for online structured prediction (OSP) under full-information feedback, i.e., when the learner observes y/: at the end of each round I.
However, the assumption that hullminformation feedback is available is often demanding, especially when outputs have complex structures. For example, in sequential ad assortment on an advertising platform, we may be able to observe only the click-through rate but not which ads were clicked, which boils down to the bandit feedback setting [24, 29]. Also, we may only have access to feedback from a while ago when designing an ad assortment for new user namelyy delayed feedback [32, 47]. Similar situations have led to plethora of studies in various online learning settings. In combinatorial bandits, algorithms under bandit feedback (referred to as full-bandit feedback in their context), instead of full-information feedback, have been widely studied [9, 14, 18, 39]. Delayed feedback also explored in various other settings, including full-information and bandit feedback [11, 27].
Duc to space limitations, we defer a further discussion of the background to Appendix B.
To extend the applicability of OSP, this study develops OSP algorithms that can handle weaker feedback bandit feedback and delayed feedback instead of full-information feedback. Following the work of Sakaue et al. [41], we consider the case where target loss functions belong to a class called the Structured Encoding Loss Function (SELF) [6. 12), general class that includes the 0-1 loss in multiclass classification and the Hamming loss in multilabel classification and ranking (see Section 2.4 for the definition). Table summarizes the surrogate regret bounds provided
Our contributions
in this study and comparisons with the existing results.

---

One of the major challenges in the bandit feedback setting is that the true output ye is not observed, making it impossible to compute the true gradient of the surrogate loss. To address this, we use an inverse- weight- gradient estimator, a common approach that assigns weights to gradients by the inverse probability of choosing each output, establishing an OVVKT) surrogate regret upper bound (Theorems 3.4 and D.2), where K | denotes the cardinality of Y. This O bound has desirable dependence on T. matching 52 (((VT) lower bound known in problem closely related to online multiclass classification with bandit feedback [45, Corollary 1]. Furthermore, our bound is better than the existing O()VT) bounds [44, 45] by a factor of vK, although the bound of Van der Hoeven al. [45] applies to broader class of surrogate losses and thus it is not directly comparable to ours (see Appendix C.3 for a more detailed discussion). We also conduct numerical experiments on online multiclass classification and find that our methods, which apply general OSP, are comparable to the existing ones specialized for multiclass classification (see Appendix H.I).
While the O(V bound is satisfactory when K = J is small, K can be extremely large in some structured prediction problems. In multilabel classification with m correct labels, we have K = (m) and in ranking problems with m items, we have K" m!. To address this issue, consider special case of SELF (denoted by SELF* in Table 1), which still includes the aforementioned examples: the 0-1 loss in multiclass classification and the Hamming loss in multilabel classification and ranking. A technical challenge to resolve the issue lies in designing an appropriate gradient estimator used in online learning methods. To this end, we draw inspiration from pseudo-inverse estimators used in the adversarial bimeaticominnttorial bandit literature [1. 9, 16]. Indeed, we cannot naively use the existing estimators, and hence we design a new gradient estimator that applies to various structured prediction problems with target losses belonging to the special SELF class. Armed with this gradient estimator, we achieve a surrogate regret upper bound of 2 (Theorem 3.6). This successfully eliminates the explicit dependence on K, although the dependence on T increases compared to the O( (VTT) bound. We also numerically observe the benefit of this approach when K large, aligning with the implication of the theoretical bounds (see Appendix H.2).
For the delayed feedback setting, the surrogate regret bounds depend on whether the delay time is fixed or variable. We here describe our results for the known fixed-delay time, denoted by D, under the full-information setting. is relatively straightforward to obtain a surrogate regret bound of ((V(D + 1)T) with standard Online Convex Optimization (OCO) algorithms for the delayed feedback. We improve this to surrogate regret bounds of (min D + 1, (D + 1)2/3T1/33) (The- orems 4.3 and E.3) and O(D + 1) (Theorems 4.4 and E.4), which are notably independent of T. The proof's require carefully bridging different lines of research: OCO algorithms for delayed feedback [20, 27] and surrogate regret analysis in OSP. In addition, we provide the lower bound of R(D + 1) (Theorem 4.5), which matches the upper bound.
Given the contributions so far, it is natural to explore OSP in environments where both delay and bandit feedback are present. We develop algorithms for this setting by combining the theoretical developments for bandit feedback without delay and delayed full-information feedback, achieving surrogate regret bounds of ((V(D= + KYT) (Theorem 5.1) and ((D1/3T2/3 (Theorem 5.2). It is worth noting that similar surrogate regret bounds can also be obtained in the variable-delay setting where the delay may differ for each round of feedback- both full-information and bandit feedback. Due to space constraints, most of the details are provided in Appendix G.
2 Preliminaries
This section describes the detailed setting of OSP and key tools used in this work: the Fenchel-Young loss. SELF, and randomized decoding.
Notation For any integer > O, let [n] {1, ... n.. Let ||-I| denote a norm with x||y||| > ||y/| for some K. > 0 for any y E R For matrix W. let | ||= Vir(W W) be the Frobenius norm. Let 1 denote the all-ones vector and e; the ith standard basis vector. For IC Rdd let cAnv(XC) be its convex hull and Tx: Rd - {0, } be its indicator function, which takes zero if the argument is contained in IC and too otherwise. For any function Ω: Rd - RU [+00). }. let d0m = {y E IRd Q(y) < +0o} be its effective domain and (0) = sup ( (0, y) - N(y) : y E RRd) be its convex conjugate. Table 2 in Appendix A summarizes the notation used in this paper.
3

---

2.1 Online structured prediction (OSP)
We describe the problem setting of OSP. Let X' be the space of input vectors and y be the finite set of outputs. Define K = 1 Following the literature [7, 41], we assume that y is embedded into I& in a standard manner, e.g., y = .ci..... O2) in multiclass classification with d classes.
Let W be a closed convex domain. linear estimator W E W transforms the input vector x into the score vector Wr. a. In OSP, at each round / = ,,...,7 T, the true output yr E y. The learner receives 2 and computes the score vector 0, = W., using the linear estimator W.. Then, the learner selects prediction 3/: based on 0t, which is called decoding. and incurs a loss of Lig yt). Finally, the learner receives feedback, which depends on the problem setting, and updates W; to Wi+1 using some online learning algorithm, denoted by ALG, which is applied to the surrogate loss function W + S(W x;; ye))
the environment selects an input aa E X and
The goal of the learner is to minimize the cumulative target loss Σ I(@rye). which equivalent to minimizing the surrogate regret R Σ L(Dr - Ei=1 S(Ux;; yr). We assume that the imput and output are generated in an oblivious manner. Note that when ) = fei.....es ea) and L vr) = [ * yr). the above setting reduces to online multiclass classification, which was studied in prior work [44, 45]. Let B = diam(W) denote the diameter of W measured by 11-IIp and C2 m ||=|||2 the maximum Euclidean norm of input vectors in X.
The feedback observed by the learner depends on the problem setting. The most basic setting the full-information setting, where the true output Yr: is observed as feedback at the end of each round t, extensively investigated by Sakaue et al. [41]. By contrast, we study the following weaker feedback: In the bandit feedback setting, only the value of the loss function is observed. Specifically, at the end of each round t, the learner observes the target loss value L y as feedback. In the delayed feedback setting, the feedback is observed with certain delay. In this paper, we consider especially a fixed D-round delay setting, ie., no feedback for round S D. and for / >> D, the learner observes either full-information feedback Yt-D or bandit feedback ( Dj Vt- JtD)) We also discuss the verla setting in Appendix G.
In this paper, we make the following assumptions:
Assumption 2.1. (1) There exists v > O such that for any distinct y, y E V, it holds that 1'y || (2) For each y E y, the target loss function L-; y) is defined on conv()?). non-negative, and affine w.r.t. its first argument. (3) There exists 7 such that for any y E conv())) and y E Y, it holds that L S 7 ?lly' yl and L(y': 3) S (4) It holds that L(y y) = 0 if and only if y = y.
As discussed in [41, Section 2.3], these assumptions natural and hold for various structured pre- diction problems and target loss functions, including SELF (see Section 2.4 for the formal definition).
2.2 Fenchel-Young loss
We use the Fenchel-Young loss [7] as the surrogate loss, which subsumes many representative surro- gate losses, such as the logistic loss, Conditional Random Field (CRF) loss [30], and SparseMAP [35].
See [7, Table 1] for more examples.
Definition 1 ([7. Muuchel-Younge loss)). Let Q: Rd + R U {+oc} be a regularization function with y C dQ). The Fenchel- Young loss generated by Ω denoted by Sq: (ooom((""xdo((ff) -> Rgo. is defined as Sa Sn(O:)) y) = Ω (0) 2(v) (0. y)
The Fenchel-Yooue loss has the following useful properties:
Proposition 2.2 ([7, Propositions 2 and 3] and [41, Proposition 3D). Let V. - - be a differentiable, Legendre-type, function" that is X-strongly convex w.r.t. 11-11, and suppose that conv()') C dom (V) and dom( = Rd. Define Ωt = V + Icnnv(y) and let Sa be the Fenchel- Young loss generated by Q. For any 0 Rd, we define the regularized prediction function as Ga (0) = arg (axx((0,)) y) ((( y E Rd) arg max (0. 3) (V()) y E conv())). Then, for any y E V. (n y) differentiable w.r.t. 0, and satisfies V.a y) (o( y. Furthermore, holds that Sn y) 2 2 21)
A function v is called Legendre-type if, for any sequence Ii, Ø2, in int(dom(V)) that converges to a boundary point of int (d)mm)))) it holds that lim V (x:) ||2 +00.

---

In what follows, let S (W) = Sn (W z;; yt) for simplicity. Importantly from the properties of the Fenchel-Young loss, there exists some such that for any W W,
[V) - (W).
(1)
Indeed, from Proposition 2.2, we have || = (0,) yr 111 - 12 (0.) yell S A holds with 2C2
x² S.W,),, where we used (W, (ūn(0.) y )ar and ||:1|2 x||-||- Thus, (1)
2// />. Below, let L,(y) Ly: ye) and G. = (W,) = (0n(O.) y y1),,
2.3 Examples of structured prediction
We present several instances of structured prediction along with specific parameter values introduced so far; see [41, Section 2.3] for further details.
Multiclass classification Let y = (cr. (c...... ................... ..)) and || |-111- As the 0-1 loss satisfies L(y; = [y * c. = プラ U/ = (1
+ Σ jهز UU 2 || yll1, we have = 2 in Assumption 2.1. Also, 2 holds since lle, e, = 2 if * j. The logistic surrogate loss is a Senchel-Young. loss Sn generated by the negative Shanmon entropy f2 = H +Is, (up to a constant factor originating from the base of log), where (y) = - Ee D: log ys and Aa is the (d- (od-1)-dimennn d-mmensiional probability simplex. Since a 1-strongly convex function w.r.t. ||-11: on Ad, we have X 1.
1j and |-1|= 11-112 When using the Hamming loss as the larget loss function L(y': y) = 2/ - 1 [// # y:l. Assumption 2.1 is satisfied with v = 1 and ry 4 The MAP surrogate loss Sn (,, y) = b - - _ (0) 011 is a Fenchel-Young loss
Multilabel classification Let
generated by 52 211-112 + Iconv(y)- Since Ω is 1-strongly convex w.r.t. 11-112, we have A = 1.
Ranking We consider predicting the ranking of m items. Let ||-11 = |1- d = m², and y C 1) 1]dd be the set of all vectors representing X m permutation matrices. We use the target loss function that counts mismatches, Lyy Llyyy//) 3) = 1 Di= [y,,, #B.,.. where ji E [m]] is a unique index with
Viy. = 1 for each E [m]. In this case, Assumption 2.1 is satisfied with v = 4 and 7 2m surrogate loss given by (0; y) (0, (0 (0) y) + H (fe where f H +conv())) and controls the regularization strength. The first term in Si2 measures the affinity between O and y. while the second term evaluates the uncertainty of (0). Since Q is mc
1 We use
strongly convex, we have mc
2.4 Structured encoding loss function (SELF)
We introduce general class of target loss functions, called the (generalized) Structured Encoding Loss Function (SELF) [6, 12, 13]. A target loss function is SELF if it can be expressed as
(3 Ut) = (g: yy + 6) + c(y)).
(2)
where b E Rd is a constant vector, V E: dRdd is a constant matrix, and ) + R is a function. The following examples of target losses, taken from [6, Appendix A], belong to the SELF class:
Multiclass classification: the 0-1 loss is SELF with V = 1 - I, b = O, and c(y) = 0.
Multilabel classification: the Hamming loss, L(y': = Ei= 1 [VV', is a SELF with V=
-31, b- 11, and c(y) - d (y, 1), where c(y) is constant if the number of correct labels is fixed. Ranking: the Hamming loss T.(y' y) = m Em 1 [VL,, * yi.j.). where jr [mi] is a unique index with yı,j for each E [m]] a SELF with V = II/m, b = 0. and c(y) =
Following the work by Sakaue et al. [41], we assume that the target loss function L is a SELF
2.5 Randomized decoding
We employ the randomized decoding [41], which plays an essential role, particularly in deriving an upper bound independent of the output set size K | in Section 3.4. The randomized de- coding (Algorithm 1) returns either the closest y E y to (0 E conv())) (see Proposition 2.2) or random ÿ E )' satisfying Ely Z 1] In (0). where Z follows the Bernoulli distri- bution with a parameter p. Intuitively, the parameter p is chosen so that if Tn is close to y", the decoding more likely returns y"; otherwise, it more likely returns ÿ. reflecting uncertainty.
5

---

A crucial property of the randomized decoding the following lemma, which we use in the subsequent analysis:
Algorithm 1 Randomized decoding og
Input: 0 &Rd
Lemma 2.3 ([41, Lemma 4J). For any (0. y) E
1: Compute (n()) defined in Proposition 2.2.
R x X., the randomized decoding on satisfies
2: y" t arg min (n(O)]l: y E )).
[| (0); y)] S 41 y)) where the ex- pectation taken w.E.t the randomness of sa.
3: A < 11y Yn (0) p 6--min 24 /v}.
XU
4: Sample Z ~ Ber(p).
5: if Z = 0 then : - y
Remark 1. In randomized decoding, computa- tion of ÿn (0) is the dominant cost, but we can compute it efficiently using Frank-Wolfe-yype algorithm (see e.g. Garber and Wolf [22] and Sakaue et al. [41, Section 3.1] for details).
6: if Z 1 then y +- y where ÿ is randomly
drawn from y so that Bly Z = 1 = (0)
Output: (n) y
3 Bandit feedback
In this section, we present two OSP algorithms for the bandit feedback setting and analyze their surrogate regret. Our results can be extended to handle bandit and delayed feedback; see Section Here, we focus on the simpler case without delay to provide clearer exposition of our core ideas.
3.1 Randomized decoding with uniform exploration
We discuss the properties of our decoding function, called Randomized Decoding with Uniform Exploration (RDUE), which will be used in subsequent sections. As discussed in Section 2.5, the randomized decoding (Algorithm 1) was introduced as a decoding function [41] for OSP with full-information feedback. However, naively applying it does not lead to a desired bound under bandit feedback due to the lack of exploration. We extend the randomized- decoding framework to handle bandit feedback effectively.
A Algorithm Randomized decoding with uniform exploration (RDUE) 4/12
Input:
R q E [0.
1: Sample X ~ Ber
2: if X then ÿ (
3: if X = 1 then Sample y from y uniformly at random and ÿ yy" Output: wn( 9
RDUE (Algorithm 2) is procedure that, with probability q E [0, 1]. selects y uniformly at random from V and with probability 1 1- q, selects the output of the randomized decoding. Let (r be the probability that the output of RDUE, Dh coincides with y at round t. Note that for any y E V, it K thanks to the uniform exploration. Furthermore, similar to the property of the
holds that pr (y) 2 4. randomized decoding in Lemma 2.3, RDUE satisfies the following property:
Lemma 3.1. For any (0, y) E Rd x Y, RDUE tn satisfies (0); y)] S 2 (1 (1- (0: q K- where the expectation is taken w.r.. the internal randonness of RDUE.
Proof. With probability - the randomized decoding is used; otherwise, a uniformly random
output is chosen. Thus, ( (0); (0); ():p0 y)] < (1 ( (0): y)] q K-1 holds, where Φn the randomized decoding and we used ((::) S 1. Combining this with Lemma 2.3 completes the proof.
Based on this lemma, we make the following assumption for convenience: Assumption 3.2. There exists (0, 1) such that E, [L (..) (1 aW)) + q. Here, EcH-]
denotes the conditional expectation given the past outputs, y1 yt-1-
This assumption can be satisfied by using RDUE for < 1
カ (1 q) if 11 q). due
to Lemma 3.1. In what follows, we set a = 1 A Note that >> 47 > 17 - 9) holds in the cases of multiclass classification, multilabel classification, and ranking (see Section 2.3 and [41] for details). The purpose of this assumption is to ensure that a reduction in the surrogate loss leads to a proportional reduction in the target loss.
3.2 Online gradient descent
We use the adaptive Online Gradient Descent (OGD) algorithm [42] as ALG, which we apply to surrogate loss S. OGD updates W, to W4+1 by using the gradient G. = VS,(W)) and learning

---

rate as W t Iw W G)),,, where (2) - arg min xewlx [p.. OGD achieves the following bound:
Lemma 3.3 (e.g. [37, Theorem 4.14). Lel 1/1 3/ G l Then, OGD achieves
E (S((W)) (() S E (Ge, W. -U) S - SVBB Σ [G for any U W.
3.3 Algorithm based on inverse-weighted gradient estimator with O regret
We present an algorithm that achieves a surrogate regret upper bound of O(VKT).
Algorithm based on inverse- gradient estimator In the bandit setting, the true output yo is not observed, and thus we need to estimate the gradient of S,W,) (W,) required for updating W.. To
do this, we use the inverse-weighted gradient estimator G: 1 = Gt. where G. = V...WW))
9.
(O.) yt )=:"" Note that G2 is unbiased, i.e., EE [G]]]] GG. We use RDUE with q B ByK/I K/T as the decoding function (assuming T > B² K for simplicity). For ALG, we employ the adaptive
OGD in Section 3.2 with the learning rate of 1/2 2/
Remark 2. This study defines the bandit feedback as the value of the target loss function (()). Note, however, that the above algorithm operates using only the weaker feedback of 1 * yıl.
Regret bounds and analysis The above algorithm achieves the following surrogate regret bound:
Theorem 3.4. The above algorithm achieves the surrogate regret of B[Rr] S 2. 1)BVKT.
This upper bound achieves the rate of vT, which matches the existing surrogate regret upper bound for bandit multiclass classification in [45]. Regarding the dependence on K, our bound improves the existing O(KVT) bound in [44, 45] by a factor of v K. Note, however, that the O(K (T) bound in [45] applies to a broader class of surrogate loss functions. For example, in K-class classification, their bound applies to the base-k logistic loss for l S K, while ours is restricted to the base-2 logistic loss. A more detailed discussion is given in Appendix C.3. As for tightness, an 22( (T) lower bound is provided in [45] for the graph feedback setting, variant of the bandit feedback model. This suggests that the VT dependence would be close being tight, although this lower bound does not directly apply to the bandit setting. Therefore, whether the rate of /T is improvable not is left open.
Proof of Theorem 3.4. From the convexity of S. and the unbiasedness of G.. - U}}. From Lemma 3.3 and Jensen's in- E E T (S, (U))] I EE (G., W. equality, this is further upper bounded as EE (Gi, W. - -U} S vBB B E |G < (Wi,,, which follows from (z) 2 K/q and (I). From Assumption 3.2,
B " (WW)), where we used [. = [ < K 1
E[ S EI ((1 - (W.) - St(U))] + TT S BV 26K E (WW) - aE|EL= Se (W.)
TT 6B2 K + qT, where we used ci /z- c2 S e2/ for 0, c1 2 0, and 02 0. Plugging
20q
q B K/T into the last inequality completes the proof.
We can also prove surrogate regret bound of O(y KT (18) + log(1/8)), which holds with probability 1 1-6 8. The precise statement and proof are provided in Appendix D.2. To prove this high-probability bound, we follow the analysis of Theorem 3.4 and use Bernstein's 's inequality. To address the challenges posed by the randomness introduced by bandit feedback, we adopt an approach similar to that used in [45], and arguably, we have simplified their analysis.
3.4 Algorithm based on pseudo-inverse matrix estimator with O(72/3) regret
We provide an algorithm with new estimator that achieves a K-independent surrogate bound, and we identify the conditions and the class of loss functions under which this new estimator can be used.
7

---

While the surrogate regret bound of O(VKT) achieves the presumably tight dependence on T, the dependence on K | is undesirable for general structured prediction. In fact, we have K = (m) in multilabel classification with m correct labels and K = m! in ranking with m items. To address this issue, we present an algorithm that significantly improves the dependence on K when the target loss function belongs to a special class of SELF (2) with the following additional assumptions:
Assumption 3.5. (i) The matrix V is known and invertible, and b and c(-) are known and non- negative. (ii) Let Q = Ey-- [yy 1, where μ. is the uniform distribution over V. At least one of the following two conditions holds: (ii-a) Q is invertible, or (ii-b) for any y E V. Vy lies in the linear subspace spanned by vectors in y. (iii) For some w > 0, it holds that (r Q (V (V-1)T) S w. (iv) For any Y E y and y E V. it holds that (ύr. Vy 1.
The first and fourth conditions are true in the examples in Section 2.4, assuming that the number of correct labels, m, fixed in multilabel classification. (While the fourth condition does not hold when > d/2 in multilabel classification, we can flip 0 and 1 in the labels to redefine the problem that satisfies the condition.) The second one holds if y consists of linearly independent vectors or V is proportional to the identity matrix; either is true in the examples. Also, deriving reasonable bounds on w in those examples is not difficult; see also Appendix D.4 for details.
Algorithm based on pseudo-inverse matrix estimator As with Section 3.3, we consider estimating the gradient. Let P. = Ey--p [yy"] and define the estimator Yt of y: by y: = V-1 De (ū:, Vyt), where P is the Moore-Penrose pseudo-inverse matrix of Pt. Note that, given that b and c(-) are known, we can compute (ūr, yy.) L.. T b) c(y.). Importantly, is unbiased, i.e. [ = y/ from the second requirement of Assumption 3.5.
By using this Dr. we define the pseudo-inverse matrix estimator G. by G. = (0n(O.) - Tt ) which is also unbiased, i.e., E,G.,] G.. Our estimator is inspired by those used in adversarial linear bandits and adversarial combinatorial full-bandits [1, 9, 16].
We use RDUE with = (4wB2 as the decoding function (assuming T 2 CBBC2 for simplicity). To update W., we use OGD in Section 3.2 as ALG with 1):- B/v B 2 G.
Regret bounds This algorithm achieves the following surrogate regret bound independent of K: Theorem 3.6. The above algorithm achieves B[Rr] /332/33)
The proof can be found in Appendix D.3. Note that we leverage the structure of OSP when using the pseudo-inverse matrix estimator, which largely differs from the existing approaches to surrogate regret analysis for online classification and OSP [41, 44, 45]. With the pseudo-inverss matrix estimator, we can upper bound the second moment of the gradient estimator G. without K, which allows for the surrogate regret bound that does not explicitly involves K. This is in contrast to the inverse- weighted gradient estimator in Section 3.3. The -reese-weiggted gradient estimator involves division by Pt. whose lower bound comes from uniform exploration )) consequently, its upper bound depends on K = [ In other words, the above pseudo-inverse matrix estimator offers an alternative way to obtain an unbiased gradient estimator while eschewing uniform exploration on V. However, this comes at the price of a somewhat looser bound on the second moment, which increases the dependence on T.
As a corollary of Thcorem 3.6, we can derive specific bounds for each problem as follows:
Corollary 3.7. The above algorithm achieves [[[T]] = (dd/3372/3) in multiclass classification in multilabel classification with m
with the 0-1 loss (w = ) B[Rr] = ((d)) correct labels and the Hamming loss (w = / (d m)), and [[[r]] = 0mm3/372/3) in ranking with the number of items and the Hamming loss (w = m²).
/m(ddmmm - m O(dP/m(d
The proof of Corollary 3.7 is deferred to Appendix D.4. The bound for multilabel classification with m correct labels can be significantly better than the O ((KTT) bound in Section 3.3 since K- = / (d):
similarly, the bound for ranking can be much better than the OVVKT) bound since K = -mm.
Complexity of computing Pf The matrix P. equals the sum of Ey-p, [yy] and Ey-wllrr J.. The expectation Ey-p, [yy" "] can be calculated analytically in the multiclass and multilabel clas-
8

---

sification and ranking. For Ey-ulvy"], when (0) is obtained via the Pt obtained from the convex combination coefficients, whose support size is at most O(d) as implied by Carathéodory's theorem (cf. [4]). Therefore, we can compute P. in O(d9) time, and the pseudo-inversion takes the same order of complexity.
algorithm.
4 Delayed full-information feedback
This section discusses OSP with fixed-delay full-information feedback and presents two algorithms that achieve surrogate regret bounds of ((min + 1, (D + 1)2/$11/33) and O(D + 1), which are better than the O(v(D) (D 1Y7) bound obtained by standard OCO algorithm under delayed feedback [27]. Although the first upper bound worse than the second, we include here a preliminary step toward the algorithm for the delayed and bandit feedback setting described in Section 5.
Below, we make the following assumption based on the randomized decoding of [41].
Assumption 4.1. There exists a constant a E (0, 1) that satisfies E. S (1 aW,.
From Lemma 2.3, if X > 47, this condition is satisfied with decoding. We suppose that such a decoding function is used in this section.
dz by using the randomized xv
4.1 Algorithm based on ODAFTRL with Ommin + 1, (D 1323311/33) regret
Algorithm We employ the Optimistic Delayed Adaptive FTRL algorithm (ODAFTRL) [20] as ALG, which we detail in Appendix E. for completeness. ODAFTRL computes the linear estimator by W++1 E arg ew (EEr (G,, W) Р I[])), where X > 0 is the regularization parameter. By updating A using an AdaHedge-type algorithm (AdaHedgeD), ODAFTRL achieves the following AdaGrad-type regret upper bound:
Lemma 4.2 (Informal version of [20, Theorem 121). Consider the delayed full-information set- ting. For any E W. ODAFTRL with the AdaHedgeD update of > achieves a regret bound of ΣL (S((W,) - S.( - OVV I + +D E.
Regret bounds and analysis The above algorithm achieves the following surrogate regret bound: Theorem 4.3. The above algorithu achieves E[Rr] = =Omin + (D 11//3/11/33)
Recall that the proof ideas for deriving surrogate regret bounds in the non-delayed setting [41, 45] differ from those in the standard OCO and numti- bandits, and thus we cannot naively extend the analyses of the algorithms for delayed feedback those settings to our case. Below is the proof sketch, and the complete proof is given in Appendix E.2.
Proof sketch. From Lemma 4.2 with || - (W,(W,) in (1) and Cauchy-Schwarz, we have EL (S. (W, (U) O(D where SIT Σ (WW)). Thus, Assumption 4.1 implies [[Rr] S Σ (W, - S())) - a E Sr = O(D/S1r)) - aSir = O(D?)
where we used Ci c2 S (4/(())) for x 2 O. c1 2 0, and C2 > 0.
We can also prove a high-probabilie surrogate regret bound of O(min D + 1, (D + 1/3 log(1/6)), which holds with probability at least 5. See Appendix E.3 for the proof.
4.2 Algorithm based on BOLD with O(D + 1) regret
Algorithm We use the Black-box Online Learning under Delayed feedback (BOLD) [27] as ALG. BOLD constructs D + independent instances of any deterministic non-delayed online learning algorithm (called BASE) denoted as BASE, BASE,,... BASED This algorithm selects which instance to use according to the value of remainder E (O...., D}. which satisfies = -- for some & Z At each round I, BOLD invokes BASE,,- Here, we adopt OGD as BASE The pseudocode of BOLD is given in Appendix E.4.

---

Regret bound The above algorithm achieves the following surrogate regret bound: Theorem 4.4. The above algorithm achieves E[Rr] O + 1).
The proof is given in Appendix E.4. The upper bound in Theorem 4.4 matches the following lower bound, whose proof is provided in Appendix E.5.
Theorem 4.5. Let d 2 2. For B (llog(dT)) there exists sequence {(m ye) with ||æell2 = 1 such that the surrogate regret with respect to the logistic surrogate loss of any possibly randomized algorithm is lower bounded by [T] = 22 (B²(DD 1)/ d)²).
5 Delayed bandit feedback
Given the results so far, it is natural to explore OSP with delayed bandit feedback. We construct algorithms for this setting by combining the theoretical developments from Sections 3 and 4.1.
5.1
Algorithm for bandit delayed feedback with O(v(K + D)T) regret
We adopt RDUE with q By/KiT for decoding (assuming T > B²K), the inverse-weighted gradient estimator G. and ODAFTRL with AdaHedgeD as ALG. Then, the following bound holds: Theorem 5.1. The above algorithm achieves E[Rr] O(v(K
(K + D)T).
The proof can be found in Appendix F.2. This upper bound incurs additional additive D(DTT) factor compared to the bound in the non-delayed case in Theorem 3.4. Whether this surrogate regret upper bound is optimal remains open. While an S2(VT) surrogate regret lower bound exists in the graph feedback setting [45], no such lower bound is known for the bandit non-delayed setting, and constructing lower bounds under delayed feedback would be more difficult.
5.2 Algorithm for bandit delayed feedback with ( regret
We provide an algorithm that improves the dependence on K from Section 5.1. We make the same assumptions on the target loss function Section 3.4. We use RDUE with q (DB 1/3 for decoding (assuming T 2 w wB2 2 D), the pseudo-inverse matrix estimator G., and ODAFTRL with the AdaHedgeD update as ALG. Then, the following bound holds:
Theorem 5.2. The above algorithm achieves E[Rr] 0(313322/3)
The proof can be found in Appendix F.3. Due to the presence of the delay, the surrogate regret bound worsens by factor of 11/3 compared to the non-delayed bandit setting. Additionally, we present algorithms for the variable-delay setting, which we defer to Appendix G due to space limitations.
The algorithm in this section employs ODAFTRL rather than BOLD for the following reasons. First, ODAFTRL leads to at least as good regret upper bounds as BOLD under bandit delayed feedback. BOLD-based algorithms with the inverse- iniigtee gradient estimator and the pseudo-inverse matrix estimator attain regret upper bounds of O (KDT) and O(D2/312/3 respectively, which are not better than the bounds Theorems 5.1 and 5.2 obtained with ODAFTRL. Second, as noted by Flaspohler et al. [20], approaches such as BOLD, which run multiple parallel instances, cause each instance to operate independently and observe only T/(D+1) losses. This reduction can significantly worsen empirical performance, particularly when T is not very large relative to D.
Conclusion
We have developed several algorithms for online structured prediction under bandit and delayed feedback and analyzed their surrogate regret. Among these contributions, of particular note the algorithm for bandit feedback whose surrogate regret bound does not explicitly depend on the output set size K, achieved by leveraging the pseudo-inverse matrix estimator. An important direction for future work is investigate the corresponding lower bounds in the bandit feedback setting. The existing lower bound of Q( /T) in the graph-feedback setting [45] suggests that similar bound likely holds here as well; however, this has yet to be proven for our settings, and the tightness of our upper bounds remains an open question.
'Here, unlike in the previous sections, we use D) instead of D + 1, since this algorithm is not intended to handle the non-delayed case of () 0.
10

---

Acknowledgments and Disclosure of Funding
The authors would like to express their sincere gratitude to the anonymous reviewers for their insightful feedback and constructive suggestions, which have significantly improved the manuscript, particularly the discussion of the upper bound under delayed feedback. TT is supported by JST ACT-X Grant Number JPMJAX210E and JSPS KAKENHI Grant Number JP24K23852. SS was supported by JST ERATO Grant Number JPMJER 1903, and KY supported by JSPS KAKENHI Grant Number JP24H00703.
References
[1] Jacob D. Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Proceedings of the 21st Annual Conference Learning Theory, pages 263-274, 2008.
2008.
[2] Gökhan Baklr, Thomas Hofmann, Bernhard Schölkopf. Alexander J. Smola, Ben Taskar, and S.V.N Vishwanathan. Predicting Structured Data. The MIT Press, 2007.
[3] Peter L. Bartlett, Michael Jordan, and Jon D. Mcauliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473): 156, 2006.
[4] Mathieu Besançon, Sebastian Pokutta, and Elias Samuel Wirth. The pivoting framework: Frank-Wand Wolfe algorithms with active set size control. In Proceedings of the 28th International Conference Artificial Intelligence and Statistics, volume 258, pages 271-279. PMLR, 2025.
[5] Alina Beygelzimer, Francesco Orabona, and Chicheng Zhang. Efficient online bandit multiclass learning with Õ(VT) regret. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 488-497. PMLR, 2017.
[6] Mathieu Blondel. Structured prediction with projection oracles. In Advances in Neural Information Processing Systems, volume 32, pages 12145-12156. Curran Associates, Inc., 2019.
[7] Mathieu Blondel, Andre F.T. Martins, and Vlad Niculae. Learning with Fenchel- Young losses. Journal of Machine Learning Research, 21(35): 2020.
[8] Nicolò Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[9] Nicolò Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 1404 2012.
[10] Nicolò Cesa-Bianchi, Alex Conconi, and Claudio Gentile. A second-order perceptron algorithm.
SIAM Journal on Computing, 34(3):640-668, 2005.
[11] Nicolò Cesa-Bianche Bianchia Claudio Gentile, Yishay Mansour, and Alberto Minora. Delay and cooperation in nonstochastic bandits. In Proceedings of the 29th Annual Conference on Learning Theory, volume 49, pages 605-622. PMLR, 2016.
[12] Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A consistent regularization approach for structured prediction. In Advances in Neural Information Processing Systems, volume 29, pages 4411-44220 Curran Associates, Inc., 2016.
[13] Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A general framework for consistent structured prediction with implicit loss embeddings. Journal of Machine Learning Research, 21 (98):1-67, 2020.
[14] Richard Combes, Mohammad Sadegh Talebi, Alexandre Proutiere, and Mare Lelarge. Combi- natorial bandits revisited. In Advances in Neural Information Processing Systems, volume 28, pages 2116-21 Curran Associates, Inc., 2015.
[15] Koby Crammer and Yoram Singer. Ultraconservative online algorithms for multiclass problems. Journal of Machine Learning Research, 3:951 1-911, 2003.
[16] Varsha Dani, Sham M Kakade, and Thomas Hayes. The price of bandit information for online optimization. Advances in Neural Information Processing Systems, volume 20, pages 345-352, 2007.
11

---

[17] Amit Daniely, Sivan Sabato, Shai Ben- aavidavi, and Shai Shalev-Shwartz Multiclass learnaiility and the ERM principle. Journal of Machine Learning Research, 16(72):2377-2444 2015.
[18] Yihan Du, Yuko Kuroki, and Wei Chen. Combinatorial pure exploration with full-bandit or partial linear feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7262-7270, 2021.
[19] Michael Fink, Shai Shalev-Shwards Yoram Singer, and Shimon Ullman. Online multiclass learning by interclass hypothesis sharing. In Proceedings of the 23rd International Conference on Machine Learning, pages 313-320. ACM, 2006.
[20] Genevieve E. Flaspohler, Francesco Orabona, Judah Cohen, Soukayna Mouatadid, Miruna Oprescu, Paulo Orenstein, and Lester Mackey, Online learning with optimism and delay. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages 3363-3373. PMLR, 2021.
[21] Dylan J. Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan, Logistic regression: The importance of being improper. In Proceedings of the 31st Conference on Learning Theory, volume 75, pages 167-208. PMLR, 2018.
[22] Dan Garber and Noam Wolf. Frank- with a nearest extreme point oracle. Proceedings of the 34th Conference on Learning Theory, volume 134, pages 2103-2132. PMLR, 2021.
[23] Claudio Gentile and Nick Littlestone. The robustness of the p-norm algorithms. In Proceedings of the 12th Annual Conference on Computational Learning Theory, pages 1 1-11. ACM, 1999.
[24] Claudio Gentile and Francesco Orabona. On multilabel classification and ranking with bandit feedback. Journal of Machine Learning Research, 15(70):44512248) 2014.
[25] Elad Hazan and Satyen Kale. Newtron: An efficient bandit algorithm for online multiclass prediction. In Advances in Neural Information Processing Systems, volume 24, pages 891-899. Curran Associates, Inc., 2011.
[26] Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, and Ken-Ichi Kawarabayashi. Delay and cooperation in nonstochastic linear bandits. In Advances in Neural Information Processing Systems, volume 33, pages 4872-4883. Curran Associates, Inc., 2020.
[27] Pooria Joulani, Andras Gyorgy, and Csaba Szepesvari. Online learning under delayed feedback. In Proceedings of the 30th International Conference on Machine Learning, volume 28, pages 1453 1461. PMLR, 2013.
(28) Pooria Joulani, Andras Gyorgy, and Csaba Szepesvari. Delay tolerant online convex optimiza- tion: Unified analysis and adaptive-gradient algorithms. In Proceedings the on Artificial Intelligence, volume 30, pages 1744-1750, 2016
the AAAI Conference
[29] Sham M. Kakade, Shai Shwarr,S and Ambuj Tewari. Efficient bandit algorithms for online multiclass prediction. In Proceedings of the 25th International Conference on Machine Learning, pages 440-447 2008
[30] John Lafferty, Andrew McCallum, and Fernando C. N. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the 18th International Conference on Machine Learning, pages 282-289. Morgan Kaufmann Publishers
Inc., 2001.
[31] Yann LeCun, Corinna Cortes, and Christopher C. J. Burges. The MNIST database of handwritten digits, 1998. http://yaann. www.eeewweeeee....eeeee.eeeeeeee cww.exdb/mmisst.....
[32] Naresh Manwani and Mudit Agarwal. Delaytron: Efficient learning of multiclass classifiers with delayed bandit feedbacks. In Proceedings of the 2023 International Joint Conference on Neural Networks, pages 1-10, 2023.
[33] Saeed Masoudian, Julian Zimmert, and Yevgeny Seldin. A best-of-boot bott-f--both-wordds algorithm for bandits with delayed feedback. In Advances in Neural Information Processing Systems, volume 35, pages 17722-1762. Curran Associates. Inc., 2022.
[34] Chris Mesterharm. On-line learning with delayed label feedback. In Proceedings of the 16th International Conference on Algorithmic Learning Theory, pages 399-419 Springer Berlin Heidelberg, 2005.
12

---

[35] Vlad Niculae, André F. T. Martins, Mathieu Blondel, and Claire Cardie. SparseMAP: Differ- entiable sparse structured inference. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 3799-3808. PMLR, 2018.
[36] Albert J. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium on Mathematical Theory of Automata, pages 615-620, 1962.
[37]
Francesco Orabona. A modern introduction to online learning. arXiv:1912.13213, 2019.
[38] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vander- plas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Edouard Duchesnay, Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12(85):2825 2830,, 2011.
[39] Idan Rejwan and Yishay Mansour. Top-k combinatorial bandits with full-bandit feedback. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 1 117, pages 752-776. PMLR, 2020.
[40] Frank Rosenblatt. The perceptron: A probabilisticc model for information storage and organiza- tion the brain. Psychological Review, 65(6):386-408, 1958.
[41] Shinsaku Sakaue, Han Bao, Taira Tsuchiya, and Taihei Oki. Online structured prediction with Fenchel-Young losses and improved surrogate regret for online multiclass classification with logistic loss. In Proceedings of the 37th Conference on Learning Theory, volume 247, pages PMLR, 2024.
[42] Matthew Streeter and H. Brendan McMahan.
Less regret via online conditioning.
arXiv:100..4862, 2010.
[43] Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann, and Yasemin Altun. Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research, (450):445-1184- 2005.
[44] Dirk van der Hoeven. Exploiting the surrogate gap in online multiclass classification. In Advances in Neural Information Prucessing Systems, volume 33, pages 9562-9572. Curran Associates, Inc., 2020.
[45] Dirk van der Hoeven, Federico Fusco, and Nicolò Cesa-Bianchi. Beyond bandit feedback in online multiclass classification. In Advances in Neural Information Processing Systems, volume 34, pages 13280-13299 13291. Curran Associates, Inc., 2021.
[46] Dirk van der Hoeven, Lukas Zierahn, Tal Lancewicki, Aviv Rosenberg, and Nicolò Cesa-Bianchi. A unified analysis of nonstochastic delayed feedback for combinatorial semi-bandits, linear bandits, and MDPs. In Proceedings of the 36th Conference on Learning Theory, volume 195, pages 1285-1321. PMLR, 2023.
[47] Marcelo J. Weinberger and Erik Ordentlcch. On delayed prediction of individual sequences. IEEE Transactions on Information Theory, 1957) 2002.
[48] Julian Zimmert and Yevgeny Seldin. An optimal algorithm for adversarial bandits with arbitrary delays. In Proceedings of the 23rd International Conference Artificial Intelligence and Statistics, volume 108, pages 3285 -3944. PMLR, 2020.
13

---

A
Notation
Table 2 summarizes the symbols used in this paper.
Table 2: Notation
Symbol
Mcaning
T TEN N
Time horizon
d N
Dimension of output space y
diam (W)
Diameter of W
C₁ = maxaex||a0||
Maximum norm of input vectors X' The maximum of the largest Euclidean norm of vectors in conv()") or the diameter of conv()))
C
= |>
Cardinality of )
ALG
Algorithm for updating linear estimators Output chosen by the learner at round / Probability that y is chosen as ÿr time
EV
Pr(y)
L:Y> x X + Rzo
Target loss function
L(Oi)= = L(T y1)
Value of target loss L yt)
So:R" x) IR20
Fenchel-Young loss generated by Ω
S(W
Wo yt)
Shorthand of surrogate loss Sn ( a;;; B:)
R7 = -T=1 (Le(3e) - (U)
Surrogate regret
G. (S,(W))
Gradient of surrogate loss
G,
Inverse weighted estimator Pseudo-inverse matrix estimator
G.
Uniform distribution over y Second moment matrix under pt Second moment matrix under Minimum eigenvalue of matrix A Upper bound of tr tr(V-IQ** V)
P. = Kyg-p yy
Q = Eyn yy 1
Amin (A)
w
E.
Conditional expectation given ....... 9.
E
Fixed-delay time
72
Variable delay time Maximum value of delay time
= max, Tr
p(t)
Time step of the fth feedback from SOLID to BASE
F = t -
> p((t)-1
1[s + < p(t)
The number of feedback from SOLID to BASE
mml
pending during the ith feedback
B
Additional related work
We discuss additional related work that could not be included in the main text.
Structured prediction Before the development of the Senchel-Youny loss framework, Niculae et al. [35] proposed SparseMAP, which used the squared f--morm regularization. The Fenchel-Your loss, described in Section 2.2, built upon the idea SparseMAP. The Structure Encoding Loss Function (SELF) was introduced by Ciliberto et al. [12, 13] analyze the relationship between surrogate and target losses, a concept known as Fisher consistency. For more extensive literature review, refer the reader to Sakaue et al. [41, Appendix A].
14

---

Online classification with full and bandit feedback In the full-information setting, the perceptron one of the most representative algorithms for binary classification [40], and the multiclass setting has also been extensively studied [15, 19]. Online logistic regression is another relevant research stream, with Foster al. [21] being a particularly representative study. The study of the bandit setting was initiated by Kakade et al. [29], and it has since been extensively explored in subsequent research [5, 21, 25]. However, to the best our knowledge, no prior work has addressed general structured prediction under bandit feedback. One of the most relevant studies is the work by Gentile and Orabona [24], who investigated online multilabel classification and ranking. However, their setting assumes access to feedback of the form [1[yr. * Vr,i)), which is more informative than bandit feedback and differs from our setting. Van der Hoeven [44] introduced the surrogate regret in the context of online multiclass classification. This study has been extended to the setting where observations are determined by a directed graph [45] and to structured prediction [41]. J. For more extensive overview of the literature online classification, refer the reader to Van der Hoeven [44].
Delayed feedback The study of delayed feedback was initiated by Weinberger and Ordentlich [47]. Since then, has been extensively explored in various online learning settings, primarily in the full-information setting of online convex optimization [20, 27, 28, 34]. Algorithms for delayed bandit feedback have been studied mainly the context of multi-armed bandits and their variants [11, 26, 33, 46, 48]. In online classification, research considering delay is scarce; the only work is that of Manwani and Agarwal [32] to our knowledge. There are several differences between their work and ours. Among them, key distinction is that their study focuses multiclass classification, whereas we address the more general OSP.
C Discussion on the surrogate regret
Our work employs the surrogate regret as the performance measure, which represents the excess target loss relative to the surrogate loss achieved by the best offline estimator. This differs from the standard regret, which is defined solely terms of the target loss. Below, we discuss the motivation and background of the surrogate regret, and compare it to the standard regret.
C.1 Background and motivation
Although the term "surrogate regret" has only recently come into use, its concept dates back to the classic analysis of the perceptron [36, 40]. Specifically, the celebrated convergence of the perceptron under linear separability can be interpreted as a finite upper bound on the surrogate regret, where the hinge loss of the best offline estimator, E SUUU), equals zero; see Orabona [37, Section 8.2]. Since then, similar performance measures have continued to attract considerable attention in the literature [8, 10, 19, 21, 23, 29]. The concept of the surrogate regret was highlighted in the recent work by Van der Hoeven [44] on online classification, and the terminology was explicitly used the subsequent work by Van der Hoeven et al. [45]. Later, Sakaue et al. [41] extended this concept to online structured prediction.
The surrogate regret is designed to evaluate how small the cumulative target loss can be made, sharing the same spirit as the standard regret in this regard. The main motivation for using the surrogate regret lies in the empirical observation that the cumulative surrogate loss can often be made very small. An extreme case is the linearly separable setting considered in the convergence analysis of the perceptron, where ΣT, (U) = holds for the hinge loss. Thus, the surrogate regret naturally captures the data-dependent easiness of problem and yields better upper bounds on the cumulative target loss as the cumulative surrogate loss becomes smaller.
C.2 Comparison to the standard regret
In online classification, given hypothesis class H consisting of mappings from X' to Aa, the standard regret is defined as Σ 1 (ğt * ye] inf Et= 1 [h(xx, + ye). Unlike the surrogate regret, it is defined solely in terms of the target loss. At conceptual level, the standard regret focuses more on worst-case analysis under the agnostic setting, whereas the surrogate regret designed to benefit from data-dependent analysis, as discussed above. For the standard regret, Daniely et al. [17] established lower bound of LLimmHH)) where Ldim(H) denotes the Littlestone dimension
15

---

of H. This does not contradict the finite upper bound on the surrogate regret, since the cumulative surrogate loss may grow with T.
C.3 Discussion the difference in surrogate loss functions
As in Section the surrogate regret, Rr, is defined by Σ (( - S(U y:) Rr. which means the choice of the surrogate loss function, S, affects the bound on the cumulative loss E. L gt)) Van der Hoeven al. [45, Theorem IJ. which applies to more general setting than bandit feedback, implies Ry OKK /T) for the bandit setting with S being a logistic loss defined with the base-K K logarithm. On the other hand, our bound of Rr O(v KT) applies to the logistic loss S defined with the base-2 logarithm. As result, while our bound on Rr is better, w the Σ (Ux yr) term be worse; this is why bound with the OKK bound in Van der Hoeven et al. [45, Theorem 1]. We may use the decoding procedure in Van der Hoeven et al. [45], instead of RDUE, to recover their bound that applies to the base- logistic loss. It should be noted that their method is specific to multiclass classification; naively extending their method to structured prediction formulated as | classification results in the undesirable dependence on K [ as is also discussed in Sakaue al. [41]. By contrast, our pseudo-inverse estimator, combined with RDUE, can rule out the explicit dependence on K, at the cost of the increase from /T to 72/3,
cannot directly compare
O( (VVKT)
D Details omitted from Section 3
This section provides the omitted details of Section
D.1 Concentration inequality
To prove high probability regret bounds, we will use the following concentration inequality.
Lemma D.1 (Bernstein's 's inequality, e.g., [8, Lemma A.8]). Let Zi..... Zr be a martingale dif- ference sequence and E (0, 1). If there exist a and which satisfy lZ for any E [T] and then with probability at least 8, holds that
ΣT
E z S
1 V2 a log 8"
Σ
Zi S
20 log
8
D.2 Proof of high probability bound
Here, we provide the proof of high probability bound. Hereafter, we let Smax = max (:(W) and (W) (W) - S.W).. The following theorem is the formal version of the high probability bound under the bandit feedback:
((())))
Theorem D.2. Consider the bandit and non-delayed setting. Let
2(a + - +1) max log(2/8) + B²Kb
C
2(1 -
Then, for any T 2 C and 8 E (0, with probability at least 1 - 5, the algorithm in Section 3.3 with q VC/T achieves
(
1-a
Rr S 2VCT + /2
+2 log(2/6). 2( -
Before proving this theorem, provide the following lemma: Lemma D.3. It holds that
E. - Σ (1- S.W).)) + q6 V2B
b
(WW.).
1=1
16

---

Proof. We have
T
T
Σ -S(())))))
Σ
B. -
- S.(W)) + - (W.) - S((T1).
From Assumption 3.2, the first term bounded as
T Σ 3 (.W). - (w))) - -.. + +TI,
T
and the second term is bounded as
T Σ
(.W.)) - -.((U) S V2B
G.ll V2B,
of G.
6K
2 V2B
b
Σ t=1
(W))
V2B
SW,,
q
where we used Lemma 3.3 and 14 S K/q. Combining the above three, we obtain
Σ (L.)) - S.(U)) -
T
(1-a)s,(W)) - + V2B
bK
Σ
(W,,),
q t=1
t=1
which completes the proof.
Proof of Theorem D.2. The surrogate regret can be decomposed as
T RT = Σ 1=1
T [.. S,UU))
- -
(3)
1=1
We first upper bound the first term in (3). Let Z, = (,())) E, T. (+ for simplicity. Then, we have
Ze S 1, E, [Z]] = 0, and E, [z]] S E. (L. S (1-aa a)S, ) + q. Hence, from Bernstein's inequality in Lemma D.1, for any E (0, 1), least 8' we have
T Σ 2. S 1=1
T ((1- + 4) + log (1/8).
V2
2log(1/8')
(4)
3
t=1
We next consider the second term in (3). Define S.UU) (S.,)) for some & E (0, 1), which will be determined later, and let 12 = 1ly, (rl/Pt(Tr) S K/q for simplicity. Then, we have E Ex(vere - re] 0, lubr: - rel KS 9. and
[. r1 < (v(r)) K KSmax
KSmax S(WW)).
Ima
q
Hence, from Bernstein's inequality in Lemma D.I, for any 8" E (0, 1), with probability at least 1 8" we have
KSmax (S.(U) (WW)) Σ (ver re) r1)s S 1 3 llog(1/8") 1=1
V2KS Smax
(5)
q
3q
Below, we proceed by case analysis.
When Σl= SU) Σ (W.). We first consider the case of S.())
From Lemma D.3, we have
T
E. (L. qT
17

---

T
T
bK
T
UU)+ + Σ
((1 - al)-a)))(W.))))) (L + V2B
Σ (W,)
1=1
T
T
Σ 1/ (Si(U) - -WS)( (1 E) (Wi)
T + (1 a)
bK
(W,) + v2B,
9 Σ (W))
Kd
Upr + (1 a) (Wi)
20(1 - E)
where the last inequality follows from 61 Vi- C2T S of/ (4c2) for x 2 0, o 2 0, and C2 > 0. From the concentration result provided in (5), this is further bounded as
K S (S:(U) (W.)
B [T+((())) - qT S Σ (S,(U) (..(W)))
3 3log(1/00)
q
/2KSmmn
Kd
log 1og(1/8") + (1-a)
Σ
(W,) + 2q(1 E)*
3q
t=1
where we recall that = S2(U) (Wi). Rearranging the last inequality and using the inequality that Ei= (U) s S.W.), we obtain
T
T KS
V2KS log(1/8")
-0,) - S9T + 61og(1/8")
S,W,) +
q
3q
1=1
1=1
T
Kb
+ (1 a 5) S()) + 2q ()
Σ
In what follows, we let 8' = 8" 8/2 and (1+0)2 for a sufficiently small constant >> which satisfies a + & > 1. Then, plugging (4) and the last inequality in (3), with probability at least 1 - 5,
Ae
we obtain
T
V2
RT S
2l0g(2/0)
Σ 1m1
((1 u)S. 4) log (2/0) + TT
3
T KSmax SWW +
/2K Smax log(2/0)
+
6 Blog(2/0)
34
T
BdKb
+ (1 - a E) Σ
WWi) + 2q(1 -)
1=1
3K8max
log(2/8) 22 (ogg(2)) + V2 1og(2/8) + 7T
<
(1 (1-a)= 9
2(a + E 1)
22KS log(2/5) + 2q(1 E)
1326
+
3q
3K S max 1og(2/6)
Kb
+ KS Saxx log(2/0) +
+ + 229TTogg22
2(a + {
2(1 -
1
V2
2(a + { 1) (1 a) log(2/0)
log(2/8)
3
2(a + - 1) (1 (1- a) log(2/8) + V2
+ qp + / (28(2
3 log(2/6).
18

---

Using the definition of g VC/T with the last inequality, we obtain
- V22
R S CV (CT) 1/4 Vlog(2/5)+
2(a+ log(2/0)
When ((=)):(U))) > E (W,)). We next consider the case of Σ S,(U) > Et= S:(,) We have
T
T
R =
(L) (.,)( + Σ -00) -
1=1
Σ (11-a),( + + v2
2 2log (/8')
log(1/8")
Σ
(E (9)) S((W))
1=1
v2
T
2 2log(1160 1/8') Σ ((1 (11-a) (w-) + log(1/8") Σ
(W,) +
a) log(1/8))
2 (18')18))))))) +
2q log(L/0"))
log(1/8)
3
where the first inequality follows from (4) and Σ S,(U) Σt= SWW..). and the second inequality follows from Assumption 3.2, the last inequality follows from ei /x-///xoop c2 <2/(402) for 0, ci 2 0, and C2 0. Substituting q /C/T and 8' 8/2 in the last inequality, we obtain
R₂ (1 (1- a) log(2/8)
v2 v log(2/0) VCT.
+ CT 1/1
2a
This completes the proof.
D.3 Proof of Theorem 3.6
Here, we provide the formal version and the proof of Theorem 3.6. Theorem D.4 (Formal version of Theorem 3.6). The algorithu Section 3.4 achieves
bB² + 25/3 1/(C,T)
R
a
We recall that P: E, [ ]. We then estimate yt by yr - De ( Vy) and G. by G. (O.) yr D T under Assumption 3.5. This G, satisfies E, G. = G.. To prove Theorem 3.6,
we will upper bound E,
||@ [|: To do so, we begin by proving the following lemma:
Lemma D.5. Let A and B positive semi-definit matrices with Im(A) Im(B) and = B. Then, holds that A 3 B.
Proof. Since Im(A) Im [), there exists an orthogonal matrix R, diagonal matrix A, and an invertible matrix that has same dimensions as such that
- R
100
0
R
and == R
0
R T.
B'
Then, we have
A+ + = R R A A-1
(0 0 R and B = R (0
0
0 B
R
(6)
From A B, we have A 2 B', which implies A-1 3 B From this and (6), we have
A B as desired.
19

---

Using this lemma, we prove property of P. and an upper bound of Eg [tr (br(B.) In what follows, we use Xmain ( (A) to denote the minimum eigenvalue of a matrix A.
Lemma D.6. Suppose that tr (V) S w for Q = By ly J. where we recall that is the uniform distribution over Y. Then, we have
Eg ((r(D)))))
}]
w
Proof. By the linearity of expectation and the trace property, we have
Es E. ) - tr V E.
[000.] (V-))) - (VV--PPPPP
= Lr V P.-
where the first inequality follows from -1 S (T., Vy.) S and the last equality follows from p P.P. = P... The right-hand side is bounded as follows:
tr V--IPp p, (v-(()))
e LeTv-iP:t (V-1
e, Σ V
(1Q) (V-I)) e
1
(1Q)
tr (
q
where in the first inequality we used Lemma D.5 and in the last inequality we used the assumption that tr(V (VV-QQ((--)))) S w. This completes the proof.
Now, we are ready to upper bound I. [|
Lemma D.7. Under the same assumption as Lemma D.6, it holds that
Ex | - (6,) + 2C3w
Proof. We have
|| 1| = (0nn - 3 T 1 < (0. -y)),, 11 + 21( - -x)x, 11
< 2| 11 + 20 - 5. I
where we recall
C₂ di)m From this inequality, we obtain
E.
|| < 2||.. + + 2C - < 2bS, 2bS, (W,)
2y Ty E. + 34 l2)
2bS, (W,) (1lv.) 21 E, | 11)
2W
S 26S, (W.) + E. (#.99. ) $ 26S, +
where in the second inequality used | < 68, (W,), in the equality we used IEg [3t]] in the last inequality we used Lemma D.6.
-/e, and
Finally, we are ready prove Theorem D.4.
Proof of Theorem D.4. From Assumption 3.2, we have
T
T T9T
E(RT]
S
E
(S.(W,) - S((U))
a.
S.
(W.)
T
< E Σ G.., W. - -U)
- -E
(WW)
7
20

---

From Lemma D.7 and the unbiasedness of G. the first term in the last inequality is further bounded
G W. - -)
E
Σ G., W, U)
V2B, E
Σ G
2B
bE
(Wi)
2BC w/q.
where the first incquality follows from Lemma 3.3 and the last incquality follows from Lemma D.7 and the subadditivity of + v for 2 0. Therefore, we obtain
T
E S 2B,
bE
(WW)
ABC.vW// - aE Σ (WW)))
+ +
(7)
bB²
2BC V ///////--- qT,
a
where we used C1 / c2x & (4/(2)2 for x 2 0, c 0, and c2 > 0. Finally, substituting
1/3
q=
the last inequality gives
bB² E[R
+ 2 (|CC,T))
which is the desired bound.
D.4 Proof of Corollary 3.7
We derive the surrogate regret upper bounds provided by the algorithm established in Theorem D.4 for online multiclass classification, online multilabel classification, and ranking. Recall that we can achieve
6B3 + (BBC,T))) E E
a
where recall that w is defined as tr (V--)) < for Q E Eg [yy J. Note that when
span())) Rd, then the matrix Q invertible and Amin Q) 0, and hence
tr 1-V--Q((VVVV0
1- S Amin QQ)
Σ ((V Te
e
Amin
Consequently, surrogate regret bounds for specific problems are obtained as follows:
Multiclass classification with 0-1 loss We first consider multiclass classification with the 0-1 loss. From V = 11 I, we have || < d for d > 2. Recalling that is the uniform distribution over y
ca), we have Ey ((y T ) 1 Σ x² for any æ E Rdd. Hence, Amin Q) = min |a| - Eynu (v x = J. where the first equality follows from [9, Lemma 2). Since span()) = Rd holds in this case, from (9), we can set w = d/ (Qin(Q) = d2, Substituting
these into our surrogate regret upper bound in (8), obtain
6B² S a
ER
+ (3BCC,T)))
Online multilabel classification with correct labels and the Hamming loss We next consider online multilabel classification with the number of correct labels m and the Hamming loss. Since V 13 have || T. Let c {0, 13 be the set of all vectors where exactly m
L
21

---

components are 1, and the remaining components are all O. By drawing y E y according to the uniform distribution over Y, the probability that a given component of is is ((=1)/(3 d Hence, for any IRd with
||0|||
1, we have
Eyru ( d
x)
m
m
m10
m(d m) d2
|001
m(d - m) d2
2
d2
7
Thus, Amin (Q) minl|alaa- ||=||a-1 Eyruy (y ) N mld-m)
holds, where the equality is from Cesa- Bianchi and Lugosi [9. Lemma 2]. Since we have span(Y) RR, from (9), we can set w || | Amin (Q). Therefore, our surrogate regret upper bound in (8) is reduced to
d
(m(m-m)
6Ba +2 m(d m)
1/3
E[ <
(BC,T)3/3.
Ranking with the Hamming loss and the number of items m We finally consider online ranking with the Hamming loss and the number of items m. From Cesa-Bianchi and Lugosi [9, Proposition 4], the smallest positive eigenvalue is at least 1/m. Hence, since V
- I. we have
rank(
Q(VVIQ'(V' = m² (r(Q")) S m²
Σ m S m
where we used rank(Q (Q+) < d = m2 and this allows us to choose w = m². Substituting these values into surrogate regret upper bound in (8), obtain
b + (2m)5/3 (BC,T))
E|
S a
E
Details omitted from Section 4
This section provides the proofs of the theorems in Section 4.
E.1
Details of Optimistic Delayed Adaptive FTRL (ODAFTRL)
We provide a more detailed explanation of the Optimistic Delayed Adaptive FTRL (ODAFTRI) algorithm used for updating W, Section 4.1. Recall that ODAFTRL computes W, by the following update rule:
t- D Σ
+ x W 2
+1+1= = arg min WEW
G, W)
(10)
where A 2 is the regularization parameter. Note that we use the notation 01 = Et ag for simplicity in the following. The ODAFTRL algorithm, when using the parameter update called AdaHedgeD, satisfies the following lemma:
Lemma E.1 ([20, Theorem 12]). Fix O. Let f:W + R be convex function for each t 1,...,T. T. Suppose that we update xS in (10) by the following AdaHedgeD update:
D-D
Ae11
Σ
5,,
F F4,, W. W.). F.t) (G,, w. W
W. arg min (W),
Wew
Grlle 1 (Gi-De,, w)) and
W. arg min Wew
FW+ min
|G
Fwr(W)- Ael
W
2 F
+ (G1,, W)
2
22

---

Then, for any U E W. ODAFTRL achieves
T
B²
(
(WW) SU) S Σ
G. W. -U)
+11
2 2max D---i--1 + SE(T]
Σ 1=1
a + zabe) )
2a
1=1
1=1
t=1
where
at B min([]G:.D.clle:::ll |G
1 x²²
1
f _=²
b, luber([]G::DDIIIl) G.Ile), and huber(æ, v)
[1ab)-bb1}
min
2 2
In the following, we let a
n² 2
for simplicity. Then, since St is the convex function we have
T
T
T Σ t=1
Σ S.W.)) Σ S,UU)
Σ
Gr, W. U) 2 2 max Os- D:s-
oz +
B
xE[T]
E.2 Proof of Theorem 4.3
We present Theorem 4.3 in more detailed form and provide its proof. In what follows, let
Cy max max 11 (yEconv()) ()) y. ())
max
|1 y'lla
denote the maximum of the largest Euclidean norm of vectors in conv())) or the diameter of conv())).
Theorem E.2 (Formal version of Theorem 4.3). Les B²a
2. Then, ODAFTRL with the AdaHedgeD
update in online structured prediction with a fixed delay of D achieves
B| & 4BC,C,D+ 26B²
[bD + 1)² 3
(a "0B''CC;((++ 1/3
min
2
Proof. From the definition of by, it holds that
T
b
min
GG- Il,
1=1
b(D + 1)
T UT Σ S.
< min
S. S(W,),,,CC((41))
where we used - A. <n En A for any matrix A,, the Cauchy-Schwarr inequality,
|Gell < (0((0) 31 y1112 | 2l I C.Cy, and ||G.]| < bs, (.). Combining this inequality with
Lemma E.1 and the definition of de we have
- ((())))(((U))
< 4B max
Σ
GG:ll
(T(T)
b(D 1)
2B
Σ
G 1 min
Σ Σ S.W.), C.,.),CC,((()))
bT Σ S.W..)
2
< C,
6
S:W)))
1=1
-2min
b(D 1)²
T
SWW))
(,=C,,C(D+1)1+ (W:)
2
1=1
t=1
23

---

where we used ||; < (W,) and the subadditivity of x x vz for 2 0 in the last inequality. From this inequality and Assumption 4.1, we can the evaluate surrogate regret as
E ((--a) (W., S((U))
T b
< +
(W)
1=1
b(D + 1)2
T
T (1 Σ S:(W))
1/4
T
+ 22mmn
S((W),
(W())
2
1=1
t=1
2hB2
b(D 1)² 3
(B 112T) 1/3
< 4,C,C,
min
2
where in the last inequality we used / czt S cc/((cc) and a c2x - (3/4)(c1((422)) 1/3 which hold for any 0, cj 2 0, and C2 0.
E.3 High-probability regret bound
We present the result the high probability bound in a more detailed form and provide its proof.
Theorem E.3. Let B² and 8 E (0, Then, ODAFTRL with the AdaHedgeD update in online structured prediction with a fixed delay of D achieves
V2
1
Rr SABC,C,D+
log
3
5
(1 (V(1
a) log + 22B²
b(D + 1)2 (a (23b
a
a
with probability at least 1 6.
Proof. We decompose Rx into
T
RT = Σ -L
Σ [E, (.))) S.(U)).
(11)
Let Z, = (g)) - E, L1 (.)). Then, we have // 1 and E, [2]] < E, L. (g:) (1- a) (W;)
from Assumption 1. Hence, from Lemma D.I, with probability least 1 ò, the first term in (11) upper bounded as
T Σ Ze < 2(1 a) Σ S. S.W,) log 3 +
1
2
log
(12)
3
t=1
1=1
From Assumption 4.1 and Lemma 1.1, the second term in (11) is also upper bounded as
E (.))) ((())) (((U))
4BC,C,DD+
b S.W..)
1/4
b(D + 1)2
S((.)) Σ S((W)), (D (s(w,)
2 min
S (Wi),
(13)
24

---

Algorithm 3 Black-box Online Learning under Delayed feedback (BOLD)
Input: BASE instances BA ,AS BASED
I: for time step I 1,2..... : T do
2: Set < = t - k(D + 1). where rt E {O...., D) and E Zz0-
3: Set W f W, as the prediction for the current time step.
4: Receive the delayed feedback.
5: Update BASE, with the feedback.
6: W, + the next prediction of BASE,
where we used the subadditivity of x + V for x 2 0. Therefore, substituting (12) and (13) into
(11) gives
V2 RT S C,D log + (1(1--a) (0(1-a)lop a) log +VbbB²
Σ
S((W))
T
1/4
+ min
2b(D 1)2 Σ S((W)), bB bB*C 1) Σ (WW)
S((W,)
t=1
(1- (1- log + 2bB2
V2
S4CC,,,D +
log
a (C
+ min b(D + 1)2
3
1/3
a 2
where we used ei Civi- c S cf (4c2) and c₁ c2x* + I (3/2)((((4c2)) 1/3 for 0, c1 2 0. and C2 > 0 in the last inequality. This is the desired bound.
E.4 Algorithm based on (D + 1) copiee of online algorithms
Here, we provide the detail of Section 4.2. The pseudocode of BOLD for fixed delay D is Algorithm 3. By using Algorithm 3, we can achive the following bound:
Theorem E.4 (Formal version of Theorem 4.4). BOLD with adaptive OGD achieves the surrogate regret of
(B² 11
E E <
Proof. Let T3 be the set of rounds for which the remainder when dividing by D + 1 is equal to j ie, {t rt = 1}. By partitioning into these disjoint sets, we have
T
D+1
Σ (s((W)) - S,( <
Σ j=1
Σ FET;
- S,(U)) -W,))
Applying OGD Section 3.2 with the learning rate of 7) = B/ Ei= Gr block, we obtain
each independent
(S.(W.) - S-(U)) VBB
Σ
TEТ,
TET,
Thus, holds that
T
D+1
Σ (S,))) ((UU)) V2B
Σ
Σ
G
1=1
j=1
FET,
T 2B2 1) Σ
G
2bB + +1) Σ (WW))
25

---

where the second inequality follows from the follows from (1). Therefore, mombiiigg this and Assumption 4.1, we have
inequality and the last inequality
B S (S,) -((U)) S(())
T
bBa (B² 1)
$ 2D + Σ S((,)) Σ
St ( S
2a
where we used ei / oz (/((22 for x 2 01 0, and c2 0 in the last inequality,
E,5 Proof of Theorem 4.5
Here we provide the proof of Theorem 4.5.
Proof. Assume for simplicity that M (B2 log (looo)(2))) is positive integer. We partition the time indices = L,..., (D + 1)M into M blocks by grouping every consecutive D + 1 rounds. each block, set an identical input vector and true class. Specifically, we define the input vectors and the true classes as follows.
For each 1,.... . 1, sample true class i, [d] uniformly random. Set H, = C, for t t= (D 1)(s - +1........ (D+ 1)s for each s = "....,M. and o; = CM-1 for t > 1D+1)M Define the offline estimator U (M++)+1) such that its s-th column (s I...., ..)....M....... is log e and its (M 1)-h column is log(dT))e Note that |U| M(log 2dj² (log(dT)) holds.
B
We denote V3 D(D+))e-I)++ y = y(D+1)(s-1)4 and S = ((D+1)a--)+i Note that, within each block, the corresponding true class is not observed at the beginning of the + rounds. Thus, for each 1,...,, .M and i = I...., caleulation as that of Sakaue et al. [41, Theorem 13], also have SU s 1 {1 4)) Thus, for each 1,...,D) D + 1, we have
D + 1, we have IE[1 77 # yil 2 1 à' By the same
M
M 1
M
B (log d)2
Σ
E
E
0 + all Σ
S(U)))
2
d
4
Summing over i = I,..., D + 1 yields
(D+1)M
(D+1)M
S,UU') = 12 (BZ( 11 (1)
Σ
E + vill
Σ
=0( (Flog
(log d)2
The contribution of rounds > (D 1)M to the surrogate regret is non-negative In fact, by the definition of U" we have E S.(U") < I- 4) < 1 1. and we also have ΣiS(--IJM [ + yill 2 since i is selected uniformly at random.
Therefore, holds that
E B + v.ll Σ S.(U') = 22 (B(D++1)
(
(log d)²
1
which completes the proof.
F
Details omitted from Section 5
This section provides the omitted proofs of the theorems in Section 5.
26

---

F1 Common analysis
We provide the analysis that commonly used in the proofs of Theorems 5.1 and 5.2. Although we use G2 as notation for the estimator for convenience in this subsection, the same argument applies equally to G. We use ODAFTRL with the AdaHedgeD update Appendix E.1 as ALG. Here, we recall that E| (W,) S(U) & EE (G,, W, - UU] from the convexity of S, and the unbiasness of G.. From Lemma E.I, holds that
T Σ 1=1
Σ G W - U) 2
max ai a [ET
a + Bebe)
(14)
where
a = B min (1l G. -Dele: P [|G.ll}} and b, S min
G D l Dullellll
By the definition of oz, we have
t-1 Σ
max Ge- Dit-1
S BE
max [E[T]
(15)
[E(T]
s=t
and thus
E
Σ G. W. U}
2 2E
max O4 Dit-1 [E(T]
E
B
E
Σ
b
1-1 Σ
T
T
< 2B
2E
max LE[T
|G&.lP
+
G
l
+
E
Σ
b
(16)
where we used the subadditivity of V for O. The last term in the last inequality is further bounded as
T
T
b
G
E
+ E
Σ
G.llF
Σ
GG&.IF
s=t-D
G.
+E
Σ
E,
[[GHlee]]
Σ
|Ga.lle
(17)
s=t-
where the second inequality follows from the triangle inequality and the equality follows from the law of total expectation.
F22 Proof of Theorem 5.1
We provide the complete version of Theorem 5.1:
Theorem F.1 (Formal version of Theorem 5.1). The algorithm Section 5.1 achieves
(4. +1 =
(bbB
E|Rrl < 4BC,C,D+
Proof.
First, we will upper bound E
ΣT
b
From (17), we have
T
T
T
E
11
+ E
E+
Grll
Σ
G@.1Ip
Aml
s=t-D
E
| 11
+ C.CCEE
Σ E.
GG..IF)
< E
Σ
G 11
+ CC
(18)
27

---

where the second and third inequality follow from the inequality Eg
||::
|F
|Gelle s C.Cyg.
Hence, from Ex ||G:11T] s C.Cy, (16) and (18), it holds that
T
Go W. - U)
s 2B 2,
E
G
+
E
Σ G |
D
[=1
T
< 4BC,C,D +4B
E
G
+ +2BC,C,VDT
bK
T
$ 4,C + 4B,
R
(WW)
+ CBC,CyVDT,
(19)
9
where in the second inequality we used the subadditivity of x + Vo for 2 0 and in the last inequality we used
E+ |
IG K
bk G (WW))
(v:)
9
q
Therefore, combining all the above arguments yields
(S, - S((UT))
R <
E
aE
S. (W,)
E
GG Wi- U) -U)
aE
S((W))
+ 7TT
bK
T
T
< <4BC,C,D + 4B,
E
(W,)
+ 2BC,C,YDT - aF
Se (Wi)
7
9
< SABC,C,D + 4bB² bK
+ D,C,C,,DDI + QTI,
a q
where the first inequality follows from Assumption 3.2, the second inequality follows from the convexity of St and the unbiasedness of G. and the last inequality follows from c1 cıvz c2 S of (402)) for x 2 e 2 0, and C2 > O. Finally, from q = B K/T, we obtain
(bbB
E|R1] < 4BC,C,D+ (a +1 +1
v KT + 2BC,C,,DDI,
which is the desired bound.
F.3 Proof of Theorem 5.2
We provide the complete version of Theorem 5.2: Theorem F.2 (Formal version of Theorem 5.2). The algorithm in Section 5.2 achieves
E R = 4BC, VDT) +
8hB²
+ +0(
Proof. First, we will derive an upper bound of E Σt= bn). We first observe that
Eg | [F]]
= E,
[| (ān (0.) - ;. [I]]
< [..II + + 1lv: - Tellel S ||..Il 1l 1 ||
< |G.|| + +Clll + C.F,F V (r((.))))
s +||G.||++ + CCC, + Cr y F. [ur (g.9.
]
< |Galle + C,C, + VCWu/ $ 20,0, + CBWlo.
(20)
28

---

where the first inequality follows from C2 2 || the third inequality follows from C3 2 1 ll2 the fourth inequality follows from Jensen's 's inequality, and the fifth inequality follows from Lemma D.6. Thus, combining (17) with the last inequality, we have
2
T
2
b
S
G
2
E
Σ
Ex
Gellr
Σ
|
8=
CZw
T
E
Σ
+
22 +
G
[=1
s
C2w
< E
Σ
G
+ DT
2C + $1
(21)
Hence, from (16), (20), and (21), we have
T
E
Gr W. U}
1=1
[-1
T
T Σ
S 2B
2E
max (E(T)
Σ
G
+
E
1
+
bt
s=--D
T
2
2C,
E
G.
+
E
b
1=1
< <BBC,C,D 4BC,D 4B
G
+2B 22(C000C, + CC./
I <8BC,C,D + & ABC,DVW/0
T
bS,(W,) + Chu ) + 2B 2B C DT.
+BB
(22)
where the first inequality follows from (16), the second inequality follows from (20), the third inequality follows from (21) and the subadditivity of + v for x 2 0, and the last inequality follows from Lemma D.7. Therefore, combining all the above arguments yields
T
T
RT S
(S,(W)) - Si(U))
aEE
(.W))
+ +
T
T
<
GG W, - -U)
- aE
(Wi)
+ T
1=1
1=1
&SBC,C,D++R 4B
2bE Σ (Wi)
+ +C
+CV220T/g
+ABC.DVw/g
T
+2B 22 +2B(2C,C,, + Co/w/q VDT al
Σ
S.(W,)
+4T
< 4BC, + DT) + 8bB² + ABC,D 2BC, + 2222) WTT + qT,
a
where the first inequality follows from Assumption 3.2, the third inequality follows from (22) and the subadditivity of + V for x 2 0, and the last inequality follows from the definition of e and
C1 C C2 S c4/(4 for x 0. c 2 0, and 02 > Finally, substituting q = (wB2CLD 1/3
T
gives the desired bound.
29

---

Algorithm 4 Single-instance Online Learning In Delayed environments (SOLID)
Input: BASE, the first prediction W of BASE
I: for time step 1 ........7 T do
2: Set Wt f W as the prediction for the current time step.
3: Receive the feedbacks H; that arrive at the end of time step t.
4: for all feedback in H, do
5: Update BASE with feedback.
6:
W < the next prediction of BASE.
G Variable delay
This section provides the algorithms and analyses under the variable-delay setting, which a natural extension of the fixed-delay setting. As the notation for the variable-delay setting, let ti denote the delay time the feedback received at time I, and define т. max, 7;- Under this setting, by leveraging the Single-instance Online Learning In Delayed environments (SOLID) [28]. we achieve
surrogate regret bound of (VTTE T.) the full-information setting (Theorem G.2), and bounds
of O(VKT + + + T.) (Theorem G.3) and O VTITT + T.) (Theorem G.4) in the bandit setting.
G.1 Single-instance Online Learning In Delayed environments (SOLID)
We provide detail of SOLID algorithm used for updating W; under the variablc-delay setting. Consider any deterministic non-delayed online learning algorithm (call it BASE). SOLID is an algorithm that, regardless of the original arrival time of the feedback, provides the feedback to BASE in the order in which it is observed, and makes predictions based on the outputs of BASE (Algorithm 4). Below, let p(t) denote the time step of the tth feedback from SOLID to BASE for any t E [T],
as in [28]. When we use OGD as BASE, SOLID achieves the following bound:
Lemma G.1 ([28, Theorem 5)). Let BASE OGD with learning rate
V2R
Σ G als) |B + 2 Σ
(Go() + +cC(((2))))
7
where satisfies îr ΣT IU -W, 1 < 4R². Then, SOLID achieves
T
-(())
t=1
T G +
T
< 2222R
Σ
D 1=1
G Goile 1 (
8=1+1
G.2 Full-information
Here, we provide the algorithm for the variable-delay full-information setting. This subsection assumes Assumption 4.1, as in Section 4.
Algorithm
We use SOLID with OGD ALG for updating W..
Regret bound and analysis The above algorithm achieves the following bound:
Theorem G.2. SOLID with OGD update in online structured prediction with a delay of TV achieves
26R
E R <
+ +4C.C,B//T.T
O(VT.T++
a
30

---

Proof. Using SOLID with OGD (Lemma G.I), we have
(W.) - S((U))
T 22/2
1.. +2 +
G Geolll
Σ |G [Gpoe)lo1(s- F, -
S())) + + +C,, T
$ 2222
(23)
where we used ||G.ll s (S.. ||G||F S CaCy, E ( - T S = 7. E
E/ and the subadditivity of x + v for æ 2 0 in the last inequality. Therefore, from this inequality, holds that
E(RT| S Σ
(W, S((U)) Σ (W,)
t=1
T + +GGGH///GGGG//TTTCCCCCCCCCCC
T
< 2222
S(WW))
2bR
C. C,C,R. +T)).
where the first inequality follows from Assumption 4.1, the second inequality follows from (23), and the last inequality follows from civr C2 S ct/ (4c2) for x 2 0, 0, and 02 0. This is the desired bound.
This result is superior to the algorithm designed for the fixed-delay feedback that can handle variable-delay feedback. When D 2 is known and small, may also use the algorithm developed for fixed-delay feedback to achieve the O(D²) bound.
G.3 Bandit feedback
We provide algorithms for the variable-delay bandit setting. This subsection assumes Assumption 3.2, as in Section Then, by using the inverse-weighted gradient estimator and the pscudo-inverse matrix estimator as gradient estimators, we can achieve surrogate regret upper bounds of O( O(TTT++ + /TiTT + Tw) and O VTLT + 72/3 + T.), respectively. Below, we provide details of these results.
G.3.1 Algorithm based inverse-weighted gradient estimator with O(VKT + VI:T TT) regret
Here, we introduce algorithm with surrogate regret upper bound of O(VKT + VIT + T.).
Algorithm We use RDUE with y = R K/T for decoding (assuming 2 R2 the gradient estimator G, as in Section 3.3, and SOLID with OGD as ALG.
Regret bound and analysis The above algorithm achieves the following surrogate regret bound: Theorem G.3. The above algorithm achieves
2b (2t
E[Rr] s AATRATTT-C.CCCCTTT-GGGGGGEGEEEEE = +T.++T)).
This result is an extension of the bound under the fixed-delay setting. In particular, if r. = D for any we obtain E[Rr] O( O(v(K DYT).
31

---

Proof. First, we recall that | & C2Cy and E. & (Wi)/ from the proof of Theorem 5.1. Using SOLID with OGD (Lemma G.1) and the subadditivity of x + /z for æ 2 we have
E Σ
(W, - (
T
T
T
< 22VRRE
Σ G. + Σ
Σ
|| (e0 eeellll// 7, 51
s=1+1
C, 2 +
S
22/2R
Σ G.G.
4RE
Σ
Σ
G (l p()) 7s S
+
(24)
The second term is bounded as
T
E
- 7, St}
A am2++1
E
B Prane
|| pmas (1F) 11 pmi 1111 1
Ps st)
T E Pmntn
T ||| - St s SC Σ To
S C,C,EE
G (mmmm))
To
(25)
8m2++
where we assumed Pmax max(p(t), p())} and Pmiin = minss used the tower property in the first and second inequalities, and used Ezll GellF] S C2 in the second and last inequalities. Hence, it holds that
p(s)},
T Σ (G(W.)-ssUU) <2V2R
bk
T
E
(W,)
+4C H.C.C,R/TTTC.CCCR 2(T + +T),
(26)
where the inequality follows from EE [|| [| < 6KS,(W.)/ and (25). Therefore, combining all the above arguments yields
T
T
< E
S((
- -al
Σ 1=1
St (W:)
+ tI
11=1
bk $2V2R
((W)
C,
+ C,C,RRR2(12) +
aB
Σ S.W..)
+ qT
26R
2(72 +
09
where the first inequality follows from Assumption 3.2, the second inequality follows from (26), and the last inequality follows from c c2r c4/(4cz) for 2 0, c 2 0, and c2 0. Finally, choosing g K//T gives the desired bound.
G.3.2
Algorithm based pseudo-inverse matrix estimator with O regret
/T.T T2/3 T.,
Here, we provide an algorithm that achieves a surrogate regret upper bound of 1/7 22/3 7.). This subsection assumes Assumption 3.5 in addition to Assumption 3.2.
V Vir +
32

---

1/3
Algorithm We use RDUE with g
for decoding (assuming T wRF the
gradient estimator G as in Section 3,4, and SOLID with OGD as ALG.
Regret bound and analysis The algorithm described above achieves the following surrogate regret bound:
Theorem G.4. The above algorithm achieves
4 + &C CCC + VT. + 12/3)
RT <
- TI.T + 2 +
Proof. First, we recall that B,[| Gelle S Cy VC2w/g and E, |I S
2bKS 20
hold from (20) and Lemma D.7, respectively. Following the same steps as in the proof of Theorem G.3, we obtain
T
2 T
E
Σ
Σ
-- s s (2C,C, + VCW/
Σ
Tt-
(27)
8=8+1
Therefore, by using these inequalities and (24), we get
RTI S
Σ
(W.) - St(U))
aE Σ (WW)
+ oT
Czw
C3w
<
4RE
bKE
S((W,)
4R
2C
V q
/
9
1=1
C.C, Ry 2( + T.)
aF
Se (W.)
+QT
46IPK
Czw
Chu
AR
+ 4R
2C,C, +
T.T C,C,RR + TT,
where the first inequality follows from Assumption 3.2, the second inequality follows from
Lemma D.7, (24), and (27), the last inequality follows from c1vz C2t < (2/(4cg for x 2 0,
(WR² 1/3
C1 2 0, and C2 > Finally, by substituting
we can obtain the desired bound. O
H Numerical experiments
This section presents the results of numerical experiments for online multiclass classification and multilabel classification under bandit feedback on MNIST and synthetic data. All experiments run system with 16GB of RAM, Apple M3 CPU, and in Python 3.11.7 macOS Sonoma 14.6.1. The code is provided in the supplementary material.
H.1 Multiclass classification
Setup We describe the experimental setup. We compare four algorithms: Gaptron [44] with logistic loss, Gappletron [45] with logistic loss and hinge loss, and our algorithm in Section 5.1. Theoretically, these methods have their own advantages: ours enjoys surrogate regret bound of O D(VKT), which is better than the O(KVT) bounds of the others; however, Gappron/Gaaplettrn can work with broader class of surrogate losses. This section aims to compare those methods from the empirical perspective.
33

---

100000
100000
75000
75000
Our
Our Al Algrrihm
Algonihm
LOsS
50000
Cuppletion Lagstic
50000
Guppleton Legistic
Caption Hingo
Captron Hinge
25000
25000
Coptron Logistic
Coptrin Logislic
36
48
96
36
24
96
K
K
(a) vl' 2,r 0.0
(b) n2' 2,
100000
100000
75000
75000
Algonthum
Algorihan
Loss
50000
Cappletoon Logistic
50000
Crppletron
Logislic
Gagtron Hings
Gaptron Hinge
25000
25000
Cagtuon Logistie
Captzon
Logistic
36
48
96
36
24
96
K
(c) n' 4, 0.0
(d) 4, 0.1
Figure 1: Results of the synthetic experiments in multiclass classification with bandit feedback. In all figures, the horizontal axis represents the number of classes K, and the vertical axis represents the cumulative target loss.
Details of algorithms As the algorithm ALG for updating the linear estimator, we employ the OGD
E [G. and no projection is performed in OGD. Here, the addition of 10-8 the denominator is to prevent division by zero. Although B = diam (W) is unknown, we fixed B = 10 in all experiments, regardless of whether this value represents the actual diameter. All other parameters are set according to theoretical values. Under these parameter settings, we repeat experiments 20 times.
in Section 3.2. Following [45], we use the learning rate of 1): = B/ B//2(100-
H.1.1 Synthetic data
We also run experiments on synthetic data to facilitate comparisons across different values of K.
Data generation We describe the procedure for generating synthetic data. The synthetic data were generated by using the same procedure Van der Hoeven et al. [45]. The input vector consists of a binary vector with entries of 0 and 1, and is composed of two parts. The first part corresponds unique feature vector associated with the label, and the second part is randomly selected and unrelated to the label. Specifically, the data is generated as follows. We generate K E N unique feature vectors of length 10n' as follows. First, we randomly select an integer s uniformly from the range 5m"), then randomly choose s elements from zero vector of length 10n' and set them to 1. The input vector is obtained by concatenating the feature vector of a randomly chosen class with vector of length 30n'. in which exactly 5n elements are randomly set to 1. Additionally, with probability r, the corresponding class label is replaced with a randomly chosen label to introduce noise. The resulting input vector thus has length n 40n'. These input vectors are generated for T rounds. Based on this procedure, we create datasets for n' E {2, 4) and r E (0.0,0.13
The results on the synthetic data are shown in Figure 1. Our algorithm achieves comparable or better performance than the existing algorithms for datasets with K < 24. contrast, when K = 48 or 96, the cumulative losses of our algorithm are larger than those of Gaptron with the hinge loss and Gappletron with the logistic loss. Note that these observations do not contradict the theoretical results: for large K, the upper bound on the cumulative 01 loss of Gappletron can
Results
34

---

0.8
0.6
Error Rate
0.4
0.2
0.0
Gappllett Gaptron
Gaptron
Prediction Logistic
Hinge
Logistic
Figure 2: A box plot of error rates of the MNIST experiment for multiclass classification with bandit feedback.
5000
4000
3000
Loss
2000
inverso-weighted estimator
1000
pscudo-inverse
matrix estimator
0
10
12
16
20
24
d
Figure 3: Results of the synsetic experiments in multilabel classification with bandit feedback. The horizontal axis shows the number of labels, and the vertical axis indicates the cumulative target loss.
be tighter than ours because of differences in the surrogate loss functions (see Appendix C.3 for details). Nevertheless, our structured prediction method does not fully demonstrate its potential in this setting, the setup favors algorithms specialized for multiclass classification. It is also worth noting that by using the same decoding function as theirs, our approach can achieve the same order of the cumulative losses in online multiclass classification with bandit feedback.
H.1.2 Real-world data
We also evaluate the algorithms on the MNIST dataset [31], widely used benchmark of handwritten digit images.
The box plot in Figure summarizes the misclassification rates. It shows that our method achieves the lowest mascffssiiiintoonn rate, even though it is not specifically designed for multiclass classification, outperforming the existing algorithms on this real dataset with K 10.
Result
H.2 Multilabel classification
In the results presented in Section 3, the algorithm based on the srcudo-inverss matrix estimator achieves a tighter upper bound in dependence on K compared the one based on the inverse- weighted gradient estimator. To examine whether this theoretical result can also be observed empirically, we conduct experiments on multilabel classification with a fixed number of correct labels.
35

---

Setup We compare two algorithms: the algorithm based on the hnverse-weighee gradient estimator Section 3.3 and the one based the pseudo-inverse matrix estimator in Section 3.4.
Data generation We generate synthetic data using the multilabel classification data-generatin generatier function in scikit-learn [38]. Specifically, we employ the make multilabel_claseee cation method in scikit-learn to generate 7 multilabel samples with feature dimension label dimension d, and an average of m correct labels per sample. We then extract only those samples that have exactly correct labels and repeat this process until obtain 7 10 such samples. Based this procedure, we create datasets with 50, E (10, 12, 16, 20, 24). m 5, and = 10
Details of algorithms As the algorithm ALG for updating the linear estimator, we employ OGD
described in Section 3.2 with learning rate 7 B/ 2(10~ 8 E |Grll and orthogonal
projection. The small constant 10 in the denominator prevents division by zero. We fixed B = 50 for all experiments, and the other parameters were set according their theoretical values. Under these settings, each experiment was repeated 10 times.
The results are shown in Figure When is small, the algorithm based on the inverse- weighted gradient estimator incurs a smaller loss, whereas when d is large, the algorithm based on the pseudo-inverse matrix estimator performs better. The superiority of the trrerse-weighted gradient estimator for small d aligns with the theoretical result that it has a more favorable dependence on T. Similarly, the better performance of the gseudo-invers matrix estimator for large d agrees with the theoretical result that it does not depend explicitly on K. These experimental results thus provide empirical support for our theoretical findings.
Results
36

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and introduction, we claim that we study online structured prediction, present algorithms for bandit and/or delayed feedback, and analyze their surrogate regret bounds. Those are the contributions of this work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in Section 6.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
37

---

Answer: [Yes]
Justification: We present the assumptions in Section 2 and in the beginning of each relevant section. Theoretical results are followed by proofs, though some of them are deferred to the appendix due to space limitation.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide details of the experiments in Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
38

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide the code and data used in the experiments as supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines htttss//nips..c/pbbiii guides/CodeSubmissioooolllll
for more details.
While we encourage the release code and data, we understand that this might not be possible, so No is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (htips: http://gguiiieeeeeeueeeiiiiieeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We provide the training/test details in Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: The focus of this study is theory, and the experiments are provided for supplementary purposes.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
39

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide it in Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The focus of this study is on theory, and the experiments are limited to simple synthetic data and the MNIST datasets. Thus, do not violate the Neurips Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The focus of this study is on theory and does not have societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
40

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our experiments are for validation purpose, and do not involve any such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assetts are released, the license, copyright information, and terms of use package should be provided. For popular datasets, paperswithcode. wtterrswwihcodee.om/tteeee has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
41

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The focus of this study on theory and does not introduce new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The focus of this study is on theory and does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The focus of this study is theory and does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
42

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy https://beciis.cccoooooccccc///l for what should or should not be described.
43


Reviews:
[{"review_id": "pGztvtL8R2", "reviewer": "Reviewer_CFW5", "summary": "This paper studies the Online Structured Prediction problem, specifically in two problem settings: (i) bandit feedback and (ii) delayed feedback. For the bandit setting, the paper presents an algorithm with a surrogate regret bound of $O(\\sqrt{KT})$. For the delayed feedback setting, the regret is $O(\\sqrt{(K + D)T}$.", "questions": "1. Could you explain the multiclass classification model in lines 168-173? Why is $L(y; e_i)= \\indic[y \\neq y]$? The indicator function evaluates to 0 always in the presented form\n\n2. The paper motivates the structured learning problem through several examples, including multiclass classification, multilabel prediction, and ranking. However, the practical significance of the proposed model remains unclear. It is not evident how this approach offers tangible benefits over standard methods in real-world scenarios. For instance, in the case of multiclass prediction, given the setup described, wouldn’t the algorithm risk learning a model that simply overfits to the training data?\n\n3. The paper mentions the bandit setting (with incomplete information) as a key extension to the past works. However, [38] and others have studied the bandit setting. Could you explain and position the contribution w.r.t the existing literature?\n\n4. Is the key contribution the improvement on the sublinear dependence on K? If so, given that the models considered in existing works are more general, could you explain how essentially the algorithm and proof techniques achieve the \\sqrt{K} improvement beyond the simplified problem setting compared to other works?\n\n5. The regret bound in Theorem 4.3 is different from the bound mentioned in the abstract and introduction of the papers? Can you explain?\n\n6. Could you explain Assumption 3.2? What is the meaning of L_t(\\hat{y}_t)?\n\n7. Can you provide experimental results to support the results and improvement over existing approaches?\n\n8. The paper claims the bound I Theorem 4.3 is independent of $T$? However, there is a dependence on $T$.\n\n9.  Can you explain the technical challenges and the novelty in the proof approach for the delayed feedback extension?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well written and easy to read.\n2. The paper addresses an interesting problem setting (parts of it are unclear though).\n\nWeaknesses:\n\n1. There are multiple errors through the paper; the paper warrants a careful revision.\n\n2. The abstract mentions that algorithms are numerically tested; however, there are no numerical results provided in the paper.\n\n3. The delayed feedback extension seems to be straightforward. They key contributions are not fully cleara in the current presentation.", "was_revised": true, "final_justification": "I am raising the score since the author rebuttal addressed all point sin the review. The surrogate vs. general loss discussion seems to be critical for this work after reviewing the discussion with Rev  4VTE.", "rebuttal": "Thank you very much for taking the time to provide such a thoughtful and detailed review. Below, we present our responses to your comments.\n\n\n## **Q1. Multiclass classification model**\n> 1. Could you explain the multiclass classification model in lines 168-173? Why is $L(y;e_i)=\\indic[y\\neq y]$? The indicator function evaluates to $0$ always in the presented form.\n\nWe apologize for the confusion caused by the typographical error. The correct definition is $L(\\boldsymbol{y};\\mathbf{e}\\_i)=\\mathbb{1}[\\boldsymbol{y}\\neq \\mathbf{e}\\_i]$. We will correct this in the revised version.\n\n## **Q2. Practical significance**\n> 2. The paper motivates the structured learning problem through several examples, including multiclass classification, multilabel prediction, and ranking. However, the practical significance of the proposed model remains unclear. \n\nIn practice,  structured prediction arises across various domains, from natural language processing to bioinformatics (BakIr et al., 2007, [2]), as discussed in Section 1. In particular, our online setting with efficient linear estimators is well suited for applications such as ad click prediction (McMahan et al., 2013, “Ad Click Prediction: A View from the Trenches”) and ranking in recommendation systems (Rendle et al., 2009, “BPR: Bayesian Personalized Ranking from Implicit Feedback”), where both real-time performance and efficiency are critical.\n\n> It is not evident how this approach offers tangible benefits over standard methods in real-world scenarios. For instance, in the case of multiclass prediction, given the setup described, wouldn’t the algorithm risk learning a model that simply overfits to the training data?\n\nThank you for the question. We are not entirely sure what is meant by \"standard method\" in this context, so we would appreciate clarification if possible. If the question refers to batch learning, then the problem setting itself is fundamentally different, making direct comparison difficult.\n\nOur work considers the online learning setting, in which issues such as overfitting—commonly discussed in statistical learning—do not arise. Unlike batch learning, where a predictor is trained using a given training dataset and evaluated on a test dataset, online learning assumes that data arrives sequentially and the model (in our case, matrix $\\boldsymbol{W}\\_t$) is updated in an online manner. Therefore, there is no distinction between training and test data in online learning, and thus the overfitting risk present in batch learning does not exist in our setting.\n\n## **Q3. Relation to existing literature**\n> 3. The paper mentions the bandit setting (with incomplete information) as a key extension to the past works. However, [38] and others have studied the bandit setting. Could you explain and position the contribution w.r.t the existing literature?\n\nOur work addresses a more general problem class than those in prior studies. Specifically, while Van der Hoeven (2020, [38]) and Van der Hoeven et al. (2021, [39]) focused on online **multiclass classification** under bandit feedback, our work addresses online **structured prediction**, which includes multiclass classification as a special case. At the same time, our work can be seen as an extension of the existing study on online structured prediction with full-information feedback (Sakaue et al., 2024, [35]) to bandit and delayed feedback.\n\n## **Q4. Improvement of the dependence on $K$**\n> 4. Is the key contribution the improvement on the sublinear dependence on $K$? \n\nYes, one of our main contributions is establishing the $O(\\sqrt{KT})$ regret bound, improving upon the $O(K\\sqrt{T})$ bound of Van der Hoeven (2020, [38]) and Van der Hoeven et al. (2021, [39]). We would like to remark that another, more important contribution is the regret upper bound that is explicitly independent of $K$, achieved through the use of the pseudo-inverse matrix estimator.\n\n> If so, given that the models considered in existing works are more general, \n\nWe would like to clarify that the statement “the models considered in existing works are more general” is not accurate. As explained in our response to the third question, we address structured prediction, which is a more general framework than multiclass classification considered in Van der Hoeven (2020, [38]) and Van der Hoeven et al. (2021, [39]).\nOne caveat is that these previous studies cover a broader class of surrogate losses, including the (smooth) hinge loss. That said, our work—based on the Fenchel–Young loss framework, following Sakaue et al. (2024, [35])—subsumes the standard logistic loss as a special case. To be precise, while we focus on the logistic loss with base $2$, their framework also accommodates the base-$K$ logistic loss. We believe that we have adequately addressed this subtle difference in the main text. Indeed, Reviewer 4Bpe noted, “I particularly appreciated the authors for their clear (and honest) comparison with related work (e.g., discussion on pages 261–269).”\n\n> could you explain how essentially the algorithm and proof techniques achieve the $\\sqrt{K}$ improvement beyond the simplified problem setting compared to other works?\n\nThe $\\sqrt{K}$ improvement leverages the following techniques:\n- Extending the randomized decoding algorithm, originally designed for full-information feedback, to a form applicable to the bandit feedback setting (RDUE, Algorithm 2).\n- Using RDUE, we show that in the bandit feedback setting, the constant $a$ in Assumption 3.2, which appears as a $1/a$ factor in the regret bound, can be made smaller compared to Van der Hoeven (2020, [38]), based on Lemma 3.1.\n- Exploiting the negative term by using the inequality $||\\boldsymbol{G}\\_t||\\_\\mathrm{F}^2 \\le bS\\_t(\\boldsymbol{W}\\_t)$ in the proof of Theorem 3.5.\n- We carefully set the mixing probability $q$ of uniform exploration (Line 276).\n\n## **Q5. Regret bound in Theorem 4.3**\n> 5. The regret bound in Theorem 4.3 is different from the bound mentioned in the abstract and introduction of the papers? Can you explain?\n\nThere might be a misunderstanding regarding the upper bound stated in the abstract. The upper bound in Theorem 4.3 pertains to the **delayed** full-information feedback setting, whereas the bound in the abstract refers to the **non-delayed** bandit feedback setting. There is no inconsistency between the main text and the abstract. In the revised version, we will modify Line 8 of the abstract to read \"for non-delayed bandit feedback\" instead of \"for bandit feedback\", to avoid confusion.\n## **Q6. Assumption 3.2**\n\n> 6. Could you explain Assumption 3.2?\n\nThis assumption ensures that a decrease in the surrogate loss leads to a proportional decrease in the target loss. It plays a crucial role in establishing an upper bound on the target loss via the surrogate loss. Note that we refer to it as an “Assumption” merely for ease of reference; it is in fact directly guaranteed by Lemma 3.1.\n\nImportantly, one must ensure that the parameter $a$ lies in the interval $(0, 1)$. As discussed in Lines 240–242, this condition is satisfied in our structured prediction setting due to Sakaue et al. (2024, [35]) with $a = 1 - \\frac{4\\gamma}{\\lambda \\nu}$. In the case of multiclass classification, Van der Hoeven et al. (2021, [39], Lemma 1) also provide a decoding method that guarantees this condition, with $a = 1/K$.\n\n> What is the meaning of $L\\_t(\\hat{y}\\_t)$?\n\n$L\\_t(\\boldsymbol{y})=L(\\boldsymbol{y};\\boldsymbol{y}\\_t)$ is a simplified notation for the loss function at time $t$. We defined it in Line 164 and in the notation table (Appendix A). In the revised version, we will add a reminder when it reappears in a distant section, in order to improve readability.\n\n## **Q7. Experiments**\n> The abstract mentions that algorithms are numerically tested; however, there are no numerical results provided in the paper.\n\n> 7. Can you provide experimental results to support the results and improvement over existing approaches?\n\nAs referenced in Lines 70–72 and Lines 84–86, we have included experiments in Appendix H. Due to space constraints, we were unable to include the experimental results in the main text. Given the extra space in the camera-ready version, we plan to include (part of) the experiments.\n\n## **Q8. Independence of $T$ in Theorem 4.3**\n\n> 8. The paper claims the bound I Theorem 4.3 is independent of $T$? However, there is a dependence on $T$.\n\nNote that the upper bound involves $\\min$. Since $\\min\\\\{D^2, D^{2/3}T^{1/3}\\\\}\\le D^2$ holds, the upper bound in Theorem 4.3 is indeed independent of $T$.\n\n## **Q9. Technical novelty in delayed feedback**\n> 9. Can you explain the technical challenges and the novelty in the proof approach for the delayed feedback extension?\n\nWe believe that exploring delayed feedback in online structured prediction is a novel direction in its own right, even though it is not the primary focus of our paper (this topic occupies only one page in our 9-page manuscript). To our knowledge, delayed feedback in this setting has received very limited attention in the literature, despite its practical importance (see also the discussion in Lines 44–48), which makes it challenging due to the scarcity of directly applicable tools. To address this challenge, we have uncovered the benefit of bridging two previously separate lines of research: online convex optimization with delayed feedback and online structured prediction. Specifically, by leveraging AdaGrad-type regret bounds under delay, we show that a finite regret bound can be achieved in the full-information setting, and that in the bandit feedback setting, our approach yields tighter bounds than the $D$-copy strategy (see also our rebuttal to Reviewer jZKi)."}, {"review_id": "vmr6rwGy3n", "reviewer": "Reviewer_vmLL", "summary": "This paper studies the problem of online structured prediction under bandit and delayed feedback by proposing algorithms based on surrogate regrets. Leveraging properties of structured surrogate losses and randomized decoding, the paper proposes two algorithms,  one using an inverse-weighted gradient estimator achieving a regret bound of $O(KT)$,  and another based on a pseudo-inverse matrix estimator achieving regret independent of label space size K, specifically $O(T^{2/3})$. They further extend their analysis to the delayed full-information setting, proposing a delayed FTRL algorithm that attains a regret of $O(\\min⁡{D^2,D^{2/3}T^{1/3}})$.", "questions": "1. In section 3.4, the algorithm use RUDE decoding with $T >> B^2K$ and claimed that this is only for simplicity. Could you elaborate on why this makes things easier and how this can be lifted?\n\n2. In section 3.4, the paper defines bandit feedback as observing the scalar loss $L_t(y^t)$, but then states the algorithm only uses the indicator $\\mathbb{I}[y^t=yt]$, then does the algorithm still holds for general bandit feedback?\n\n3. As the algorithms depend on assumptions about known invertibility and boundedness of feature spaces, can you address the computational tractability of required oracles (e.g., decoding under complex structure)?\n\n3. In practice, I am assuming $D$ can be non uniform across steps and unknown to the algorithm beforehand. But here the algorithm needs to know $D$ in advance. Can this assumption be removed?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "One strength of the paper is that it unifies structure prediction with Fenchel-Young loss framework and the regret bounds obtained under the framework are comparable to existing ones. From my understanding, the technical analysis and the algorithm designs are new and rigorous. \n\nMy main concerns are with the computation complexity of the algorithms. Although the framework generalize upon existing works (from multi class prediction to ranking), the algorithm has some assumptions on known invertibility and decoding oracle). I am not sure of the computation feasibility and complexity of the algorithms. I also have some minor presentation questions (see the questions part for more detailed questions).", "was_revised": true, "final_justification": "This work unifies structure prediction with Fenchel-Young loss framework and the regret bounds obtained under the framework are comparable to existing ones. From my understanding, the technical analysis and the algorithm designs are new and rigorous, and deserves acceptance.", "rebuttal": "Thank you very much for taking the time to provide helpful reviews. Below are our responses to your comments.\n\n## **Weakness & Q3. Computational tractability**\n> My main concerns are with the computation complexity of the algorithms. Although the framework generalize upon existing works (from multi class prediction to ranking), the algorithm has some assumptions on known invertibility and decoding oracle). I am not sure of the computation feasibility and complexity of the algorithms.\n\n> 3. As the algorithms depend on assumptions about known invertibility and boundedness of feature spaces, can you address the computational tractability of required oracles (e.g., decoding under complex structure)?\n\nWe thank the reviewer for clearly stating the concern regarding the computational aspect. Below, we explain the invertibility of matrices and the computational complexity separately.\n\n**Invertibility.**\n- The matrix $\\boldsymbol{V}$, which is assumed to be invertible in Assumption 3.6, is indeed invertible in the multiclass, multilabel classification, and ranking cases. The specific forms of $\\boldsymbol{V}$ are given in Section 2.4.\n- Regarding the matrix $\\boldsymbol{Q}$, it is invertible in the multiclass and multilabel classification cases; we confirm that its minimum eigenvalue is positive in Appendix D.4. Even if the $\\boldsymbol{Q}$ is not invertible (i.e., ii-a in Assumption 3.6 fails to hold), the same result can be established under the alternative condition (ii-b), which is indeed true in the case of ranking.\n\n**Complexity.**\n\nLet us clarify the complexity of decoding and the computation of the pseudo-inverse of $\\boldsymbol{P}_t$.\n\n- When decoding with RDUE (Algorithm 2), the dominant cost lies in computing $\\hat{\\boldsymbol{y}}\\_\\Omega(\\boldsymbol{\\theta})$, which is a solution to convex optimization over $\\mathrm{conv}(\\mathcal{Y})$ as described in Proposition 2.3. This is thoroughly addressed in Sakaue et al. (2024, [35] Section 3.1). In short, $\\hat{\\boldsymbol{y}}\\_\\Omega(\\boldsymbol{\\theta})$ can be computed via a Frank–Wolfe-type algorithm (e.g., Garber and Wolf, 2021, \"Frank–Wolfe with a nearest extreme point oracle\"), which typically requires $\\tilde{O}(d^2)$ linear optimization steps over $\\mathrm{conv}(\\mathcal{Y})$; let $\\tau\\_{\\mathrm{LO}}$ denote the time for each step.\n\n- We now explain the computation of the pseudo-inverse of $\\boldsymbol{P}\\_t = \\mathbb{E}\\_{\\boldsymbol{y} \\sim p\\_t}[\\boldsymbol{y} \\boldsymbol{y}^\\top]$. This is written as the sum of $\\mathbb{E}\\_{\\boldsymbol{y} \\sim p}[\\boldsymbol{y} \\boldsymbol{y}^\\top]$ and $\\mathbb{E}\\_{\\boldsymbol{y} \\sim \\mu}[\\boldsymbol{y} \\boldsymbol{y}^\\top]$, where $p$ is a distribution over $\\mathcal{Y}$ induced by RDUE and $\\mu$ is the uniform distribution over $\\mathcal{Y}$. The latter can be calculated analytically in the multiclass and multilabel classification and ranking cases. For the former, when $\\hat{\\boldsymbol{y}}\\_\\Omega(\\boldsymbol{\\theta})$ is obtained via the Frank–Wolfe algorithm, $p$ is obtained from the convex combination coefficients, whose support size is at most $O(d)$ as implied by Carathéodory’s theorem (cf. Wirth et al. 2024, \"The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control\"). Therefore, we can compute $\\boldsymbol{P}\\_t$ in $O(d^3)$ time, and the pseudo-inversion takes the same order of complexity.\n\nTo conclude, the total per-round complexity is typically $O(d^2 \\tau_{\\mathrm{LO}} + d^3)$, which is feasible and arguably efficient given that $\\mathcal{Y}$ may consist of up to $2^d$ labels. We will elaborate further on this point in the revised manuscript.\n\n## **Q1. Regarding $T\\ge B^2K$**\n> 1. In Section 3.4, the algorithm use RUDE decoding with $T>>B^2K$ and claimed that this is only for simplicity. Could you elaborate on why this makes things easier and how this can be lifted?\n\nSince the comment concerns the assumption $T \\ge B^2K$, we suppose it pertains to Section 3.3 rather than Section 3.4, and we respond accordingly.\n\nThe assumption $T \\ge B^2K$ is made solely to simplify the presentation. It allows us to consider only the typical scenario where $T$ is sufficiently large to ensure $q \\le 1$, which leads to a simpler expression of the regret bound in the main text.\nThis assumption can be entirely removed by setting $q = \\min\\\\{B\\sqrt{K/T}, 1/2\\\\}$ and adding an additive term of $O(K)$ to the regret upper bound in Theorem 3.5. Please let us know if this is not the kind of response the reviewer was expecting.\n\n## **Q2. Bandit feedback vs. indicator feedback**\n> 2. In Section 3.4, the paper defines bandit feedback as observing the scalar loss $L\\_t(y\\_t)$, but then states the algorithm only uses the indicator $\\mathbb{I}[\\hat{y_t}=y_t]$, then does the algorithm still holds for general bandit feedback?\n\nYes, in Section 3.3, we only use the information of $\\mathbb{1}[\\hat{\\boldsymbol{y}\\_t}=\\boldsymbol{y}\\_t]$, and thus the same result can be obtained under a more general bandit feedback setting where only the 0-1 loss value is observed (see Remark 3.4). Specifically, since $L\\_t(\\hat{\\boldsymbol{y}\\_t}) = L(\\hat{\\boldsymbol{y}\\_t}; \\boldsymbol{y}\\_t)$ is non-negative and takes zero if and only if $\\hat{\\boldsymbol{y}\\_t} = \\boldsymbol{y}\\_t$ as in Assumption 2.1, $\\mathbb{I}[L\\_t(\\hat{\\boldsymbol{y}\\_t}) > 0]$ is identical to the 0-1 feedback. On the other hand, in Section 3.4, observing the loss $L\\_t(\\hat{\\boldsymbol{y}\\_t})$ is crucial. This is because we use the actual loss values to compute a pseudo-inverse matrix estimator, which allows us to improve the dependency on $K$.\n\n## **Q4. Regarding non-uniform delay**\n> 4. In practice, I am assuming $D$ can be non uniform across steps and unknown to the algorithm beforehand. But here the algorithm needs to know in advance. Can this assumption be removed?\n\nRegarding the setting where delays can be non-uniform (which we refer to as variable delays), we discuss it in Appendix G, as mentioned in line 379. Due to space limitations, we could not include this discussion in the main text.\n\nMoreover, the assumption that the delay $D$ is known in advance is not necessary. Since the ODAFTRL algorithm determines the decision point using all observed feedback, the value of $D$ becomes known from the time the first feedback is observed. We acknowledge that the current manuscript may have given the impression that $D$ must be known beforehand, and we will revise this part to clarify the explanation accordingly."}, {"review_id": "iVyZ1eTkJj", "reviewer": "Reviewer_jZKi", "summary": "This paper considers online structured prediction with surrogate losses. This is a sequential setting where in each round t = 1,…, T the learner observes a context, issues a prediction from a discrete set and subsequently suffers a non-convex loss. The paper mostly considers the bandit setting, where the learner only sees the loss for the chosen prediction. In the delayed version of this problem the learner only observes the loss after some rounds. The goal is to control the surrogate regret, which is the difference between cumulative the losses suffered by the learner, and the minimized cumulative surrogate loss. \n\nThe authors exploit a recently developed technique that sharpens the relation between the discrete loss of the learner and the surrogate loss of the learner if the surrogate loss is a fenchel young loss. In the bandit setting this leads to a surrogate regret bound of order $\\sqrt{KT}$, where K is the cardinality of the prediction set. In the delayed feedback setting with constant delay D with full information feedback, the authors obtain a $D^2$ surrogate regret bound. In the delayed feedback setting with constant delay D with bandit feedback, the authors obtain a $\\sqrt{T(K + D)}$ surrogate regret bound.", "questions": "I am wondering of my construction for the constant delay actually works. If so, would this be optimal?\n\nI am wondering if the bounds for the delayed bandit setting are tight", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "For the remainder of this review I will focus on the multiclass classication setting with the logistic loss, a special case of the setting considered here. For the non-delayed bandit feedback setting, the results presented in this paper present a stark improvement over prior work. In prior work, the best known bound is Ksqrt{T}, which is a factor sqrt{K} worse. \n\nThe results for the delayed full information are a bit weak I suspect. If we have constant delay, we could just run D copies of the non-delayed algorithm, where each copy makes a prediction every D time steps. Since the non-delayed algorithm has surrogate regret O(1), this would lead to a surrogate regret bound of order D. I think that a similar surrogate regret bound should be obtainable for delay that is not constant. \n\nIt is not clear if the results for the delayed bandit setting are tight. Nevertheless, both results are new and show that the randomized decoding technique from earlier work can be extended to obtain interesting results beyond the setting the technique was originally developed for.", "was_revised": true, "final_justification": "The authors addressed my concern about simple improvements being possible in the delayed bandit feedback setting. I maintain that the results in the delayed full information setting could be improved, but I also believe that the contributions in this paper are interesting for the general community.", "rebuttal": "We sincerely appreciate the time and effort you devoted to providing a constructive review. Below, we present our responses to your comments.\n\n## **Q1. Comparison between the $D$ copy approach and ours**\n\n> The results for the delayed full information are a bit weak I suspect. If we have constant delay, we could just run $D$ copies of the non-delayed algorithm, where each copy makes a prediction every $D$ time steps. Since the non-delayed algorithm has surrogate regret $O(1)$, this would lead to a surrogate regret bound of order $D$.\n\n> I am wondering of my construction for the constant delay actually works. If so, would this be optimal?\n\nThank you very much for your insightful comment.\nWe have examined how the approach of preparing $D$ copies of the non-delayed algorithm (as investigated by Weinberger and Ordentlich, 2002 [41]; Joulani et al., 2013 [23]) would perform in our setting. In what follows, we call this approach the \"$D$-copy approach\" for simplicity.\n\nAs you pointed out, in the full-information feedback setting, it is indeed possible to improve the regret bound to $O(D)$. In contrast, in the bandit feedback setting, we found that our approach has advantages over the $D$-copy approach combined with the inverse-weighted gradient estimator and the pseudo-inverse matrix estimator. Specifically, \n\n- In the full-information setting, the $D$-copy approach combined with the approach of Sakaue et al. (2024, [35]) achieves a regret bound of $O(D)$, which is better than our $O(D^2)$ bound.\n- In the bandit setting with the inverse-weighted gradient estimator, the $D$-copy approach applied with our algorithm for Theorem 3.5 yields a bound of $O(\\sqrt{K D T})$, which is worse than our $O(\\sqrt{(K + D) T})$ bound. Interestingly, such degradation in the regret bound when using $D$ copies naively is also known in the literature of multi-armed bandits: For the classical multi-armed bandit problem, using $D$ copies yields a regret bound of $O(\\sqrt{ NDT})$, while the minimax regret for the problem is $\\Theta(\\sqrt{(N + D) T})$ (Corollary 11 in Cesa-Bianchi et al. 2016 [9]). Thus, our bound of $O(\\sqrt{(K + D) T})$ can be seen as an improvement over the naive $O(\\sqrt{K D T})$ bound.\n- In the bandit setting with the pseudo-inverse matrix estimator, the $D$-copy approach with our algorithm for Theorem 3.7 achieves a bound of $O(D^{1/3} T^{2/3})$, which is the same as our bound in Theorem 5.2. However, as the ODAFTRL paper points out, it is undesirable because each algorithm only leverages $\\frac{T}{D+1}$ losses (see page 4 in Flaspohler et al. 2021, [17]), limiting its empirical performance.\n\nIn summary, the $D$-copy approach has an advantage in terms of worst-case regret in the full-information setting. However, in the bandit setting, our approach demonstrates superiority against the $D$-copy approach combined with the algorithms for the non-delayed bandit setting, regardless of which estimator is used.\n\nWe would like to emphasize that our main contribution lies in the bandit feedback setting for online structured prediction. The full-information delayed feedback setting is handled simply by combining the decoding method of Sakaue et al. (2024, [35]) with ODAFTRL and is not central to our work; it occupies only half a page in our 9-page manuscript. \n\nThat said, we agree that it is beneficial to note that the improvement is achievable by the $D$-copy approach in the full-information setting. In the revised version, we will carefully discuss how the $D$-copy approach improves the bound in the full-information setting, and how our method demonstrates advantages over the $D$-copy approach in the bandit setting, in terms of both regret bounds and average-case performance. We again appreciate the reviewer's insightful comment.\n \n## **Regarding variable delay (mentioned in Weaknesses)**\n\n> I think that a similar surrogate regret bound should be obtainable for delay that is not constant.\n\nWe have provided the algorithm and the upper bounds for the variable delay setting, which is deferred to Appendix G and mentioned in Line 379 due to space constraints.\n\nHere, we briefly describe the results. \nLet $\\tau_t$ denote the delay time of the feedback at time $t$ and $\\tau_\\ast$ the maximum delay. We obtain an upper bound of $O(\\sqrt{\\tau_{1:T}}+\\tau_\\ast)$ in the full-information setting. In the bandit setting, by employing the inverse-weighted gradient estimator and the pseudo-inverse matrix estimator, we obtain upper bounds of $O(\\sqrt{KT}+\\sqrt{\\tau_{1:T}}+\\tau_\\ast)$ and $O(T^{1/6}\\sqrt{\\tau_{1:T}}+\\omega^{1/3}T^{2/3}+\\tau_\\ast)$, respectively. Please see Appendix G for the detailed statements and proofs.\n\n## **Q2. Tightness of results for the delayed bandit setting**\n\n> It is not clear if the results for the delayed bandit setting are tight. Nevertheless, both results are new and show that the randomized decoding technique from earlier work can be extended to obtain interesting results beyond the setting the technique was originally developed for. \n\n> I am wondering if the bounds for the delayed bandit setting are tight\n\nThank you for the important comment. Proving lower bounds and discussing the tightness of the upper bounds we provided are certainly an important direction. However, in the analysis of surrogate regret bounds, particularly under the bandit feedback setting, proving lower bounds is challenging. Below, we provide information regarding the difficulty of establishing lower bounds in the bandit feedback setting.\n\nVan der Hoeven et al. (2021, [39]) proved an \\$\\Omega(\\sqrt{T})\\$ lower bound in the \"graph\" feedback setup, which is a variant of the bandit feedback model. However, no surrogate regret lower bound is known for the \"bandit\" feedback setting, as their construction does not apply to this case (although this may suggest that the lower bound in the bandit setup is possibly \\$\\Omega(\\sqrt{T})\\$). Hence, there seems to be an additional difficulty in constructing surrogate regret lower bounds in the bandit setting. Extending such constructions to the delayed feedback setting would be even more challenging and is beyond the scope of this study. We will include these discussions in the revised version."}, {"review_id": "3uDQlT2a1y", "reviewer": "Reviewer_4Bpe", "summary": "The paper studies online structured prediction under bandit and delayed feedback. In the bandit setup it proposes an algorithm guaranteeing a surrogate regret of $O(\\sqrt{KT})$, where $K$ is the size of the output set, and an algorithm with surrogate regret of $O(T^{2/3})$ independent of $K$. In the case of delayed feedback with delay $D$, the paper proposes an algorithm guaranteeing regret $O(\\min(D^2,D^{2/3}T^{1/3}))$ in the full information setting, and also provides algorithms with surrogate regret guarantees for the case in which both delay and bandit feedback are present.", "questions": "None", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper addresses a well-motivated problem. The result presented in Section 3.4 is particularly noteworthy and I find it rather surprising.\n\nOverall, the theoretical results appear to be sound, and the manuscript is generally written with care and clarity. I particularly appreciated the authors for their clear (and honest) comparison with related work (e.g., discussion on pages 261–269).\n\nHowever, in some sections, the manuscript becomes quite dense with technical details, which may hinder its understanding especially for readers not deeply familiar with the specific techniques employed. In some parts of the paper, a more intuitive or high-level exposition accompanying the formal developments would help in understanding the main conceptual contributions. One example is Section 3.4, where the pseudo-inverse matrix estimator is introduced.\n\nThe results up to Section 3.3 rely on a combination of standard tools for handling bandit feedback and prior  techniques (e.g., from \\[35]). While the derivations are technically non-trivial, this part of the paper seems to lack substantial conceptual contributions/new ideas. A similar observation may apply to the delayed feedback setting: the presentation does not clearly articulate what new ideas or techniques are necessary to obtain the results, making it challenging to assess the novelty without delving deeply into the proofs.\n\nFinally, Assumption 3.6 (iii) is not explicitly discussed, despite the apparent importance of the parameter $\\omega$ in the subsequent guarantees.", "was_revised": true, "final_justification": "After reading the responses I remain quite positive about this work and will maintain my score.", "rebuttal": "Thank you for taking the time to provide this valuable review. Below are our responses to the comments.\n\n## **Intuitive explanations**\n\n> However, in some Sections, the manuscript becomes quite dense with technical details, which may hinder its understanding especially for readers not deeply familiar with the specific techniques employed. In some parts of the paper, a more intuitive or high-level exposition accompanying the formal developments would help in understanding the main conceptual contributions. One example is Section 3.4, where the pseudo-inverse matrix estimator is introduced.The results up to Section 3.3 rely on a combination of standard tools for handling bandit feedback and prior techniques (e.g., from [35]). While the derivations are technically non-trivial, this part of the paper seems to lack substantial conceptual contributions/new ideas. A similar observation may apply to the delayed feedback setting: the presentation does not clearly articulate what new ideas or techniques are necessary to obtain the results, making it challenging to assess the novelty without delving deeply into the proofs.\nWe apologize for the lack of clarity in the original explanation. Below we provide further clarification on the examples cited in Section 3.4 and the details related to delayed feedback in Sections 4 and 5.\n\n**Regarding Section 3.4**\n\n- We propose a pseudo-inverse matrix estimator inspired by studies on adversarial linear bandits and adversarial combinatorial full-bandits. By utilizing the loss values, the estimator achieves a $K$-independent bound that is particularly effective for complex structured prediction problems, such as multilabel classification.\n- Technically, unlike inverse-weighted gradient estimators, our approach constructs an unbiased estimator without relying on the inverse weighting by probability $p\\_t$. This is crucial for removing the dependence on $K$, which arises from the lower bound on $p\\_t$. The upper bound for this approach is proven using properties of positive semi-definite matrices and pseudo-inverse matrices (see Lemmas D.5–D.7 for details).\n- Additionally, we identify the conditions under which this estimator can be used and characterize the class of loss functions that satisfy these conditions. This is also technically novel.\n\n**Regarding Sections 4 and 5**\n- We discovered that existing algorithms for online convex optimization with delay, which achieve AdaGrad-type regret bounds, can be effectively utilized.\n- In Section 4, the core idea is already presented in the proof sketch of Theorem 4.3. The key technical point is leveraging the negative term via the AdaGrad-type regret bound and the inequality $\\\\|\\boldsymbol{G}\\_t\\\\|\\_\\mathrm{F}^2 \\le bS\\_t(\\boldsymbol{W}\\_t)$. (These techniques remain important even when applying the $D$-copy approach mentioned in the rebuttal to Reviewer jZKi.)\n- The algorithm and proof ideas in Section 5 are essentially a combination of the discussions already presented in Sections 3 and 4.\n\nWe will emphasize these points more clearly in the revision and do our best to provide more intuitive explanations.\n\n## **Parameter $\\omega$ of Assumption 3.6 (iii)**\n\n> Finally, Assumption 3.6 (iii) is not explicitly discussed, despite the apparent importance of the parameter $\\omega$ in the subsequent guarantees.\n\nThank you for the comment. As pointed out, the value of $\\omega$ is indeed important. In the revised version, we will update Corollary 3.8 to include not only the final upper bound but also the explicit values of $\\omega$ for each setting—namely, multiclass classification, multilabel classification, and ranking. Specifically, $\\omega$ is $d^2$ for multiclass classification, $d^5 / 4m(d - m)$ for multilabel classification with $m$ correct labels, and $m^5$ for the ranking (see Appendix D.4 for details)."}, {"review_id": "GTtjxgBM9t", "reviewer": "Reviewer_4VTE", "summary": "This paper studies the problem of online structured prediction with bandit and delayed feedback. Unlike the standard way of measuring the performance of online algorithms, the authors consider an alternative notion called surrogate regret, based on some surrogate loss (Fenchel-Young loss) introduced in prior work. While a standard bandit algorithm achieves a surrogate regret of O((KT)^{1/2}), where T is the time horizon and K is the size of the output set, the authors propose a new bandit algorithm achieving a regret of O(T^{2/3}) when the loss has some special form. Analogous results are also shown for the delayed feedback setting.", "questions": "See the weakness part above.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength: \nThe use of Fenchel-Young loss for structured prediction tasks seems interesting. The results are new. The regret bound of the proposed algorithm is independent of K, which is appealing when the size of the output set is large.\n\nWeakness:\nWhile using a carefully chosen surrogate loss to facilitate algorithm design is a good idea, I believe that the performance of an algorithm should still be evaluated with respect to the original target loss, or regret defined in terms of the target loss, which we ultimately care about. The surrogate regret proposed in this paper compares the target loss of the online algorithm to the surrogate loss of a fixed offline comparator, which raises concerns about interpretability and fairness. This mixed comparison (target vs. surrogate loss) may lead to misleading conclusions. A small surrogate regret does not necessarily imply strong performance on the original task, as the regret is not measured in a consistent way. \nFor instance, in the full-information setting with delay D=1, one can actually achieve constant surrogate regret, whereas it is well known that under the standard regret definition (based on the target loss), even the no-delay setting admits a lower bound of about T^{1/2}. It seems that the surrogate regret upper bounds achieved by this paper are based on the assumption that the target loss is less than the surrogate loss by about a factor of (1-a), and the surrogate regret bounds contain a factor of 1/a. This means that if one uses a surrogate loss close to the targe loss, with the parameter a approaching zero, than the surrogate regret could become arbitrarily large.", "was_revised": true, "final_justification": "I am raising my score as the authors have addressed some of my initial concerns. Nonetheless, I hope they will clarify the notion of surrogate regret when revising the paper, as readers unfamiliar with it may have similar concerns to those I initially had.", "rebuttal": "Thank you very much for your thoughtful and constructive review. Below are our responses to your comments.\n\n## **On the surrogate regret**\n\nWe thank the reviewer for raising this important point. Firstly, we would like to clarify a possible misunderstanding in the following statement by the reviewer:\n> The surrogate regret proposed in this paper compares the target loss of the online algorithm to the surrogate loss of a fixed offline comparator, which raises concerns about interpretability and fairness. This mixed comparison (target vs. surrogate loss) may lead to misleading conclusions. A small surrogate regret does not necessarily imply strong performance on the original task, as the regret is not measured in a consistent way. ...\n\nThe surrogate regret is not a new concept proposed in this paper. It was explicitly introduced by Van der Hoeven (2020, [38]) and has been a central concept in the subsequent work (Van der Hoeven et al., 2021, [39]; Sakaue et al., 2024, [35]). Below, we elaborate on why this measure is appropriate and justified in our setting.\n\nAs you rightly noted, the relationship between the target loss and the surrogate loss deserves careful attention. This issue has been thoroughly discussed in prior work, particularly in Sakaue et al. (2024, [35]), and our choice of target and surrogate losses in this paper follows the standard framework established in the literature. Accordingly, the surrogate loss used in our setting does not give the algorithm any unfair advantage, nor does it result in pathological behavior where the constant $a$ becomes arbitrarily small and causes the regret bound to deteriorate excessively. For example, in the case of classification with the logistic loss, which is a standard surrogate loss, the constant is $a = 1 - \\ln 2 \\approx 0.3$, which is not excessively small and ensures that the resulting bound, scaling as $1/a$, remains meaningful. \n\nMore broadly, if one were to analyze the regret solely with respect to the target loss, one would need to consider hypothesis classes consisting of models that predict discrete labels $\\boldsymbol{y}$ from input features $\\boldsymbol{x}$. However, such models are often computationally intractable to train. In practice, it is standard to adopt the surrogate loss framework, as advocated in the seminal work by Bartlett et al. (2006, [3]), as discussed in Section 1. In this approach, we can efficiently learn estimators that map a feature $\\boldsymbol{x}$ to a score vector $\\boldsymbol{\\theta}$ in the continuous Euclidean space $\\mathbb{R}^d$, by applying gradient-based methods to a surrogate loss.\n\nFrom this perspective, it is both natural and important to study how well we can bound the target loss in comparison to the best possible performance achievable under the surrogate loss framework. This leads to the study of the surrogate regret, which indeed generalizes the finite mistake bound of the classical Perceptron on linearly separable data (Rosenblatt 1958, [34]; cf. Van der Hoeven, 2020, [38], Section 1) and has been the focus of a growing body of work—Van der Hoeven (2020, [38]), Van der Hoeven et al. (2021, [39]), and Sakaue et al. (2024, [35]). This conceptual foundation is central to our work.\n\nIn summary, we understand the reasoning behind the reviewer’s concern, but we emphasize that the surrogate regret framework is theoretically sound and widely accepted and that the choice of target and surrogate losses in our paper is fully aligned with the established literature. Therefore, adopting the surrogate regret framework does not weaken the significance of our contributions. We will clarify this point in the revised version of the paper with further discussion."}]

Author rebuttal:

Meta-review: This paper looks at the online Structured Prediction with bandit or delayed feedback, with interesting results on the regret growth, in particular with delays.

All the reviewers are now very positive, thanks to the rebuttal that convinced them. Due to this, I went through the paper myself, and I can see why they are all on the acceptance side, on I concur with them, this is an interesting paper with promising result.

I therefore also recommend acceptance.
Decision: Accept (poster)