{"id":"8eafcb32-28db-4cfe-be3c-735c7eba18d8","arxiv_id":"2608.03170","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Three inexact augmented Lagrangian methods achieve optimal O(1/epsilon) primal-dual complexity for verifiable KKT points in convex linearly constrained optimization, two of them parameter-free.","lead":"This paper develops three augmented Lagrangian methods for linearly constrained convex optimization that achieve the optimal first-order complexity, O(1/epsilon), for computing verifiable approximate KKT points. It shows the classical unregularized AL framework can match the faster proximal variants without needing problem-dependent constants.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The displayed per-iteration bound in Theorem 2.8(b) has the max outside the square root, so the printed bound yields O(ε^{-3/2}) rather than O(1/ε); the central claim needs a repairable correction.","rationale":"The reader's verdict (CONDITIONAL) already identifies the displayed per-iteration bound in Theorem 2.8 as not implying the advertised O(1/ε) result, and my analysis confirms the concrete mechanism: the max term is placed outside the square root, producing an apparent ε^{-3/2} scaling. However, the reader's formal weakest_assumption emphasizes Assumption 2.3 and the deferred strongly-convex lemmas, whereas the most load-bearing and immediately checkable defect is this algebraic factor error in the printed complexity displays. The concern is real but repairable: replacing the displayed max-outside-sqrt bound with the expression obtained by direct substitution from Theorem 2.6 restores the O(1/ε) scaling, assuming the rest of the analysis (PF-AR's complexity, Proposition 2.12's outer bound) is sound. I therefore do not recommend changing the verdict: the paper's central claim is plausible and the flaw appears to be a fixable error in the statement/proof of Proposition 2.9(b) and Theorem 2.8, but the theorem as printed cannot be accepted without correction. The same factor misplacement should be checked in OPF-IAL and APF-IAL, since the paper's optimality claims for all three methods rely on it.","tokens_in":50424,"tokens_out":8356,"duration_ms":71451,"concrete_test":"Recompute Proposition 2.9(b) from Theorem 2.6, moving max{D²/(cε²), D/ρ} inside the outer square root, then substitute c = 1/ε, ρ = ε into the corrected expression to verify the total is O(Π(p0)||A||D/ε).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central advertised result, O(1/ε) gradient-evaluation complexity for (ε, ε)-approximate primal-dual solutions, does not follow from the theorem as printed. In Proposition 2.9(b), the PF-AR call inside O-IAL is bounded by O(sqrt(¯L + c||A||²) · max{D²/(cε²), D/ρ}). Combining with Proposition 2.12's outer-iteration count O(Π(p0)/(ε²c²)) and choosing c = O(1/ε), ρ = ε gives O(Π(p0) · (¯L + ||A||²/ε)^{1/2} · D²/ε) = O(ε^{-3/2}), not O(1/ε). The source of the error is that PF-AR's Theorem 2.6 complexity is O(sqrt(¯L_sub · D / ϵ_inner)), where ¯L_sub = ¯L + c||A||² and ϵ_inner = min{cε²/(4D), ρ}. Expanding this gives O(sqrt((¯L + c||A||²) · max{D²/(cε²), D/ρ})), i.e., the max belongs inside the square root, not outside as displayed in (2.27) and (2.24). The same factor misplacement appears in the OPF-IAL bounds (Proposition 2.17(b), Theorem 2.13) and in the APF-IAL proof. If corrected, the total bound with c = 1/ε, ρ = ε becomes O(Π(p0)||A||D/ε), which would support the advertised O(1/ε) claim. But as printed, the theorem's internal algebra is inconsistent, and the optimal-complexity conclusion is unsupported without this repair.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes three inexact augmented Lagrangian methods (O-IAL, OPF-IAL, APF-IAL) for linearly constrained convex composite problems with a compact nonsmooth domain. The central claim is that these methods attain an optimal O(1/epsilon) first-order complexity for finding verifiable (epsilon, epsilon)-approximate primal-dual (KKT) solutions in the convex case, with two parameter-free variants, and a near-optimal O(epsilon^{-1/2} log(1/epsilon)) bound in the strongly convex case. The algorithms preserve the standard unregularized AL subproblem structure and use two new parameter-free inner solvers: PF-AR for convex subproblems and R-FISTA for strongly convex subproblems. Numerical experiments on six problem classes compare O-IAL and APF-IAL against the proximal AL method of Lu and Mei, reporting frequent 5-50x speedups. The proofs combine a telescoping dual-distance argument for outer iterations with a parameter-free accelerated regularization analysis for inner iterations.","tokens_in":50997,"tokens_out":15764,"duration_ms":141273,"significance":"If the claimed bounds are correct, the paper settles an interesting structural question: standard, unregularized inexact AL methods, without proximal regularization, ergodic averaging, or knowledge of problem constants, can in principle match the optimal verifiable KKT complexity previously achieved only by specialized or proximal variants. The paper also contains a genuinely useful parameter-free composite stationarity solver, PF-AR, and a simplified restarted strongly convex solver, R-FISTA. The numerical study is broad and includes an SDP application, and the code is publicly linked. However, the advertised O(1/epsilon) conclusion rests on a load-bearing algebraic bound that is misstated in the printed theorems, and one key contraction estimate in the AR-L proof is not justified by the stated assumption; both issues are repairable but currently prevent the central claim from following as written.","major_comments":[{"comment":"The displayed inner complexity bound (2.27) is not implied by Theorem 2.6. Since PF-AR has complexity O(sqrt(L_sub D / epsilon_inner)) with L_sub = Lbar + c||A||^2 and epsilon_inner = min{c eps^2/(4D), rho}, the correct inner bound is O(sqrt((Lbar + c||A||^2) * max{D^2/(c eps^2), D/rho})), with the max inside the square root. As printed, the max is outside, giving O(sqrt(Lbar + c||A||^2) * max{D^2/(c eps^2), D/rho}). Substituting c = O(1/eps) into the printed bound yields O(eps^{-3/2}) for eps = rho, not O(1/eps). The same misplaced max appears in (2.24), (2.25), and in the OPF-IAL bounds (2.47) and Theorem 2.13. The advertised optimal O(1/eps) complexity therefore does not follow from the manuscript as written, although it does follow after moving the max inside the square root and then substituting c = 1/eps, rho = eps.","section":"Theorem 2.8(b), Proposition 2.9(b), and Theorem 2.13 / Proposition 2.17(b)"},{"comment":"The contraction estimate used to prove Theorem 2.4 is not justified. In (A.17)-(A.19) the authors conclude that (1/N_s) sqrt(2 c_A Lbar / sigma_s) <= 1/8 using the bound (A.18). But (A.18) is an upper bound on N_s, namely N_s <= 8 sqrt(2 c_A Lbar / sigma_s), so the displayed inequality has the wrong direction. To obtain a 1/8 contraction, one needs a lower bound on the number of inner iterations, e.g., a lower bound on the Lipschitz estimate L_s^k. The stated Assumption 2.3 only provides L_s^k <= c_A Lbar. This gap affects the proof of AR-L and hence the PF-AR complexity in Theorem 2.6, which is the engine behind all three AL methods. The issue is likely repairable by strengthening Assumption 2.3 to also require L_s^k >= Lbar / c_A, which standard backtracking or universal-gradient implementations do satisfy, but it must be stated and used consistently.","section":"Assumption 2.3 and Appendix A, Eqs. (A.17)-(A.19)"},{"comment":"The outer-iteration bound (2.36) is stated using Pi(p0), but the proof says 'let p* be an arbitrary optimal solution' and then uses ||p* - p0||^2. To obtain Pi(p0) one must choose p* to minimize the distance to p0, or take an infimum over optimal multipliers. As written the transition from 'arbitrary p*' to Pi(p0) is not immediate. This is a local fix, but it should be clarified.","section":"Proposition 2.12"}],"minor_comments":[{"comment":"The APF-IAL bound (2.50) does not contain the misplaced-max error found in O-IAL and OPF-IAL: the inner PF-AR estimate in Proposition 2.22(b) correctly places the tolerance inside the square root. It would be helpful to state explicitly that the O(1/eps) claim for APF-IAL is not affected by the correction needed in (2.27).","section":"Section 2.4, Theorem 2.20"},{"comment":"The numerical experiments set c = 10 (or c1 = 10) while the theoretical optimal complexity requires c = O(1/eps) with eps = 1e-5. The paper acknowledges testing outside the compact-domain assumption in some experiments but does not mention this deviation from the parameter regime of Theorem 2.8. A brief remark would help readers interpret the experiments.","section":"Section 4"},{"comment":"The strongly convex analysis relies on Lemma B.1, whose proof is omitted with a reference to prior work [43, 44]. Given that Lemma B.1 is load-bearing for the near-optimal strongly convex claims, the paper should either reproduce the proof or state very precisely which statements in [44] are being imported.","section":"Appendix B, Lemma B.1 and Proposition 3.2"},{"comment":"The terminology 'estimate of the Lipschitz constant' in Assumption 2.3 should specify whether L_s^k is an upper estimate, a lower estimate, or both up to a universal factor. The current wording 'L_s^k <= c_A Lbar' is compatible with the proof only if a lower bound of similar type is also assumed.","section":"Assumption 2.3"}],"recommendation":"major_revision","confidential_remarks":"The main advertised result is very likely recoverable: the max misplacement is a clear typo-level error that the authors can correct, and the Assumption 2.3 gap is fixable by adding a standard lower bound on the Lipschitz estimate. The paper's contributions are substantive and the numerical study is impressive. I would encourage the editor to send the revision back to the authors rather than reject, but the current version should not be accepted because the central O(1/eps) theorem, as printed, is internally inconsistent."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is a paper worth taking seriously, but the central theorem as printed has a repairable bug. In Proposition 2.9(b) and Theorem 2.8(a), the PF-AR subproblem cost is written as O(√(L + c‖A‖²) · max{D²/(cε²), D/ρ}). From Theorem 2.6, the actual cost is O(√((L + c‖A‖²) · max{D²/(cε²), D/ρ})) — the max belongs inside the square root. With the printed version and c = 1/ε, ρ = ε, you get O(ε^{-3/2}), not O(1/ε). The advertised optimal complexity is unsupported by the displayed algebra. The same misplacement propagates through the OPF-IAL and APF-IAL bounds.\n\nWhat the paper does well is real. It answers a structural question: standard unregularized AL methods can, in principle, reach verifiable KKT complexity O(1/ε) without proximal regularization, ergodic averaging, or parameter knowledge. PF-AR is a clean extension of Lan et al.'s accumulative regularization to composite problems, and the three AL variants are thoughtfully designed — best-iterate, restarted parameter-free, and adaptive last-iterate. The numerical study is extensive: six problem classes, 5–50× speedups over ProxALM, and code is on GitHub. The telescoping dual-distance argument in Lemma 2.11 is elegant.\n\nSoft spots, in proportion. The misplacement above is the main one; it is load-bearing but easily fixed. Second, the strongly convex results rely on the authors' own R-FISTA restart analysis, with key lemmas deferred to [44] and [43]. That is acceptable if those results are solid, but a referee should verify they cover the large-c subproblems used here. Third, Assumption 2.3 assumes an accelerated inner solver with Lipschitz estimate O(L + c‖A‖²); R-FISTA plausibly satisfies it, but it remains an assumption.\n\nNet: the central insight is likely correct, the paper is well structured, and the experiments are convincing. It deserves peer review, but the authors should be asked to fix the factor placement and to either prove or precisely cite the deferred lemmas. With that repair, this becomes a solid contribution to AL complexity theory.","headline":"The O(1/ε) claim is likely right but the printed algebra doesn't support it: the max in the PF-AR bound belongs inside the square root, so Theorem 2.8(b) as written yields O(ε^{-3/2}), not O(1/ε).","tokens_in":51410,"tokens_out":2920,"would_cite":true,"duration_ms":26776,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65K05","49M37","90C06","65K10","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that standard inexact augmented Lagrangian methods can compute verifiable approximate KKT points for linearly constrained convex composite problems at the optimal O(1/epsilon) first-order complexity, including…","keywords":["augmented Lagrangian","first-order methods","parameter-free","optimal complexity","verifiable termination","primal-dual solution","KKT point","linearly constrained convex optimization"],"falsifier":"Run OPF-IAL on a family of linearly constrained convex instances with known smoothness, domain diameter, and penalty parameter set to $c=1/\\epsilon$, measuring the total number of gradient evaluations needed to reach $\\|Az-b\\|\\le\\epsilon$ and $\\|r\\|\\le\\epsilon$ for $\\epsilon=10^{-3},10^{-4},10^{-5},10^{-6}$. If the empirical growth is worse than $\\mathcal O(1/\\epsilon)$ on a log-log plot, or if the output triple ever fails the containment and residual conditions of (2.2), then the central claim would be disproved.","tokens_in":50227,"feed_emoji":"🎯","tokens_out":6028,"duration_ms":56271,"temperature":0.7,"pith_summary":"This paper asks whether the classical inexact augmented Lagrangian (AL) architecture can find verifiable approximate KKT points for linearly constrained convex composite problems at the optimal $\\mathcal O(1/\\epsilon)$ first-order complexity, without proximal regularization, ergodic averaging, or prior knowledge of problem constants. It answers yes, constructing three methods, O-IAL, OPF-IAL, and APF-IAL, that attain $\\mathcal O(1/\\epsilon)$ gradient-evaluation complexity for finding an $(\\epsilon,\\epsilon)$-approximate primal-dual solution. Two of the methods are parameter-free, and all three give nonergodic guarantees, with a last-iterate guarantee for APF-IAL. In the strongly convex case the same methods reach $\\mathcal O(\\epsilon^{-1/2}\\log(\\epsilon^{-1}))$ without knowing the strong convexity modulus. The paper also reports speedups frequently ranging from 5 to 50 times over a representative proximal AL method on six problem classes.","feed_headline":"Inexact AL methods hit optimal O(1/epsilon) KKT complexity","feed_subtitle":"Standard, unregularized augmented Lagrangian loops need no proximal terms or tuned constants to reach the optimal rate.","key_machinery":"The central object is PF-AR, a parameter-free accumulative regularization method for convex composite minimization that produces verifiable stationarity certificates, i.e., a pair $(\\hat x,\\hat v)$ with $\\hat v\\in\\nabla\\psi_s(\\hat x)+\\partial\\psi_n(\\hat x)$ and $\\|\\hat v\\|\\le\\epsilon$ in $\\mathcal O(1/\\epsilon)$ gradient evaluations. PF-AR repeatedly calls a subroutine AR-L with doubling diameter guesses; AR-L uses a backtracking line-search and a termination criterion based on a true subgradient norm rather than a gradient mapping, which is essential for the AL analysis. The AL outer loop then combines approximate dual stationarity with the full multiplier update to obtain the telescoping estimate that bounds feasibility residuals by $\\|p^*-p_0\\|^2$. For strongly convex problems, a restarted FISTA scheme, R-FISTA, supplies the inner solver to reach $\\mathcal O(\\epsilon^{-1/2}\\log(\\epsilon^{-1}))$ complexity.","core_discovery":"The central claim is that the standard, unregularized inexact AL framework is sufficient for optimal verifiable primal-dual complexity. For problems of the form $\\min \\{\\psi_s(z)+\\psi_n(z) : Az=b\\}$ with convex smooth $\\psi_s$ and closed proper convex $\\psi_n$ on a compact domain, the paper constructs three AL methods that output a triple $(z,p,r)$ with $r\\in \\nabla\\psi_s(z)+\\partial\\psi_n(z)+A^*p$, $\\|r\\|\\le\\epsilon$, and $\\|Az-b\\|\\le\\epsilon$, in $\\mathcal O(1/\\epsilon)$ gradient evaluations. The key is to maintain approximate dual stationarity at every outer iteration; then the multiplier update $p_{k+1}=p_k+c(Az_{k+1}-b)$ yields a telescoping dual-distance estimate that controls primal feasibility without ergodic averaging. This improves prior verifiable AL bounds of $\\mathcal O(\\epsilon^{-4/3})$, $\\mathcal O(\\epsilon^{-3/2})$, $\\mathcal O(\\epsilon^{-7/4})$, and $\\mathcal O(\\epsilon^{-2})$, and removes the logarithmic factor from proximal AL guarantees.","pith_inferences":["Editorial inference: the outer-loop telescoping argument depends only on small dual-stationarity residuals, so any inner solver providing such certificates at optimal cost could carry the same $\\mathcal O(1/\\epsilon)$ AL complexity, potentially extending the result to other composite structures beyond compact domains.","Editorial inference: the PF-AR stationarity-certificate subroutine is likely reusable as a standalone parameter-free solver for composite minimization with verifiable stopping, since its guarantees do not rely on the AL outer loop.","Editorial inference: a natural stress test is whether the optimal bound persists when the smoothness of the AL subproblem grows with the penalty parameter $c$; the analysis suggests it does as long as an accelerated method satisfying the constant-factor Lipschitz estimate is available, but the paper does not test this regime numerically.","Editorial inference: the same design may transfer to stochastic or distributed oracles whenever the inner solver can maintain approximate dual stationarity, since the outer complexity proof is agnostic to how the inner certificate is produced."],"forward_implications":["For linearly constrained convex composite problems, optimal $\\mathcal O(1/\\epsilon)$ first-order complexity can be achieved with standard, unregularized AL subproblems and a directly verifiable stopping rule.","Two of the proposed methods, OPF-IAL and APF-IAL, remove the need to know the domain diameter or the distance to an optimal multiplier, so the optimal rate is attainable without problem-dependent tuning.","In the strongly convex setting all three methods attain $\\mathcal O(\\epsilon^{-1/2}\\log(\\epsilon^{-1}))$ without knowledge of the strong convexity parameter.","The APF-IAL variant adaptively increases the penalty parameter and subproblem tolerances, and it provides a last-iterate guarantee, not only a best-iterate guarantee.","On six problem classes, including elastic-net regression, group-sparse SVMs, and a quantum semidefinite program, the methods were often 5 to 50 times faster than the ProxALM baseline under identical termination criteria."],"supporting_citations":[{"why":"Supplies the parameter-free accumulative regularization architecture and the key distance estimates that PF-AR extends to composite problems with verifiable subgradient certificates.","marker":"[16]"},{"why":"Establishes the $\\mathcal O(\\epsilon^{-4/3})$ ergodic primal-dual AL bound that this paper improves to the optimal $\\mathcal O(1/\\epsilon)$.","marker":"[49]"},{"why":"Gives the $\\mathcal O(\\epsilon^{-3/2})$ fast inexact AL bound that serves as a comparison benchmark for the new methods.","marker":"[30]"},{"why":"Provides the $\\mathcal O(\\epsilon^{-2})$ nonergodic AL bound that this paper's nonergodic guarantees improve upon.","marker":"[25]"},{"why":"Defines the verifiable primal-dual/KKT criterion used in the paper and gives an $\\mathcal O(\\epsilon^{-7/4})$ AL bound that is surpassed here.","marker":"[15]"},{"why":"Supplies both an $\\mathcal O(\\epsilon^{-7/4})$ standard I-AL bound and a logarithmically suboptimal PAL bound that the current work improves.","marker":"[27]"},{"why":"Provides the representative proximal AL method, ProxALM, used in the numerical comparisons and its $\\mathcal O(\\epsilon^{-1}\\log(\\epsilon^{-1}))$ complexity baseline.","marker":"[26]"},{"why":"Supplies the restart analysis and potential-function lemmas that R-FISTA simplifies and uses for the strongly convex case.","marker":"[44]"},{"why":"Provides the uniform multiplier bound, Lemma 2.21, that APF-IAL uses to control feasibility through the increasing penalty parameter.","marker":"[43]"}],"fun_headline_variants":["Parameter-free AL hits optimal O(1/eps) KKT","Nonergodic AL achieves optimal primal-dual rate","No proximal term, no tuning: AL hits optimal rate","Standard AL subproblems attain optimal verifiable rate","AL without proximal terms reaches optimal complexity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire optimal-complexity result rests on the assumption that every augmented-Lagrangian subproblem can be solved by an accelerated subroutine whose error after $k$ steps shrinks like a constant over $k^2$, using a smoothness estimate that is only a constant factor larger than the true one.","fun_headline_variants_meta":{"raw":{"variants":["Parameter-free AL hits optimal O(1/eps) KKT","Nonergodic AL achieves optimal primal-dual rate","No proximal term, no tuning: AL hits optimal rate","Standard AL subproblems attain optimal verifiable rate","AL without proximal terms reaches optimal complexity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001325,"raw_usage":{"total_tokens":5482,"prompt_tokens":1123,"completion_tokens":4359,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":739,"completion_tokens_details":{"reasoning_tokens":4283}},"tokens_in":739,"tokens_out":4359,"duration_ms":29809,"temperature":1.0,"reasoning_tokens":4283,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T04:19:25.972090+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run OPF-IAL on a family of linearly constrained convex instances with known smoothness, domain diameter, and penalty parameter set to $c=1/\\epsilon$, measuring the total number of gradient evaluations needed to reach $\\|Az-b\\|\\le\\epsilon$ and $\\|r\\|\\le\\epsilon$ for $\\epsilon=10^{-3},10^{-4},10^{-5},10^{-6}$. If the empirical growth is worse than $\\mathcal O(1/\\epsilon)$ on a log-log plot, or if the output triple ever fails the containment and residual conditions of (2.2), then the central claim would be disproved.","supporting_citations":[{"cited_title":"Computational Optimization and Applications , volume=","cited_arxiv_id":null,"evidence_quote":"Establishes the $\\mathcal O(\\epsilon^{-4/3})$ ergodic primal-dual AL bound that this paper improves to the optimal $\\mathcal O(1/\\epsilon)$."},{"cited_title":"Operations Research , volume=","cited_arxiv_id":null,"evidence_quote":"Gives the $\\mathcal O(\\epsilon^{-3/2})$ fast inexact AL bound that serves as a comparison benchmark for the new methods."},{"cited_title":"A conditional-gradient-based single-loop augmented Lagrangian method for inequality constrained optimization","cited_arxiv_id":"2605.22539","evidence_quote":"Provides the $\\mathcal O(\\epsilon^{-2})$ nonergodic AL bound that this paper's nonergodic guarantees improve upon."},{"cited_title":"INFORMS Journal on Optimization , volume=","cited_arxiv_id":null,"evidence_quote":"Defines the verifiable primal-dual/KKT criterion used in the paper and gives an $\\mathcal O(\\epsilon^{-7/4})$ AL bound that is surpassed here."},{"cited_title":"International Conference on Machine Learning , pages=","cited_arxiv_id":null,"evidence_quote":"Supplies both an $\\mathcal O(\\epsilon^{-7/4})$ standard I-AL bound and a logarithmically suboptimal PAL bound that the current work improves."},{"cited_title":"Journal of Optimization Theory and Applications , volume=","cited_arxiv_id":null,"evidence_quote":"Supplies the restart analysis and potential-function lemmas that R-FISTA simplifies and uses for the strongly convex case."},{"cited_title":"Journal of Optimization Theory and Applications , volume=","cited_arxiv_id":null,"evidence_quote":"Provides the uniform multiplier bound, Lemma 2.21, that APF-IAL uses to control feasibility through the increasing penalty parameter."}],"review_version":1}