Spherical Convex Hull Membership: Complexity and Performance of Geometric and Accelerated Methods

1 Introduction

• The spherical problem asks whether the origin belongs to the convex hull of unit vectors, with an approximate point or strict separator as the desired certificate.An approximate point is an explicitly represented convex combination with norm at most ε; it certifies proximity, not exact membership.Source: §1 · p. 1
• A cumulative geometric-progress condition gives STA a conditional O(1/ε) bound, while a three-point example attains Θ(ε^-2) iterations.The same conditional rate holds for STA–WMC when the condition holds for its actual STA steps.Source: §1 · p. 2
• The paper gives self-contained membership-bound derivations for entropic Nesterov acceleration and NWP, and an unconditional O(mn√log n/ε) arithmetic bound for the hybrid.The hybrid combines STA, Wolfe minimum-norm correction, and NWP, with correction work included.Source: §1 · p. 2
• The computational comparison covers five methods and examines STA steps, correction costs, and the safeguard’s effects on runtime and budgeted completion.The work model counts products by V or V^T at O(mn) each and includes additional arithmetic; experiments use double precision.Source: §1 · p. 2

2 STA: geometry, progress, and a sharp slow trajectory

• A witness satisfies pᵀv_i > ∥p∥^2/2 for every input vertex, yielding a perpendicular-bisector separator and a lower bound involving the hull’s distance from the origin.A positive minimum score gives strict separation, but does not by itself meet the stronger witness test.Source: §2 · p. 3
• A strict pivot updates p to the nearest point on [p,v], and the exact progress relation depends on the residual norm and the pivot’s opposite depth.The segment update also updates the convex coefficients and requires no projection onto the full hull.Source: §2 · p. 3
• STA returns a convex combination of norm at most ε or a strict separator within O(ε^-2) iterations and O(mn/ε^2) arithmetic operations.The residual bound applies after strict-pivot updates unless the algorithm has already terminated.Source: §2 · p. 3

2.1 A three-point example

• On the three-point example, deepest pivots alternate between horizontal vertices and still require Θ(ε^-2) iterations.Their midpoint is zero, so remembering and combining the two pivots resolves this example, but does not establish a faster general bound.Source: §2.1 · p. 4

2.2 Interior geometry

• If the hull contains a radius-ρ ball about zero in its linear span, deepest-pivot STA has O(ρ^-2 log(1/ε)) iterations.This favorable interior regime does not cover boundary membership such as the three-point example.Source: §2.2 · p. 4

3 Conditional amortized O(1/ε) convergence of ordinary STA

• T(ε) = O(N0 + 1/(γε)) when the trajectory satisfies the cumulative progress condition with constants independent of ε.The bound applies until the trajectory reaches zero; exact termination only improves the stopping bound.Source: §3 · p. 5
• The average normalized-depth condition permits poor steps to be compensated by deeper pivots, unlike a requirement that every step make sufficient progress.For example, sk ≥ c√δk eventually implies O(1/ε) accuracy dependence; consecutive blocks with average ak ≥ γ give O(B + 1/(γε)) additional steps.Source: §3 · p. 5
• Uniform complexity over an input class requires uniform control of N0 and γ; for a fixed trajectory, these constants may depend on the input and pivot choices, but not ε.A finite observed average certifies only the finite estimate, and identifying boundary input classes with uniform constants remains open.Source: §3 · p. 5

3.1 Relation to earlier pointwise conditions

• Earlier STA analysis gives conditional O(M/ε) iterations under a pointwise pivot-distance condition, while this theorem supplies an explicit cumulative progress certificate.The cumulative condition relaxes a pointwise lower bound on ak, but is not asserted to be weaker than the earlier tolerance-dependent condition.Source: §3.1 · p. 5

4 The Nemirovski weighted-pivot method

• NWP specializes Nemirovski’s Mirror-Prox framework and returns an explicit approximate convex combination or strict separator.Its weighted pivot gives greater weight to vertices with smaller inner products with the current direction.Source: §4 · p. 6, §4.1 · p. 6

4.1 Algorithm

• The algorithm accumulates weighted-pivot updates and stops when the averaged residual is small enough or a full score test verifies strict separation.The returned convex combination uses the accumulated coefficient vector divided by the number of updates.Source: §4.1 · p. 6

4.2 Convergence and complexity

