Answer: A deterministic algorithm running in time \(\operatorname{poly}(m,\tau,L,1/\varepsilon)\) returns a rational budget-feasible vector satisfying all the requested \((1-1/e)\) multiplicative and \(\varepsilon\) additive guarantees.
Theorem 3.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a feasible set of target values $W_1...W_n$, Algorithm \ref{alg:multi-submodular} outputs a set $S$ such that $f_i(S) \geq (1-\epsilon)\left(1 - \frac{m}{k(1 +\epsilon')\epsilon^3}\right)\left(1 - \frac{1}{e}\right)W_i - \epsilon$ with probability at least $1-\delta$. Asymptotically as $k\to\infty$, the approximation ratio can be set to approach $1 - 1/e$ so long as $m= o(k \log^3 k)$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses μ_t summing to \(1\), group memberships \(a_{gt}\), rational contact rates λ_{tu}, a seed budget β, and feasible group targets \(W_g\), choose seed fractions \(x_t\in[0,1]\) with \(\sum_t \mu_t x_t\le\beta\). Define \(z_t^{(0)}=x_t\), \(z_u^{(q+1)}=x_u+(1-x_u)(1-\exp(-\sum_t\mu_t\lambda_{tu}z_t^{(q)}))\), and \(\Phi_g(x)=\sum_t\mu_t a_{gt}z_t^{(\infty)}/\sum_t\mu_t a_{gt}\). Maximize \(\sum_t\mu_t z_t^{(\infty)}\) subject to \(\Phi_g(x)\ge W_g\); for additive error \(\varepsilon>0\), determine the complexity of returning an \(x\) with \(\Phi_g(x)\ge W_g-\varepsilon\) for every group and total influence within \(\varepsilon\) of optimum, as a function of \(\tau,r,L,1/\varepsilon\).
A society is given by its support: \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) counts listed types, not all possible types.
There are \(m=r\geq1\) groups, with memberships \(a_{gt}\in\{0,1\}\); each type belongs to at least one group and each group has positive mass. Groups may overlap.
Inputs include binary-rational directed contact rates \(\lambda_{tu}\geq0\), budget \(0<\beta\leq1\), targets \(W_g\in[0,1]\), and precision \(0<\varepsilon<1\). Let \(L\) be the total input bit length.
For \(x\in[0,1]^\tau\) with \(\sum_t\mu_tx_t\leq\beta\), define \(z_t^{(0)}=x_t\) and \(z_u^{(q+1)}=x_u+(1-x_u)(1-\exp(-\sum_t\mu_t\lambda_{tu}z_t^{(q)}))\).
Define \(z^{(\infty)}\) as this sequence's coordinatewise limit, \(I(x)=\sum_t\mu_tz_t^{(\infty)}\), and \(\Phi_g(x)=\frac{\sum_t\mu_ta_{gt}z_t^{(\infty)}}{\sum_t\mu_ta_{gt}}\).
Promise that some budget-feasible \(x\) satisfies every \(\Phi_g(x)\geq W_g\); let \(\mathrm{OPT}\) be the supremum of \(I(x)\) over these points.
Does a randomized algorithm, polynomial in \(m=r,\tau,L,1/\varepsilon\), return a rational budget-feasible \(x\) satisfying simultaneously \(\Phi_g(x)\geq(1-1/e)W_g-\varepsilon\) for every group and \(I(x)\geq(1-1/e)\mathrm{OPT}-\varepsilon\), with probability at least \(2/3\), or is attaining this guarantee NP-hard?
Discrete multiobjective monotone submodular maximization with promised feasible targets admits a randomized oracle approximation whose simultaneous factor approaches \(1-1/e\) in the large-budget, few-objective regime. [Verified guarantee](https://www.ijcai.org/proceedings/2019/0831.pdf)
No result settling this exponential fixed-point mass model was located.
The requested guarantee is achievable in deterministic polynomial time. In particular, a randomized algorithm can achieve it with probability \(1\).
The proof has two essential ingredients:
The argument applies to arbitrarily overlapping groups and uses only the \(\tau\) listed types.
Write
\[
\]
\(A_{ut}=\mu_t\lambda_{tu}\), and define
\(T_x(z)_u=1-(1-x_u)\exp(-(Az)_u)\).
Thus the prescribed iteration is \(z^{(0)}=x\) and \(z^{(q+1)}=T_x(z^{(q)})\). Below, denote its limit by \(Z(x)\).
The map \(T_x\) is coordinatewise increasing on \([0,1]^\tau\), maps this cube into itself, and satisfies \(T_x(x)\geq x\). Consequently, the sequence is increasing and bounded, so \(Z(x)\) exists. Continuity gives \(T_x(Z(x))=Z(x)\).
Let \(F_0(x)=I(x)\) and \(F_g(x)=\Phi_g(x)\) for \(1\leq g\leq m\). Each \(F_j\) is a convex combination of the coordinates of \(Z(x)\); hence \(0\leq F_j(x)\leq1\).
For each root type \(u\), construct a multitype branching tree as follows. Independently for every vertex of type \(v\), its number of children of type \(t\) is Poisson with mean \(A_{vt}\). Independently mark every type-\(t\) vertex with probability \(x_t\).
Let \(p_u^{(q)}(x)\) be the probability that the tree rooted at type \(u\) contains a marked vertex within depth \(q\). At depth zero this probability is \(x_u\). The Poisson probability-generating function gives
\(p_u^{(q+1)}(x)=1-(1-x_u)\exp\!\left(-\sum_t A_{ut}p_t^{(q)}(x)\right).\)
Therefore \(p^{(q)}(x)=z^{(q)}(x)\). Taking increasing limits,
\(Z_u(x)=\Pr(\text{the tree rooted at type }u\text{ contains a marked vertex}).\)
For any finite tree with \(N_t\) vertices of type \(t\), its conditional activation probability is
\(h_N(x)=1-\prod_t(1-x_t)^{N_t}.\)
This representation yields two properties needed below.
Every finite-depth activation probability is coordinatewise increasing in \(x\). Taking limits shows that \(Z_u\), and therefore every \(F_j\), is coordinatewise increasing.
For a finite tree, \(s\mapsto h_N(sx)\) is concave on \([0,1]\). Indeed, differentiating twice gives a sum of nonpositive terms. Since \(h_N(0)=0\),
\(h_N(sx)\geq s\,h_N(x)\qquad(0\leq s\leq1).\)
Apply this inequality to each finite-depth tree and then take expectations and increasing limits. For every \(x\in[0,1]^\tau\),
\[Z_u(sx)\geq sZ_u(x),\qquad F_j(sx)\geq sF_j(x). \tag{1}\]
This proof includes seed vectors with zero coordinates.
We first prove a value-oracle result.
Lemma. Given rational \(x\in(0,1)^\tau\) and rational \(0<\xi<1\), one can compute rational approximations to all coordinates of \(Z(x)\), each with additive error at most \(\xi\), in time polynomial in the encoding lengths of \(A,x\), in \(\tau\), and in \(\log(1/\xi)\).
Suppose \(p,q\in[0,1]^\tau\) are fixed points of \(T_x\). They satisfy \(p,q\geq x>0\).
If \(\theta=\max_u p_u/q_u>1\), then \(p\leq\theta q\). For \(a\geq0\),
\(1-e^{-\theta a}\leq\theta(1-e^{-a}).\)
Extend the formula defining \(T_x\) to nonnegative vectors. Monotonicity and the preceding inequality give
\(p=T_x(p)\leq T_x(\theta q)\leq\theta T_x(q)-(\theta-1)x=\theta q-(\theta-1)x.\)
At a coordinate attaining \(p_u/q_u=\theta\), this is a contradiction. Thus \(p\leq q\). Interchanging them gives \(p=q\).
Furthermore, every \(z\in[0,1]^\tau\) satisfying \(z\leq T_x(z)\) is dominated by \(Z(x)\): iteration from \(z\) increases to a fixed point, which must be the unique one.
Fix rational \(0<\kappa<1\), and define
\(K_\kappa=\left\{z\in[0,1-\kappa]^\tau: -\log(1-z_u)-(Az)_u+\log(1-x_u)\leq0\ \text{for every }u\right\}.\)
Each displayed constraint is convex. Moreover, it is equivalent to \(z_u\leq T_x(z)_u\). Thus every \(z\in K_\kappa\) satisfies \(z\leq Z(x)\).
The map \(T_x\) is concave in its argument. Hence
\(T_x((1-\kappa)Z(x))\geq(1-\kappa)T_x(Z(x))+\kappa T_x(0)\geq(1-\kappa)Z(x).\)
Consequently,
\[(1-\kappa)Z(x)\in K_\kappa. \tag{2}\]
We can therefore approximate every coordinate of \(Z(x)\) by approximately maximizing \(\sum_u z_u\) over this convex set.
Put
\(x_{\min}=\min_u x_u,\qquad s=\min\{x_{\min},1-\kappa\},\qquad c=(s/2)\mathbf1.\)
The box \([0,s]^\tau\) lies in \(K_\kappa\), because \(z_u\leq x_u\) and \(Az\geq0\) there. In particular, \(K_\kappa\) contains the Euclidean ball of radius \(s/4\) around \(c\). It is contained in the ball of radius \(\tau\) around \(c\). These radii have polynomial encoding length.
Here is an explicit weak separation oracle. Write
\(G_u(z)=-\log(1-z_u)-(Az)_u+\log(1-x_u).\)
At \(c\),
\(G_u(c)\leq\log\!\left(\frac{1-x_u}{1-s/2}\right)\leq-x_u/2\leq-\sigma,\qquad \sigma=x_{\min}/2.\)
For a query point \(y\) outside \([0,1-\kappa]^\tau\), a violated box inequality gives an exact separating hyperplane. Otherwise, for requested distance accuracy \(\theta>0\), approximate every \(G_u(y)\) within
\(\rho=\theta\sigma/(4\tau).\)
If some approximation exceeds \(\rho\), then \(G_u(y)>0\). Its gradient is the rational vector
\(\nabla G_u(y)=\frac{1}{1-y_u}e_u-A_{u\cdot}.\)
By convexity, this vector strictly separates \(y\) from \(K_\kappa\).
If all approximations are at most \(\rho\), then every \(G_u(y)\leq2\rho\). Set
\(a=\frac{2\rho}{\sigma+2\rho},\qquad \widetilde y=(1-a)y+ac.\)
Convexity gives \(G_u(\widetilde y)\leq0\), so \(\widetilde y\in K_\kappa\). Also,
\(\|y-\widetilde y\|_2\leq a\tau\leq2\rho\tau/\sigma=\theta/2.\)
Thus the oracle either returns a rational separating hyperplane or correctly certifies distance at most \(\theta\).
All these computations have polynomial bit complexity. In particular, logarithms of positive rationals can be computed to absolute error \(\rho\) in time polynomial in their encoding length and \(\log(1/\rho)\). One elementary construction uses range reduction and
\(\log v=2\sum_{k=0}^{\infty}\frac{t^{2k+1}}{2k+1},\qquad t=\frac{v-1}{v+1},\qquad 1\leq v\leq2,\)
for which \(0\leq t\leq1/3\) and the truncation error decreases geometrically.
We now use the standard weak-separation/weak-optimization theorem: for a compact convex body with known rational inner and outer balls and a polynomial-time weak separation oracle, linear optimization can return a rational point within distance \(\delta\) of the body and within additive \(\delta\) of the optimal objective, in polynomial time in the relevant encoding lengths and \(\log(1/\delta)\). This is the Grötschel–Lovász–Schrijver theorem. [Geometric Algorithms and Combinatorial Optimization](https://link.springer.com/book/10.1007/978-3-642-78240-4).
Every hypothesis has been verified above. If the theorem is formulated relative to the inner parallel body, the stated version follows by moving each feasible point toward \(c\): a movement fraction \(a\) creates an interior ball of radius \(a(s/4)\), while changing the objective by at most \(a\tau\).
Weakly maximize \(\sum_u z_u\) over \(K_\kappa\), obtaining rational \(y\) with
\(\operatorname{dist}(y,K_\kappa)\leq\delta,\qquad \sum_u y_u\geq\max_{z\in K_\kappa}\sum_u z_u-\delta.\)
Choose \(v\in K_\kappa\) with \(\|y-v\|_2\leq\delta\). Since \(v\leq Z(x)\), equation (2) implies
\(\sum_u(Z_u(x)-v_u)\leq\tau\kappa+(\tau+1)\delta.\)
Every summand is nonnegative, so, coordinatewise,
\(|Z_u(x)-y_u|\leq\tau\kappa+(\tau+2)\delta.\)
Taking \(\kappa=\xi/(2\tau)\) and \(\delta=\xi/(2(\tau+2))\) proves the lemma.
Because each \(F_j\) is a convex combination of these coordinates, the same oracle approximates every objective within \(\xi\), without any dependence on the reciprocal of a group’s mass.
Set
\(\eta=\varepsilon/4,\qquad u_t=\min\{1,\beta/\mu_t\},\qquad d=\eta/(2\tau),\qquad b_t=d\,u_t.\)
Every budget-feasible original seed vector satisfies \(x_t\leq u_t\). Introduce the rational polytope
\(Q=\left\{w\in[0,1]^\tau:\sum_t\mu_tu_tw_t\leq\beta\right\},\)
and define the regularized seed vector and objectives by
\(x(w)=b+(1-\eta)(u_t w_t)_t,\qquad f_j(w)=F_j(x(w)).\)
Since \(\mu_tu_t\leq\beta\),
\(\sum_t\mu_tb_t\leq\eta\beta/2.\)
Consequently, every \(w\in Q\) gives a budget-feasible seed vector:
\[\sum_t\mu_tx_t(w)\leq\eta\beta/2+(1-\eta)\beta=(1-\eta/2)\beta\leq\beta. \tag{3}\]
Throughout the entire cube,
\(d\,u_t\leq x_t(w)\leq1-\eta/2.\)
Thus all value-oracle queries use strictly positive seeds strictly below \(1\).
On an infinite branching tree, strictly positive seed probabilities make the probability of no marked vertex zero. Its conditional activation probability is therefore the constant \(1\).
On a finite tree, the conditional activation probability remains \(h_N(x)\). For an integer \(n\geq0\) and \(0<p<1\),
\(np(1-p)^{n-1}\leq1,\qquad n(n-1)p^2(1-p)^{n-2}\leq2.\)
These inequalities follow from the probabilities of exactly one and exactly two successes in a binomial distribution.
Differentiating \(h_N(x(w))\), these bounds imply
\(0\leq\partial_i h_N(x(w))\leq1/d,\)
and, for every pair \(i,j\),
\(-2/d^2\leq\partial_{ij}h_N(x(w))\leq0.\)
For example, the mixed derivative for distinct coordinates is the negative product of their two first-derivative factors. A repeated-coordinate derivative uses the second binomial bound.
These bounds are uniform over finite trees. On a neighborhood of the cube, the seed probabilities remain strictly between zero and one, with comparable bounds. Dominated differentiation therefore applies to the branching-tree expectations. It follows that every \(f_j\) is twice continuously differentiable and satisfies
\[\partial_i f_j(w)\geq0,\qquad -H\leq\partial_{ij}f_j(w)\leq0,\qquad H=2/d^2. \tag{4}\]
Thus every gradient decreases coordinatewise when its argument increases. Crucially, \(H\) is polynomial in \(\tau\) and \(1/\varepsilon\), independently of \(\beta\), the masses, and the contact rates.
For any original feasible \(x^*\), put \(w_t^*=x_t^*/u_t\). Then \(w^*\in Q\), and monotonicity together with (1) gives
\[f_j(w^*)=F_j(b+(1-\eta)x^*)\geq(1-\eta)F_j(x^*). \tag{5}\]
In particular, defining \(U_g=(1-\eta)W_g\), the promise ensures that some \(w^*\in Q\) satisfies every \(f_g(w^*)\geq U_g\).
For any \(w,w^*\in[0,1]^\tau\), equations (4) imply
\[\nabla f_j(w)\cdot w^*\geq f_j(w^*)-f_j(w). \tag{6}\]
To verify this, let \(r=(w^*-w)_+\). Along the increasing segment from \(w\) to \(w\vee w^*\), diminishing returns gives
\(f_j(w\vee w^*)-f_j(w)\leq\nabla f_j(w)\cdot r.\)
Monotonicity gives \(f_j(w\vee w^*)\geq f_j(w^*)\). Finally, \(r\leq w^*\) and \(\nabla f_j(w)\geq0\), proving (6).
Choose
\(\gamma=\varepsilon/(64\tau),\qquad \nu=\varepsilon/64,\qquad N=\left\lceil4H\tau^2/\varepsilon\right\rceil.\)
Start with \(w^{(0)}=0\). At iteration \(k\), obtain rational estimates satisfying
\(\|\widehat a_j-\nabla f_j(w^{(k)})\|_\infty\leq\gamma,\qquad |\widehat f_g-f_g(w^{(k)})|\leq\nu.\)
These estimates are computable in polynomial time. For gradients, use a forward or backward coordinate difference whose endpoints remain in the cube. With step \(h\leq\gamma/(2H)\), its truncation error is at most \(Hh/2\). Evaluating each endpoint within \(\gamma h/8\) adds at most \(\gamma/4\) error. The remaining margin permits rounding to a fixed dyadic precision.
Solve the rational linear program
\(\max_{v\in Q}\widehat a_0\cdot v\)
subject to
\[\widehat a_g\cdot v\geq U_g-\widehat f_g-(\tau\gamma+\nu),\qquad 1\leq g\leq m. \tag{7}\]
Choose a rational optimal basic solution \(v^{(k)}\), and update
\(w^{(k+1)}=w^{(k)}+v^{(k)}/N.\)
The linear program is always feasible. Indeed, any comparison point \(w^*\in Q\) satisfying the regularized group targets obeys (6), so
\(\widehat a_g\cdot w^*\geq U_g-f_g(w^{(k)})-\tau\gamma \geq U_g-\widehat f_g-(\tau\gamma+\nu).\)
Moreover,
\(w^{(k)}=\frac1N\sum_{\ell<k}v^{(\ell)}.\)
Since \(Q\) is convex and contains zero, every iterate lies in \(Q\), and the update segments lie in the cube.
Return the rational vector \(x(w^{(N)})\).
Write \(w=w^{(k)}\) and \(v=v^{(k)}\).
For each group, equation (7) and the approximation errors give
\[\nabla f_g(w)\cdot v\geq U_g-f_g(w)-2\tau\gamma-2\nu. \tag{8}\]
For the objective, let \(x^*\) be any original seed vector satisfying the budget and all original targets, and let \(w^*\) be its comparison point. This point is feasible in (7). Optimality of \(v\), followed by (6), gives
\[\nabla f_0(w)\cdot v \geq\widehat a_0\cdot v-\tau\gamma \geq\widehat a_0\cdot w^*-\tau\gamma \geq f_0(w^*)-f_0(w)-2\tau\gamma. \tag{9}\]
Taylor’s theorem and (4), using \(0\leq v_i\leq1\), yield
\[f_j(w+v/N)\geq f_j(w)+\frac1N\nabla f_j(w)\cdot v-\frac{H\tau^2}{2N^2}. \tag{10}\]
Let \(\alpha_N=1-(1-1/N)^N\), so \(\alpha_N\geq1-1/e\). Iterating the recurrences obtained from (8)–(10), and using \(f_j(0)\geq0\), gives
\(f_g(w^{(N)})\geq\alpha_N U_g-(2\tau\gamma+2\nu)-\frac{H\tau^2}{2N},\)
and
\(f_0(w^{(N)})\geq\alpha_N f_0(w^*)-2\tau\gamma-\frac{H\tau^2}{2N}.\)
Our choices ensure
\(2\tau\gamma+2\nu=\varepsilon/16,\qquad 2\tau\gamma=\varepsilon/32,\qquad H\tau^2/(2N)\leq\varepsilon/8.\)
Using \(U_g=(1-\eta)W_g\), \(W_g\leq1\), and \(\eta=\varepsilon/4\), we obtain
\(\Phi_g(x(w^{(N)})) \geq(1-1/e)W_g-\frac{7\varepsilon}{16} \geq(1-1/e)W_g-\varepsilon.\)
For the objective, equation (5) applies to every original feasible comparison point. Taking the supremum over these points therefore gives, without assuming that the supremum is attained,
\(I(x(w^{(N)})) \geq\alpha_N(1-\eta)\mathrm{OPT}-\varepsilon/32-\varepsilon/8 \geq(1-1/e)\mathrm{OPT}-\frac{13\varepsilon}{32} \geq(1-1/e)\mathrm{OPT}-\varepsilon.\)
Budget feasibility follows exactly from (3).
Here \(H=128\tau^2/\varepsilon^2\), so the number of iterations is
\(N=O(\tau^4/\varepsilon^3).\)
Each iteration uses polynomially many value-oracle calls and one rational linear program with \(\tau\) variables and \(m\) group constraints.
The oracle’s required accuracy for finite differences is inverse-polynomial in \(\tau\) and \(1/\varepsilon\). Its running time depends polynomially on the logarithm of that accuracy. Its geometric bounds also have polynomial encoding length: in particular, \(u_t\geq\beta\), so all queried seed coordinates are at least \(d\beta\).
Round value and gradient estimates to fixed dyadic precisions sufficient for the prescribed errors. By the derivative bound \(1/d\), the resulting linear-program coefficients have uniformly polynomial bit length. An optimal basic solution consequently has polynomial bit length. Summing the \(N\) update vectors increases encoding length by at most a polynomial factor.
Thus every query, linear program, iterate, and final seed vector has polynomial encoding length, and the complete algorithm runs in time polynomial in \(m,\tau,L,1/\varepsilon\).
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance and establishes the requested polynomial-time guarantee. I found no major mathematical issue. One minor precision specification should be made explicit to turn the finite-difference prescription into a fully specified polynomial-time algorithm.
The matrix orientation is consistent: \(A_{ut}=\mu_t\lambda_{tu}\) reproduces the prescribed incoming contact sum.
The map \(T_x\) preserves the cube, is coordinatewise increasing, and satisfies \(T_x(x)\geq x\). Thus the specified iteration increases to a limit, and continuity makes that limit a fixed point. The normalized group weights are legitimate convex-combination weights because every group has positive mass.
The branching-tree recurrence agrees exactly with the iteration. Each finite-depth tree is finite almost surely, since all Poisson means are finite. Increasing depth therefore gives the asserted probability of encountering a marked vertex, including when the full tree is infinite.
Conditional finite-tree activation is \(h_N(x)=1-\prod_t(1-x_t)^{N_t}\). It is increasing in every coordinate. Along \(sx\), the second derivative is nonpositive: differentiating the product twice produces nonnegative terms, which acquire a minus sign in \(h_N\).
Consequently, the stated concavity inequality follows from \(h_N(0)=0\). Expectations and increasing depth limits preserve it. This establishes equation (1) even when some seeds vanish. No continuity at zero seeds is assumed.
The uniqueness argument correctly uses positivity of every seed coordinate. At a coordinate attaining the maximal ratio \(\theta>1\), the term \((\theta-1)x_u>0\) gives the required contradiction. Iteration from any subsolution increases to a fixed point, so uniqueness proves its domination by \(Z(x)\).
The logarithmic constraints defining \(K_\kappa\) have the correct sign and are equivalent to the subsolution inequalities. Each is convex. Concavity of \(T_x\) verifies equation (2), and the imposed upper coordinate bound is satisfied.
The proposed inner box, inner ball, and outer ball are valid. The strict-slack estimate at \(c\) also holds. In the separation branch, convexity makes the rational gradient a separating normal; strict negativity at \(c\) ensures that this normal cannot vanish when the queried constraint is positive. In the acceptance branch, the interpolation calculation establishes actual distance at most \(\theta/2\).
The weak-separation-to-weak-optimization result is applicable to this compact, full-dimensional, explicitly bounded convex body. The distance and objective guarantees stated by the prover agree with the weak-oracle framework in the [original Grötschel–Lovász–Schrijver paper](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1981a.pdf). The required geometric parameters have polynomial encoding length, even when the inner radius is numerically very small.
Finally, the coordinate-recovery calculation is correct. Since \(v\leq Z(x)\), the bound on the sum of coordinate deficits bounds each deficit individually. Adding the distance from \(y\) to \(v\) gives precisely \(\tau\kappa+(\tau+2)\delta\). The stated choices yield error at most \(\xi\).
Every budget-feasible original vector satisfies \(x_t\leq u_t\). The baseline spends at most \(\eta\beta/2\), and equation (3) proves exact budget feasibility.
The bounds \(du_t\leq x_t(w)\leq1-\eta/2\) hold throughout the cube. Thus all algorithmic oracle queries lie in the domain of the value-oracle lemma.
Conditional on an infinite tree, the probability of no mark is zero because there are finitely many types and every seed probability is positive. Its activation function is therefore constant on the positive-seed domain.
For finite trees, the binomial bounds give the claimed first- and second-derivative bounds after rescaling. Both repeated and distinct coordinate derivatives are nonpositive. A neighborhood of the cube remains inside the positive-seed domain with uniform comparable bounds, so dominated differentiation justifies the asserted continuous differentiability of the expectations.
Equation (5) correctly preserves every original comparison vector. Neither the contact rates nor reciprocal group masses enter the resulting derivative bounds.
The segment from \(w\) to \(w\vee w^*\) stays in the cube. The Hessian signs imply that gradients decrease along this increasing segment. Monotonicity and \((w^*-w)_+\leq w^*\) then establish equation (6).
The promised comparison vector satisfies every approximate group constraint in equation (7), with the error allowances having the correct signs. The linear program is therefore feasible.
Each iterate is a convex combination of previously chosen vectors and zero. This proves membership in \(Q\), including along each update segment.
The one-sided difference truncation bound \(Hh/2\) is correct. Two endpoint errors of at most \(\gamma h/8\) contribute at most \(\gamma/4\) to the derivative error, leaving room for rounding.
Minor issue: the instruction specifies only \(h\leq\gamma/(2H)\). An arbitrarily small rational satisfying this inequality could require excessive encoding length and excessive value-oracle precision. Section 8’s assertion that the required accuracy is inverse-polynomial implicitly assumes a controlled choice of \(h\).
Minimum clarification: specify a positive rational step with polynomial encoding length and \(\log(1/h)\) bounded polynomially in the stated parameters, and specify how the forward or backward direction is chosen to keep its endpoint in the cube. This is a routine numerical specification; it requires no new mathematical argument.
Rechecking the error propagation gives exactly the losses claimed in equations (8) and (9). Taylor’s theorem gives the remainder \(H\tau^2/(2N^2)\), since every direction coordinate lies in \([0,1]\).
The recurrence solutions and \(\alpha_N\geq1-1/e\) are correct. The constants also check:
These yield the stated total losses \(7\varepsilon/16\) and \(13\varepsilon/32\), respectively.
The objective argument holds for every originally feasible comparison vector. Taking its supremum is therefore legitimate and does not require attainment of \(\mathrm{OPT}\).
The values \(H=128\tau^2/\varepsilon^2\) and \(N=O(\tau^4/\varepsilon^3)\) are correct. The bound \(u_t\geq\beta\) ensures polynomial encoding length for the oracle’s geometric parameters.
Fixed-precision estimates give rational linear programs with polynomial coefficient lengths. Their bounded feasible regions admit optimal basic solutions of polynomial encoding length. Accumulating polynomially many such solutions preserves polynomial encoding length.
The algorithm addresses all listed types, arbitrary group overlap, every promised feasible target vector, and the objective simultaneously. Its deterministic guarantee implies the required success probability.
⟨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.