Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness

Problem setting

• The work formulates lower bounds in the fixed finite-sum IFO model, where repeated component queries and history-dependent choices must be allowed.This scope is necessary to determine minimax complexity for modern variance-reduced methods.Source: §1 · pp. 1–2

Dense weak hiding

• Dense weak hiding distributes each hidden direction across a fixed sign table while making unopened links invisible to function values and gradients.A bounded radial map handles arbitrary query points, and balancing row revelation against admissible stages yields the √n factor.Source: §1 · p. 2

PL optimization

• For 3 ≤ κmax ≤ √n, the lower bound is Ω(n + n log(Δ/ε)/[1 + log(√n/κmax)]), with globally strongly convex average objectives.For κmax ≥ √n, the construction gives the corresponding geometrically weighted regime.Source: §1 · p. 2

Nonconvex optimization

• Ω(n + √n ΔLmax/ε^2) is the matching nonconvex IFO lower bound for randomized algorithms with unrestricted component and query selection.The result matches PAGE and SPIDER under individual and mean-squared smoothness.Source: §1 · pp. 1–2

PL optimization

• Restarted PAGE matches the PL lower bounds under mean-squared smoothness and improves the standard PAGE guarantee when κms < √n.Each epoch costs O(n) calls in expectation and contracts the function-value gap by Θ(κms/√n).Source: §1 · p. 2

Nonconvex stationarity

• Earlier individual-smoothness nonconvex bounds were only Ω(n + ΔLmax/ε^2) or Ω(ΔLmax/ε^2), below the PAGE and SPIDER rate.The gap persisted because existing arguments either imposed linear-span structure or did not preserve the average gradient.Source: §2 · p. 3
• The new lower bound recovers the missing √n factor without a linear-span restriction for randomized finite-sum IFO algorithms.Earlier unrestricted-query constructions lost signal by assigning separate blocks to components.Source: §2 · p. 3

PL lower bounds

• For PL problems, prior results covered deterministic full-gradient or linear-span methods and generally required large condition numbers, while all-condition-number bounds could be only Ω(n).The paper instead covers randomized IFO algorithms for every κmax ≥ 3.Source: §2 · p. 3

Strongly convex connections

• The small-κ construction has a globally strongly convex average objective, extending the corresponding denominator to unrestricted randomized IFO algorithms under individual smoothness.Its components need not be convex, unlike classical strongly convex finite-sum lower bounds.Source: §2 · pp. 3–4

Proof techniques

• Dense weak hiding replaces span-based progress arguments with fixed encoding tables and mutual-information control of what component replies reveal.This handles randomized component choices and arbitrary query points.Source: §2 · p. 4

Scope and assumptions

• The formal setting allows arbitrary finite dimensions, and the hard-instance dimension may depend on problem parameters and the oracle budget.The paper notes that its lower bounds assume n exceeds a universal threshold.Source: §3 · p. 4

Algorithmic scope

• The randomized IFO algorithm may adapt component indices and query points to private randomness and the complete transcript, with no linear-span or zero-respecting restriction.Algorithms may repeat indices, stop randomly, and return unqueried points.Source: §3 · p. 4

Nonconvex stationarity

• For nonconvex stationarity, the IFO complexity is tight under both smoothness models, with PAGE and SPIDER supplying the upper bound and the same hard instances supplying the lower bound.The result applies when 0 < ε^2 ≤ c0ΔLs.Source: §3 · p. 5

PL complexity

• Theorem 3.3 gives matching PL lower bounds under individual and mean-squared smoothness for every κs ≥ 3.The hard instances are individually Lmax-smooth and also satisfy mean-squared smoothness with the same bound.Source: §3 · p. 5
• In the small-κmax branch, the average hard objective is globally strongly convex even though its components need not be convex.This supplies the small-condition-number regime under individual smoothness.Source: §3 · p. 5

4 DENSE WEAK HIDING

