Answer: Uniform inner convergence holds when \(0<\eta_r\le 1/M\) and \(\sum_r\eta_r=\infty\), where \(M=\alpha+8AK^2(1-\varepsilon)^4\). The requested outer conclusions hold under a unique highest unanswered optimal score everywhere, giving a uniform positive gap and eventual \(F_r=F\), or under equality of augmented-history likelihoods at exact top ties together with attainment of the approximate maxima. A sufficient attainment condition is that the prescribed tie rule chooses a greatest-likelihood question at every finite-iterate top tie.
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet [T] = {1, 2, · · · , T} where T is a pos- itive integer. If the outer-level ℓ(θ) is uniformly Lipschitz continuous and the iterates ⟨Sθ⟩T∈N in the inner-level con- verge uniformly to Sθ as T →+∞, then max ℓT(θ) → max ℓ(θ), meaning that for every sequence ⟨θ⟩T∈N such that θ ∈arg maxθ ℓT(θ), we have ⟨θ⟩T admits a convergent subsequence and for every subsequence ⟨θsub⟩T such that θsub →¯θ, where ¯θ ∈max ℓ(θ).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate-answer set \(\mathcal C\), question bank \(\mathcal O\), and finite worker-type set \(\mathcal T\) with rational masses \(\mu_t\), where each type specifies its response behavior, form the NO2 likelihood and pairwise question-value objective by weighting each type’s response-history contributions by \(\mu_t\). Under what conditions does the resulting gradient-based bilevel optimization retain Theorem 1’s convergence guarantee for the maximizing beliefs and question values?
Let \(m\ge2\) questions and \(K\ge1\) independent binary candidate variables have a given bipartite support graph, with every question having a nonempty parent set. A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Each type supplies a deterministic binary response vector and an observed partial history \(\Gamma_t\), leaving at least one question unanswered. Let \(L\) be the total input bit length; state any running times in \(m,K,\tau,L\) and the additional parameters.
The belief vector \(\theta\) consists of independent candidate probabilities \(p_k\) and edge failure probabilities \(q_{ik}\), all in \([\varepsilon,1-\varepsilon]\), for a given rational \(0<\varepsilon<1/2\); put \(q_{ik}=1\) on nonedges. Conditional on candidate configuration \(c\in\{0,1\}^K\), questions are independent and \(P_\theta(O_i=0\mid c)=\prod_{k:c_k=1}q_{ik}\). Write \(P_\theta(\Gamma)\) for the resulting marginal history probability; candidate probabilities need not sum to one.
Set \(Y^t_{ij}=1\) exactly when the observed history of type \(t\) contains a positive response to \(i\) and a negative response to \(j\), and otherwise set it to zero. Define \(\beta_i=\sum_k(1-q_{ik})p_k\), \(D_{ij}=(\beta_i+\beta_j)(s_i-s_j)\), and, for a given rational \(\alpha>0\), \(G_\mu(S,\theta)=\sum_t\mu_t\sum_{i\ne j}Y^t_{ij}\bigl(D_{ij}-\log\sum_{a\ne b}e^{D_{ab}}\bigr)-\alpha\|S\|_2^2/2\), with \(S\in\mathbb R^m\).
Let \(S^*(\theta)\in\operatorname{argmax}_S G_\mu(S,\theta)\). Define \(S^{(0)}_i=1/m\) and \(S^{(r+1)}=S^{(r)}+\eta_r\nabla_S G_\mu(S^{(r)},\theta)\), where \(\eta_r>0\). For each type, append its response to the unanswered question with largest score in \(S\), breaking ties by a fixed question order, to obtain \(\Gamma_t(S)\).
Define \(F(\theta)=\sum_t\mu_t\log P_\theta(\Gamma_t(S^*(\theta)))\) and \(F_r(\theta)=\sum_t\mu_t\log P_\theta(\Gamma_t(S^{(r)}(\theta)))\).
Under what conditions on the instance and step sizes do the inner iterates converge uniformly to maximizing question values, while \(\max_\theta F_r(\theta)\to\max_\theta F(\theta)\) and every sequence \(\theta_r\in\operatorname{argmax}_\theta F_r(\theta)\) has a convergent subsequence whose every accumulation point maximizes \(F\)?
For finite workers, a conditional convergence result asserts convergence of approximate optimal values and accumulation points of maximizers under uniform inner convergence and a Lipschitz outer objective; it does not establish global convergence of outer gradient ascent. [Source](https://ojs.aaai.org/index.php/AAAI/article/view/38820).
A general bilevel approximation theorem establishes analogous conclusions under compactness, joint continuity, unique bounded inner solutions, uniform Lipschitz dependence on inner variables, and uniform inner convergence; it does not specifically analyze history selection by deterministic question ranking. [Source](https://proceedings.mlr.press/v80/franceschi18a/franceschi18a.pdf).
The inner problem has a unique maximizer for every admissible belief vector, and suitable gradient steps converge to it uniformly. The additional issue is deterministic ranking: convergence of scores does not, by itself, imply convergence of the selected-history likelihoods.
Here are two sufficient conditions for the outer conclusions:
These are sufficient conditions, not a characterization of all instances for which the conclusions happen to hold.
Let \(E\) be the number of support edges, and let
\( \Theta=[\varepsilon,1-\varepsilon]^{K+E}. \)
Define the aggregated comparison weights and their total by
\( a_{ij}=\sum_{t=1}^{\tau}\mu_tY^t_{ij},\qquad A=\sum_{i\ne j}a_{ij}. \)
For each ordered pair, put
\( v_{ij}(\theta)=(\beta_i+\beta_j)(e_i-e_j),\qquad h(\theta)=\sum_{i\ne j}a_{ij}v_{ij}(\theta). \)
Then the inner objective is
\( G_\mu(S,\theta)=h(\theta)^\top S-A\log Z(S,\theta)-\frac{\alpha}{2}\|S\|_2^2,\qquad Z(S,\theta)=\sum_{i\ne j}\exp(v_{ij}(\theta)^\top S). \)
If a type has \(u\) observed positive answers and \(v\) observed negative answers, it contributes \(uv\) comparisons. Since at least one question is unanswered, \(u+v\le m-1\). Consequently,
\( 0\le A\le \left\lfloor\frac{(m-1)^2}{4}\right\rfloor. \)
Set
\( B=2K(1-\varepsilon)^2,\qquad V=\sqrt{2}\,B,\qquad M=\alpha+AV^2. \)
Indeed, each summand in \(\beta_i\) is at most \((1-\varepsilon)^2\), so \(\beta_i+\beta_j\le B\) and \(\|v_{ij}\|_2\le V\).
For every \(\theta\in\Theta\), the maximizer \(S^*(\theta)\) exists and is unique. Moreover,
\( \|S^*(\theta)\|_2\le \frac{AV}{\alpha}, \)
and \(\theta\mapsto S^*(\theta)\) is continuous.
Proof. Every comparison contribution is a log softmax probability and therefore is nonpositive. Thus
\( G_\mu(S,\theta)\le-\frac{\alpha}{2}\|S\|_2^2. \)
Continuity and this coercive upper bound imply existence of a maximizer.
Let \(\pi_{ij}=\exp(v_{ij}^\top S)/Z\). Differentiation gives
\( -\nabla_S^2G_\mu(S,\theta)=\alpha I+A\operatorname{Cov}_{\pi}(v_{ij}). \)
For any vector \(x\),
\( 0\le x^\top\operatorname{Cov}_{\pi}(v_{ij})x\le \mathbb E_\pi[(x^\top v_{ij})^2]\le V^2\|x\|_2^2. \)
Hence, uniformly in \(S,\theta\),
\( \alpha I\preceq-\nabla_S^2G_\mu(S,\theta)\preceq MI. \)
In particular, \(G_\mu\) is \(\alpha\)-strongly concave, proving uniqueness.
At \(S=0\), the softmax weights are uniform. Since \(v_{ji}=-v_{ij}\), their mean is zero, and \(\nabla_SG_\mu(0,\theta)=h(\theta)\). Strong concavity and stationarity at \(S^*\) imply
\( \alpha\|S^*\|_2^2\le h(\theta)^\top S^*\le AV\|S^*\|_2, \)
which proves the bound.
Finally, suppose \(\theta_n\to\theta\). Boundedness gives convergent subsequences of \(S^*(\theta_n)\). If such a subsequence converges to \(\bar S\), the maximizing inequalities, together with joint continuity of \(G_\mu\), give
\( G_\mu(\bar S,\theta)\ge G_\mu(S,\theta)\quad\text{for every }S. \)
Uniqueness implies \(\bar S=S^*(\theta)\). All subsequential limits are therefore the same, proving continuity. \(\square\)
Assume the prescribed step sizes satisfy
\( 0<\eta_r\le\frac1M,\qquad \sum_{r=0}^{\infty}\eta_r=\infty. \)
Then the iterates converge uniformly:
\( e_r:=\sup_{\theta\in\Theta}\|S^{(r)}(\theta)-S^*(\theta)\|_2\longrightarrow0. \)
More precisely, with
\( R=\frac1{\sqrt m}+\frac{AV}{\alpha}, \)
one has
\( e_r\le R\prod_{\ell=0}^{r-1}(1-\alpha\eta_\ell)\le R\exp\!\left(-\alpha\sum_{\ell=0}^{r-1}\eta_\ell\right). \)
Proof. Write \(f_\theta=-G_\mu(\cdot,\theta)\). For any \(S,T\), integration of the Hessian along the segment between them gives
\( \nabla f_\theta(S)-\nabla f_\theta(T)=H(S-T),\qquad \alpha I\preceq H\preceq MI. \)
For \(0<\eta\le1/M\), every eigenvalue of \(I-\eta H\) belongs to \([0,1-\alpha\eta]\). Thus the gradient update is a contraction with factor \(1-\alpha\eta\). Applying this with \(T=S^*(\theta)\), and using the uniform initial-distance bound \(R\), proves the product estimate. The exponential estimate follows from \(1-x\le e^{-x}\); the divergent sum implies convergence. \(\square\)
For example, \(\eta_r=1/M\) gives
\( e_r\le R e^{-\alpha r/M}. \)
No summability condition on \(\sum_r\eta_r^2\) is needed for these deterministic, exact-gradient updates.
Positive step sizes alone do not suffice. If \(A=0\), the update is \(S^{(r+1)}=(1-\alpha\eta_r)S^{(r)}\); the constant choice \(\eta_r=2/\alpha\) makes the nonzero initialization oscillate.
Let \(U_t\) be the unanswered questions of type \(t\), and let \(j_{t,r}(\theta)\) be the question selected using \(S^{(r)}(\theta)\). Without any gap or tie assumption,
\( 0\le\max_{j\in U_t}S_j^*(\theta)-S_{j_{t,r}(\theta)}^*(\theta)\le2e_r. \)
To verify this, let \(i\) maximize \(S^*\) on \(U_t\). Since \(j_{t,r}\) maximizes \(S^{(r)}\),
\( S_i^*-S_{j_{t,r}}^*\le(S_i^*-S_i^{(r)})+(S_{j_{t,r}}^{(r)}-S_{j_{t,r}}^*)\le2e_r. \)
Thus selected questions become uniformly optimal in score value, even when their identities do not stabilize.
For \(j\in U_t\), define
\( \Gamma_{t,j}=\Gamma_t\text{ with type }t\text{’s response to }j\text{ appended},\qquad \ell_{t,j}(\theta)=\log P_\theta(\Gamma_{t,j}). \)
These are fixed-history functions; no ranking is involved in their definition.
For every partial binary history \(\Gamma\),
\( P_\theta(\Gamma)\ge\varepsilon^{K+E+m}>0. \)
Indeed, consider only the configuration in which all candidates are active. Its probability is at least \(\varepsilon^K\). Conditional on that configuration, a negative response to question \(i\) has probability at least \(\varepsilon^{d_i}\), where \(d_i\) is its degree. A positive response has probability at least \(\varepsilon\), because its parent set is nonempty. Conditional independence supplies the stated bound.
Consequently, each \(\ell_{t,j}\) is continuous and smooth on the parameter box.
One also has the useful uniform bound
\( |\ell_{t,j}(\theta)-\ell_{t,j}(\theta')|\le\frac1\varepsilon\|\theta-\theta'\|_1. \)
To prove it, represent the model by independent candidate Bernoulli variables and independent edge-failure Bernoulli variables. A question is positive precisely when some active parent has a nonfailed edge. This representation has the required conditional distribution.
For any parameter coordinate \(x\), differentiation of an event probability gives
\( \frac{\partial}{\partial x}\log P_\theta(\Gamma)=\mathbb E_\theta\!\left[\frac{B_x}{x}-\frac{1-B_x}{1-x}\,\middle|\,\Gamma\right], \)
where \(B_x\) is the corresponding Bernoulli variable. The integrand has absolute value at most \(1/\varepsilon\). Integrating these coordinate bounds along the segment joining \(\theta\) and \(\theta'\) proves the inequality.
This regularity applies to each fixed-history branch. Ranking can still make their selected combination discontinuous.
Assume:
Gap condition. For every \(\theta\in\Theta\) and every type \(t\) with \(|U_t|\ge2\), the highest score in \(S^*(\theta)\) on \(U_t\) is unique.
For each such type, the difference between its largest and second-largest score is a positive continuous function of \(\theta\). Continuity follows because order statistics of finitely many continuous functions are continuous. Compactness of \(\Theta\), and finiteness of the support, therefore give a number \(\Delta>0\) such that
\( S^*_{j_t^*(\theta)}(\theta)-S_j^*(\theta)\ge\Delta \)
for every type with multiple unanswered questions and every competing \(j\in U_t\).
Whenever \(2e_r<\Delta\), every approximate selection equals its exact selection. Hence there is \(r_0\) such that
\( F_r(\theta)=F(\theta)\quad\text{for every }\theta\in\Theta,\ r\ge r_0. \)
The unique selection is locally constant in \(\theta\), so \(F\) is continuous. It therefore attains a maximum on \(\Theta\). For all \(r\ge r_0\),
\( \max_{\theta\in\Theta}F_r(\theta)=\max_{\theta\in\Theta}F(\theta),\qquad \operatorname{argmax}F_r=\operatorname{argmax}F. \)
Thus any sequence of approximate maximizers has a convergent subsequence, and every accumulation point maximizes \(F\): compactness gives subsequences, and continuity makes \(\operatorname{argmax}F\) closed.
For \(\eta_r=1/M\), it suffices to take
\( r_0=\max\!\left\{1,\left\lceil\frac M\alpha\log\!\left(\max\{1,4R/\Delta\}\right)\right\rceil\right\}. \)
This ensures \(e_r\le\Delta/4\).
If every type has only one unanswered question, selection is independent of scores and \(F_r=F\) for every \(r\). Otherwise, the gap condition is strong: because \(\Theta\) is connected, each type’s unique winning question must remain the same throughout the box.
The argument guarantees attainment for all sufficiently large \(r\). If maximizers are required at every earlier index as well, attainment at those finitely many indices must also be assumed or verified.
Define the exact top set
\( T_t(\theta)=\operatorname{argmax}_{j\in U_t}S_j^*(\theta). \)
Assume:
Exact-tie compatibility. For every \(\theta,t\) and every \(i,j\in T_t(\theta)\),
\( \ell_{t,i}(\theta)=\ell_{t,j}(\theta). \)
This condition allows the selected question to change with \(\theta\).
Under exact-tie compatibility, \(F\) is continuous and
\( \sup_{\theta\in\Theta}|F_r(\theta)-F(\theta)|\longrightarrow0. \)
Proof of continuity. Suppose \(\theta_n\to\theta\). Along any subsequence, finiteness of the support and question sets permits a further subsequence on which all selected question indices are constant, say \(j_t\). Continuity of \(S^*\) implies \(j_t\in T_t(\theta)\). Exact-tie compatibility and continuity of the likelihood branches then give
\( F(\theta_n)\longrightarrow\sum_t\mu_t\ell_{t,j_t}(\theta)=F(\theta) \)
along that further subsequence. This implies continuity of \(F\).
For uniform approximation, define the near-top set
\( T_t^\delta(\theta)=\left\{j\in U_t:\max_{i\in U_t}S_i^*(\theta)-S_j^*(\theta)\le\delta\right\} \)
and the modulus
\( \omega(\delta)=\sup_{\theta\in\Theta}\sum_t\mu_t\max_{i,j\in T_t^\delta(\theta)}|\ell_{t,i}(\theta)-\ell_{t,j}(\theta)|. \)
We claim \(\omega(\delta)\to0\) as \(\delta\downarrow0\). Otherwise, choose \(\delta_n\downarrow0\) and parameters witnessing a discrepancy bounded away from zero. Compactness gives a convergent parameter subsequence, and finiteness permits all witnessing indices to be fixed along a further subsequence. At the limit, each witnessing pair belongs to the corresponding exact top set. Continuity and exact-tie compatibility force every discrepancy to tend to zero, a contradiction.
The score-regret bound places each approximate selected question in \(T_t^{2e_r}(\theta)\); the exact selected question is in \(T_t^0(\theta)\). Therefore,
\( \sup_{\theta\in\Theta}|F_r(\theta)-F(\theta)|\le\omega(2e_r)\longrightarrow0. \)
This proves the proposition. \(\square\)
Uniform convergence does not itself prove that a discontinuous \(F_r\) attains its supremum. The following explicit condition suffices.
Let
\( T_{t,r}(\theta)=\operatorname{argmax}_{j\in U_t}S_j^{(r)}(\theta), \)
and let \(j_{t,r}(\theta)\) be its first member in the prescribed question order. Require, for every sufficiently large \(r\),
\( \ell_{t,j_{t,r}(\theta)}(\theta)\ge\ell_{t,j}(\theta)\quad\text{for every }j\in T_{t,r}(\theta),\ \theta,t. \)
Under this condition, \(F_r\) is upper semicontinuous. Indeed, the finite iterates are continuous in \(\theta\). Along a convergent parameter sequence, pass to a subsequence with constant selected indices. Those indices belong to the top sets at the limit, and the displayed inequality makes their limiting likelihoods no greater than the likelihoods selected at the limit. Summing with positive masses proves upper semicontinuity.
An upper semicontinuous function on the compact box attains its maximum. Thus exact-tie compatibility together with this finite-iterate tie condition yields precisely
\( \max_\theta F_r(\theta)\longrightarrow\max_\theta F(\theta). \)
If \(\theta_r\in\operatorname{argmax}F_r\), write \(d_r=\sup_\theta|F_r-F|\). Then
\( F(\theta_r)\ge\max_\theta F(\theta)-2d_r. \)
Compactness supplies convergent subsequences; continuity of \(F\) shows that every accumulation point maximizes \(F\).
Even without approximate attainment, the proved statement remains valid with suprema:
\( \sup_\theta F_r(\theta)\longrightarrow\max_\theta F(\theta). \)
Moreover, every sequence satisfying
\( F_r(\theta_r)\ge\sup_\theta F_r(\theta)-\zeta_r,\qquad \zeta_r\to0, \)
has only \(F\)-maximizing accumulation points, by the same argument with error \(2d_r+\zeta_r\).
Here is an admissible instance in which \(F\) is not even upper semicontinuous.
Take \(m=4\), \(K=1\), all four support edges, one type of mass \(1\), and \(\varepsilon=1/8\). Its observed history is \(O_1=1,O_2=0\); its unanswered responses are \(O_3=0,O_4=1\). Put question \(3\) before question \(4\) in the fixed order.
Consider the parameter point
\( p=\frac12,\qquad q_1=\frac14,\qquad q_2=\frac34,\qquad q_3=q_4=\frac14. \)
Only \(Y_{12}\) is nonzero. Writing \(b_i=\beta_i\), one has
\( b_1=\frac38,\qquad b_2=\frac18,\qquad b_3=b_4=\frac38. \)
Choose a sufficiently large positive integer \(\alpha\). We verify that slightly increasing \(q_3\) makes question \(4\) strictly outrank question \(3\).
Set \(h=(b_1+b_2)(e_1-e_2)\). At \(S=0\), the Hessian of \(\log Z\) is
\( H_0=\frac16\sum_{a<b}(b_a+b_b)^2(e_a-e_b)(e_a-e_b)^\top. \)
Put \(x=1/\alpha\). Stationarity is
\( S=x\bigl(h-\nabla\log Z(S)\bigr). \)
At \(x=0,S=0\), the derivative of this equation with respect to \(S\), after bringing all terms to the left, is \(I\). The analytic implicit-function theorem therefore gives an analytic solution near \(x=0\), with expansion
\( S^*=xh-x^2H_0h+O(x^3). \)
For positive small \(x\), uniqueness identifies this solution with the inner maximizer. Direct calculation gives
\( (H_0h)_3-(H_0h)_4=\frac{(b_1+b_2)(b_2-b_1)(b_3-b_4)}3. \)
Consequently,
\( S_3^*-S_4^*=\frac{(b_1+b_2)(b_1-b_2)(b_3-b_4)}{3\alpha^2}+O(\alpha^{-3}). \)
Analyticity also permits differentiation of this expansion with respect to \(b_3\). At the specified point,
\( \frac{\partial}{\partial b_3}(S_3^*-S_4^*)=\frac1{24\alpha^2}+O(\alpha^{-3})>0 \)
for all sufficiently large \(\alpha\).
At \(b_3=b_4\), exchange symmetry and uniqueness give \(S_3^*=S_4^*\) exactly. Increasing \(q_3\) slightly decreases \(b_3\), so the positive derivative implies \(S_3^*<S_4^*\).
At the tie, the rule selects question \(3\), whose appended response is negative:
\( P_\theta(O_1=1,O_2=0,O_3=0)=p(1-q_1)q_2q_3=\frac9{128}. \)
After the perturbation, the rule selects question \(4\), whose response is positive:
\( P_\theta(O_1=1,O_2=0,O_4=1)=p(1-q_1)q_2(1-q_4)=\frac{27}{128}. \)
Hence \(F\) takes the value \(\log(9/128)\) at the tie, while approaching along these perturbations gives \(\log(27/128)\). It is not upper semicontinuous there.
This example establishes failure of the regularity hypothesis, not failure of every possible outer convergence conclusion. In particular, a fixed-history smoothness argument cannot justify a general ranking-dependent Lipschitz claim.
The following counts use real arithmetic, counting an exponential or logarithm evaluation as one operation.
The coefficients \(a_{ij}\) can be precomputed in \(O(\tau m^2)\) arithmetic operations, in addition to reading the input of length \(L\). For a fixed \(\theta\), computing the \(\beta_i\) costs \(O(E)\); each inner gradient costs \(O(m^2)\), since every feature has only two nonzero coordinates. Thus computing \(r\) iterates costs
\( O(L+\tau m^2+E+rm^2). \)
With \(\eta_r=1/M\), uniform score error at most \(\delta>0\) is guaranteed after at most
\( r_\delta=\max\!\left\{1,\left\lceil\frac M\alpha\log\!\left(\max\{1,R/\delta\}\right)\right\rceil\right\} \)
iterations.
After selecting the appended questions in \(O(\tau m)\) operations, direct enumeration of candidate configurations evaluates all selected-history probabilities in
\( O\!\left(2^K(K+E+\tau m)\right) \)
operations. This enumeration is over candidate configurations, not over possible society types; the society dependence is on its actual support size \(\tau\).
Accordingly, one direct evaluation of \(F_r\), including preprocessing, has arithmetic cost
\( O\!\left(L+\tau m^2+E+rm^2+\tau m+2^K(K+E+\tau m)\right). \)
These are arithmetic counts, not polynomial bit-time claims. The inner iteration bound depends on the numerical condition ratio \(M/\alpha\), which can be exponential in its binary encoding length. Numerical implementation also requires a specified precision for exponentials and logarithms. No efficient global outer-optimization algorithm follows from the convergence proof.
The finite-worker statement in the cited [BiO-HMC paper](https://ojs.aaai.org/index.php/AAAI/article/view/38820/42782) is conditional on uniform inner convergence and outer Lipschitz regularity. The [Franceschi et al. theorem](https://proceedings.mlr.press/v80/franceschi18a/franceschi18a.pdf), Theorem 3.2, likewise assumes joint continuity, unique bounded inner solutions, uniform Lipschitz dependence on the inner variable, and uniform inner convergence.
Here the inner assumptions have explicit proofs and constants. Deterministic history selection requires additional analysis, supplied by the gap or tie-compatibility conditions above. The resulting statements concern globally optimal outer values and accumulation points of global approximate maximizers; they do not establish global convergence of outer gradient ascent.
⟨structured verdict parsed — rendered above⟩
The output resolves the requested convergence question under its stated sufficient conditions. The inner convergence proof and both outer convergence arguments are sound. I found one minor clarification needed in the supplementary discontinuity example, and no major issue.
The result is conditional: the prover does not claim that the outer conclusions hold for every admissible instance, characterize necessary conditions, or establish global convergence of outer gradient ascent.
The definitions of \(a_{ij}\), \(A\), \(v_{ij}\), and \(h\) correctly rewrite the objective as
\(G_\mu(S,\theta)=h^\top S-A\log Z-\alpha\|S\|_2^2/2\).
A type with \(u\) observed positive answers and \(v\) observed negative answers contributes exactly \(uv\) ordered comparisons. Since \(u+v\le m-1\), the bound
\(A\le\lfloor(m-1)^2/4\rfloor\) follows after averaging with masses summing to one.
Nonedges contribute zero to \(\beta_i\). On an edge, \((1-q_{ik})p_k\le(1-\varepsilon)^2\), so the stated bounds \(B=2K(1-\varepsilon)^2\) and \(V=\sqrt{2}B\) are valid. Consequently,
\(M=\alpha+AV^2=\alpha+8AK^2(1-\varepsilon)^4\), agreeing with the final claim.
Each comparison contribution is nonpositive because its exponential is one term in \(Z\). Thus the coercive upper bound is valid and implies existence of a maximizer.
The Hessian identity
\(-\nabla_S^2G_\mu=\alpha I+A\operatorname{Cov}_{\pi}(v_{ij})\)
is correct. The covariance estimate establishes both strong concavity and the global Hessian upper bound, uniformly over \(S\) and \(\theta\).
At zero, cancellation between opposite ordered pairs gives \(\nabla_SG_\mu(0,\theta)=h(\theta)\). The strong-concavity argument correctly yields
\(\|S^*(\theta)\|_2\le AV/\alpha\). The case \(S^*=0\) requires no division; when \(A=0\), the bound correctly forces \(S^*=0\).
The continuity argument uses a common bounded set of maximizers, joint continuity, and uniqueness. Passing the maximizing inequality to a convergent subsequence is valid for every fixed comparison point \(S\).
Integrating the Hessian along a segment produces a symmetric matrix with eigenvalues in \([\alpha,M]\). Under \(0<\eta_r\le1/M\), the update therefore contracts distances by at most \(1-\alpha\eta_r\).
The initial norm is \(\|S^{(0)}\|_2=1/\sqrt m\), so the stated uniform bound \(R\) is correct. The product and exponential estimates follow, and \(\sum_r\eta_r=\infty\) guarantees uniform convergence.
The boundary case \(M=\alpha\), including a possible zero contraction factor, is covered. No square-summability assumption is needed for these exact deterministic updates.
The oscillation example with \(A=0\) and \(\eta_r=2/\alpha\) correctly shows that positive step sizes alone do not ensure convergence of the score vectors.
The selected-question regret inequality
\(0\le\max_{j\in U_t}S_j^*-S_{j_{t,r}}^*\le2e_r\)
follows directly from approximate-score maximality and the coordinate bounds supplied by the Euclidean error.
It holds uniformly over parameters and types, including exact ties and singleton unanswered sets. It establishes convergence in optimal score value without asserting stabilization of question identities.
The all-active candidate configuration has probability at least \(\varepsilon^K\). Conditional on it, a negative response has probability at least \(\varepsilon^{d_i}\), and a positive response has probability at least \(\varepsilon\), using the nonempty-parent assumption.
The total degree contribution from negative observed questions is at most \(E\), and there are at most \(m\) positive observations. Thus the conservative bound
\(P_\theta(\Gamma)\ge\varepsilon^{K+E+m}\)
is valid for consistent partial binary histories, including all augmented histories used here.
The independent edge-failure representation reproduces the specified model, including conditional independence between questions. The conditional score identity for a Bernoulli coordinate is correct, and its absolute value is bounded by \(1/\varepsilon\). Integrating along a segment proves the stated Lipschitz estimate.
These arguments concern fixed-history branches. The prover correctly avoids transferring their regularity automatically to the ranking-dependent objective.
Largest and second-largest order statistics are continuous. Under uniqueness everywhere, compactness and the finite support give a common positive gap whenever some type has multiple unanswered questions.
If \(2e_r<\Delta\), every approximate selection agrees with the exact selection. Hence eventual equality \(F_r=F\) is established.
Unique exact selections are locally constant, making \(F\) continuous. Compactness then gives attainment, and closedness of its maximizing set gives the asserted accumulation-point conclusion.
The explicit \(r_0\) bound ensures \(e_r\le\Delta/4\), including the case where the logarithmic term vanishes. The singleton-only case is handled separately.
The qualification about early indices matters: this argument establishes attainment for sufficiently large \(r\). If the task is read as requiring maximizers at every index, the finitely many earlier attainment conditions must also be assumed or verified, exactly as the prover acknowledges.
The subsequence argument for continuity is valid. Selected indices can be fixed along a further subsequence, their limits belong to the exact top sets, and compatibility makes their likelihood values equal to the prescribed exact selection’s value.
The compactness argument proving \(\omega(\delta)\to0\) is also valid. There are finitely many types and witnessing index pairs, so they can all be fixed along a subsequence. Their limiting score deficits vanish, and compatibility forces the limiting discrepancies to vanish.
Both exact and approximate selections belong to the stated near-top sets. Therefore the bound by \(\omega(2e_r)\) correctly establishes uniform convergence of \(F_r\) to \(F\). No Lipschitz dependence on score vectors is assumed or needed in this argument.
Finite iterates are continuous in \(\theta\). The finite-iterate tie condition ensures that any limiting selected branch has likelihood no greater than the branch chosen at the limit. This proves upper semicontinuity of \(F_r\), hence attainment on the compact box.
Uniform convergence then correctly yields convergence of maximum values. The estimate
\(F(\theta_r)\ge\max_\theta F(\theta)-2d_r\)
proves that every accumulation point of maximizing parameters maximizes \(F\).
Without approximate attainment, the statements using suprema and vanishing optimization errors remain valid. The prover correctly separates these conclusions from statements involving attained maxima.
The instance satisfies the support, history, response, and parameter restrictions. Only \(Y_{12}\) is nonzero, and the listed \(\beta_i\) values are correct.
I rechecked the factor \(1/6\) in \(H_0\), the expression for \((H_0h)_3-(H_0h)_4\), and the derivative coefficient \(1/(24\alpha^2)\). They are correct. Exchange symmetry gives an exact tie at the base point, and the derivative sign yields the asserted selection change after a sufficiently small increase in \(q_3\).
Both probabilities are correct: \(9/128\) at the tie and \(27/128\) on the perturbed branch. Their unequal limits establish failure of upper semicontinuity. The prover appropriately limits this example’s conclusion to failure of regularity.
Minor issue: the implicit-function argument is written initially with \(x\) as the varying parameter, but subsequently differentiates its asymptotic remainder with respect to \(b_3\). Pointwise analyticity in \(x\) alone would not justify that differentiation.
Minimum clarification requested: state the parameter-dependent analytic implicit-function theorem being used, explicitly including the varying \(b\)-coordinates, and specify that the remainder has the required local derivative control in \(b_3\). This is a routine clarification of the cited theorem application; it does not require a new argument.
The arithmetic counts are consistent with precomputing comparisons, exploiting two-coordinate features in each gradient, and sharing conditional question probabilities across types during candidate enumeration. Dependence is correctly on actual support size \(\tau\), rather than the number of possible types.
The iteration bound and its numerical dependence on \(M/\alpha\) are correctly stated. These are exact-real-arithmetic evaluation bounds, with transcendental evaluations counted as operations; they do not establish polynomial bit complexity or an algorithm for global outer optimization.
The descriptions of the conditional conclusions agree with [BiO-HMC, Theorem 1](https://ojs.aaai.org/index.php/AAAI/article/view/38820/42782) and [Franceschi et al., Theorem 3.2](https://proceedings.mlr.press/v80/franceschi18a/franceschi18a.pdf). The latter requires compactness, joint continuity, unique bounded inner solutions, uniform Lipschitz dependence on inner variables, and uniform inner convergence. The prover supplies independent ranking-specific arguments rather than asserting that all these hypotheses automatically hold here.
The requested conditional convergence result is established. The sole issue is an expositional clarification in the additional counterexample. The output does not classify the computational complexity of the continuous global optimization problem.
⟨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.