• NWP’s potential argument bounds the accumulated residual, yielding an approximate point or strict separator within the stated iteration bound for any input.The proof uses nonnegativity of the potential on membership inputs to bound the residual; otherwise it establishes a positive score for separation.Source: §4.2 · pp. 6–7
• Each NWP update uses four full input products, O(mn) arithmetic, and O(m+n) auxiliary storage excluding the input matrix.The implementation retains intermediate scores and vectors across iterations.Source: §4.2 · pp. 7–8

5 Entropic Nesterov acceleration for spherical convex hull membership

• The method minimizes 1/2 ∥Vx∥² over the simplex using the ℓ1 norm and entropy d(x) = log n + Σ_i x_i log x_i.The implemented updates and the membership bound are presented here, with supporting derivations in Appendices A.1 and A.2.Source: §5 · p. 8

5.1 Algorithm and membership bound

• The y_k update transfers weight from large-score coordinates to a minimum-score coordinate, with an exact update obtained by sorting donors and minimizing a piecewise quadratic.The implementation also offers the nearest point to the origin on [Vy_k, Vz_k] as an explicit convex-combination output.Source: §5.1 · p. 8
• O(√log n/ε) iterations suffice for membership, and output refinement preserves this bound.The estimate uses the entropy bound d(x*) ≤ log n on membership inputs.Source: §5.1 · p. 8

5.2 Separation and computational cost

• The membership estimate does not provide an unconditional accelerated iteration bound for the method’s strict-separation checks.The experiments nevertheless test candidate directions for separation.Source: §5.2 · p. 9
• Including output refinement, each iteration uses three full input products and O(mn+n log n) arithmetic, with O(m+n) auxiliary storage.For m ≥ log n, its per-iteration cost has the same asymptotic order as NWP’s.Source: §5.2 · p. 9

6 Safeguarding STA with WMC and NWP

• The hybrid first attempts WMC after a slow block of STA steps and activates the NWP safeguard only if progress remains insufficient.The WMC corral and NWP sequence are retained as separate persistent states.Source: §6 · p. 9, §6.2 · pp. 10–11

6.1 WMC with retained state

• WMC maintains a corral whose affine minimum-norm point lies in its convex hull, inserting improving vertices and deleting points when affine-minimizer coefficients are negative.The correction preserves feasibility and does not increase the norm; over J scans it uses at most J insertions, J deletions, and 2J affine minimizations.Source: §6.1 · pp. 9–10
• Updated QR factorization and coefficient reconstruction keep the total arithmetic cost of J corrective scans at O(Jmn).The corral size is at most min(m+1,n), and the factorization is updated on insertion or deletion.Source: §6.1 · p. 10

6.2 Combining STA, WMC, and the NWP safeguard

• For fixed block size B, the hybrid uses O(√log n/ε) full input products and O(mn(1/ε + L + B)) arithmetic, including corrections.The guarantee applies whether the origin is inside, on the boundary of, or outside the convex hull, and the failed progress test forces NWP to advance.Source: §6.2 · p. 11

7 STA–WMC with remembered pivots

• STA–WMC combines persistent WMC with remembered STA pivots, a relative-progress trigger, and no NWP safeguard.The experiment evaluates the combined effect of pivot reuse and the correction schedule.Source: §7 · p. 12

7.1 Algorithm

• The candidate pool retains distinct STA pivots and may exceed the active corral; a reported separator must still pass a full-set test.The correction phase searches remembered candidates first and scans the full input set when none improves the corral point.Source: §7.1 · p. 12

7.2 Progress and complexity

• In exact arithmetic, STA–WMC returns an approximate point or full-input-verified separator within O(ε^-2) ordinary STA steps and O(mn/ε²) arithmetic.The bound follows because ordinary STA steps decrease squared residual and accepted WMC refinements never increase it.Source: §7.2 · pp. 12–13
• Under the averaged progress condition along STA–WMC’s actual trajectory, O(N0 + 1/(γε)) ordinary steps and O(mn(N0 + 1/(γε))) arithmetic suffice.For fixed N0 and γ, these become O(1/ε) steps and O(mn/ε) arithmetic; the condition is not inferred from a separate ordinary STA run.Source: §7.2 · p. 13

7.3 Comparison of complexity guarantees

• The hybrid preserves NWP’s guarantee while allowing STA and WMC progress, unlike the conditional O(1/ε) bounds for STA and STA–WMC.The conditional bounds require averaged progress along each method’s own trajectory.Source: §7.3 · p. 13

8 Computational comparisons