• Dense weak hiding combines a fixed sign table, bounded radial map, and smooth threshold gate to hide stages from unrestricted queries.The gate makes unopened links contribute neither function value nor gradient.Source: §4 · pp. 5–6
• Each component stores one weakly biased row, but averaging all rows exactly recovers ρΘ(j), preserving the hidden direction after rescaling.The table is fixed before interaction, so repeated queries to a component return the same row.Source: §4 · p. 6
• The bounded radial map converts any query point into a unit-ball alignment vector, preventing arbitrarily large queries from bypassing the construction.Its derivative bounds do not depend on the ambient dimension, while the induced row derivatives scale as O(1/ρ).Source: §4 · p. 6
• At ρ ≍ n−1/2, the row-cost–stage-count tradeoff is maximized and produces an Ω(√n ΔLmax/ε2) lower-bound factor.The two branches balance at nρ = ρ−1; Proposition C.6 formalizes the tradeoff for every admissible bias.Source: §4 · pp. 6–7

5.1 ONE-STAGE INFORMATION BOUND

• At ρ ≍ n−1/2, revealing one hidden stage requires Ω(n) distinct component rows, even when indices depend on the complete preceding transcript.The mutual information in the first r rows is only O(Drρ2), while repeated indices add nothing.Source: §5.1 · p. 7

5.2 SEQUENTIAL COMPOSITION ACROSS STAGES

• Unopened future links have zero value and gradient, so stages can only be completed in order except on the separately controlled future-alignment event.This makes the sequential composition argument compatible with unrestricted query points.Source: §5.2 · p. 7
• Assigning calls to the current stage and bounding unusually fast completions shows that stage costs add across successive revelations.If J stages finish within N ≤ rJ/2 calls, at least J/2 must finish unusually quickly, enabling a Markov bound.Source: §5.2 · p. 7

6.1 NONCONVEX STATIONARITY

• At ρ ≍ n−1/2, the nonconvex construction uses Θ(ΔLmaxρ/ε2) stages, giving an Ω(√n ΔLmax/ε2) lower bound plus the complementary Ω(n) term.The scaling preserves individual smoothness, initial gap, and an 8ε gradient barrier for an unfinished final stage.Source: §6 · p. 7, §6.1 · p. 8

6.2 GLOBAL PL: TWO GEOMETRICALLY SCALED CONSTRUCTIONS

• For global PL, stage scales must decrease geometrically so the first unfinished stage controls the objective contribution of later stages.The large-κmax construction uses one scale for the gate and contribution, whereas the small-κmax construction separates them.Source: §6.2 · p. 8
• The single-scale geometric construction is admissible only when κmax ≳ √n, while 3 ≤ κmax < √n requires separate gate and contribution scales.For small κmax, the ratio Rj/Wj is ≍ κmaxρ, with Rj much smaller than Wj when κmax ≪ √n.Source: §6.2 · p. 8
• The PL constructions satisfy the required smoothness and curvature conditions, and an unfinished terminal stage leaves objective gap at least 8ε.For small κmax, the average objective is globally strongly convex; for large κmax, μ is the PL constant.Source: §6.2 · pp. 8–9

7 RESTARTED PAGE

• For small κms, each Θ(n)-call PAGE epoch shrinks the gap by qep = Θ(κms/√n), while κms ≥ √n requires longer epochs for constant contraction.This schedule reflects the hard instance’s Ω(n) stage-revelation cost and geometric gap reduction.Source: §7 · p. 9
• Algorithm 1 restarts PAGE with a full-gradient initialization, probabilistic refreshes, and a randomly selected iterate from each epoch.The displayed schedule sets p = 1/(n + 1), η = 1/[Lms(1 + √n)], and T = ⌈4(n + Aep)⌉.Source: §7 · p. 9
• Each epoch costs at most n + 3T expected IFO calls and contracts the objective gap, yielding the stated complexity bound after the required number of epochs.Appendix E proves the contraction and exact expected IFO cost.Source: §7 · p. 9

