PaperlayerView exact revision on arXiv

Source-linked AI summary

Faster Linear Programming with $\sqrt{\mathrm{rank}}$ Linear System Solves

Zhao Song

arXiv:2609.30853v1math.OCcs.DS

TL;DR

The Lee–Sidford rank-governed solve bound carried a log^13 m factor, and reducing that overhead was identified as a future direction. The algorithm combines Gram-pullback score transport and lazy auxiliary-weight repairs that charge score drift to retained defect. The result improves the Lee–Sidford bound [LS19] by a factor of log^9 m.

  • Problem

    The Lee–Sidford rank-governed solve bound carried a log^13 m factor, and reducing that overhead was identified as a future direction.

    Source: §1.1 · p. 3

  • Method

    The algorithm combines Gram-pullback score transport and lazy auxiliary-weight repairs that charge score drift to retained defect.

    Source: §2.3 · p. 5

  • Results

    The result improves the Lee–Sidford bound [LS19] by a factor of log^9 m.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The authors conjecture that O(√n log(mU/ε)) such linear-system solves suffice.

    Source: §1.1 · p. 3

    The theorem uses an exact real-arithmetic model and makes no Turing-model bit-complexity claim.

    Source: §4.4 · p. 16

Abstract

from arXiv · show

Lee and Sidford [LS19] showed that the linear program $\min\{c^\top x\ :\ A^\top x=b,\ l\leq x\leq u\}$ over $x\in\mathbb{R}^m$, where $A\in\mathbb{R}^{m\times n}$, can be solved to accuracy $\epsilon$ using $O(\sqrt n\log^{13}m\cdot\log(mU/\epsilon))$ solves of linear systems in $A^\top\mathbf DA$ for positive diagonal matrices $\mathbf D$, where $U$ bounds the magnitudes of the input and of the initial point. Theirs is the first such bound governed by $\mathrm{rank}(A)=n$ rather than by the number of constraints $m$. Song [Son19] mentioned that reducing the $\log^{13}m$ factor is an interesting future direction. Given an interior point and a finite certified magnitude bound $U$, we give an algorithm that uses $O(\sqrt n\log^{4}m\cdot\log(mU/\epsilon))$ solves of such linear systems, improving the Lee--Sidford bound by a factor of $\log^{9}m$. We conjecture that $O(\sqrt n\log(mU/\epsilon))$ such linear-system solves suffice.

1 Introduction

The introduction places the work in the history of polynomial-time linear programming and the shift toward rank-governed path-following methods. It presents a lower-logarithm solve bound for a bounded LP under stated initialization and magnitude assumptions.

1 Introduction

  • The simplex method is foundational in practice but has exponential worst-case behavior, while the ellipsoid and projective methods established polynomial-time bounds.For square instances, the cited analyses give O(d^4L) and O(d^3.5L) arithmetic operations, respectively.Source: §1 · p. 2
  • Later interior-point methods shifted attention from polynomiality to the cost of linear algebra along a central path.Renegar's iteration bound depends on the number of inequalities, while Vaidya's method sharpened arithmetic complexity.Source: §1 · p. 2
  • Modern methods include rank-governed path-following bounds and faster algorithms for dense and tall linear programs.The introduction surveys bounds for dense standard-form and tall dense instances, including subsequent improvements to the latter.Source: §1 · p. 2

1.1 Our results

  • The target LP has equality constraints and coordinate bounds, with a nonempty interior feasible region; the complexity statement assumes boundedness and a finite certified magnitude bound U.The input includes an interior point, and the theorem returns a feasible solution within ε of optimality.Source: §1.1 · p. 2
  • Given ϵ∈(0,1), an interior point of Eq. (1), and finite certified magnitude bound U satisfying the preceding display, the algorithm outputs feasible x with c⊤x≤OPT+ϵ at constant probability, improving Lee–Sidford [LS19] by a factor of log^9 m.Separately, the passage conjectures that O(√n log(mU/ϵ)) such linear-system solves suffice.Source: §1.1 · p. 3
  • The authors conjecture that O(√n log(mU/ε)) such linear-system solves suffice.The work and depth accounting also charges for sparse matrix-vector products and vector operations, not only the solves.Source: §1.1 · p. 3

