{"id":"bbcdc683-f5a9-4937-866d-741f2859eb13","arxiv_id":"2607.20769","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For smooth strongly convex problems, the required memory scales as (ρ^K/ε)^{dΘ} up to a square-root gap in ε; for convex problems with β-growth (β>2) the scaling is polynomial in ε^{-1} with a K-phase transition beyond which extra memory gives no benefit.","lead":"This paper derives worst-case bounds on how many precomputed optimal solutions must be stored offline to guarantee ε-accurate answers after K online gradient steps for parametric convex problems. It shows the memory-computation tradeoff is driven by the optimizer's convergence rate and by the Lipschitz sensitivity of the solution map to the problem parameter.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"β-growth lower bound (Thm 4) uses hard instance requiring RX>RΘ and RX+RΘ≥2.314, conditions absent from theorem; lower bound unproven for small-X geometries.","rationale":"The reader identified exactly this gap: the β-growth lower bound's hard-instance construction requires RX>RΘ and RX+RΘ≥2.314, which are not stated in Theorem 4. My reading of Appendices E and F confirms that the lower-bound proof relies on these conditions in more than a cosmetic way: they ensure the unconstrained minimizer is feasible, the PGD trajectory avoids the boundary of X, and the constant 0.865RΘ used in the Bernoulli-inequality step is valid. Without them, the lower bound is unproven for a substantial part of the assumed parameter space. I do not see a comparably serious flaw in the upper bounds or in the strongly convex Theorem 1: the upper bound is a direct covering argument, and the lower-bound construction there satisfies its stated feasibility condition RX≥√(LΘRΘ/μ), with constants absorbed into Ω. The β-growth gap is therefore the single most load-bearing concern. It does not invalidate the framework, the upper bounds, or the experimental plausibility; it calls for either adding the missing geometric conditions to Theorem 4 or extending the lower-bound construction. Since the reader's CONDITIONAL verdict already reflects this concern, no verdict change is needed.","tokens_in":30891,"tokens_out":9454,"duration_ms":81005,"concrete_test":"Analytically or numerically check the small-X regime with dΘ=1, Θ=[-1,1] (RΘ=1), X=[-0.1,0.1] (RX=0.1), β=4. Use the same hard-family template, but clip the unconstrained optimum to X and run projected gradient descent with η=1/Lf,2; compute the exact or numerically converged minimum memory M(K,ε) for a few values of ε, K. Compare with the RHS of Eq. (22): Ω((min{Lf,2,LΘ}RΘ^2)^{dΘ/β}[ε^{-(β-2)/β}−C2K]_+^{dΘ/(β-2)}). If the observed M falls below this lower bound for some ε,K (e.g., because one stored solution covers all θ with |θ| above the clamp threshold), the theorem as stated is false; if the lower bound still holds, the missing geometric conditions are harmless and the theorem only needs a clarifying remark.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's near-matching lower bound for the β-growth regime (Theorem 2, restated as Theorem 4, Eq. (22)) is proven via the hard family f(x;θ)=Φ||x − (θ;0)/(RX+RΘ)||^β in Appendix F, which explicitly reuses the construction of Appendix E. That construction is stated with the restrictions 'with RX > RΘ (strict) and RX + RΘ ≥ 2.314' (Appendix E, just below Eq. (13)). These restrictions are not present in Theorem 4's hypotheses, which only assume compact X and Θ with radii RX and RΘ and β-growth (Assumptions 1–4 and 6). The proof needs these geometric conditions to guarantee that the unconstrained minimizer x⋆(θ)=θ/(RX+RΘ) lies in X, that the warm start x0 and all PGD iterates remain in B2(0,RΘ) (where the sublinear convergence analysis is valid), and that the initial distance bound ≤0.865RΘ used in the Bernoulli/linearization argument holds. If RX≤RΘ, the constructed minimizer may leave X, the projection onto X becomes active, and the PGD trajectory analysis in Appendix E, including the telescoping bound leading to Eq. (20), is no longer valid. Thus the stated Ω lower bound, and with it the claimed phase transition in K, is not established for all geometries satisfying the theorem's assumptions. This is load-bearing because the paper's central contribution is the matching/near-matching characterization of M(K,ε) and the claim that the phase transition appears in both upper and lower bounds.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a semi-amortized parametric optimization protocol: an offline phase stores M optimal solutions at selected parameters; online, a nearest-neighbor warm start is refined by K projected gradient descent steps. It defines M(K,ε), the minimal memory needed to guarantee ε-accuracy over the whole parameter space, and derives upper and lower bounds for μ-strongly convex objectives (Theorem 1) and for convex objectives satisfying a β-growth condition with β>2 (Theorem 2, restated as Theorem 4). It also provides corollaries on the memory cost of acceleration, a meta-framework reducing the analysis to an optimizer convergence rate and a solution-map sensitivity, and experiments on parameterized Tikhonov regression.","tokens_in":31218,"tokens_out":12502,"duration_ms":108737,"significance":"If the results held in the stated generality, they would provide a useful complexity-theoretic characterization of memory–computation tradeoffs in amortized optimization: memory scales with the parameter dimension dΘ rather than the decision dimension dX, linearly convergent optimizers are exponentially expensive to accelerate, and β-growth problems exhibit a phase transition in the online budget K. The paper's strengths include explicit constants, detailed proofs in the appendices, no fitted parameters in the bounds, a clear reduction framework, and experiments whose structural constants are computed in closed form. The main caveat is that both lower-bound proofs rely on geometric restrictions on X and Θ that are not present in the theorem statements, so the matching/near-matching lower bounds are not yet established for the full claimed class.","major_comments":[{"comment":"The lower bound in Theorem 4 is proved by reusing the hard family (13) from Appendix E, which is introduced 'with RX > RΘ (strict) and RX + RΘ ≥ 2.314' (Appendix E, below Eq. (13)). Neither condition appears in Theorem 4's hypotheses. These conditions are needed for the proof: the unconstrained minimizer x⋆(θ)=θ/(RX+RΘ) must lie in X, the warm start and all PGD iterates must remain in B2(0,RΘ) where the sublinear analysis is valid, and the initial distance must satisfy ∥x0−x⋆∥≤0.865RΘ for the Bernoulli/linearization step leading to Eq. (20). If RX≤RΘ or RX+RΘ<2.314, the projection onto X can become active and the telescoping argument in Appendix E is no longer valid. Thus the Ω lower bound in Eq. (22), and with it the claimed phase transition in K, is not established for all geometries satisfying Assumptions 1–4 and 6. The same issue affects the lower-bound statement of Theorem 2 in Sect","section":"Theorem 4 / Appendix F, Eq. (22)"},{"comment":"The lower-bound construction in Appendix D assumes RX ≥ sqrt(LΘRΘ/µ) to ensure that the unconstrained minimizer x⋆(θ)=LΘθ/(µRX) lies in B2(0,RX). This condition is not part of Theorem 1's statement or of Assumptions 1–5. If RX < sqrt(LΘRΘ/µ), the analytic minimizer is outside X, the projection onto X is active, and the derivation of the exact warm-start gap and the tight rate ρ² collapses. Hence the bound Ω((RΘLΘρ^K/√ε)^{dΘ}) is not proved for the full parameter regime claimed. The theorem should either include this condition explicitly or be extended with a different hard instance for small X.","section":"Theorem 1 / Appendix D"}],"minor_comments":[{"comment":"The abstract says 'matching upper and lower bounds' for the strongly convex case, but Theorem 1 has an ε versus √ε gap in the exponent; the body correctly calls these 'almost matching.' Please reword the abstract to avoid overstating the result.","section":"Abstract and Section 4.1"},{"comment":"The notation '−O(K)' and '−Ω(K)' inside the bounds is non-quantitative; the explicit constants C1 and C2 appear only in Theorem 4 in Appendix F. Please use the explicit constants in the main statement.","section":"Theorem 2 statement, Section 4.2"},{"comment":"Mα(K) is defined as the 'minimum memory required' for a prescribed acceleration, but Corollaries 1 and 2 only provide suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff suff su","section":"Section 4.3 and Contributions"}],"recommendation":"major_revision","confidential_remarks":"The two missing-geometry issues are the main technical hurdle. They may be fixable: either add the geometric conditions to the theorem statements (which would narrow but not destroy the contribution) or construct different hard instances for the small-X regime. I would support acceptance after such a revision, but not before."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere's my read on 2607.20769. It does something genuinely new: it gives the first worst-case memory rates for semi-amortized parametric optimization with a nearest-neighbor warm start and K PGD steps, and it identifies the two structural drivers (convergence rate of the online optimizer, Lipschitz sensitivity of the solution map). The strong-convexity and β-growth bounds, the phase transition in K, and the exponential-vs-polynomial memory cost of acceleration are real contributions. The meta-framework is clean and likely to be reused.\n\nThe problems start with the word \"matching.\" Theorem 1's bounds differ by a factor of two in the exponent of ε, and Theorem 2's by a factor β. That's not matching. The abstract oversells it. The acceleration corollaries are also only sufficient constructions, despite the paper saying Mα(K) is the \"minimum memory\" required. That's a terminology issue, minor.\n\nBigger: both lower bounds have unstated geometric conditions that the proof needs and the theorem statements omit. For Theorem 4 (the β-growth lower bound), the hard instance in Appendix E requires RX > RΘ and RX+RΘ ≥ 2.314. Those conditions never appear in Theorem 4's hypotheses. The proof depends on them to keep the iterates in a region where the sublinear convergence analysis works and the Bernoulli step holds. Without them, the claimed Ω bound is not established. The same pattern appears in the strongly convex lower bound: the construction needs RX^2 ≥ LΘRΘ/μ, which is not in Theorem 1's assumptions. So both lower bounds are conditional on geometry that the theorems do not state. This is load-bearing because the paper's selling point is the phase transition showing up in both upper and lower bounds.\n\nOn the other hand, the upper bounds are simple and correct, and the lower-bound constructions are clever and likely correct under the stated (but omitted) conditions. The experiments are qualitative but align with the theory. Self-citation [13] is limited and not circular. No fitted constants, no suspicious claims otherwise.\n\nWho is this for? Anyone working on amortized optimization, warm-starting, or algorithms with predictions in continuous optimization. The paper deserves a serious referee: the core idea is novel and the gaps are fixable. I'd send it to review with a recommendation of major revision — add the missing conditions to the theorem statements (or fix the proofs), fix the \"matching\" language, and tone down the \"minimum\" claims to \"sufficient.\"","headline":"A real first pass at a memory-computation theory for amortized optimization, but the lower-bound theorems overclaim: they need geometry conditions that never make it into the statements.","tokens_in":31721,"tokens_out":4430,"would_cite":true,"duration_ms":41471,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C60"],"pacs":[],"model":"deepseek-v4-flash","headline":"Semi-amortized optimization's memory needs scale with parameter dimension, not solver dimension","keywords":["amortized optimization","memory complexity","parametric convex optimization","projected gradient descent","warm-start","covering number","strong convexity","beta-growth condition"],"falsifier":"Construct a strongly convex parametric family with fixed parameter dimension dΘ and two different decision dimensions dX; if the measured minimal memory M(K,ε) moves with dX, Theorem 1's dΘ-only scaling fails. Alternatively, on a β-growth family with known Φ,Lf,2, fix ε and increase K while adding memory; if required memory keeps shrinking when K is pushed past the predicted threshold ε^{-(β-2)/β}, the phase-transition claim is contradicted.","tokens_in":30753,"feed_emoji":"⚖️","tokens_out":7109,"duration_ms":62626,"temperature":0.7,"pith_summary":"Offline memory can substitute for online computation when solving a family of parameterized convex optimization problems, but the exchange rate is set by two structural quantities: how fast the online optimizer converges and how sensitively the optimal solution moves with the problem parameter. This paper proves that the minimum memory M(K,ε) needed to guarantee ε-accuracy after K steps of projected gradient descent scales as (ρ^K/ε)^{dΘ} for strongly convex smooth problems — up to a factor of two in the ε exponent — where dΘ is the dimension of the parameter space, not the dimension of the decision variable. For objectives satisfying a β-growth condition with β>2, the memory requirement is close to (ε^{-(β-2)/β} − K)^{dΘ/(β-2)} and exhibits a phase transition: once K reaches roughly ε^{-(β-2)/β}, additional memory provides no benefit. The paper also shows that accelerating a fast linearly-convergent solver with memory is exponentially costly in K, while accelerating a slow sublinear solver is only polynomially costly. These bounds, verified on parameterized ridge regression, give the first matching memory–computation–accuracy characterization for semi-amortized parametric convex optimization.","feed_headline":"Memory cost follows parameter dimension, not solver dimension","feed_subtitle":"For smooth convex problems, memory scales as (ρ^K/ε)^{dΘ}; past a K threshold, extra stored solutions stop helping.","key_machinery":"The central object is the (K,ε)-Θ-net: a finite set of stored parameters whose nearest-neighbour predictor returns a warm start close enough that K steps of projected gradient descent reach ε accuracy. Memory complexity M(K,ε) is the minimum cardinality of such a net. The proof machinery reduces the problem to covering Θ at radius R ≈ E^{-1}(K,ε)/(2LΘ), where E(K,gap) is PGD's convergence-rate bound and the optimality gap is Lipschitz in the parameter with constant 2LΘ (Lemma 3). The lower bounds are produced by explicit hard function families — a quadratic with minimizer x⋆(θ)=(LΘ/μRX)(θ,0) for strong convexity, and f(x;θ)=Φ∥x−(θ,0)/(RX+RΘ)∥^β₂ for β-growth — whose PGD dynamics are exactly","core_discovery":"The paper establishes that the memory complexity M(K,ε) — the fewest stored optimal solutions needed so that K steps of projected gradient descent reach ε accuracy for every parameter — is governed by a covering of the parameter space whose radius is set by the optimizer's convergence rate and the parameter-Lipschitz constant of the objective. Theorem 1 gives Ω((RΘLΘ ρ^K/√ε)^{dΘ}) ≤ M(K,ε) ≤ O((RΘLΘ ρ^K/ε)^{dΘ}) under μ-strong convexity and smoothness, where ρ=1−μ/Lf,2 is PGD's contraction rate; thus memory depends on the parameter dimension dΘ rather than the decision dimension dX, and warm-start memory is useful only while K < log(1/ε)/log(1/ρ). Theorem 2 extends near-matching bounds to co","pith_inferences":["Editorial inference: the dΘ-dependence means any reduction in effective parameter dimension — a manifold, sparsity, or symmetry — should multiplicatively shrink memory; this is a roadmap, not a result, in the paper.","Editorial inference: the β-growth phase transition should be visible in a single experiment: fix ε and plot required memory vs K; the curve should flatten at K≈(16βLf,2/((β−2)Φ^{2/β}))ε^{-(β-2)/β}. The paper's Figure 2 already shows this flattening for β=4,6.","Editorial concern about the lower bound: the hard instance requires RX>RΘ and RX+RΘ≥2.314, conditions absent from Theorem 2's statement; whether the Ω bound survives without them is open.","Editorial extension: the meta-framework's two-input structure suggests the same memory–computation tradeoff can be derived for accelerated methods, projection-free schemes, or nonconvex problems once their convergence rates are known."],"forward_implications":["Memory scales with the parameter dimension dΘ, not the decision dimension dX, so amortization is viable precisely when the parameter space is low-dimensional relative to the decision space.","Under strong convexity, extra memory yields essentially nothing once K ≥ log(1/ε)/log(1/ρ); past that threshold PGD alone already reaches ε-accuracy and M(K,ε)=Θ(1).","Accelerating fast solvers is exponentially expensive: to improve PGD's linear rate by a factor α, memory must grow like (1/α)^{KdΘ}.","For β-growth problems with β>2, memory is a cheap substitute: the memory cost of α-acceleration grows only polynomially in K.","A phase transition separates the regimes: beyond K≈ε^{-(β-2)/β}, memory stops helping; the transition appears in both upper and lower bounds, marking it intrinsic to the problem class."],"fun_headline_variants":["Amortized optimization: memory scales with parameter, not solution, dimension","For smooth convex problems, memory useful only when K is small","Quantified tradeoff: memory vs computation in semi-amortized optimization","Warm-start memory: extra storage stops helping past a K phase transition","Parameter-space covering sets memory need for K-step PGD"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the lower-bound hard instances are representative of all allowed geometries; the β-growth lower bound is proven only for instances satisfying RX>RΘ and RX+RΘ≥2.314, yet Theorem 2 states it without those conditions, so for other geometries the claimed memory requirement may be an overestimate.","fun_headline_variants_meta":{"raw":{"variants":["Amortized optimization: memory scales with parameter, not solution, dimension","For smooth convex problems, memory useful only when K is small","Quantified tradeoff: memory vs computation in semi-amortized optimization","Warm-start memory: extra storage stops helping past a K phase transition","Parameter-space covering sets memory need for K-step PGD"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000253,"raw_usage":{"total_tokens":1448,"prompt_tokens":838,"completion_tokens":610,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":582,"completion_tokens_details":{"reasoning_tokens":519}},"tokens_in":582,"tokens_out":610,"duration_ms":6220,"temperature":1.0,"reasoning_tokens":519,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T09:25:26.249288+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a strongly convex parametric family with fixed parameter dimension dΘ and two different decision dimensions dX; if the measured minimal memory M(K,ε) moves with dX, Theorem 1's dΘ-only scaling fails. Alternatively, on a β-growth family with known Φ,Lf,2, fix ε and increase K while adding memory; if required memory keeps shrinking when K is pushed past the predicted threshold ε^{-(β-2)/β}, the phase-transition claim is contradicted.","supporting_citations":[],"review_version":1}