• Tight lower bounds hold under individual smoothness for nonconvex optimization and both κmax regimes under PL, while Restarted PAGE matches the PL rates.Source: §8 · p. 9
• The small-κmax hard construction has a globally strongly convex average objective.Source: §8 · p. 9
• Open directions include fixed ambient dimension, noisy finite-sum oracle models, and the range κ < 3.Source: §8 · p. 9
• The lower bounds assume n exceeds a universal threshold.Source: §8 · p. 9

AI USE STATEMENT

• The authors used large language model assistants for brainstorming, proof-draft review, and manuscript editing, then verified the final manuscript.Source: AI USE STATEMENT · p. 11

Appendix dependencies.

• Figure 2 separates shared lower-bound arguments from the nonconvex, PL, and Restarted PAGE branches, with solid arrows marking proof dependencies.Source: Appendix dependencies · p. 12, Figure 2 · p. 12

A COMMON DEFINITIONS AND CALCULUS

• The lower bounds share a smooth threshold gate, fixed encoding table, and bounded radial map, with stage-indexed random objects and component-row coordinates.Source: A COMMON DEFINITIONS AND CALCULUS · p. 12

A.1 CONSTRUCTIONS AND BASIC PROPERTIES

• The encoding construction samples a fixed sign table whose rows have an exact average while causally revealed rows leave unseen labels uniformly assigned subject to residual sums.Source: §A.1 · p. 13, §A.2 · p. 14
• The admissible bias grid includes a choice with ρ on the order of n^-1/2, while the construction is uniform over parity-compatible biases and requires n ≥ 1024 for the optimized choice.Source: §A.1 · pp. 12–13

A.2 PROOFS OF THE SHARED PRIMITIVES

• The radial map stays inside the unit ball and supports dimension-free derivative control, while the smooth gate has flat regions that suppress derivatives outside its transition zone.Source: §A.1 · pp. 12–14, §A.2 · pp. 14–15

A.3 DERIVATIVE BOUNDS

• The derivative analysis bounds Hessians of gated links and radial gradients, enabling control of the block-row constructions used in the hard instances.Source: §A.3 · p. 15, §A.4 · p. 16

B DENSE WEAK HIDING: ONE-STAGE INFORMATION AND SEQUENTIAL REVELATION

• Dense weak hiding requires Ω(min{n, ρ^-2}) distinct rows to reveal one stage, and the sequential argument aggregates this row cost across stages.Source: B DENSE WEAK HIDING: ONE-STAGE… · p. 17

B.1 ONE-STAGE INFORMATION BOUND

• The one-stage proof bounds information in each newly revealed row, sums the first r distinct rows, and converts low mutual information into low early-alignment probability.Adaptive queries are fixed before unseen rows are observed; repeated rows contribute no new information, and a stopped history retains every query witnessing early alignment.Source: §B.1 · pp. 17, 18, 20
• Choosing the parity-compatible bias m ≥ √n yields the optimized one-stage bound with r = ⌊n/512⌋ and early alignment probability at most 1/8.This holds for n ≥ 1024 under the stated dimension condition.Source: §B.1 · pp. 17, 18, 21
• The coupling lemma transfers the one-stage probability bound to actual stage completion: completion before the rth distinct row is returned occurs with probability at most the same bound.The coupled interactions agree through the first completion query because completion is checked before the response.Source: §B.1 · pp. 21–22

B.2 SEQUENTIAL REVELATION