2 Technique Overview

The overview attributes the reduced logarithmic overhead to refined weight geometry, defect-aware prediction and score maintenance, and a projected-residual potential that allows larger path steps.

2.1 The logarithmic overhead in the Lee–Sidford method

  • The Lee–Sidford [LS19] overhead combines centering-step restrictions with repeated approximate Lewis fixed-point computations and leverage-score estimation.Their resulting system bound is O(√n log^13 m · κ), with κ accounting for logarithmic path length and target accuracy.Source: §2.1 · p. 4

2.2 Weight geometry and defect-adaptive prediction

  • Placing the regularization floor inside the Lewis fixed point and using Pythagorean geometry gives a mixed norm with tracking tolerance Θ(q^-1/2).The overview sets q := log(4m/n), with consistency ck = Θ(q) and mixed-norm coefficient C = Θ(√q).Source: §2.2 · p. 4
  • The retained Jacobian defect supplies centrality slack and also bounds the variance of the stochastic predictor.The defect can be certified with the required one-sided guarantee.Source: §2.2 · p. 4

2.3 Score transport and lazy auxiliary repairs

  • Score transport combines an exact one-row leverage-score update with fresh sketches; Gram-pullback transport charges transitions to defect, while lazy repairs wait for accumulated coordinate error.Polynomial-length certified epochs keep confidence logarithms O(log m) on arbitrarily long paths and add only a constant factor to the resource ledger.Source: §2.3 · pp. 4–5

2.4 Four logarithms from the projected residual

  • The projected-residual potential permits path steps of size Θ(R/(k√n)); amplified prediction costs O(kℓ) systems per call and is absorbed because q ≤ ℓ.Telescoping the negative terms also pays for the additive floor in the defect certificate.Source: §2.4 · p. 5
  • The projected-residual analysis yields a leading system count of O(√n qℓ^3κ), giving the four-logarithm work bound.Cold initialization and the terminal Newton tail are included in that bound.Source: §2.4 · p. 6

3 Preliminaries

The preliminaries establish notation, barrier and centrality quantities, and the Lee–Sidford path facts used under specified tracking conditions.

3.1 Basic notation

  • The notation section fixes vector and matrix conventions, including norms, transposes, pseudoinverses, diagonal operators, and coordinatewise operations.It also defines [d] as the index set {1, …, d}.Source: §3.1 · p. 6

3.2 Centrality and Lee–Sidford path facts

  • The path framework uses interval-barrier row scaling and defines permitted systems as solves in A^TDA with positive diagonal D and one right-hand side.The section records a computable centrality proxy obtained with the same permitted solve as the projected Newton residual.Source: §3.2 · pp. 6–7
  • The Lee–Sidford path estimates cover Newton contraction, weight changes, and changes in the path parameter under centrality and tracking hypotheses.The proofs apply with a norm Nw dominating the infinity norm and a centrality-equivalence constant at most two.Source: §3.2 · p. 7

4 Geometric foundations and the mixed-ball oracle

This section develops robust regularized-weight geometry, including stable projection scores and projector and Jacobian defect bounds, and uses it to sharpen mixed-norm geometry. It also develops a mixed-ball oracle for residual chasing, where prediction reduces the tracking penalty and permits a smaller centrality radius.

4.1 Projection-score perturbations and regularized Lewis fixed points

  • Diagonal rescalings yield relative stability of projection columns and leverage scores, enabling the hybrid provider to transport diagonal responses and sketch endpoint discrepancies.The provider restarts after constant cumulative effective drift, and transition sketches are drawn only after both query endpoints are fixed.Source: §4.1 · pp. 8–9
  • Regularizing inside the Lewis fixed point bounds weight dynamic range, makes the governing exponents depend on log(4m/n), and supports direct ℓ∞ contraction.The regularized fixed point is unique and smooth under positive row rescaling; approximate iterations converge when their logarithmic error is sufficiently small.Source: §4.1 · pp. 9–11

