{"id":"7e3a7cf6-2f1e-40fb-8d49-3aef14bcaaf0","arxiv_id":"1908.09941","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper provides stochastic algorithms with O(1/epsilon^{4/v}) iteration complexity for finding near-stationary points of non-convex inf-projection objectives, with a variance-regularization application.","lead":"This paper develops stochastic algorithms for non-convex inf-projection problems, where the objective is the minimum over an auxiliary variable, covering difference-of-convex and bi-convex problems. It proves first-order convergence rates and shows faster variance-based regularization than a min-max baseline on four large datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Stationarity measure omits normal cone for constrained X; Lemma 4's boundary optimality equality breaks the main convergence claim.","rationale":"The reader's weakest assumption identifies the same normal-cone/boundary issue, and my reading agrees. This is load-bearing because the paper's headline contribution is the first convergence guarantee for stochastic inf-projection measured by dist(0,∂F(x)); if the stationarity measure does not match the constrained problem, the theorems do not establish the claimed guarantee. The counterexample uses only smooth g and l, simple uniformly convex h with bounded domain, and a one-dimensional interval X, so it falls directly under Theorem 2's hypotheses. The fix is clear: either state X=R^d (or assume iterates remain interior) or carry the normal cone through Definition 1 and Lemma 4. I did not find a separate fatal flaw: Proposition 1 and the smooth/nonsmooth complexity derivations appear internally consistent once the constrained stationarity is handled; the T_y^k/T_x^k typo in Theorem 3 and the Lemma 3/5 numbering mismatch are minor. For these reasons the conditional verdict should remain unchanged.","tokens_in":26132,"tokens_out":14607,"duration_ms":137395,"concrete_test":"Analytically test the counterexample X=[0,1], g=0, h(y)=y²/2+I_{[-B,B]}(y) with B>1, l(x)=x. Run the deterministic (noise-free) MSPG from x_1=y_1=0.5; the iterates converge to (1,1), where dist(0,∂F)=1, contradicting Theorem 2. Alternatively, re-derive Lemma 4 retaining N_X(v_k): the stated equality fails at v_k=1, and the proof cannot bound dist(0,∂F(v_k)) by the algorithm's contraction quantities.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Problem (1) and Algorithms 1–3 are explicitly constrained to a closed convex set X, yet Definition 1 measures stationarity by dist(0,∂F(x)) without the normal-cone term N_X(x). Lemma 4 (Appendix B.3) derives the key bound by writing the first-order optimality of v_k as 0=∇g(v_k)−∇l(x_k)^T y_k+γ(v_k−x_k); for v_k on the boundary of X the correct condition contains an additional N_X(v_k) term, so the equality and the resulting bound on ‖∇F(x_k)‖ or dist(0,∂F(v_k)) are not justified. The same gap enters Lemma 3, where dist(0,∂F) is bounded by ‖∇_x f‖, while Proposition 1 only controls dist(0,∂f) with respect to the joint constrained subdifferential; these quantities can differ when the x-constraint is active. A valid instance satisfying all Section 3 assumptions is X=[0,1], g=0, h(y)=y²/2+I_{[-B,B]}(y) with B>1, l(x)=x; then F(x)=−x²/2 and the global minimizer over X is x=1, at which dist(0,∂F(1))=1. Hence the stated convergence to an ε-stationary point of F cannot hold for general closed convex X unless the theorems are restricted to X=R^d or the stationarity notion is replaced by dist(0,∂F(x)+N_X(x)).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers non-convex and possibly non-smooth inf-projection problems of the form min_{x∈X} F(x) = g(x) + min_{y∈dom(h)} [h(y) - ⟨y, l(x)⟩], where X is a closed convex set. It proposes two stochastic algorithms: MSPG for the case where g and l are smooth but not necessarily convex, and St-SPG for cases where g or l are convex but possibly non-smooth, under monotonicity conditions on h*. The central theoretical claim is that these algorithms find an ε-stationary point of F measured by dist(0, ∂F(x)), with total iteration complexity O(1/ε^{4/v}) under the smoothness and uniform-convexity conditions summarized in Table 1. The paper also applies the inf-projection formulation to variance-based regularization and presents experiments comparing the proposed algorithms with min-max baselines.","tokens_in":26452,"tokens_out":10771,"duration_ms":89635,"significance":"If the stated convergence results are correct, this would be the first comprehensive stochastic convergence guarantee for non-convex inf-projection minimization measured directly in dist(0, ∂F(x)). The paper is largely self-contained: Proposition 2 on the SPG subproblem is re-derived in the appendix rather than merely cited, and the convergence rates are derived rather than fitted. The variance-based regularization experiments provide a useful empirical demonstration, and the complexity rates O(1/ε^{4/v}) are plausible and interesting. However, the stationarity measure used in the theorems omits the normal cone of the constraint set X, and this gap is load-bearing for the main claims.","major_comments":[{"comment":"The stationarity measure dist(0, ∂F(x)) in Definition 1 is the unconstrained subdifferential of F and does not include the normal cone N_X(x), even though Problem (1) constrains x to a closed convex set X and Algorithms 1–3 project onto X. For boundary points, the correct constrained stationarity condition is dist(0, ∂F(x) + N_X(x)) ≤ ε. The gap is not merely cosmetic: it falsifies the theorems as stated. Take X=[0,1], g=0, h(y)=y²/2 + I_{[-B,B]}(y) with B>1, and l(x)=x. Then F(x)= -x²/2 on [0,1], and the global minimizer is x=1 with dist(0,∂F(1))=1. Starting from x₁=y₁=1, both the x- and y-updates of MSPG stay at 1, so every output has dist(0,∂F(x_τ))=1, contradicting the claim of Theorem 2 that E[dist(0,∂F(x_τ))] ≤ ε. Lemma 3 bounds the unconstrained gradient of F, but it does not control the constrained stationarity of F+I_X; the same issue propagates through Lemma 4 and Corollaries 4–5.","section":"Definition 1; Lemmas 3–4; Theorems 2 and Corollaries 4–5"},{"comment":"The first-order optimality condition for v_k is written as the equality 0 = ∇g(v_k) - ∇l(x_k)^T y_k + γ(v_k - x_k). This equality is valid only if v_k lies in the relative interior of X or if X=R^d. If v_k is on the boundary of X, the optimality condition must include a normal-cone term n ∈ N_X(v_k). The subsequent bounds on ‖∇F(x_k)‖ and dist(0,∂F(v_k)) therefore do not follow for a general closed convex constraint set. Since these bounds feed directly into Corollaries 4 and 5, the stated convergence to ε-stationary points of the constrained problem is not established.","section":"Appendix B.3, Lemma 4"}],"minor_comments":[{"comment":"In the displayed statement, the inner-iteration budgets are mislabeled: it reads T_y^k = k/γ + 1 and T_t^k = k/µ + 1, but the proof and the constants in the displayed bounds require T_x^k = k/γ + 1 and T_y^k = k/µ + 1.","section":"Theorem 3"},{"comment":"In the derivation after 'Since ρ = ...', the second term involving G_l^v should be G_l^v ((1+v)/(2v))^v L_{h*} ‖x_{k+1} - x_k‖^v rather than ‖u_k - y_k‖^v; the final displayed bound with coefficient G_l^{v+1} is consistent with this correction.","section":"Lemma 4, Part I"},{"comment":"The symbol z_k in the last displayed bound of Lemma 4, Part II should be v_k, since the proof bounds ‖x_{k+1} - v_k‖. Also, Corollary 5 writes dist(0, ∇F(v_τ)) although g is non-smooth; the subdifferential notation dist(0, ∂F(v_τ)) is appropriate.","section":"Lemma 4, Part II and Corollary 5"},{"comment":"Rockafellar and Wets is cited as both 1998 and 2009; one entry should be removed or unified. In Section 5, hyper-parameter ranges such as λ ∈ {10^{-5}:2} are written in nonstandard set notation; interval or power-of-ten notation would be clearer.","section":"References and notation"}],"recommendation":"major_revision","confidential_remarks":"The constraint-set issue is the main obstacle to publication. The counterexample is simple and directly falsifies the stated theorems for general closed convex X, so the authors must either restrict the claims to X=R^d or, preferably, replace the stationarity notion with dist(0, ∂F(x)+N_X(x)) and adjust Lemmas 3 and 4 accordingly. I believe the gap is fixable within the manuscript's scope, and I would not require new experiments. The self-citation to Xu et al. 2018a is appropriate because the relevant subproblem convergence result is re-derived in the appendix."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First things first: this paper gives a useful unified treatment of stochastic inf-projection problems, and the main convergence proofs are mostly careful. The genuinely new bit is analyzing stationarity directly in terms of dist(0,∂F(x)) for the target function, covering both smooth and DC/bi-convex cases, and the inf-projection reformulation of variance-based regularization is a nice practical angle. I also appreciate that they re-derive the SPG subproblem convergence in the appendix instead of just pointing at Xu et al. 2018a.\n\nBut there is a real gap, and the stress-test note is right: the theory silently assumes the constraint set X is inactive. Definition 1 measures stationarity by dist(0,∂F(x)), without the normal cone term N_X(x). Lemma 4 in Appendix B.3 writes the first-order optimality of the subproblem solution v_k as 0=∇g(v_k)−∇l(x_k)^T y_k+γ(v_k−x_k), which only holds in the interior of X. On the boundary the correct condition includes N_X(v_k). This is not a nitpick. Take X=[0,1], g=0, h(y)=y^2/2+I_{[-B,B]}(y) with B>1, l(x)=x. Then F(x)=−x^2/2, the minimizer is x=1, and dist(0,∂F(1))=1. So the stated convergence to an ε-stationary point of F cannot hold as written for general closed convex X. The fix is straightforward: either restrict the theorems to X=R^d or replace the stationarity measure with dist(0,∂F(x)+N_X(x)). The rest of the proof machinery looks sound.\n\nOther soft spots are minor. There are a few typos—T_y^k/T_x^k mix-up in Theorem 3, z_k/v_k in Lemma 4, a constant typo—and the experiments lack error bars and released code, so the empirical claims are suggestive, not definitive. The citation pattern is fine; the self-citation is to the algorithm they build on, and they re-derive the key subproblem result.\n\nBottom line: the paper deserves a serious referee, but I would not accept it in the current form. It needs a statement that narrows the scope or repairs the normal-cone issue, plus typo cleanup. If that is done, the convergence results are likely correct for the unconstrained case, and the variance-regularization application would make it a solid contribution.","headline":"Solid framework for stochastic inf-projection problems, but the stationarity measure omits active constraint normals, so the stated convergence guarantee needs either X=R^d or a normal-cone-corrected measure.","tokens_in":26974,"tokens_out":5648,"would_cite":true,"duration_ms":54407,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper provides the first comprehensive stochastic convergence analysis for non-convex inf-projection problems, proving that its MSPG and St-SPG algorithms reach a (nearly) ε-stationary point of the target function with total…","keywords":["inf-projection minimization","non-convex optimization","stochastic proximal gradient","difference of convex functions","biconvex functions","stationary point","variance-based regularization","first-order convergence"],"falsifier":"Take $X=[0,1]$, $g(x)=0$, $h(y)=y^2/2$, and $\\ell(x)=x$, so $y^*(x)=x$ and $F(x)=-x^2/2$. The constrained minimizer is $x=1$, where $\\partial F(1)=\\{-1\\}$ and the boundary-free distance is $\\operatorname{dist}(0,\\partial F(1))=1$, even though $x=1$ is stationary in the constrained sense because the normal cone $N_X(1)=[0,\\infty)$ contains $-1$. Checking this boundary case settles whether the paper's stationarity measure is adequate for constrained problems.","tokens_in":25913,"feed_emoji":"🎯","tokens_out":9466,"duration_ms":90860,"temperature":0.7,"pith_summary":"This paper studies minimization problems of the form $F(x)=g(x)+\\min_y [h(y)-\\langle y,\\ell(x)\\rangle]$, where the inner minimization can be handled implicitly and the outer target $F$ is non-convex and possibly non-smooth, covering difference-of-convex functions and biconvex functions as special cases. The authors propose two stochastic algorithms—a mini-batch stochastic proximal gradient method (MSPG) when $g$ and $\\ell$ are smooth, and a stagewise stochastic proximal gradient method (St-SPG) when $g$ and $\\ell$ are convex but nonsmooth—and prove that both find a (nearly) $\\epsilon$-stationary point of $F$, measured directly by $\\operatorname{dist}(0,\\partial F(x))$, with iteration complexity $O(1/\\epsilon^{4/v})$. The significance is that this is, per the authors, the first comprehensive convergence guarantee for stochastic optimization of non-convex inf-projection problems in terms of the original target function rather than only the joint objective. The paper also shows that variance-based regularization can be reformulated in this inf-projection form, leading to empirically faster convergence than min-max formulations.","feed_headline":"Stochastic methods now hit stationary points of inf-projections","feed_subtitle":"Two algorithms converge to a (nearly) ε-stationary point of the target objective, covering DC and biconvex problems.","key_machinery":"The load-bearing object is the inf-projection structure itself: because $h$ is uniformly convex, the inner minimizer $y^*(x)=\\arg\\min_y [h(y)-\\langle y,\\ell(x)\\rangle]$ is unique, and under standard variational-analysis regularity the target subdifferential collapses to $\\partial F(x)=\\partial g(x)-\\nabla\\ell(x)^\\top y^*(x)$. The paper's bridging lemmas convert whatever stationarity measure the algorithm actually controls—$\\operatorname{dist}(0,\\partial f(x,y))$ for MSPG, or subproblem residuals $\\|x_k-v_k\\|$ and $\\|y_k-u_k\\|$ for St-SPG—into $\\operatorname{dist}(0,\\partial F(x))$, using the duality that $\\nabla h^*$ is $(L_{h^*},v)$-H\\\"older continuous exactly when $h$ is $p$-uniformly convex with $v=1/(p-1)$. That exponent $v$ is why every complexity bound in the paper has the form $O(1/\\epsilon^{4/v})$.","core_discovery":"The central claim is that stochastic first-order methods can converge to a stationary point of the inf-projected objective $F(x)=g(x)+\\min_y[h(y)-\\langle y,\\ell(x)\\rangle]$ itself, not merely to a stationary point of the joint function $f(x,y)$. Under smoothness and bounded-variance assumptions, MSPG achieves $\\mathbb{E}[\\operatorname{dist}(0,\\partial F(x_\\tau))^2]\\le O(1/T^v)$ when $g$ and $\\ell$ are smooth, giving $T=O(1/\\epsilon^{2/v})$ iterations and total cost $O(1/\\epsilon^{4/v})$ for an $\\epsilon$-stationary point. When $g$ and $\\ell$ are convex but possibly nonsmooth, St-SPG treats each stage as a strongly convex proximal subproblem in $x$ and $y$, and the paper's Corollaries 4 and 5 show the same $O(1/\\epsilon^{4/v})$ total complexity, returning a nearly stationary point when $g$ is nonsmooth. The argument works by bridging two levels of stationarity: the algorithm controls either $\\operatorname{dist}(0,\\partial f(x_\\tau,y_\\tau))$ or subproblem residuals $\\|x_k-v_k\\|$ and $\\|y_k-u_k\\|$, and Lemmas 3 and 4 convert those quantities into $\\operatorname{dist}(0,\\partial F(x))$ using H\\\"older continuity of $\\nabla h^*$ and Lipschitz properties of $\\ell$.","pith_inferences":["Inference: if a normal-cone term were added to the stationarity measure and to the first-order optimality equality in the proof, the same two-step bridge would likely extend to arbitrary convex compact sets $X$; the current analysis is cleanest when $X=\\mathbb{R}^d$ or when iterates stay in the interior.","Inference: the one-sample stochastic gradient trick for variance regularization should generalize to any objective containing functions of the empirical mean, such as $\\mathbb{E}[\\ell]^2$ or higher powers, because the dual variable $y$ carries the mean and no $n$-dimensional distribution is needed.","Inference: users of the nonsmooth case should remember the guarantee is 'nearly' stationary: the returned point itself may be only $O(\\epsilon^{1/v})$ away from an $\\epsilon$-stationary point, so comparing algorithms on raw gradient norms at the returned point will be pessimistic unless that offset is accounted for.","Inference: a direct stress test of the boundary caveat is to run St-SPG on a biconvex problem whose optimum lies on the boundary of $X$; the current theorem predicts the reported $\\operatorname{dist}(0,\\partial F(x))$ may fail to certify constrained stationarity there."],"forward_implications":["For smooth $g$ and $\\ell$, MSPG reaches $\\mathbb{E}[\\operatorname{dist}(0,\\partial F(x_\\tau))]\\le\\epsilon$ with total cost $O(1/\\epsilon^{4/v})$; when $h$ is strongly convex ($v=1$) this becomes $O(1/\\epsilon^4)$.","For convex nonsmooth $g$ and $\\ell$, St-SPG attains the same total complexity, and in the nonsmooth-$g$ case it returns a point within distance $O(\\epsilon^{1/v})$ of an $\\epsilon$-stationary point.","The inf-projection formulation is usable when $h^*(\\ell(x))$ is non-decomposable, because an unbiased stochastic gradient of the joint function costs one sample of $\\ell(x)$ rather than a gradient of the composition $h^*(\\ell(x))$.","The stagewise framework is modular: the inner SPG solver can be swapped for other stochastic algorithms for strongly convex subproblems without changing the stationarity-bridging argument.","For variance-based regularization, the inf-projection formulation introduces only a one-dimensional dual variable $y$, avoiding the $n$-dimensional distribution variable that makes min-max formulations scale poorly with sample size."],"supporting_citations":[{"why":"Supplies the variational-analysis chain rule that identifies $\\partial F(x)$ with $\\partial g(x)-\\nabla\\ell(x)^\\top y^*(x)$, the foundation of the stationarity measure.","marker":"Rockafellar & Wets, 2009"},{"why":"Gives the duality between $p$-uniform convexity of $h$ and $(L,v)$-H\\\"older continuity of $\\nabla h^*$, fixing the exponent $v$ used in every complexity bound.","marker":"Nesterov, 2015"},{"why":"Provides the stagewise stochastic DC algorithm template and the SPG convergence rates that St-SPG reuses.","marker":"Xu et al., 2018a"},{"why":"Supplies the stochastic strongly-convex convergence lemma used in the proof of Proposition 2.","marker":"Zhao & Zhang, 2015"},{"why":"Establishes mini-batch stochastic proximal gradient convergence for composite objective $f(w)$, the starting point of MSPG's analysis.","marker":"Ghadimi et al., 2016"},{"why":"Derives the empirical Bernstein bound that motivates variance-based regularization, the paper's application benchmark.","marker":"Maurer & Pontil, 2009"},{"why":"Provides the min-max stochastic algorithm and efficient dual update used as the empirical baseline in the experiments.","marker":"Namkoong & Duchi, 2016"}],"fun_headline_variants":["Provable stochastic convergence for non-convex inf-projection problems","Stochastic algorithms achieve stationarity for inf-projection objectives","First convergence guarantees for stochastic inf-projection minimization","Stochastic optimization of inf-projections with provable stationarity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the constraint set $X$ never actively constrains the solution: the proofs use equality-style first-order optimality and define stationarity without a boundary term, so if $X$ has a boundary the stated convergence to $\\operatorname{dist}(0,\\partial F(x))\\le\\epsilon$ may not certify a constrained stationary point.","fun_headline_variants_meta":{"raw":{"variants":["Provable stochastic convergence for non-convex inf-projection problems","Stochastic algorithms achieve stationarity for inf-projection objectives","First convergence guarantees for stochastic inf-projection minimization","Stochastic optimization of inf-projections with provable stationarity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000593,"raw_usage":{"total_tokens":2826,"prompt_tokens":1038,"completion_tokens":1788,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":654,"completion_tokens_details":{"reasoning_tokens":1721}},"tokens_in":654,"tokens_out":1788,"duration_ms":15227,"temperature":1.0,"reasoning_tokens":1721,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:58:35.802375+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $X=[0,1]$, $g(x)=0$, $h(y)=y^2/2$, and $\\ell(x)=x$, so $y^*(x)=x$ and $F(x)=-x^2/2$. The constrained minimizer is $x=1$, where $\\partial F(1)=\\{-1\\}$ and the boundary-free distance is $\\operatorname{dist}(0,\\partial F(1))=1$, even though $x=1$ is stationary in the constrained sense because the normal cone $N_X(1)=[0,\\infty)$ contains $-1$. Checking this boundary case settles whether the paper's stationarity measure is adequate for constrained problems.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the variational-analysis chain rule that identifies $\\partial F(x)$ with $\\partial g(x)-\\nabla\\ell(x)^\\top y^*(x)$, the foundation of the stationarity measure."},{"cited_title":"and Zhang, T","cited_arxiv_id":null,"evidence_quote":"Supplies the stochastic strongly-convex convergence lemma used in the proof of Proposition 2."},{"cited_title":"and Duchi, J","cited_arxiv_id":null,"evidence_quote":"Provides the min-max stochastic algorithm and efficient dual update used as the empirical baseline in the experiments."}],"review_version":1}