• Sequential revelation shows that, with per-stage early-completion probability at most p, row costs accumulate across stages while unrevealed future directions remain independent of the current interaction.The augmented interaction reveals a completed direction and the next initialization row without an additional IFO call, while the truncated interaction omits unopened links.Source: §B.2 · pp. 22–23
• For radial chains satisfying the stated independence, reply, completion, and call-assignment conditions, every query paired with a future stage—and the final output—has bounded alignment.The same control extends to arbitrary target failure probability with only logarithmic growth in the dimension.Source: §B.2 · pp. 22–23
• Sequential revelation bounds future-stage information and makes augmented and truncated interactions agree pathwise when future gates remain unopened.A union bound gives P(Efuture) ≤ 1/128, while incomplete stages reveal no next-stage information beyond a possible initialization row.Source: §B.2 · p. 24

B.3 COUNTING CALLS ACROSS STAGES

• Disjoint stage-assigned calls and Markov’s inequality transfer per-stage completion bounds to the original IFO, yielding the stated multi-stage lower bound.The argument does not assume independence across stages; Corollary B.6 uses p = 1/8 per stage and δ = 1/128 jointly.Source: §B.3 · pp. 24–25

B.4 AUXILIARY QUADRATIC FOR THE ADDITIVE n TERM

• An auxiliary quadratic establishes the standalone Ω(n) IFO lower bound that supplies the additive n term in Theorems 3.1 and 3.3.Each exact response reveals its selected encoding row, while mutual-information control and Fano’s inequality prevent accurate recovery from at most N ≤ floor(n/4) calls.Source: §B.4 · pp. 25–26

C NONCONVEX FIRST-ORDER LOWER BOUND

• Theorem 3.1 applies to fully adaptive randomized IFO algorithms, allowing history-dependent queries and measurable outputs, and guarantees a hard finite sum in a suitable dimension.The theorem fixes n ≥ 1024, Lmax, Δ, and ε under the stated parameter relation, then bounds algorithms using at most the theorem’s specified call budget.Source: C NONCONVEX FIRST-ORDER LOWER BOUND · p. 26

C.1 CONSTRUCTION

• The construction hides each stage direction in a fixed biased sign table and uses smooth gates so unopened links contribute neither function values nor gradients.A response before stage completion uses only the current table, while a completion response may expose one successor initialization row.Source: §C.1 · pp. 26–27, §C.3 · p. 28

C.2 INITIAL GAP AND INDIVIDUAL SMOOTHNESS

• Individual smoothness is controlled independently of the number of stages and dimension through the bias-dependent bound H(ρ), with the optimized bias satisfying the stated universal bound.The component smoothness analysis uses bounded gate derivatives and block-row estimates, avoiding factors depending on T or D.Source: §C.2 · p. 28

C.3 GRADIENT LOWER BOUND AND SCALING

• For tunable bias ρ, the scaled instance is Lmax-smooth, has initial gap at most Δ, and requires Tρ = Θ(ΔLmaxρ/ε^2) stages to avoid an 8ε gradient.The bias–smoothness tradeoff converts the row threshold and stage count into an IFO lower bound for randomized algorithms under the stated admissibility conditions.Source: §C.3 · p. 29

C.4 OPTIMIZED BIAS

• With the optimized parity-compatible bias ρ ≍ n^-1/2, the construction yields the Ω(√n ΔLmax/ε^2) nonconvex lower bound when the optimized stage count is at least two.The final stage is reserved for the algorithm’s output, while earlier stages consume the row budget needed for sequential revelation.Source: §C.3 · p. 29, §C.4 · p. 30
• Ω(√n ΔLmax/ε^2) queries are required while the output satisfies ∥∇F(X̂)∥≥8ε.This follows from T−1≥T/2 and nρ=m=Θ(√n).Source: §C.4 · p. 31
• The reserved last stage makes the lower-bound conclusion valid for an output that was never queried.The construction reserves this stage specifically to handle the unqueried output.Source: §C.4 · p. 31
• Under the displayed requirement, D=O(log((N+2)(T+2))) and d=TD.The dimension relation follows after substituting the preceding parameter choices.Source: §C.4 · p. 31

C.5 THE LINEAR SAMPLE-SIZE TERM