4.2 Projector and Jacobian defects

  • Refined projector and Jacobian bounds make the first two parameter losses quadratic, while regularization inside the weight function removes the log m sensitivity loss.The resulting analysis runs on q = log(4m/n) rather than ℓ = log(4m).Source: §4.2 · p. 12
  • A Pythagorean estimate for the projected Newton direction replaces separate triangle-inequality losses in the mixed norm.The analysis charges the projection error to the complementary component, retaining slack rather than bounding both terms independently.Source: §4.2 · p. 12
  • The regularized Lewis-weight Jacobian retains Pythagorean slack and admits a diagonal approximation, sharpening the geometric bounds.The Jacobian result supplies a diagonal matrix D with 0 ⪯ D ⪯ pI that approximates its action coordinatewise.Source: §4.2 · p. 12

4.3 Robust centrality geometry

  • Putting the floor inside the Lewis fixed point bounds dynamic range by 2m/n and gives c1(g) ≤ 2n, cs(g) ≤ 2, replacing [LS19]’s O(m^Θ(1−p)) sensitivity.For [LS19], constant sensitivity requires 1−p = O(1/ell); the new construction replaces ell with q.Source: §4.3 · pp. 14–15

4.4 The mixed-ball response oracle

  • Predicting log-weight movement and chasing only its residual avoids [LS19]’s enlargement penalty, reducing tracking error from O(EckLch) to O(ELch).The residual movement set has radius Θ(δ/ck), so constant enlargement costs only Θ(δ/ck).Source: §4.4 · p. 16
  • With the residual alone being chased, centrality enters neither chasing hypothesis, allowing R = Θ(1/ell) while E = Θ(q^-1/2/ell).The passage identifies this as a second, larger saving from prediction.Source: §4.4 · p. 16
  • The mixed-ball oracle returns a feasible point with certified near-optimal linear objective using no permitted systems and O(mJ log m) scalar work and O(J log m) depth.Its guarantees use the exact real-RAM model; the theorem makes no bit-complexity claim.Source: §4.4 · pp. 16–17
  • With b∈V/8, s≤E/100, μE=1/100, and ||qobs−q||∞≤5E, Lemma 4.11 bounds descent for the observed greedy softmax step and accounts for observation error.The oracle uses an approximate residual observation and a mixed-ball response.Source: §4.4 · pp. 18–19

5 Residual chasing and retained-defect geometry

Section 5 develops stochastic residual tracking and Jacobian stability alongside retained-defect geometry for large-radius predictors and retained movement. It also presents a computable projection onto a defect body to turn predictor estimates into feasible motion while preserving the centrality budget.

5.1 Stochastic residual chasing

  • With probability at least 19/20, Lemma 5.1 maintains its stronger tracking invariant and movement conclusions; the guarantees also hold through a pre-noise externally stopped process.On the event that the external stop exceeds the horizon, the full-horizon conclusions apply.Source: §5.1 · p. 20
  • Mean-zero residual error enters the potential only through its second moment, paired with the same support function that the player's move decreases.Source: §5.1 · p. 21
  • The resolvent is stochastic and contractive in the stated norms; Jacobian stability and finite-segment error bounds control variation along centering steps.The resolvent has nonnegative entries and unit row sums; the finite-segment bound is stated under Lemma 4.9's Newton-segment hypotheses.Source: §5.1 · pp. 22–24

