Answer: Polynomial-time solvable in \(m,\tau,L,\log(1/\epsilon)\). The specified item-block dynamics have conditioning-dependent geometric convergence of the expected extrapolated gap, but can require exponentially many updates for fixed accuracy.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven an initial iterate x0 and stepsizes η0 j = 1/Lj, ∀j satisfying (4), let xk be the random iterates gener- ated by Algorithm 1. Then, E F(xk+1) −F ∗≤(1 −ρ)k F(x0) −F ∗ , (7) where ρ = min n µ mLmaxθ2(A,C), 1 m o and Lmax = maxj Lj. Karimi, Nutini, and Schmidt (2016) also develop a block- coordinate method that applies to EG. Unlike their result, our result admits larger stepsizes that can vary per block, as well as a line search strategy, which is helpful for practical performance as we show in Section 8.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) goods and \(\tau\) buyer types with rational masses \(\mu_t>0\), per-capita budgets \(B_t>0\), and linear valuations \(v_t\in\mathbb{Q}_{\ge 0}^m\), compute a feasible allocation \(x_t\ge 0\) with objective gap at most \(\epsilon\) for the mass-weighted EG program \( \max_x \sum_t \mu_t B_t \log(v_t^\top x_t) \), subject to \( \sum_t \mu_t x_{tj}\le 1 \) for each good. Characterize the expected convergence and running time of item-block updates in \(m\), \(\tau\), input bit length, and conditioning parameters.
A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\tau\) is the support size, not the number of possible types. Assume \(\sum_t\mu_t=1\), \(m,\tau\ge1\), binary-rational per-capita budgets \(B_t>0\), and valuations \(v_t\in\mathbb Q_{\ge0}^m\setminus\{0\}\); each good has unit supply.
An allocation \(x_t\in\mathbb R_{\ge0}^m\) is per capita. Define \(X=\{x\ge0:\sum_t\mu_t x_{tj}\le1\text{ for every }j\}\), \(G(x)=\sum_t\mu_t B_t\log(v_t^\top x_t)\), and \(G^\star=\max_{x\in X}G(x)\), with \(\log0=-\infty\). The accuracy input is binary-rational \(0<\epsilon<1\); \(L\) is the total input bit length.
For item-block dynamics, put \(W=\sum_t\mu_t B_t\), \(a_t=(B_t/W)\sum_jv_{tj}\), and \(\widetilde f(x)=\sum_t h_t(v_t^\top x_t)\), where \(h_t(u)=-\mu_t B_t\log u\) for \(u\ge a_t\), and \(h_t(u)=-\mu_t B_t\log a_t-(\mu_t B_t/a_t)(u-a_t)+(\mu_t B_t/(2a_t^2))(u-a_t)^2\) otherwise.
Start from \(x^0_{tj}=B_t/W\). At each step independently sample an item uniformly and update only its column by \(x^+_{\cdot j}=\operatorname{Proj}_{K_\mu}(x_{\cdot j}-L_j^{-1}\nabla_{\cdot j}\widetilde f(x))\), where projection is Euclidean, \(K_\mu=\{z\ge0:\sum_t\mu_t z_t\le1\}\), and \(L_j=\max_t\mu_t B_t v_{tj}^2/a_t^2\). Leave a column unchanged when \(L_j=0\).
Is computing a rational \(x\in X\) with \(G^\star-G(x)\le\epsilon\) polynomial-time in \(m,\tau,L,\log(1/\epsilon)\), or is it NP-hard?
What expected convergence and bit running time do these item-block updates yield for this accuracy, in \(m,\tau,L,\epsilon\), with all conditioning dependence explicit?
For finite buyers, Nan, Gao, and Kroer establish linear convergence of the expected extrapolated objective gap for uniformly sampled item-block updates with block-specific stepsizes; the rate depends on smoothness, curvature, and a Hoffman constant. [Source](https://arxiv.org/pdf/2303.00506).
Gao and Kroer establish linear convergence of projected-gradient methods for finite linear Fisher markets under relaxed strong-convexity conditions. [Source](https://papers.nips.cc/paper_files/paper/2020/file/f75526659f31040afeb61cb7133e4e6d-Paper.pdf).
The allocation problem is polynomial-time solvable in \(m,\tau,L,\log(1/\epsilon)\).
The specified item-block updates satisfy a geometric bound on the expected extrapolated objective gap. Their rate, however, contains a numerical condition parameter that can be exponentially large in the input bit length. Indeed, even with two types, two goods, and fixed \(\epsilon=1/2\), these updates can require exponentially many iterations.
Below I prove both statements, give explicit conditioning constants, and distinguish exact rational arithmetic from an implementation with controlled rounding.
All logarithms are natural. All norms and projections are Euclidean.
Write
\( c_t=\mu_tB_t,\qquad S_t=\sum_jv_{tj},\qquad U_t=\frac{S_t}{\mu_t},\qquad R_t=\frac{U_t}{a_t}=\frac{W}{c_t}. \)
These quantities are positive. For every \(x\in X\),
\( 0\le u_t(x):=v_t^\top x_t\le U_t, \)
because feasibility implies \(x_{tj}\le1/\mu_t\).
The allocation \(x^0_{tj}=B_t/W\) is feasible and satisfies \(u_t(x^0)=a_t>0\). The set \(X\) is compact, and \(G\) is upper semicontinuous with the stipulated value at zero utility. Consequently, an optimum exists, and every optimum has positive utility for every type.
Let \(x^\star\) maximize \(G\), and write \(u_t^\star=u_t(x^\star)\). The optimality conditions give nonnegative supply multipliers \(p_j\) satisfying
\( \frac{B_tv_{tj}}{u_t^\star}\le p_j, \)
with equality whenever \(x_{tj}^\star>0\), and
\( p_j\left(1-\sum_t\mu_tx_{tj}^\star\right)=0. \)
These conditions follow either from the normal cone of the allocation polytope or from the usual convex-program optimality conditions. A strictly feasible allocation with all utilities positive exists, so the latter application is valid.
Multiplying the equality on positive coordinates by \(\mu_tx_{tj}^\star\) and summing gives
\( \sum_jp_j =\sum_jp_j\sum_t\mu_tx_{tj}^\star =\sum_tc_t =W. \)
Hence
\( \frac{B_tS_t}{u_t^\star} =\sum_j\frac{B_tv_{tj}}{u_t^\star} \le\sum_jp_j=W, \)
which proves
\( u_t^\star\ge a_t. \)
Each \(h_t\) is twice continuously differentiable, with
\( h_t''(u)= \begin{cases} c_t/a_t^2,&0\le u<a_t,\\ c_t/u^2,&u\ge a_t. \end{cases} \)
Thus \(h_t\) is strictly convex on \([0,U_t]\).
At \(x^\star\), the value and gradient of \(\widetilde f\) agree with those of \(-G\), because \(u_t^\star\ge a_t\). The first-order optimality inequality for \(-G\) therefore also holds for \(\widetilde f\). Convexity implies that \(x^\star\) minimizes \(\widetilde f\).
Strict convexity in the utility vector implies that every minimizer of \(\widetilde f\) has the same utility vector \(u^\star\). Therefore
\( X^\star:=\arg\min_{x\in X}\widetilde f(x) =\{x\in X:u(x)=u^\star\} =\arg\max_{x\in X}G(x), \)
and
\( \min_{x\in X}\widetilde f(x)=-G^\star. \)
Define the extrapolated gap by
\( \Delta(x)=\widetilde f(x)+G^\star. \)
In particular, \(\Delta(x)\ge0\).
This is the extrapolation principle used for finite Fisher markets by [Gao and Kroer](https://papers.nips.cc/paper_files/paper/2020/file/f75526659f31040afeb61cb7133e4e6d-Paper.pdf). The argument above verifies it directly for the per-capita coordinates and weighted supply constraints in this question.
The proof in this section does not use item-block dynamics.
Let
\( n=m\tau,\qquad \mu_{\min}=\min_t\mu_t,\qquad B_{\min}=\min_tB_t,\qquad \mathcal R=\frac{n}{\mu_{\min}}. \)
The set \(X\) lies in the ball of radius \(\mathcal R\) centered at the origin.
Consider the rational polytope
\( D=\{x\in X:u_t(x)\ge a_t/2\text{ for every }t\}. \)
It contains every optimizer. On \(D\), minimize the normalized objective
\( \phi(x)=-\sum_tc_t\log\frac{u_t(x)}{a_t}. \)
Its gradient is rational at every rational point of \(D\). Moreover,
\( \|\nabla\phi(x)\|_2 \le\|\nabla\phi(x)\|_1 =\sum_t\frac{c_tS_t}{u_t(x)} \le2\sum_t\frac{c_tS_t}{a_t} =2W. \)
Thus \(\phi\) is \(2W\)-Lipschitz on \(D\).
Put
\( z=\frac34x^0,\qquad r_0=\frac{B_{\min}}{4W}. \)
Since \(W\ge B_{\min}\), we have \(r_0\le1/4\). The ball of radius \(r_0\) about \(z\) lies in \(D\):
\( r_0\|v_t\|_2\le\frac{B_{\min}S_t}{4W}\le a_t/4. \)
Now choose
\( \theta=\min\left\{\frac12,\frac{\epsilon}{24W\mathcal R}\right\}, \qquad w=(1-\theta)x^\star+\theta z. \)
Convexity of \(D\) shows that the ball of radius \(\theta r_0\) about \(w\) lies in \(D\). Every point \(y\) in that ball satisfies
\( \phi(y)-\phi(x^\star) \le4W\mathcal R\theta+2W\theta r_0 \le6W\mathcal R\theta \le\epsilon/4. \)
The first term uses convexity and the Lipschitz bound between \(z\) and \(x^\star\); the second uses the Lipschitz bound inside the ball.
Apply the rational central-cut ellipsoid method, initially enclosing \(D\) in the ball of radius \(\mathcal R\).
At a center outside \(D\), use a violated rational linear constraint. At a center \(x\in D\), use the rational gradient cut
\( \nabla\phi(x)^\top(y-x)\le0. \)
If \(\phi(x)>\phi(x^\star)+\epsilon/2\), this cut retains the entire ball constructed above: every point of that ball has smaller objective value, and the convexity inequality implies that it satisfies the cut.
The standard rational ellipsoid volume bound therefore guarantees that within
\( O\left(n^2\left[1+\log\frac{\mathcal R}{\theta r_0}\right]\right) \)
iterations, some feasible queried center has objective gap at most \(\epsilon/2\). Otherwise all cuts would retain a ball whose volume exceeds the final ellipsoid volume.
The hypotheses needed for the rational ellipsoid implementation hold:
For the last point, each positive rational ratio \(u_t(x)/a_t\) has polynomial encoding length. Its logarithm can be evaluated by scaling into \([1,2]\) and using the convergent series
\( \log r =2\sum_{k=0}^{\infty} \frac{((r-1)/(r+1))^{2k+1}}{2k+1}. \)
On \([1,2]\), the series parameter is at most \(1/3\), so the number of terms is linear in the desired precision. The weights \(c_t\) affect the required precision only through their encoding lengths.
Return the feasible queried center with smallest approximate objective. Its true gap is at most \(3\epsilon/4\), and hence at most \(\epsilon\).
Because
\( \log\mathcal R,\quad \log(1/r_0),\quad \log(1/\theta) \)
are polynomially bounded in \(m,\tau,L,\log(1/\epsilon)\), this proves the claimed polynomial-time rational solvability.
Define
\( \kappa_t=\frac{c_t}{U_t^2}, \qquad \kappa=\min_t\kappa_t, \qquad \Lambda=\max_jL_j, \qquad \ell=m\Lambda. \)
We have \(\kappa>0\) and \(\Lambda>0\), because every valuation vector is nonzero. Also, throughout the feasible utility box,
\( \kappa_t\le h_t''(u)\le c_t/a_t^2. \)
Consequently:
\( \max_t\frac{c_t\|v_t\|_2^2}{a_t^2}\le m\Lambda. \)
Let \(A\) be the utility matrix, so \(Ax=u(x)\), and write \(X=\{x:Cx\le d\}\), using the weighted supply constraints and nonnegativity constraints.
A relative Hoffman constant \(H\) is any constant satisfying
\( \operatorname{dist}(x,X^\star) \le H\|Ax-u^\star\|_2 \qquad(x\in X). \)
Here is an input-derived upper bound that avoids leaving \(H\) unspecified.
Let \(Q\) be the product of the denominators of all \(\mu_t\) and \(v_{tj}\), and put
\( V=\max\{1,\max_{t,j}v_{tj}\}, \qquad \overline H=Q^n(nV)^{n-1}. \)
Then \(H\le\overline H\).
To prove this, fix \(x\in X\), let \(z\) be its projection onto \(X^\star\), and put \(d_x=x-z\). Polyhedral projection optimality gives
\( d_x=A^\top\alpha+C_I^\top\beta, \qquad \beta\ge0, \)
where the constraints indexed by \(I\) are active at \(z\). Since the rows of \(A\) are independent, dependent active inequality rows can be eliminated, while maintaining nonnegative coefficients, until
\( M=\begin{bmatrix}A\\C_I\end{bmatrix} \)
has independent rows. Indeed, a dependence modulo the span of \(A\) permits subtracting a suitable multiple of that dependence from \(\beta\), eliminating at least one positive coefficient.
Writing \(\gamma=(\alpha,\beta)\), feasibility of \(x\) gives
\( \|d_x\|_2^2 =\alpha^\top(Ax-u^\star)+\beta^\top C_I(x-z) \le\|\gamma\|_2\|Ax-u^\star\|_2. \)
Also,
\( \|d_x\|_2=\|M^\top\gamma\|_2 \ge\sigma_{\min}(M)\|\gamma\|_2. \)
Thus the required bound holds with \(1/\sigma_{\min}(M)\).
If \(M\) has \(k\) rows, a nonzero \(k\)-column minor has absolute determinant at least \(Q^{-k}\). Moreover, every singular value is at most \(\|M\|_F\le nV\). Hence
\( \sigma_{\min}(M) \ge\frac{Q^{-k}}{(nV)^{k-1}}, \)
and therefore \(1/\sigma_{\min}(M)\le\overline H\), as claimed.
In particular,
\( \log_2\overline H=O(n(L+\log n)). \)
The bound is conservative, but it is explicit, rational, and has polynomial encoding length.
In what follows, \(H\) can be any certified upper bound; choosing \(H=\overline H\) makes every constant computable from the input. Define
\( \lambda=\frac{\kappa}{H^2}, \qquad \rho=\frac1m\min\left\{1,\frac{\lambda}{\Lambda}\right\}. \)
For \(x\in X\), let \(z\) be its nearest point in \(X^\star\). Strong convexity in utilities and the Hoffman inequality imply
\( \widetilde f(z) \ge\widetilde f(x) +\nabla\widetilde f(x)^\top(z-x) +\frac{\lambda}{2}\|z-x\|_2^2. \)
For a common quadratic coefficient \(\Lambda\), define
\( q_\Lambda(x)= \min_{y\in X} \left\{ \nabla\widetilde f(x)^\top(y-x) +\frac{\Lambda}{2}\|y-x\|_2^2 \right\}. \)
Taking \(y=x+s(z-x)\), where \(s=\min\{1,\lambda/\Lambda\}\), yields
\( q_\Lambda(x)\le-s\Delta(x). \)
Indeed, the previous inequality bounds the linear term by
\(-s\Delta(x)-s\lambda\|z-x\|_2^2/2\), and the quadratic term contributes
\(\Lambda s^2\|z-x\|_2^2/2\). Their squared-distance coefficient is nonpositive.
The feasible set is a product over item columns. Each exact block update minimizes its block quadratic model with coefficient \(L_j\le\Lambda\). Block smoothness and uniform sampling therefore give
\( \mathbb E[\Delta(x^{k+1})\mid x^k] \le\Delta(x^k)+\frac1m q_\Lambda(x^k) \le(1-\rho)\Delta(x^k). \)
A block with \(L_j=0\) has zero valuations throughout that column, so its model and objective change are both zero.
Consequently,
\( \boxed{\mathbb E[\Delta(x^k)] \le(1-\rho)^k\Delta(x^0).} \)
This matches the conditioning-dependent rate structure in [Nan, Gao, and Kroer, Theorem 1](https://arxiv.org/pdf/2303.00506); the proof above handles the weighted constraints directly.
The initial gap has the useful bound
\( \Delta(x^0) =G^\star-G(x^0) \le\sum_tc_t\log R_t \le W\log\tau \le(\tau-1)W. \)
For the middle inequality, \(c_t/W\) is a probability vector and the sum is \(W\) times its entropy.
If \(\tau=1\), the initial allocation is already optimal. Henceforth assume \(\tau\ge2\), and set
\( D_0=(\tau-1)W, \qquad M=D_0+\frac32W=(\tau+\tfrac12)W. \)
Since every \(h_t\) decreases on \([0,U_t]\),
\( \Delta(x)\le\widetilde f(0)+G^\star =\Delta(x^0)+\frac32W \le M \qquad(x\in X). \)
An expected bound on \(\Delta\) must not simply be identified with an expected bound on \(G^\star-G\): the objectives differ below the thresholds \(a_t\).
Strong convexity at an optimum gives the more detailed inequality
\( \Delta(x)\ge \frac12\sum_t\kappa_t(u_t(x)-u_t^\star)^2. \)
The first-order term is nonnegative by optimality.
Define
\( \delta_{\mathrm{safe}} =\min_t\frac{c_t}{8R_t^2}, \qquad R_{\max}=\max_tR_t. \)
If \(\Delta(x)\le\delta_{\mathrm{safe}}\), then
\( |u_t(x)-u_t^\star| \le U_t\sqrt{\frac{2\Delta(x)}{c_t}} \le a_t/2. \)
Thus \(u_t(x)\ge a_t/2\) for every type.
For \(a_t/2\le u<a_t\), let
\( d_t(u)=-c_t\log u-h_t(u). \)
We have \(d_t(a_t)=d_t'(a_t)=0\), and
\( 0\le d_t''(u) =\frac{c_t}{u^2}-\frac{c_t}{a_t^2} \le\frac{3c_t}{a_t^2}. \)
Integrating twice proves
\( 0\le d_t(u) \le\frac{3c_t}{2a_t^2}(a_t-u)^2. \)
Since \(u_t^\star\ge a_t\), summing and using the strong-convexity inequality yields
\( G^\star-G(x) \le(1+3R_{\max}^2)\Delta(x) \quad\text{whenever }\Delta(x)\le\delta_{\mathrm{safe}}. \)
Therefore, with
\( \delta= \min\left\{ \delta_{\mathrm{safe}}, \frac{\epsilon}{1+3R_{\max}^2} \right\}, \)
we have the certified implication
\( \boxed{\Delta(x)\le\delta \ \Longrightarrow\ G^\star-G(x)\le\epsilon.} \)
For the exact dynamics this gives
\( \Pr\{G^\star-G(x^k)>\epsilon\} \le \min\left\{1,\frac{D_0(1-\rho)^k}{\delta}\right\}. \)
An unconditional expected logarithmic guarantee can be obtained by a rational mixture with the initial allocation.
Put
\( \beta=\min\left\{\frac12,\frac{\epsilon}{2D_0}\right\}, \qquad \widehat x^k=(1-\beta)x^k+\beta x^0, \qquad C_R=\sum_tc_tR_t^2. \)
Every utility of \(\widehat x^k\) is at least \(\beta a_t\). Compare it with
\((1-\beta)x^\star+\beta x^0\). Convexity of \(-G\), the derivative bound for logarithms above \(\beta a_t\), and Cauchy–Schwarz give
\( G^\star-G(\widehat x^k) \le \beta D_0+ \frac{1-\beta}{\beta}\sqrt{2C_R\Delta(x^k)}. \)
The Cauchy–Schwarz calculation used here is
\( \sum_t\frac{c_t|u_t(x)-u_t^\star|}{a_t} \le \sqrt{\sum_t\kappa_t(u_t(x)-u_t^\star)^2} \sqrt{\sum_t\frac{c_t^2}{a_t^2\kappa_t}} \le\sqrt{2C_R\Delta(x)}. \)
Taking expectations and applying Jensen’s inequality proves
\( \mathbb E[G^\star-G(\widehat x^k)] \le \beta D_0+ \frac{1-\beta}{\beta}\sqrt{2C_RD_0}\,(1-\rho)^{k/2}. \)
In particular, expected gap at most \(\epsilon\) follows whenever
\( k\ge \frac1\rho \log^+\left(\frac{8C_RD_0}{\epsilon^2\beta^2}\right), \)
where \(\log^+r=\max\{0,\log r\}\).
For a guarantee that holds for every returned allocation, define
\( \mathcal C(x)= \max_{z\in X}\nabla\widetilde f(x)^\top(x-z). \)
Convexity gives \(\Delta(x)\le\mathcal C(x)\). If \(g=\nabla\widetilde f(x)\), then \(g_{tj}\le0\), and the product structure of \(X\) gives the exact rational formula
\( \mathcal C(x) = \sum_{t,j}g_{tj}x_{tj} + \sum_j\max_t\frac{-g_{tj}}{\mu_t}. \)
Thus the stopping test \(\mathcal C(x)\le\delta\) requires no logarithmic evaluations.
Let \(D_X=2\mathcal R\), an upper bound on the diameter of \(X\). Smoothness, optimality, and the Hoffman inequality imply
\( \mathcal C(x) \le \Delta(x)+\ell D_X\sqrt{\frac{2\Delta(x)}{\lambda}}. \)
For completeness, take a nearest optimum \(z\) and a minimizer \(y\) of the linear function \(g^\top y\) over \(X\). Decompose
\( g^\top(x-y) =(g-\nabla\widetilde f(z))^\top(x-y) +\nabla\widetilde f(z)^\top(x-z) +\nabla\widetilde f(z)^\top(z-y). \)
The three terms are bounded respectively by
\(\ell D_X\|x-z\|_2\), \(\Delta(x)\), and zero. Finally,
\(\|x-z\|_2\le\sqrt{2\Delta(x)/\lambda}\).
Define
\( \eta= \min\left\{ \frac{\delta}{2}, \frac{\lambda\delta^2}{8\ell^2D_X^2} \right\}. \)
Then
\( \Delta(x)\le\eta \ \Longrightarrow\ \mathcal C(x)\le\delta \ \Longrightarrow\ G^\star-G(x)\le\epsilon. \)
For exact updates stopped at the first passing certificate, Markov’s inequality gives expected iteration count
\( O\left( \frac{1+\log^+(D_0/\eta)}{\rho} \right). \)
Indeed, the probability of not having stopped by iteration \(k\) is at most
\(\min\{1,D_0(1-\rho)^k/\eta\}\); summing these tails proves the bound.
For a rational vector \(y\), Euclidean projection onto \(K_\mu\) has the form
\( z_t=\max\{0,y_t-\gamma\mu_t\}. \)
If \(\sum_t\mu_t\max\{0,y_t\}\le1\), then \(\gamma=0\). Otherwise, for the positive-coordinate set \(I\),
\( \gamma= \frac{\sum_{t\in I}\mu_ty_t-1} {\sum_{t\in I}\mu_t^2}. \)
Sorting the breakpoints \(y_t/\mu_t\) identifies \(I\) in
\(O(\tau\log(\tau+1))\) rational arithmetic operations. All derivatives are rational:
\( h_t'(u)= \begin{cases} -c_t/u,&u\ge a_t,\\ c_t(u-2a_t)/a_t^2,&0\le u<a_t. \end{cases} \)
Hence every exact iterate is rational.
However, a constant arithmetic-operation count is not a constant bit cost. Utility reciprocals and the projection can enlarge denominators. Using a common denominator for the current allocation gives the conservative encoding-length recurrence
\( b_{k+1} \le C(\tau+1)b_k+\operatorname{poly}(m,\tau,L) \)
for a universal constant \(C\). To see this, each utility numerator has size
\(O(b_k+\operatorname{poly}(L))\); a common denominator for the updated column can include the product of at most \(\tau\) such numerators, followed by the rational projection denominator.
Thus a \(K\)-step exact run has a valid bit-time upper bound
\( (C(\tau+1))^{O(K)}\operatorname{poly}(m,\tau,L). \)
One way to obtain a guaranteed output with this bound in expectation is to run independent exact trials of length
\( K= \left\lceil \frac1\rho\log\frac{4M}{\eta} \right\rceil, \)
accepting a trial only when its final certificate passes. Its expected extrapolated gap is at most \(\eta/4\), so acceptance probability is at least \(3/4\). The number of trials has bounded expectation.
This is a conservative bound, not a claim that exact denominators always grow at that rate. It explains why the geometric iteration theorem alone is insufficient for a polynomial bit-time conclusion.
A substantially better bit bound follows with one explicit modification: after an exact block update, round each updated coordinate downward to a dyadic grid of spacing \(q=2^{-b}\). Downward rounding preserves feasibility.
On all of \(X\),
\( \|\nabla\widetilde f(x)\|_2 \le\|\nabla\widetilde f(x)\|_1 \le2W=:J. \)
Rounding changes the updated block by norm at most \(\tau q\). Therefore the rounded process satisfies
\( \mathbb E[\Delta(x^{k+1})\mid x^k] \le(1-\rho)\Delta(x^k)+J\tau q. \)
Choose
\( b= \left\lceil \log_2^+\frac{4J\tau}{\rho\eta} \right\rceil. \)
Then \(J\tau q\le\rho\eta/4\), and
\( \mathbb E[\Delta(x^k)] \le(1-\rho)^k\Delta(x^0)+\eta/4. \)
Check the rational certificate after every \(K\) updates, using the \(K\) above. From any feasible starting state, the bound \(\Delta\le M\) implies that the next check fails with conditional probability at most \(1/2\). Consequently, the expected number of updates before a certified output is at most \(2K\).
All stored allocation coordinates now have encoding length
\(O(L+b)\): a column is either its original rational column or a dyadic column. Each candidate update and certificate is computable with rational numbers of polynomially bounded length. For example, the conservative bound
\( s=O\bigl(n^2(L+b+\log(n+1))\bigr) \)
bounds all temporary rational encoding lengths. Using elementary integer arithmetic yields the expected bit-time bound
\( O\left( \left[ K\bigl(\tau\log(\tau+1)+\log(m+1)\bigr)+n \right]s^3 \right). \)
The term involving \(\log(m+1)\) includes exact uniform sampling by rejection.
In particular, substituting \(H=\overline H\), the dependence is
\( \boxed{ \operatorname{poly}(m,\tau,L,\log(1/\epsilon))\, m\max\left\{1,\frac{\Lambda\overline H^2}{\kappa}\right\} \left(1+\log\frac{4M}{\eta}\right). } \)
Every conditioning quantity in this expression has been defined explicitly. The rounding precision itself has polynomial encoding length:
\( b=O\bigl(n(L+\log(n+1))+\log(1/\epsilon)\bigr). \)
Thus controlled rounding avoids denominator explosion, but the condition parameter
\( m\max\left\{1,\frac{\Lambda\overline H^2}{\kappa}\right\} \)
can still be exponential in the input length. The resulting worst-case bound is exponential in numerical conditioning and logarithmic in accuracy, rather than a polynomial-time bound in the binary input length.
The rounded process is an implementation variant; the exact geometric bound in Section 4 applies to the updates exactly as stated in the question.
The lack of a polynomial iteration guarantee is substantive.
Choose a dyadic \(q=2^{-b}\) with \(b\ge2\), and let
\( \mu_1=1-q,\qquad \mu_2=q,\qquad B_1=B_2=1/q, \)
and
\( v_1=(1,0),\qquad v_2=(0,1). \)
Take fixed accuracy \(\epsilon=1/2\). Here
\( W=1/q,\qquad a_1=a_2=1,\qquad x^0_{tj}=1. \)
The optimum assigns each good entirely to its interested type, so
\( u_1^\star=\frac1{1-q}, \qquad u_2^\star=\frac1q. \)
Let \(s=x_{22}\). Only updates of good \(2\) change \(s\), and its block smoothness constant is
\( L_2=\mu_2B_2=1. \)
As long as \(s\ge1\), the unprojected update increases \(s\) by \(1/s\). Projection cannot increase it beyond that candidate, so
\( s^+\le s+1/s. \)
Projection also cannot decrease this coordinate below its old value. To verify this, let \(d=1/s\). The old column is feasible, and the candidate increases only its second coordinate by \(d\). At projection multiplier \(\gamma=d/q\), that coordinate has returned to its old value, while every other coordinate has weakly decreased. The weighted sum is therefore at most one. The chosen multiplier cannot exceed \(d/q\), proving \(s^+\ge s\).
Thus \(s\ge1\) throughout, and each update of good \(2\) satisfies
\( (s^+)^2 \le(s+1/s)^2 =s^2+2+1/s^2 \le s^2+3. \)
After \(k\) total updates,
\( s^2\le1+3k. \)
Meanwhile, each type’s utility is individually bounded above by its optimum utility. Since \(c_2=\mu_2B_2=1\), the objective gap satisfies
\( G^\star-G(x) \ge\log\frac{1/q}{s}. \)
Accuracy \(\epsilon=1/2\) therefore requires
\( s\ge\frac{e^{-1/2}}q, \)
and hence
\( \boxed{ k\ge\frac{e^{-1}q^{-2}-1}{3}. } \)
This lower bound holds for every sequence of sampled items. The instance has \(m=\tau=2\), fixed accuracy, and input length \(O(b)\), whereas the required number of updates is \(\Omega(2^{2b})\).
Therefore the allocation problem is polynomial-time solvable, while these particular dynamics can have exponential running time even before exact-arithmetic costs are considered.
⟨structured verdict parsed — rendered above⟩
Verdict: proved with minor gaps. The substantive mathematical argument is correct. It establishes polynomial-time rational approximation, a conditioning-dependent geometric rate for the specified exact dynamics, certified stopping rules, and an exponential iteration lower bound. Two expositional issues need clarification; neither requires new mathematics.
Positivity of the masses, budgets, and valuation sums makes all quantities in Section 2 well-defined. Feasibility implies \(x_{tj}\le 1/\mu_t\), so the bound \(u_t(x)\le U_t\) is valid.
The initial allocation uses exactly one unit of each good and gives utility \(a_t>0\). Compactness and upper semicontinuity therefore give an optimum with finite objective value. An optimum cannot have zero utility for any type, since its objective would then be negative infinity.
The stated optimality conditions have the correct scaling: the factors \(\mu_t\) cancel between the objective derivative and the weighted supply constraint.
Strict feasibility with positive utilities is available, so the multiplier argument applies. Complementarity and equality on positive allocation coordinates justify \(\sum_jp_j=W\). Summing the inequalities for a fixed type then gives \(u_t^\star\ge a_t\).
This argument also covers goods valued by no type: their multipliers are zero.
The quadratic and logarithmic branches agree in value, first derivative, and second derivative at \(a_t\). The displayed curvature formulas are correct.
At an original optimum, both objectives have matching gradients and values. The first-order optimality inequality consequently establishes extrapolated optimality. Strict convexity in utilities gives uniqueness of the optimal utility vector, without incorrectly claiming uniqueness of the allocation.
Thus the claimed equality of optimizer sets and \(\min_X\widetilde f=-G^\star\) is valid. The cited quadratic extrapolation construction is consistent with [Gao and Kroer’s paper](https://papers.nips.cc/paper_files/paper/2020/file/f75526659f31040afeb61cb7133e4e6d-Paper.pdf); the write-up supplies its own argument for the weighted coordinates.
The restricted polytope \(D\) contains every optimum. On \(D\), the calculation \(\|\nabla\phi(x)\|_1\le2W\) is correct, including the cancellation \(\sum_tc_tS_t/a_t=W\).
The proposed interior ball satisfies all three classes of constraints:
The interpolated ball about \(w\) lies in \(D\). The constants in its objective bound are valid: \(r_0\le\mathcal R\), and the definition of \(\theta\) ensures \(6W\mathcal R\theta\le\epsilon/4\), including the branch \(\theta=1/2\).
The cut-retention argument is correct. Whenever a feasible queried center has gap exceeding \(\epsilon/2\), its gradient cut retains the entire constructed ball. Infeasibility cuts also retain that ball. The resulting volume contradiction establishes the existence of a sufficiently good queried center.
Selecting the smallest approximate objective, with evaluation error at most \(\epsilon/8\), raises its true gap by at most \(\epsilon/4\). The claimed final bound \(3\epsilon/4\) therefore follows.
The logarithm series has the stated geometric convergence after scaling into \([1,2]\). The weights and scaling exponent require only polynomial additional precision.
Minor issue: the finite-precision rational ellipsoid theorem is not stated precisely. The text gives the geometric iteration bound and suitable oracle properties, but leaves the guarantee of polynomially bounded center encodings implicit. An exact central-cut ellipsoid update can involve irrational quantities, so rational oracle outputs alone do not explain that guarantee.
Minimum clarification: state or cite the rational ellipsoid implementation theorem being used, including preservation of containment, sufficient volume contraction, and polynomial encoding lengths. The supplied radii, rational cuts, and encoding bounds provide the necessary application data.
Since \(R_t=W/c_t\ge1\), the interval \([0,U_t]\) contains the threshold \(a_t\). The lower curvature bound \(\kappa_t=c_t/U_t^2\) is valid throughout that interval.
The Hessian within an item column is diagonal across types, so \(L_j\) is a valid block smoothness constant. The stated full-gradient constant \(\ell=m\Lambda\) is also valid.
At least one \(L_j\) is positive. A zero \(L_j\) means every valuation in that column is zero, justifying the unchanged-column convention.
The utility matrix has independent rows because each row has a separate type block and is nonzero. The projection normal-cone representation applies to the polyhedral optimal set.
The elimination argument preserves nonnegative inequality multipliers while obtaining independent rows. Feasibility gives the correct sign for the active-constraint contribution. The singular-value estimate then yields the claimed distance bound.
The determinant lower bound, matrix norm bound, and resulting \(\overline H\) are valid. Its logarithmic encoding bound is also valid.
Minor issue: \(H\) is introduced as “any constant” satisfying the Hoffman inequality, followed by “Then \(H\le\overline H\).” Taken literally, this is false: any sufficiently large multiple of a valid constant is also valid. The proof establishes that \(\overline H\) itself is valid, or that the smallest admissible constant is at most \(\overline H\).
Minimum clarification: specify one of those intended meanings. The later choice \(H=\overline H\), and all resulting rate bounds, remain justified.
The strong-convexity inequality and Hoffman bound give the displayed quadratic term with coefficient \(\lambda=\kappa/H^2\).
Substitution of \(x+s(z-x)\), with \(s=\min\{1,\lambda/\Lambda\}\), produces the claimed model decrease. The squared-distance coefficient is nonpositive in both branches of that definition.
Product feasibility, exact block-model minimization, and \(L_j\le\Lambda\) justify the conditional expectation inequality. Hence the rate \(\rho=m^{-1}\min\{1,\lambda/\Lambda\}\) and the geometric expected-gap bound follow.
This rate structure agrees with [Nan, Gao, and Kroer, Theorem 1](https://arxiv.org/pdf/2303.00506). Its citation is corroborative; the weighted-coordinate result is proved directly here.
The entropy bound gives \(\Delta(x^0)\le W\log\tau\le(\tau-1)W\).
The case \(\tau=1\) is correctly separated: the initial allocation is optimal. Subsequent quantities involving \(D_0\) are used only under the explicit assumption \(\tau\ge2\).
Each extrapolated term is decreasing for nonnegative utility, and its value at zero exceeds its value at \(a_t\) by \(3c_t/2\). Thus the global bound \(\Delta(x)\le M\) is valid.
The utility-distance inequality follows from strong convexity at an optimum and the nonnegative first-order term.
The constants in \(\delta_{\mathrm{safe}}\) correctly ensure \(u_t(x)\ge a_t/2\). On that range, the remainder curvature bound and its integrated estimate are correct. Summation gives the stated factor \(1+3R_{\max}^2\).
Consequently, the deterministic implication using \(\delta\) and the Markov probability bound are valid. The write-up correctly distinguishes extrapolated-gap convergence from logarithmic-gap convergence.
The mixture is feasible, rational, and has utility at least \(\beta a_t\). The comparison allocation and logarithmic derivative bound apply on that positive range.
The Cauchy–Schwarz factors are correct, including the coefficient \(C_R\). Jensen’s inequality then justifies the expected-gap bound. The displayed sufficient iteration count is conservative and valid.
Convexity gives \(\Delta(x)\le\mathcal C(x)\). Nonpositive gradient coordinates and the independent weighted supply constraints justify the exact rational formula.
In the decomposition at an optimum, the three contributions have the claimed upper bounds. The definition of \(\eta\) makes each of the two contributions to the certificate bound at most \(\delta/2\).
The tail argument therefore gives the stated expected stopping count. Every allocation accepted by the certificate satisfies the requested deterministic accuracy.
The weighted Euclidean projection formula is correct, including the feasible-positive-part branch. Breakpoint sorting identifies the active coordinates.
Derivatives, projections, and exact iterates are rational. The denominator-growth recurrence is a conservative bound, rather than an assertion that such growth always occurs.
The fixed-length independent-trial construction avoids inferring expected bit time merely from expected stopping time. Its success probability and bounded expected number of trials are justified.
Downward rounding preserves feasibility. The global gradient bound \(J=2W\) and rounding displacement bound imply the stated additive objective error.
The selected precision makes the stationary error at most \(\eta/4\). At each batch endpoint, the conditional expected gap is at most \(\eta/2\), giving certificate failure probability at most \(1/2\).
The rational encoding and elementary-arithmetic bounds are conservative. Maintaining current utilities supports the stated per-update arithmetic accounting. The conditioning dependence remains explicit and potentially exponential.
The write-up correctly labels this process as a modification of the exact updates.
All instance data meet the task assumptions and have encoding length \(O(b)\). The stated optimum utilities and \(L_2=1\) are correct.
The projection-multiplier argument establishes that \(s\) remains at least one and cannot increase beyond \(s+1/s\). Therefore \(s^2\le1+3k\) holds for every sampling sequence.
Each type’s utility is bounded by its respective optimum utility, so the total objective gap is at least the type-2 contribution. Accuracy \(1/2\) forces the stated lower bound on \(s\), and hence \(\Omega(2^{2b})\) updates.
This establishes exponential iteration requirements for the specified dynamics, while remaining consistent with polynomial-time solvability by a different algorithm.
There are no blocking mathematical issues. The minimum requested revisions are the precise rational ellipsoid theorem statement and correction of the Hoffman-constant quantifier.
⟨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.