• When T < 2, an auxiliary quadratic supplies the full lower bound.The construction uses the quadratic defined in Lemma B.9.Source: §C.5 · p. 31
• The optimized bias satisfies ρ = Θ(n^-1/2), making the condition T ≥ 2 equivalent up to universal constants to the complementary complexity regime.The radial-chain construction is applied where its second complexity term is at least a constant multiple of n.Source: §C.5 · p. 31
• Choosing c0 sufficiently small ensures γ ≤ Lmax, so every component remains Lmax-smooth in the auxiliary construction.The budget is also reduced so that N ≤ ⌊n/4⌋.Source: §C.5 · p. 31
• In the complementary regime, √n ∆Lmax/ε^2 = O(n), so the target n + √n ∆Lmax/ε^2 bound is itself O(n).The quadratic argument completes the bound in this regime after adjusting universal constants.Source: §C.5 · p. 31

D PROOFS FOR THE GLOBAL PL BOUNDS

• Geometric stage scales prevent the PL constant from shrinking with chain length by making the first unfinished stage control the remaining contribution.The two-scale construction handles the range where the weighted geometric ratio is inadmissible, while the weighted chain treats the large-κ branch.Source: D PROOFS FOR THE GLOBAL PL BOUNDS · pp. 31–32

Appendix A. The row S(j)

• The shared fixed sign-table encoding averages each component’s row contribution to the full hidden stage signal, while smooth threshold gates make unopened links and their gradients vanish.The gate thresholds distinguish information-stage completion from full opening, and all staged constructions use the same encoding table.Source: D PROOFS FOR THE GLOBAL PL BOUNDS · p. 32, Appendix A · p. 32

D.5 VERIFICATION OF INDIVIDUAL SMOOTHNESS

• Every weighted-chain component is individually smooth with a Hessian bound independent of the number of stages, dimension, weight tail, and smallest weight.The construction verifies component smoothness using the explicit bound Hmain and the admissible gate parameter range ρ ≤ 17/512.Source: §D.1 · p. 33, §D.5 · p. 37

D.2 DECOMPOSITION OF THE GAP BY BLOCKS

• The weighted construction proves a global PL inequality by decomposing the gap into nonnegative block terms and using the first gate that is not fully open to create a gradient barrier.When all gates are open, strong convexity controls the gap; otherwise, later contributions are bounded by the weighted tail factor T(w).Source: §D.2 · p. 34, §D.3 · p. 35, Figure 5 · p. 35

D.6.1 WEIGHT GEOMETRY AND STAGE COUNT

• The weighted branch changes regimes at κmax = √n, with κmax ≥ κw(n) := 2Γ√n required for its geometric construction and the bounded transition interval covered separately.After rescaling, the construction enforces the target initial gap and individual smoothness, while an unrevealed suffix preserves objective error.Source: §D.6.1 · p. 37, §D.6.2 · pp. 38–39

D.6.3 SEQUENTIAL REVELATION, QUERY COST, AND DIMENSION

• The information-cost analysis yields M = O((κmax/√n) log(∆/ε)) stages and converts sequential revelation into the weighted-chain lower-bound call count.The argument combines one-stage information costs, dimension d = MD, and logarithmic requirements absorbed into a single accuracy-dependent factor.Source: §D.6.3 · p. 39

D.7 AUXILIARY Ω(n) BOUND

• For κmax ≥κw(n) := 2Γ√n, the weighted chain together with an auxiliary quadratic proves the lower bound, with the auxiliary term supplying Ω(n) when needed.The weighted construction has failure probability 95/128, while the auxiliary argument has failure probability 11/16.Source: §D.7 · p. 40

D.8 TWO-SCALE CHAIN: CONSTRUCTION