5.2 Large-radius defect geometry

  • For directions h, the retained defect is d(h)^2 = p^2r^2 − s^2, making explicit slack discarded by the basic contraction estimate.The retained-defect bound assumes ∥log w − log g∥∞ ≤ H ≤ 1/4.Source: §5.2 · p. 25
  • The large-radius construction has R = O(1/c_k), E = O(1/c_k), and R^2 = O(E); retained movement applies when δ ≤ R and E,R ≤ r0/c_k.Source: §5.2 · p. 26
  • The large-radius defect split predictor combines coordinatewise and weighted Jacobian estimates, using O(log(m/ζ)) systems for the coordinate estimate and certificate and O(ck) systems for the weighted estimate.Its construction and guarantees apply directly at large radius, without a separate small-radius hypothesis.Source: §5.2 · pp. 26–28

5.3 Projection onto the defect body

  • The computable defect projection returns a feasible approximate metric projection, with O(mJ log m) scalar work and O(J log m) arithmetic depth; under the stated scale condition, it uses no linear systems.The procedure uses exact active-set fixed-slice computations and exact-subgradient bisection.Source: §5.3 · pp. 29–31
  • The defect projection produces feasible motion satisfying the residual-game requirements while preserving the centrality budget, with ν = 1/5.The construction applies the computable projection at the certified defect scale and uses the one-sided certificate to establish feasibility and the required bounds.Source: §5.3 · pp. 31, 33

6 Initialization, path composition, and defect certification

Section 6 develops initialization and path-composition procedures for obtaining an LP solution, alongside defect-dependent certification methods. It also presents defect-scaled stochastic estimation, finite medoid aggregation, and a one-sided numerical certificate for the retained defect.

6.1 Warm starts and fixed-point initialization

  • An E/2-accurate auxiliary weight advanced by the projected predictor remains within E of the new regularized Lewis vector, and an absolute number of rounds restores E/2 accuracy.The first query transition has logarithmic row drift O(R); later refinement queries have drift O(E).Source: §6.1 · p. 33
  • Fixed-point computation takes J = O(log(2 + D/ϵ_fp)) rounds from initial logarithmic error D; in hybrid maintained mode with D ≤ E, J = O(1).In exact mode, the fresh-mode guarantee holds deterministically and the exact branch costs O(nJ) permitted systems.Source: §6.1 · pp. 34–35

6.2 Path composition and outer reduction

  • The composition lemma preserves centrality and weight-tracking invariants across a centering move and a controlled path-parameter change.For sufficiently small maintained centrality, the fixed-weight barrier objective also has a unique minimizer, enabling terminal-distance conversion.Source: §6.2 · pp. 36–37
  • The outer reduction returns a feasible output with c^T x ≤ OPT + ε when both calls in Algorithm 10 satisfy their stated invariants.The terminal barrier state is converted into the original LP guarantee.Source: §6.2 · p. 38

6.3 Defect estimation and certification

  • The residual-game lemma allows a positive step radius measurable before fresh randomness, provided the conditional bias and fluctuation hypotheses hold and the movement bound is adjusted.The defect-adaptive construction selects this radius from coarse data revealed before the step’s fresh randomness.Source: §6.3 · p. 40
  • The defect operator satisfies 0 ⪯ H ⪯ ρI, and for the present p, ρ is bounded away from one by an absolute constant.The estimators target variance that shrinks with the retained defect rather than with the full Newton motion.Source: §6.3 · p. 40
  • The stochastic fixed-point lemma provides separate weighted-norm and coordinatewise defect estimators, with the coordinate estimator using O(log(m/ζ)) systems in an absolute number of rounds with probability at least 1 − ζ.The weighted estimator uses O(ck) systems in O(log ck) sequential rounds.Source: §6.3 · pp. 40–41
  • With probability at least 1 − ζ/3, the finite medoid rule selects a candidate within 3r of y, using O(mB^2) scalar operations and O(log m + log B) arithmetic depth.It chooses the candidate with minimum distance to its (B + 1)/2-th closest candidate, for odd B ≥ cmed log(3/ζ).Source: §6.3 · p. 42
  • Given ∆ ≥ δ, the coarse chain and O(log(1/ζ)) additional systems produce a one-sided certificate for the retained defect with explicit inflation and failure probability below ζ.The certificate’s one-sided direction is explicit, and its batch sizes are fixed before sampling.Source: §6.3 · pp. 43–44

