Answer: Every admissible run satisfies the stated distributional regret inequality.
Proposition 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor an α-informative user with true pref- erence vector w∗and bounded length feature vectors ∥φ∗(x)∥≤R, the average regret incurred by Coactive Cri- tiquing after T iterations is upper bounded by REGT ≤ 2R α √ T ∥w∗∥+ 1 αT T X t=1 ξt + ηt See the Appendix for the proof. The sum PT t=1 ηt on the right hand side depends on the effectiveness of the user’s cri- tiques and how often they are asked, as well as the problem structure. The latter factor is beyond our control, but the for- mer can be (partially) controlled by properly designing the interaction with the user.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support of user types \(h\), rational masses \(\mu_h\) summing to one, a common feasible option set \(X\), and a complete preference and feedback model for each type, run an independent Coactive Critiquing learner for each type. After \(T\) rounds, does the mass-weighted mean regret \(\sum_h \mu_h \mathrm{REG}_{T,h}\) satisfy the mass-weighted sum of the Proposition 2 bounds under per-type \(\alpha\)-informativity, bounded feature norms, and the corresponding improvement-error and missing-feature terms? The finite cohort with \(n_h\) identical users of each type is represented by \(\mu_h=n_h/n\).
A society is specified by its support: \(\tau\) types with positive binary-rational masses \(\mu_h\) summing to \(1\); \(\tau\) counts listed types, not possible types. Let \(L\) be the total input bit length; express any running times in \(m,\tau,L,T\), including oracle costs.
The common feasible set \(X\) is nonempty. Each type has features \(\phi_h^*:X\to\mathbb R^m\), weights \(w_h^*\in\mathbb R^m\), utility \(u_h^*(x)=\langle w_h^*,\phi_h^*(x)\rangle\), and \(\|\phi_h^*(x)\|_2\le R_h\), where \(R_h>0\). All required maxima are attained; maximizing ties may be resolved arbitrarily.
Run a separate learner for each type for \(T\ge1\) rounds. Initially its weights are zero and it knows a specified subset of feature coordinates. Represent unknown coordinates by zeros, and denote the resulting feature map before round \(t\)'s critique by \(\psi_{h,t}\).
Choose \(x_{h,t}\in\arg\max_{x\in X}\langle w_{h,t},\psi_{h,t}(x)\rangle\), receive feasible feedback \(\bar x_{h,t}\in X\), and add this pair to that learner's history. Request a critique when no weight vector strictly ranks every historical feedback option above its proposal using the currently known coordinates.
A critique reveals one previously unknown coordinate of \(\phi_h^*\), whose learned weight starts at zero; if none remain, retain the current coordinates. Let \(\phi_{h,t}\) denote the zero-padded feature map after this possible revelation. Update \(w_{h,t+1}=w_{h,t}+\phi_{h,t}(\bar x_{h,t})-\phi_{h,t}(x_{h,t})\); retain all revealed coordinates thereafter.
For each type assume \(\alpha_h\in(0,1]\) and signed errors \(\xi_{h,t}\in\mathbb R\) satisfying \(u_h^*(\bar x_{h,t})-u_h^*(x_{h,t})=\alpha_h[u_h^*(x_h^*)-u_h^*(x_{h,t})]-\xi_{h,t}\), where \(x_h^*\in\arg\max_{x\in X}u_h^*(x)\).
Define \(\eta_{h,t}=u_h^*(\bar x_{h,t})-u_h^*(x_{h,t})-\langle w_h^*,\phi_{h,t}(\bar x_{h,t})-\phi_{h,t}(x_{h,t})\rangle\) and \(\mathrm{REG}_{T,h}=T^{-1}\sum_{t=1}^T[u_h^*(x_h^*)-u_h^*(x_{h,t})]\); missing-feature errors may have either sign.
Does every admissible run satisfy \(\sum_h\mu_h\mathrm{REG}_{T,h}\le\sum_h\mu_h\left[\frac{2R_h\|w_h^*\|_2}{\alpha_h\sqrt T}+\frac{1}{\alpha_h T}\sum_{t=1}^T(\xi_{h,t}+\eta_{h,t})\right]\), or is there an admissible counterexample?
Known for an individual user: the corresponding regret bound holds for the growing-feature learner; this is a regret guarantee, not a polynomial-time inference theorem. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/10929/10788)
No separate result for exactly the stated distributional formulation was verified.
Every admissible run satisfies the stated inequality. The proof is deterministic and permits both error terms to have either sign. The corresponding individual guarantee appears as Proposition 2 in [Teso, Dragone, and Passerini](https://ojs.aaai.org/index.php/AAAI/article/download/10929/10788); below is a direct proof for the precise update rule in the question.
Fix a type \(h\), and suppress its index temporarily. Work throughout in the fixed ambient space \(\mathbb R^m\), padding unknown coordinates and their learned weights with zeros.
Let \(K_t\) be the coordinates known before round \(t\)’s critique, and \(J_t\) those known afterward. For a coordinate set \(S\), let \(P_S\) be the coordinate projection that zeros coordinates outside \(S\). Thus
\(\psi_t(x)=P_{K_t}\phi^*(x)\), and \(\phi_t(x)=P_{J_t}\phi^*(x)\).
The revelation and retention rules give \(K_t\subseteq J_t\) and \(K_{t+1}=J_t\).
We first prove that \(w_t\) is zero outside \(K_t\). This holds initially because \(w_1=0\). If it holds at round \(t\), then both \(w_t\) and the update difference are supported on \(J_t\). Consequently, \(w_{t+1}\) is supported on \(J_t=K_{t+1}\), establishing the induction.
In particular, every coordinate newly revealed during round \(t\) has weight zero in \(w_t\). Hence, for every \(x\in X\),
\(\langle w_t,\phi_t(x)\rangle=\langle w_t,\psi_t(x)\rangle\).
Define the update difference by
\(\Delta_t=\phi_t(\bar x_t)-\phi_t(x_t)\).
Because \(x_t\) maximizes the pre-critique score and \(\bar x_t\in X\), it follows that
\(\langle w_t,\Delta_t\rangle =\langle w_t,\psi_t(\bar x_t)\rangle-\langle w_t,\psi_t(x_t)\rangle \le 0\).
This reasoning allows arbitrary maximizing ties. It also covers rounds in which no coordinate is revealed.
Coordinate projection cannot increase the Euclidean norm. Therefore, for every feasible \(x\),
\(\|\phi_t(x)\|_2\le\|\phi^*(x)\|_2\le R\).
The triangle inequality gives
\(\|\Delta_t\|_2\le\|\phi_t(\bar x_t)\|_2+\|\phi_t(x_t)\|_2\le 2R\).
Using the update \(w_{t+1}=w_t+\Delta_t\) and the nonpositive inner product proved above,
\(\|w_{t+1}\|_2^2 =\|w_t\|_2^2+2\langle w_t,\Delta_t\rangle+\|\Delta_t\|_2^2 \le\|w_t\|_2^2+4R^2\).
Summing over the \(T\) rounds, with \(w_1=0\), yields
\(\|w_{T+1}\|_2^2\le 4R^2T\), hence \(\|w_{T+1}\|_2\le 2R\sqrt T\).
Write \(r_t=u^*(x^*)-u^*(x_t)\). By the assumed feedback identity and the definition of the post-revelation missing-feature error,
\(\langle w^*,\Delta_t\rangle =u^*(\bar x_t)-u^*(x_t)-\eta_t =\alpha r_t-\xi_t-\eta_t\).
The updates telescope in the fixed ambient space:
\(\sum_{t=1}^T\Delta_t=w_{T+1}-w_1=w_{T+1}\).
Consequently,
\(\alpha T\,\mathrm{REG}_T =\langle w^*,w_{T+1}\rangle+\sum_{t=1}^T(\xi_t+\eta_t)\).
Cauchy–Schwarz and the norm bound imply
\(\langle w^*,w_{T+1}\rangle \le\|w^*\|_2\|w_{T+1}\|_2 \le 2R\|w^*\|_2\sqrt T\).
Dividing by the positive quantity \(\alpha T\) proves
\(\mathrm{REG}_T \le \dfrac{2R\|w^*\|_2}{\alpha\sqrt T} +\dfrac{1}{\alpha T}\sum_{t=1}^T(\xi_t+\eta_t)\).
No step replaces an error by its absolute value or assumes an error is nonnegative.
The preceding proof applies separately to every listed type \(h\). Since each \(\mu_h>0\), multiplication by \(\mu_h\) preserves its inequality. Summing over the \(\tau\) listed types gives exactly
\(\displaystyle \sum_{h=1}^{\tau}\mu_h\mathrm{REG}_{T,h} \le \sum_{h=1}^{\tau}\mu_h \left[ \frac{2R_h\|w_h^*\|_2}{\alpha_h\sqrt T} +\frac{1}{\alpha_h T}\sum_{t=1}^{T}(\xi_{h,t}+\eta_{h,t}) \right]. \)
Thus there is no admissible counterexample.
The historical strict-ranking test does not require an additional lemma for this guarantee: the proof works for any revelation schedule that retains coordinates and initializes newly revealed weights at zero.
This establishes a regret guarantee, without asserting a running-time bound. The premises do not specify computational representations or costs for feature evaluation, exact maximization over \(X\), or historical strict-ranking feasibility. In particular, the finite support and input length \(L\) alone do not establish polynomial-time implementation.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The argument establishes the stated inequality for every admissible run. No major or minor issues were found.
The prover correctly represents all feature maps and weights in \(\mathbb R^m\). The identities \(K_t\subseteq J_t\) and \(K_{t+1}=J_t\) follow from revelation and retention. Initially \(w_1=0\), so it is supported on \(K_1\). If \(w_t\) is supported on \(K_t\), the update difference is supported on \(J_t\), making \(w_{t+1}\) supported on \(K_{t+1}=J_t\). The induction is valid.
Because \(w_t\) vanishes outside \(K_t\), newly revealed coordinates contribute nothing to the current score. Thus
\[
\langle w_t,\phi_t(x)\rangle=\langle w_t,\psi_t(x)\rangle
\]
for every feasible \(x\). Applying the proposal’s maximizing property to the feasible feedback gives \(\langle w_t,\Delta_t\rangle\le0\). This uses the correct pre-critique maximization rule and remains valid after revelation. Arbitrary maximizing ties cause no difficulty.
Coordinate projection is a contraction for the Euclidean norm, so \(\|\phi_t(x)\|_2\le R\). The triangle inequality therefore gives \(\|\Delta_t\|_2\le2R\). Expanding the squared norm of the update and using the nonpositive cross term yields
\[
\|w_{t+1}\|_2^2\le\|w_t\|_2^2+4R^2.
\]
Summation from \(t=1\) through \(T\), with zero initial weights, correctly gives \(\|w_{T+1}\|_2\le2R\sqrt T\). The constants and indices are correct.
The definition of \(\eta_t\) uses the post-revelation feature map, exactly as does \(\Delta_t\). Combining it with the feedback identity correctly gives
\[
\langle w^*,\Delta_t\rangle=\alpha r_t-\xi_t-\eta_t.
\]
The updates telescope in the fixed ambient space, despite changing known-coordinate sets. Consequently,
\[
\alpha T\,\mathrm{REG}_T
=\langle w^*,w_{T+1}\rangle+\sum_{t=1}^T(\xi_t+\eta_t).
\]
Both error signs are handled correctly; neither nonnegativity nor absolute-value replacement is used.
Cauchy–Schwarz applies to the two vectors in \(\mathbb R^m\) and supplies the required upper bound on their inner product. Division by \(\alpha T\) preserves the inequality because \(\alpha>0\) and \(T\ge1\). The resulting expression is exactly the required per-type bound.
The argument applies to each listed type separately, with its own parameters and realized history. Multiplication by each positive mass preserves the inequality, and the finite sum over the \(\tau\) listed types gives exactly the target statement. No independence assumption or restriction on possible unlisted types is needed. The mass normalization is consistent with the task, although the aggregation step requires only nonnegative masses.
The historical strict-ranking condition only selects the revelation schedule. Every schedule generated by that condition satisfies the retention and zero-initialization properties used in the proof, so omitting an analysis of the ranking test introduces no gap. The derivation also covers no revelation, exhausted coordinates, an empty initial coordinate set, \(T=1\), and \(w_h^*=0\).
The attribution to Proposition 2 is accurate: the cited paper states the corresponding individual growing-feature regret bound. The submitted argument establishes the precise formulation directly, so its validity does not depend on importing that proposition’s hypotheses. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/10929/10788)
No running time or complexity classification is claimed. Accordingly, the requirement to express any running times in \(m,\tau,L,T\), including oracle costs, is not violated. The established result is a regret guarantee.
Required repair or clarification: none.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.