• For 3 ≤κmax <√n, the two-scale chain separates gate scales Rj from contribution scales Wj, preserving sequential hiding while respecting individual smoothness.Using the short scale for contributions would exceed the Lmax Hessian budget; the longer Wj scale reduces component curvature while Rj activates the next stage.Source: §D.7 · p. 40, §D.8 · p. 42, Figure 6 · p. 42
• The two-scale construction has individually Lmax-smooth components and a globally µ-PL average; for 3 ≤κmax ≤√n, its average is also µ-strongly convex.The construction is globally μ̄-strongly convex, with μ̄ = µ in the small-κmax range.Source: §D.8 · p. 42

D.9 TWO-SCALE CHAIN: ANALYTIC PROPERTIES

• The analytic bounds control every component’s nonlinear Hessian by a universal fraction of Lmax, while exact averaging preserves the corresponding mean-scale bounds and establishes the µ-PL property.The proof uses block-row Hessian bounds and the fixed table average, whose nonlinear terms gain a factor ρ.Source: §D.9 · p. 43

D.10 TWO-SCALE CHAIN: SEQUENTIAL HIDING AND STAGE COUNT

• For every n ≥ n0 = 1024, κmax ≥ 3, and 0 < ε ≤ c∆, every randomized algorithm using fewer than the stated IFO-call threshold fails with probability at least 11/16 on some individually Lmax-smooth finite sum with globally µ-PL average objective and initial gap at most ∆.Source: §D.10 · p. 46

ASSEMBLY ACROSS ALL CONDITION-NUMBER REGIMES

• The regime assembly uses the two-scale branch below √n, the weighted branch above 2Γ√n, and the two-scale construction across the transition interval to obtain the corresponding lower bounds.Each multi-stage branch costs Θ(n) calls per stage, and the auxiliary quadratic supplies the remaining Ω(n) term.Source: ASSEMBLY ACROSS ALL CONDITION-NUMBER… · p. 46

E RESTARTED PAGE UPPER BOUND

• Restarted PAGE achieves the Theorem 3.3 upper bound under mean-squared smoothness and global µ-PL, using an epoch whose expected cost is at most n + 3T and whose contraction factor satisfies qT ≤1/4.The epoch combines full-gradient refreshes with single-component difference updates; the restart length is chosen across both condition-number regimes.Source: E RESTARTED PAGE UPPER BOUND · p. 47, §E.1 · p. 47

E.1 CONTRACTION AND COST OVER ONE EPOCH

• E[F(b_x) − F* | x] ≤ q_T(F(x) − F*), with q_T := κ_ms(1 + √n).The contraction follows by summing the Lyapunov descent over the epoch and applying the pointwise PL inequality.Source: §E.1 · p. 48
• The epoch uses at most n + 3T expected IFO calls.The initial full gradient costs n calls; refreshes cost n calls, while difference updates cost two calls in expectation, yielding an expected per-update cost at most 3.Source: §E.1 · p. 48
• The proof combines objective-smoothness descent with PAGE estimator recursions in a Lyapunov function initialized using an exact full gradient.The estimator recursion is obtained by conditioning on refresh and difference updates and applying mean-squared smoothness.Source: §E.1 · p. 48

E.2 RESTARTS TUNED TO THE CONDITION NUMBER

• The guarantee assumes global PL and mean-squared smoothness, with initial gap at most Δ and target accuracy satisfying 0 < ε ≤ cΔ.The bound is stated for a universal constant c < 1.Source: §E.2 · p. 49
• The common epoch rule sets A_ep = κ_ms(1 + √n), T = ⌈4(n + A_ep)⌉, and repeats epochs until the expected gap reaches ε.Repeated conditioning gives an expected gap that contracts geometrically across epochs.Source: §E.2 · p. 49
• O(n log(Δ/ε)) calls follow from lengthening small-κ_ms epochs to T = Θ(n), which strengthens contraction to Θ(κ_ms/√n).The estimator is unchanged, and each epoch still costs Θ(n) because it begins with a full gradient.Source: §E.2 · p. 49
• For κ_ms ≥ √n, choosing T = Θ(κ_ms(1 + √n)) yields the standard large-condition-number schedule with constant contraction.The parameter A_ep is Ω(n) in this regime, so the epoch cost is Θ(A_ep).Source: §E.2 · p. 49