7 Certified prediction and path-following assembly

This section assembles certified prediction, adaptive score increments, and conditionally analyzed centering into checkpointed path-following phases with explicit resource caps. It adds restart and once-only deterministic terminal-tail rules, along with deterministic epoch normalization that bounds resource use and preserves path invariants.

7.1 Certified predictor construction

  • The certified predictor uses a positive-semidefinite surrogate whose operators stay O(E)-close to their exact counterparts, alongside an unbiased Gaussian defect-energy estimator with a certification-useful variance bound.The surrogate satisfies 0 ⪯ Q+ ⪯ S+ ⪯ I, with L+ = S+ − Q+; each defect-estimator sample uses two projection applications and two permitted solves.Source: §7.1 · pp. 45–47

7.2 Gaussian increment primitive

  • Fresh shared Gaussian sketches drawn after query endpoints are fixed give conditionally unbiased score increments and the conditional martingale and variance bounds for adaptive queries.The increment primitive replaces per-query score sketches; each sketch sample costs two permitted solves.Source: §7.2 · p. 48

7.3 Within-step hybrid filtration

  • On a conditional coarse-good event with failure probability at most ζ, the hybrid-score centering call returns its state and satisfies the residual bias and fluctuation hypotheses.The call contributes O(E) hybrid effective drift and O(1) score-process transitions; outside that process it uses O(L* + q) systems and O(log q) depth.Source: §7.3 · pp. 49–50

7.4 Path following and resource budgets

  • Mpath=⌈Apath(ckβ|log(t1/t0)|/R + ck log(R/τ) + 1)⌉ caps phase calls, including terminal-centering calls, while preserving tracking and auxiliary-weight invariants.The guarantee holds on the specified coarse, stopped-tracking, and no-exact-replacement events, under the phase's stated initialization and epoch conditions.Source: §7.4 · pp. 50–51
  • Resetting the first terminal-loop counter after checkpoint normalization ensures its consecutive contractions remain valid, with at most one successful reset and an inverse-polylogarithmic terminal length.The accepted checkpoint leaves the whole loop before the next checkpoint; the switch threshold is independent of U and ε.Source: §7.4 · p. 52
  • The fixed-weight Newton tail runs once outside the retry loop, uses no score or predictor calls, and reaches the terminal centrality target within a deterministic cap.Quadratic contraction preserves tracking and interiority; the tail uses O(κ + ℓ) systems.Source: §7.4 · p. 52
  • EpochNormalize preserves feasibility and the path parameter while reducing centrality to ε_rec, tracking error to K/4, and maintaining the stated auxiliary-weight and exact raw-score invariants.Under the lemma’s feasible-interior input and tracking assumptions, each permitted-system, sequential-round, and exact scalar-operation count is at most D_norm(1 + A_L)^d_norm(4m)^d_norm.Source: §7.4 · p. 53
  • Structural constants for Algorithms 2–7 can be fixed independently of m, n, U, and ε before the remaining scale, provider, switch, and resource-cap constants are chosen.Source: §7.4 · p. 55

8 Score maintenance and certified checkpoints

Section 8 develops exact and hybrid score-maintenance methods for the path algorithm, establishing their guarantees across queries, transitions, initialization, coupling, interface transfer, and restarts. It also uses bounded, certified checkpoint attempts to complete the two path phases with constant probability and controlled resources.

8 Score maintenance and certified checkpoints

  • Attempts announce deterministic local caps before work or randomness, reject before exceeding them, and accept checkpoints only after score, feasibility, interiority, and companion-band checks pass.Accepted states restore the fresh-start path hypotheses, including the potential bound; each accepted checkpoint starts a new residual game.Source: §8 · pp. 57–59
  • With at least 4/5 conditional probability per good attempt, checkpointed execution completes both path phases with constant probability and uses systems, system depth, and scalar work within a constant factor of the uncheckpointed bounds.The attempt limit is 4Jep; the final segment can finish without a mandatory exact checkpoint.Source: §8 · pp. 57, 59