• The public-data study used 14 classification datasets, tolerance ε = 10^-6, three runs per query, and a nominal five-second allowance per run.Reported times include initialization, updates, and stopping tests, but exclude data preparation and independent answer verification.Source: §8 · pp. 13–14, Table 2 · p. 14
• The public-data queries test whether convex hulls of two labeled groups intersect or admit a strict separator, using normalized signed augmented columns.These are geometric feasibility tests, not prediction-accuracy tests; the study used full supplied training files and feature representations.Source: §8 · pp. 13–14
• STA–WMC completed every public-data case, while the hybrid also completed every case; STA and Nesterov completed ten consistently, and NWP completed eight.Nesterov also completed svmguide1 in one repetition near the deadline; all returned certificates passed independent checks.Source: §8 · pp. 14–15, Table 2 · p. 14
• STA was fastest on diabetes and colon-cancer, while the hybrid and STA–WMC improved completion on several cases where ordinary STA did not finish.The hybrid and STA–WMC medians were 2.27 and 2.97 seconds on Adult, but 1.61 and 0.0417 seconds on Splice; the hybrid guarantee did not imply the smallest measured runtime.Source: §8 · p. 15
• The 204 synthetic inputs comprise 66 random-membership, 72 boundary-membership, and 66 separation cases, with synthetic-study allowances distinct from the public-data budget.Random cases guarantee origin membership; boundary cases place the origin on a supporting face; separation cases place it at a prescribed positive distance outside the hull.Source: §8 · p. 15, Table 3 · p. 15
• STA–WMC completed all 204 synthetic cases, while the hybrid completed 192, including every separation case; Nesterov beat STA-based methods on the highest-dimensional random configuration.The synthetic comparison reports completion counts and broad timing patterns rather than rankings from small timing differences.Source: §8 · pp. 15–16, Table 3 · p. 15

9 Conclusions and practical guidance

• The hybrid has an unconditional O(mn√log n/ε) work bound including affine corrections, while STA and STA–WMC have conditional O(mn/ε) work for fixed averaged-progress constants.For ordinary STA, a three-point example establishes a sharp unconditional Θ(ε^-2) obstruction; the same conditional rate for STA–WMC requires the averaged condition along its actual ordinary-step sequence.Source: §9 · p. 16
• STA–WMC completes all 204 controlled synthetic cases and all public-data cases, while the hybrid completes all public-data cases but not every synthetic case within budget.STA is effective on favorable interior and separation instances; Nesterov is faster than STA-based methods on the highest-dimensional random configuration.Source: §9 · p. 16

A Supporting proofs for Nesterov acceleration

• The appendix gives a self-contained proof of the Nesterov convergence estimate for the spherical convex-hull problem.It also explains how the simplex update is computed.Source: A Supporting proofs for Nesterov… · p. 16
• The simplex analysis uses the ℓ1 norm, with the convention 0 log 0 = 0.Source: A Supporting proofs for Nesterov… · p. 16
• The vectors xk, yk, and zk denote Nesterov iterates and are distinct from the Nemirovski iterates.Source: A Supporting proofs for Nesterov… · p. 16

A.1 Nesterov acceleration estimate

• Entropy d has minimum zero at x0 = 1/n, is bounded above by log n, and is 1-strongly convex in ℓ1.The proof also uses 1 as a valid smoothness constant and weights ωk = (k + 1)/2.Source: §A.1 · p. 16
• Proposition A.1 states an estimate for the Nesterov iterates that applies to any minimizer x* of f on the simplex.Source: §A.1 · p. 16
• On membership inputs, the estimate yields residual bound (24) through a potential-function induction and the minimizing property of the iterates.The proof bounds the potential using convexity and then uses f(x*) = 0 when the origin belongs to the convex hull.Source: §A.1 · pp. 16–17

• The update minimizes a linear term plus half the squared ℓ1 distance from the current iterate by transferring weight to a minimum-gradient coordinate.Source: §A.2 · p. 17
• Donors are positive-weight coordinates with gradients above the minimum, sorted by decreasing gradient, and candidate transfers are evaluated over cumulative donor-weight intervals.Source: §A.2 · p. 17
• The algorithm selects the candidate transfer with the smallest objective; transfers beyond the available donor weight cannot improve the objective.If no eligible donors exist, the current iterate is optimal.Source: §A.2 · p. 17
• Sorting takes O(n log n) time, while the remaining work and auxiliary storage are O(n).Source: §A.2 · p. 17