F.1 FROM DETERMINISTIC TO RANDOMIZED ALGORITHMS

• Conditioning over private randomness transfers deterministic hard-distribution bounds to a fixed instance on which the randomized algorithm retains the stated failure probability.Every supported instance has initial gap at most Δ, individually L_max-smooth components, and, for PL instances, satisfies the global PL inequality.Source: §F.1 · p. 50

F.2 A GENERIC CAPPING LEMMA

• A capping lemma converts expected stopping-time guarantees into fixed-call guarantees using Markov’s inequality and a measurable fallback output.The argument uses a union bound over stopping-time and error events and requires no independence.Source: §F.2 · p. 50

F.3 APPLICATIONS TO UPPER AND LOWER BOUNDS

• The fixed-budget arguments convert Restarted PAGE guarantees and randomized lower bounds into expected-call complexity statements for nonconvex and PL optimization.The conversion uses truncation, rescaling, and constant-success-probability arguments; the resulting bounds are identified with Theorems 3.1 and 3.3.Source: §F.3 · pp. 50–51

G.1 FORMAL IFO MODEL AND THEOREM CONVENTIONS

• The randomized IFO model permits adaptive component indices and query points, repeated indices, arbitrary queries, randomized stopping, and unqueried outputs.Queries are measurable with respect to the complete preceding transcript and the private random seed.Source: §G.1 · p. 52
• The formal nonconvex theorem uses n0 = 1024 and failure probability p0 = 11/16, with a dimension-dependent construction for large n.For n below the threshold, replicating one hard function across components preserves the asymptotic order up to universal constants.Source: §G.1 · p. 52
• Prior PL results cover restricted condition-number ranges or give only Ω(n) across all κ_ms, motivating the appendix’s explicit parameter-range comparisons.The cited logarithmic result requires κ_ms ≥729196√n, while the all-range result gives only Ω(n).Source: §G.1 · p. 53
• The new upper bounds use κ_ms, while the lower-bound instances use κ_max and remain individually smooth, so they also belong to the mean-squared class.This links the individual-smoothness hard instances to the corresponding mean-squared lower bounds.Source: §G.1 · p. 53

G.2 ASSUMPTIONS ON THE FUNCTION CLASSES

• Mean-squared smoothness does not imply three componentwise inequalities at the same numerical constant: uniform component bounds, componentwise co-coercivity, or separate-reference-point bounds.Proposition G.1 establishes these failures using convex quadratic finite sums.Source: §G.2 · p. 54
• A component gradient can have a Lipschitz constant √n times larger than the mean-squared constant, invalidating sampled-component descent or self-bounding steps at the same scale.The appendix also notes that related variance-to-Bregman and separate-reference-point inequalities fail under mean-squared smoothness alone.Source: §G.2 · pp. 54–55
• Mean-squared smoothness controls all components at one common pair of points, not estimates that pair each component with its own reference point.This is the specific scope boundary exposed by the separate-reference-point counterexample.Source: §G.2 · p. 54

G.3 MEAN-SQUARED SMOOTHNESS OF THE DENSE CHAIN

• The dense chain has mean-squared smoothness L_ms = Θ(L_max), with universal constants independent of n, D, and T.The upper bound follows from individual smoothness, while the lower bound is obtained from a Hessian witness involving the gated chain link.Source: §G.3 · p. 55
• The smoothness comparison preserves the hard-instance construction across the two smoothness classes rather than relying only on an aggregate-class lower bound.The appendix’s containment discussion emphasizes that a lower bound for a larger aggregate class does not automatically transfer to the smaller individual class.Source: §G.2 · p. 53, §G.3 · p. 55