8.1 Exact diagonal self-transport

  • Exact one-row transport preserves the own-row response, while a fresh Gaussian sketch estimates only the nonlocal endpoint discrepancy to update approximate scores.The endpoint bound controls the nonlocal remainder through companion-weighted drift.Source: §8.1 · pp. 60, 61, 63
  • Clipping a transported score to [0, 1] cannot increase its error, and when weighted drift is zero, the exact transported value is retained.With zero weighted drift the projections coincide, so the transition returns t without a sketch.Source: §8.1 · p. 64

8.2 Hybrid maintenance and stopping

  • Hybrid maintenance bounds fresh-base cost by O(E−2Lconf(1 + Ω)); each row uses two endpoint systems per transition and one system per base, with constant factors absorbed in Eq. (25).An ordinary transition provides a uniform fallback charged to centered ℓ∞ drift. If no branch is eligible, the transition is charged h0 and a fresh base is forced at the new endpoint.Source: §8.2 · pp. 64, 65, 68

8.3 Compatibility with the path algorithm

  • Every maintained-mode fixed-point and inflated-surrogate query has a companion satisfying Eq. (23), and compatible constants ensure eligible transitions within the stated bounds.The constants are selected in a noncircular order so the query companion band, transition eligibility and radii, and base and crossing failure bounds hold before the auxiliary stopping time.Source: §8.3 · p. 69
  • In the fresh branch, the final Gaussian score sketch uses O(E^-2 log(2mJ/ζ)) rows when the outer solver sets ε_fp=E/4.The exact branch satisfies the same statement with zero error.Source: §8.3 · p. 72
  • A coupling replaces the first violating raw-relative score response and all later responses with exact scores, so violations do not censor a centering call after predictor noise is drawn.The coupling preserves the predictor identities’ original conditional sigma-fields and stops only at existing pre-noise auxiliary stops.Source: §8.3 · pp. 72–73
  • When cancE ≤ 1/2 and canc ≤ min{1/8, c0}, raw-relative scores transfer to the fixed-point and inflated-surrogate interfaces, including clipped and zero scores.Every fixed-point score meets Lemma 4.4’s hypothesis, and every inflated-surrogate score meets Lemma 7.1’s additive hypothesis.Source: §8.3 · p. 73
  • Each completed centering call incurs O(E) total hybrid effective drift and O(1) score transitions, with non-score work and depth of O(L*+q) systems and O(log q) system rounds.The direct one-call interface preserves the predictor bias and second-moment statements under their original conditional sigma-fields.Source: §8.3 · pp. 71, 73, 74

9 Gram-pullback score transport and lazy repairs

Section 9 transports score changes through the old column space and refines auxiliary weights only when accumulated error requires it. These routines charge principal score transitions to retained defect and feed into the final bound.

9 Gram-pullback score transport and lazy repairs

  • Principal score transitions are charged to retained defect, while auxiliary weights are refined only when accumulated error requires it.The hybrid provider combines these routines with an amplified predictor and projected-residual potential to prove the final bound.Source: §9 · p. 74

9.1 Score transport through the old column space

  • The Gram-pullback update satisfies the relative recurrence and MGF interface with effective drift 8θ, using two permitted systems per sample.It also requires O(nnz(A) + m) additional scalar work per sample.Source: §9.1 · p. 74
  • The hybrid maintenance and exact-continuation conclusions remain valid for TicketScore before the first invalid ticket or existing auxiliary stop.The proof uses exact-continuation coupling after the first raw-relative violation without conditioning a predictor on later score events.Source: §9.1 · p. 75

