{"id":"46291889-1a12-420a-bd0a-152c90548287","arxiv_id":"2505.09349","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A primal-dual method with restricted dual steps and ball-shaped safety sets achieves safe iterates and O-tilde(1/eps^2) strong-convex sample complexity, the first zero-violation guarantee for primal-dual schemes.","lead":"This paper proposes a primal-dual algorithm that keeps every query inside a safe region when minimizing an unknown function under one smooth safety constraint, using noisy measurements. It claims a large improvement in sample efficiency over current safe-optimization methods, with the first safety guarantee for primal-dual updates.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unstated diameter bound is load-bearing: Lemma 4 and Lemma 6 reuse R=||x0-x*|| to bound arbitrary feasible or sublevel points; without it Delta_f can exceed the claimed bound and mu_d can vanish, so the stated rates and safe initialization are unsupported.","rationale":"I read the paper as proposing a genuinely new safe primal-dual scheme whose main claims are (i) every oracle query is feasible with high probability and (ii) sample complexities O~(1/eps^2), O~(1/eps^4), and O~(1/eps^6) for strongly convex, convex, and nonconvex problems. The high-level architecture is coherent: the dual feasibility half-line, safety balls around primal iterates, and local strong concavity of the dual are natural mechanisms. However, the proof relies on a finite radius R that is only ever assumed to bound the initial distance ||x0 - x*||. The reader's weakest-assumption analysis correctly identifies Lemma 6 as a place where this R is used to bound distances between x_lambda and the Slater point. I agree with that concern, and I would add that the same overloading of R appears earlier, in Lemma 4, where Delta_f is bounded using R without a diameter assumption. A concrete one-dimensional instance shows the Lemma 4 bound is false as stated. This is a real correctness risk because it touches both the initialization safety guarantee and the linear convergence that produces the headline rates. The gaps are plausibly fixable by adding an explicit diameter or sublevel-set bound and redefining Delta_f accordingly, so the appropriate disposition remains conditional rather than rejection. My agreement with the reader is partial rather than full because I see the diameter issue as broader than Lemma 6: it also breaks the initialization argument and the lambda* bound in Lemma 4. I do not see a reason to move the verdict from the reader's CONDITIONAL assessment.","tokens_in":27171,"tokens_out":28770,"duration_ms":295095,"concrete_test":"Run the one-dimensional instance f(x)=x^2, g(x)=(x-1)(x-2), x0=1.5, which satisfies the stated assumptions with R=0.5. Recompute Lemma 4's claimed bound Delta_f <= ||grad f(hat x)||R + (M_f/2)R^2 and compare it with the exact value Delta_f = max_{x in [1,2]} x^2 - 1 = 3. The bound gives 4*0.5 + 0.5 = 2.5 (or 2.25 using the paper's own estimate of ||grad f(hat x)||), so the lemma fails as stated. Then add an explicit diameter bound for the feasible set or the sublevel set {x : g(x) >= -beta/2}, and re-derive Theorem 13 to see whether the claimed rates survive.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central sample-complexity and safety claims depend on a finite radius R, but the assumptions only bound the initial distance ||x0 - x*|| <= R. This same R is then used in two load-bearing places. In Lemma 4, Delta_f := max_{x in X} f(x) - f(x*) is claimed to be bounded via ||grad f(hat x)||R + (M_f/2)R^2, which requires a diameter bound on X, not merely a bound on the distance from x0 to x*. A concrete counterexample to the stated bound is f(x)=x^2, g(x)=(x-1)(x-2), with feasible set X=[1,2], x*=1, x0=1.5, R=0.5. The exact Delta_f is 4-1=3, while the bound in Lemma 4 gives about 2.25. Thus the proof of Lemma 4, and hence the initialization lambda check = Delta_f/alpha in Algorithm 1 and the bound on lambda*, are not justified by the stated assumptions. Lemma 6 similarly asserts mu_d >= beta^2/(4R^2(M_f + lambda M_g)) for all lambda with g(x_lambda) >= -beta/2, using the same R as if every such x_lambda lay within R of the Slater point. Without an explicit bound on the sublevel set, mu_d can be arbitrarily small, so the linear convergence of dual iterates in Theorem 13, and therefore the O~(1/eps^2), O~(1/eps^4), and O~(1/eps^6) claims, do not follow. This is not merely a loose constant: it is a missing assumption that affects both safety of the initial phase and the convergence rates.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a primal-dual method (SCSA, extended to SafePD) for stochastic optimization with a single smooth inequality constraint, with the requirement that every oracle query be feasible. The algorithm first chooses a sufficiently large dual variable, then alternates between dual gradient-ascent steps and primal minimization over a safety ball, and finally uses a regularization scheme for nonconvex problems. The main theoretical claims are high-probability safety of all primal and dual iterates and sample complexities of O~(1/eps^2), O~(1/eps^4), and O~(1/eps^6) for strongly convex, convex, and nonconvex problems, respectively. An extension to multiple constraints via smoothing is also sketched.","tokens_in":27540,"tokens_out":18086,"duration_ms":178423,"significance":"If the claims hold, this would be a substantial improvement over the log-barrier baseline LB-SGD and would be the first primal-dual safe optimization method with zero constraint violation under a stochastic first-order oracle. The algorithmic idea is attractive: restricting dual steps to the primal feasibility set and chaining safety balls is a natural and potentially useful construction. The paper provides explicit algorithms, proof sketches, and supporting experiments. However, the two lemmas that carry the convergence rates rely on an unstated uniform radius R; until that assumption is added or derived, the central safety and sample-complexity claims are not established.","major_comments":[{"comment":"The bound Delta_f <= ||grad f(hat x)|| R + (M_f/2) R^2 is asserted with R defined only by ||x0 - x*|| <= R, but the argument requires a bound on the diameter of the feasible set X. The stated bound is false even when X is bounded: take f(x)=x^2, g(x)=(x-1)(x-2), x0=3/2, and R=1/2; then Delta_f = f(2)-f(1) = 3, while the claimed bound is 4*(1/2) + (1/2)*(1/4) = 2.25. Since Algorithm 1 sets lambda_0 = Delta_f/alpha and Lemma 9 relies on lambda_0 >= (f(x0)-min_x f(x))/(-g(x0)), the safe-initialization step is not justified by the stated assumptions. The authors should either add an explicit diameter bound on X or prove an alternative bound on Delta_f from the existing assumptions.","section":"Section 3, Lemma 4"},{"comment":"Lemma 6's lower bound mu_d >= beta^2/(4R^2(M_f + lambda M_g)) is obtained by bounding ||x_lambda - x_tilde|| <= R for every lambda with g(x_lambda) >= -beta/2. No such uniform bound follows from Assumptions 1, 2, 3, and 8, which only give ||x0 - x*|| <= R; the proof explicitly uses 'the bounded diameter of the set ||x_tilde - x|| <= R' without adding this as an assumption. If this sublevel set has large diameter, mu_d can be arbitrarily small, and the linear contraction of the dual iterates in Theorem 13 - and hence the O~(1/eps^2), O~(1/eps^4), and O~(1/eps^6) sample complexities claimed for strongly convex, convex, and nonconvex problems - does not follow. This is a load-bearing missing assumption and should be stated explicitly or derived from additional regularity conditions.","section":"Section 3, Lemma 6"},{"comment":"The extension to multiple constraints by replacing max_i g_i(x) with a smoothed surrogate does not, as written, preserve safety with respect to the original constraint. The safety chain and Lemma 7 are proved for the smoothed constraint h_nu, and h_nu(x) <= 0 does not imply max_i g_i(x) <= 0 when h_nu is only an approximation of the maximum. The paper needs a margin condition - for example h_nu(x) <= -nu - and should account for this margin in the stated sample complexity of the multi-constraint extension.","section":"Section 6"}],"minor_comments":[{"comment":"The keyword 'safe leaning' appears to be a typo and should read 'safe learning'.","section":"Abstract / Keywords"},{"comment":"The LB-SGD sample-complexity rates are quoted inconsistently: the text says O~(1/eps^4), O~(1/eps^6), O~(1/eps^7) for strongly convex, convex, and nonconvex problems, while Table 1 lists O~(1/eps^5), O~(1/eps^6), O~(1/eps^7). Please reconcile the two statements.","section":"Section 1 and Table 1"},{"comment":"The proof defines lambda_hat* as 'arg min_{lambda in R} d(lambda)', but d is a concave dual function and the intended object is the maximizer. This typo makes the proof of the inequality -g(x_lambda) >= (mu_d/2)(lambda - lambda*) harder to follow.","section":"Appendix C.1, proof of Lemma 23"},{"comment":"The accuracy condition on eta_t is stated in Lemma 11 as eta_t <= mu_f(-g_hat(x_{t-1}))^2/(32 L_g^2), while the proof uses eta_t <= mu_f(-g_hat(x_t))^2/(8 L_g^2). The discrepancy should be fixed and the exact value used in Algorithm 1 should be referenced.","section":"Section 4.1, Lemma 11"},{"comment":"The captions refer to a 'shady area' without defining it; please state whether it is the min-max range or the standard deviation over the 10 runs.","section":"Section 7, Figures 3 and 4"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the unstated uniform radius R used in Lemmas 4 and 6. If the authors cannot add a legitimate assumption that makes this radius available, the central sample-complexity claims will need to be withdrawn or substantially reframed. The multi-constraint extension also needs a safety-margin argument before it can be considered a contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the half-line observation is real, and safe primal-dual with zero violations is a genuinely new angle. But the paper as written doesn't prove its headline rates. Both the initialization safety and the dual strong-concavity constants need a bounded-diameter assumption that isn't in the paper.\n\nWhat's new: with a single smooth constraint, the primal-feasible region in dual space is exactly {λ ≥ λ*}, and the authors exploit that by keeping dual iterates on that half-line and confining primal steps to Lipschitz safety balls. That is a clean conceptual contribution, and the two-mechanism design (safe initialization via a large λ0, safe transitions via \\hat{S}(xt)) is a natural and elegant way to get zero-violation primal-dual updates. The claimed rates (O~(1/ε^2) strongly convex, O~(1/ε^4) convex, O~(1/ε^6) nonconvex) are a real jump over LB-SGD, and the proof structure is coherent if the missing assumptions are supplied.\n\nThe soft spots are load-bearing. The stress-test note is right: Lemma 4's bound on Δf uses R=||x0-x*|| to bound f(\\hat{x})-f(x*) for \\hat{x} that can be far from x0. Concretely, f=x^2, g=(x-1)(x-2), X=[1,2], x*=1, x0=1.5, R=0.5 gives true Δf=3 but the claimed bound ≈2.25. So \\check{λ}=Δf/α may not satisfy Lemma 9's safety condition, and the initial phase can be unsafe. Lemma 6 has the same problem: μd ≥ β^2/(4R^2 M_L) assumes every xλ with g(xλ)≥-β/2 is within R of the Slater point, but Lipschitz gives a lower bound on distance, not an upper bound. Without a diameter bound on the sublevel set, μd can be arbitrarily small and the linear convergence in Theorem 13 collapses; the O~(1/ε^2) rates do not follow. These are fixable by adding a bounded-diameter assumption and adjusting the initialization argument, but as stated the theorems are not established. Lemma 31 also adds conditions on regularizers (μf≥ρf/2, μg≥ρg/2) that aren't highlighted in the main text.\n\nCredit where due: the paper is honest that the experiments are illustrative, the prior-work table is useful, and the disturbance analysis in Appendix C is careful given the intended assumptions. The self-citation to LB-SGD is appropriate, not a red flag.\n\nWho should read it: people working on safe black-box optimization with first-order methods. The idea will likely be cited regardless of whether these rates survive. Recommendation: send to serious referees, but ask them to require a clean statement of the boundedness assumption and a repaired Lemma 9 before the rates are taken at face value.","headline":"A genuinely new safe primal-dual idea whose headline rates currently rest on an unstated diameter bound and a shaky initialization lemma; worth a serious referee, not worth citing as-is.","tokens_in":28127,"tokens_out":6459,"would_cite":false,"duration_ms":58510,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C30","90C47"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes a primal-dual method for black-box minimization under a single unknown smooth safety constraint that keeps every iterate and oracle query feasible with high probability and reaches sample complexity $\\tilde…","keywords":["safe optimization","safe learning","primal-dual method","single smooth constraint","sample complexity","stochastic first-order oracle","KKT conditions","nonconvex optimization"],"falsifier":"Run the algorithm on a one-dimensional strongly convex instance such as $f(x)=x^2$, $g(x)=(x-1)^2-1$, and measure the number of dual iterations needed to reach complementary slackness $\\varepsilon_c$; then repeat on a version with a long flat corridor in the constraint sublevel set while keeping $\\|x_0-x^*\\|\\le R$. If the iteration count grows polynomially in the corridor length instead of staying $O(\\log 1/\\varepsilon_c)$, the uniform-diameter premise behind Lemma 6 fails and the stated rates do not follow.","tokens_in":26915,"feed_emoji":"🔒","tokens_out":14123,"duration_ms":140707,"temperature":0.7,"pith_summary":"The paper proposes a primal-dual algorithm for black-box minimization under a single unknown smooth safety constraint, with access to noisy first-order measurements of both the cost and the constraint. The central aim is to prove that one can solve the problem to accuracy $\\varepsilon$ while every primal and dual iterate, and every oracle query, remains feasible with probability at least $1-\\delta$. The paper claims sample complexity $\\tilde O(1/\\varepsilon^2)$ for strongly convex objectives, $\\tilde O(1/\\varepsilon^4)$ for convex objectives, and $\\tilde O(1/\\varepsilon^6)$ for non-convex objectives, improving on the previous log-barrier baseline in each setting. The method is presented as the first primal-dual approach with a safety guarantee of this kind. If correct, safety under a single smooth constraint no longer requires dimensionally exploding Bayesian optimization or noise-amplified log-barrier gradients.","feed_headline":"Safe primal-dual hits near-optimal sample complexity","feed_subtitle":"All iterates and queries stay feasible while beating log-barrier rates in every convexity regime.","key_machinery":"The argument is carried by a chain of nested safety balls $S(x_t)=B_d(x_t,-\\hat g(x_t)/L_g)$: any point in such a ball is strictly feasible by the $L_g$-Lipschitz continuity of $g$. At each step the algorithm estimates $\\hat g(x_t)$ from a minibatch, updates the dual variable with step size $\\gamma=\\mu_f/(8L_g^2)$, and solves the primal subproblem constrained to the safety ball, so every inner iterate remains safe. The matching smoothness and local strong concavity of the dual function, with $\\mu_d\\ge \\beta^2/(4R^2(M_f+\\lambda M_g))$, convert these safe steps into linear convergence of the dual iterates, giving the outer-iteration count $O(\\log 1/\\varepsilon_c)$. For non-convex problems, quadratic regularizers around the previous iterate make each subproblem strongly convex, and the same ball-chain machinery is reused in the outer loop.","core_discovery":"The paper's central claim is that for a single smooth constraint, the dual view exposes the safe region directly: the primal feasibility set in dual space is the halfline $\\{\\lambda\\ge \\lambda^*\\}$, where $\\lambda^*$ maximizes the dual function $d(\\lambda)=\\min_x [f(x)+\\lambda g(x)]$. Starting from a deliberately large dual variable $\\check\\lambda$ and taking small dual-gradient steps toward $\\lambda^*$, the corresponding primal minimizers $x_\\lambda$ stay feasible. Moreover, by bounding each step so that $x_{\\lambda_{t+1}}$ lies inside the safety ball $S(x_t)=B_d(x_t,-\\hat g(x_t)/L_g)$, the algorithm can move safely from one primal iterate to the next using any feasible inner solver. The dual function is smooth and locally strongly concave, so the dual iterates converge linearly, and from this the paper derives the rates described above. The same construction is extended to non-convex problems by solving a sequence of strongly convex regularized subproblems, and to multiple constraints by smoothing the maximum of the constraints.","pith_inferences":["The safety geometry only uses the constraint's Lipschitz constant, not its smoothness, so a version of the same ball-chain argument should extend to nonsmooth constraints with a Hölder or Lipschitz modulus; the paper does not develop this.","The rates hide the local-strong-concavity constant, which depends on the diameter of the near-boundary sublevel set; for large feasible sets the practical iteration count will scale with that diameter even though the stated assumptions do not bound it.","Since all guarantees hold with probability $1-\\delta$, translating this method to a physical system requires setting $\\delta$ from a risk budget; the minibatch sizes grow like $\\log(T/\\delta)/\\varepsilon^2$, so confidence amplification is cheap in $\\varepsilon$ but not free."],"forward_implications":["In the strongly convex regime, the sample complexity $\\tilde O(1/\\varepsilon^2)$ matches the standard unconstrained stochastic-gradient rate up to logarithms, so the single constraint becomes essentially cost-free in sample count.","The convex rate $\\tilde O(1/\\varepsilon^4)$ and non-convex KKT rate $\\tilde O(1/\\varepsilon^6)$ improve on the log-barrier baseline's $\\tilde O(1/\\varepsilon^6)$ and $\\tilde O(1/\\varepsilon^7)$; extending to multiple constraints via smoothed max costs one factor $1/\\varepsilon$ but still beats the baseline in the convex and strongly convex cases.","Every outer step is an ordinary dual-gradient update plus one minibatch constraint estimate, and any feasible constrained solver can play the inner role, so improvements in strongly convex optimization transfer directly to safe learning.","The output is a certified $(\\varepsilon_p,\\varepsilon_c)$-approximate KKT point; under the stated accuracy conditions this also yields an $\\varepsilon$-optimal feasible value, not merely a feasible point."],"supporting_citations":[{"why":"Supplies the rank-condition strong concavity result that Lemma 6 adapts to the single-constraint case.","marker":"Yu and Neely (2015)"},{"why":"Provides the dual-function Hessian formula used to lower-bound local strong concavity.","marker":"Bertsekas (1997)"},{"why":"The log-barrier safe optimization baseline whose sample complexity the new rates are compared against.","marker":"Usmanova et al. (2023)"},{"why":"Defines the Bayesian-optimization safe learning approach that motivates the need for better scaling methods.","marker":"Berkenkamp et al. (2016)"},{"why":"Gives the randomized smoothing procedure used to turn the max of multiple constraints into a single smooth constraint.","marker":"Duchi et al. (2012)"},{"why":"Provides the moving-regularizer technique used by the non-convex Algorithm 3 to build a sequence of strongly convex subproblems.","marker":"Zhang et al. (2020)"},{"why":"Source of the constraint-qualification condition that Assumption 16 extends for the non-convex proof.","marker":"Mangasarian and Fromovitz (1967)"}],"fun_headline_variants":["Primal-dual keeps all iterates safe under one smooth constraint","First primal-dual with provably safe updates for smooth constraints","Dual view unlocks safe optimization with linear convergence","Safe primal-dual beats log-barrier rates while staying feasible"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claimed rates rely on a uniform bound on how far the Slater point is from every point with constraint slack at least $-\\beta/2$; the listed assumptions only bound the initial distance to the optimum, and if the feasible region contains a long near-flat corridor the local strong concavity constant $\\mu_d$ can collapse, breaking the linear dual convergence and the $O(1/\\varepsilon^2)$ rate.","fun_headline_variants_meta":{"raw":{"variants":["Primal-dual keeps all iterates safe under one smooth constraint","First primal-dual with provably safe updates for smooth constraints","Dual view unlocks safe optimization with linear convergence","Safe primal-dual beats log-barrier rates while staying feasible"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00074,"raw_usage":{"total_tokens":3287,"prompt_tokens":915,"completion_tokens":2372,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":531,"completion_tokens_details":{"reasoning_tokens":2303}},"tokens_in":531,"tokens_out":2372,"duration_ms":17887,"temperature":1.0,"reasoning_tokens":2303,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:35:49.781340+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the algorithm on a one-dimensional strongly convex instance such as $f(x)=x^2$, $g(x)=(x-1)^2-1$, and measure the number of dual iterations needed to reach complementary slackness $\\varepsilon_c$; then repeat on a version with a long flat corridor in the constraint sublevel set while keeping $\\|x_0-x^*\\|\\le R$. If the iteration count grows polynomially in the corridor length instead of staying $O(\\log 1/\\varepsilon_c)$, the uniform-diameter premise behind Lemma 6 fails and the stated rates do not follow.","supporting_citations":[{"cited_title":"Log barriers for safe black-box optimization with application to safe reinforcement learning, 2023","cited_arxiv_id":null,"evidence_quote":"The log-barrier safe optimization baseline whose sample complexity the new rates are compared against."},{"cited_title":"A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems","cited_arxiv_id":null,"evidence_quote":"Provides the moving-regularizer technique used by the non-convex Algorithm 3 to build a sequence of strongly convex subproblems."}],"review_version":1}