9.2 A pointwise predictor bound and lazy auxiliary repairs

  • For every weighted-chain realization on the coarse event, the principal Gram drift is at most AGd, giving a valid ticket θ = AGd.The final absolute radius choice ensures 8θ ≤ h0.Source: §9.2 · p. 76
  • Threshold-triggered lazy repairs keep auxiliary error below E/2; score queries number O(1 + b) for a prefix of b atomic instructions.Repairs replace the mandatory fixed-point call after a projected predictor and charge their score drift to accumulated predictor errors.Source: §9.2 · p. 77
  • The clipped-predictor centering call uses O(ℓ + q) non-score systems, O(log q) system depth, and O((nnz(A) + m)ℓ^2) non-score scalar work.It retains the auxiliary, movement, and conditional residual-game guarantees of Lemma 7.4.Source: §9.2 · pp. 78–79

10 A four-logarithm bound from the projected residual

Section 10 develops a four-logarithm bound by combining an amplified weighted predictor with a squared projected-residual potential, using the Lewis-weight Jacobian to couple path forcing to dissipated potential. Under the stated LP assumptions, it bounds work, queries, and rounds—including rejected attempts—and gives deterministic resource caps for an algorithm that returns a feasible epsilon-optimal solution with constant probability.

10.1 Amplification and the forcing identity

  • O(log(1/ζ)) independent weighted-chain copies amplify the predictor on the shared high-probability coarse event, while the Lewis-weight Jacobian couples path forcing to dissipated potential.With log(1/ζ) = O(ℓ), the non-score cost per call is O(kℓ) systems, O(log k) system rounds, and O((nnz(A) + m)ℓ^2) scalar work; the forcing permits larger path steps without increasing total score drift.Source: §10 · p. 79, §10.1 · p. 80

10.2 Finite Newton steps

  • V+ ≤ (1 − 1/(2k))V − c*kD^2 + A*knξ^2 for V := X^2 + ΛkY^2, giving contraction with explicit defect dissipation.The potential also satisfies Δ^2 ≤ 2V and V ≤ LΛΔ^2. Finite residual transport controls weighted and coordinate residuals when Δ ≤ R ≤ r0/k, the tracking band holds, and the amplified coarse event occurs.Source: §10.2 · pp. 82, 84

10.3 Path steps, terminal accuracy, and checkpoint caps

  • At normalized checkpoints, the method strengthens requested accuracy to εrec ≤ ρ/(8√LΛ) and certifies V ≤ ρ^2/4, while the cost-switch estimate remains bounded by ρ/(4√LΛ).These changes introduce no dependence on κ into normalization.Source: §10.3 · p. 84
  • The first terminal phase uses a fixed-t loop of ⌈8k log(4R/τsw)⌉ steps, restarting its counter after checkpoint normalization; the second ends its stochastic stream at tout and runs a fixed-weight tail.The final tail uses no score queries or weight updates and costs O(1 + log(2 + log(R/τout))) = O(κ + ℓ) systems.Source: §10.3 · p. 85
  • O(√n qℓ^3κ + qℓ^3) bounds the stated work, and scalar work is O((nnz(A) + m)Nℓ^2) of the same leading order.Here ℓ = log(4m), q = log(4m/n), and κ = Aκ(1 + log(emU/epsilon)).Source: §10.3 · pp. 86–87
  • O(N + qκ + log(q/E) + 1) bounds queries, while O(√n qℓ log qκ + κ + log ℓ + 1) bounds rounds.The query total includes checkpoint queries, initialization, and the once-only tail.Source: §10.3 · p. 87
  • The algorithm halts on every outcome within its permitted systems and returns a feasible epsilon-optimal solution with constant probability.The theorem assumes the LP, an interior point x0, and a finite certified magnitude bound U.Source: §10.3 · pp. 87–88
  • Resource counters remain monotone through rejected attempts, and each operation announces its charge before work or randomness, so caps stop excess work on other outcomes.On good trajectories the caps do not change execution; rejected attempts are included in the summed caps.Source: §10.3 · pp. 87–88
  • In the bounded-fan-in model, some output depends on at least m/n diagonal inputs, implying solve depth Ω(1 + log(m/n)).A depth-d computation depends on at most a^d inputs for an absolute a > 1.Source: §10.3 · p. 89
Loading 2609.30853v1…