Weekly computational mathematics digest

Main result claims

• Theorem-backed: The authors prove order-optimal convergence rates in expectation for Hölder source smoothness ν in (0, 1/2], under bounded positive step sizes whose cumulative sum diverges.
• Rate: Their estimate is E‖x_k^δ−x†‖² ≤ C[(1+s_k/N)^−2ν + δ²s_k/N], yielding the claimed optimal root-mean-square rate O(δ^2ν/(1+2ν)) with early stopping.
• Almost-sure result: Using a Lyapunov argument and Robbins–Siegmund, the authors also establish sample-path error bounds and the same order in norm almost surely.
• Qualification: The analysis is for linear ill-posed systems in Hilbert spaces and ν≤1/2; it does not establish the same guarantees for nonlinear inverse problems.

Main result claims

• Methodology: The authors propose SGMR-IBP, an Arnoldi-based iterative back-propagation method that avoids the Givens transformations and eigenvalue calculations required by the earlier GMR-IBP scheme.
• Adaptivity: They add an adaptive step-size update intended to improve robustness across identification problems.
• Theory and experiments: The authors report a feasibility analysis and two numerical examples supporting effectiveness; the public publisher page does not expose enough detail to independently compare exact error or runtime metrics.
• Qualification: The evidence is limited to two examples and the contribution is specialized to polynomial nonlinear system identification rather than a general nonlinear least-squares solver.

Main result claims

• Theorem-backed: The author claims that for every (0<c_1<c_2<1), a bounded-below (C^infty) function on (mathbb{R}^2) with Lipschitz gradient can make every method in the stated conjugacy class generate an infinite sequence with (| abla f(x_k)|=1).
• Line search: The constructed steps are first local minimizers and simultaneously satisfy strong Wolfe, weak Wolfe, Armijo, and Goldstein conditions for the prescribed constants.
• Scope: The class includes BFGS, L-BFGS with arbitrary memory, the positive Broyden family, and Hestenes–Stiefel CG; two dimensions are claimed to be minimal.
• Verification: Section 6 and the companion Python package numerically check the trajectory and line-search metrics, but this remains a designed worst-case construction rather than evidence about typical problems.

Main result claims

• Methodology: The authors claim complexity guarantees for practical model-based trust-region variants that retain useful interpolation points and need only one or two new function evaluations per iteration.
• Complexity: The full-space linear-interpolation method retains (O(n^2arepsilon^{-2}))-type evaluation complexity, while random (q)-dimensional subspaces recover nearly tight (O(narepsilon^{-2}))-type dependence under the stated assumptions.
• Noisy evaluations: The analysis extends to bounded deterministic zeroth-order noise and quantifies the noise-dependent stationarity floor; Theorems 5.12–5.13 treat randomized subspaces.
• Empirical: Section 6 reports that the theoretically supported implementation can match established Powell-style trust-region codes, although performance remains benchmark- and tuning-dependent.

Main result claims

• Algorithm: The authors propose direct and matrix-free indirect primal-dual Newton-MR variants using CR/LSMR-type inner iterations, inexact normal steps, and approximate null-space projections.
• Complexity: They claim the first line-search SQP-type iteration bound simultaneously allowing inexact inner solves and nonconvex Lagrangian curvature; Algorithm 4 reaches an ((arepsilon_c,arepsilon_p))-stationary point in (O(1/min{arepsilon_c,arepsilon_p^2})) outer iterations under the paper’s assumptions.
• Empirical: Against augmented-Lagrangian and SQP baselines, the reported constrained-NLS and Poisson-PINN tests favor the PDN variants; Table 2 gives the best reported (L_2) relative and (L_infty) PINN test errors.
• Qualification: The guarantees require regularity and boundedness assumptions, and the headline experiments implement the direct rather than fully matrix-free variant.

Main result claims

• Exact dynamics: The authors derive a discrete-time scalar law separating schedule/decay forcing from geometric self-quenching and identify a sharp contraction–expansion boundary.
• Instability: In the solved normalized-regression model, Proposition 3.6 proves the interior balance point is an unstable spiral source; Proposition 3.5 gives an exact period-two orbit.
• Optimizer comparison: A homogeneous-optimizer framework predicts weaker self-quenching for adaptive methods than for nonadaptive ones.
• Empirical: Experiments on MLPs, CNNs, and GPT-2 using MNIST, CIFAR, WikiText, and OpenWebText reportedly track the law closely, with performance peaking near the predicted boundary; this is mechanistic evidence, not a universal training prescription.

Main result claims

• Upper bound: Using recursive anchoring and robust mean estimation, the authors obtain high-probability residual guarantees for nonexpansive self-maps in spaces of weak Rademacher type (q>1).
• Type-2 rate: For (ell_p), (2le pleinfty), they claim (widetilde O(sigma^2arepsilon^{-3}+arepsilon^{-1})) stochastic-oracle complexity.
• Lower bound: A near-matching high-dimensional (ell_infty) lower bound holds against randomized algorithms succeeding with constant probability, including sparse-noise settings.
• Qualification: The endpoint (ell_1) is excluded under only the stated second-moment assumption, and the contribution is theoretical rather than experimentally benchmarked.

Main result claims

• Non-anytime lower bound: Theorem 1.1 proves an exponent (p_{mathrm{sil}}=log_2(1+sqrt2)), up to a subpolynomial correction, matching the known silver-schedule upper bound.
• Anytime lower bound: Theorem 1.2 shows every infinite nonnegative schedule has infinitely many horizons with the corresponding optimal anytime exponent, again up to subpolynomial factors.
• Technique: The hard-function construction switches gradient directions between selected checkpoints; Lemma 3.9 supplies the core “silver inequality.”
• Qualification: The result concerns predetermined nonnegative step sizes on smooth convex objectives, not adaptive line searches or momentum methods, and supplies no computational benchmark.

Main result claims

• Global convergence: Theorem 2.15 claims almost-sure convergence from every initial point on a bounded periodic domain to the unique global minimizer.
• Local rate: For noise exponent (alpha>1), almost every path eventually converges quadratically; the proof combines finite-time basin entry with a shrinking quadratic tube.
• Exploration: Lemma 2.6 gives a geometric tail bound for first entrance into the local basin.
• Qualification: The analysis assumes a known normalized minimum value, a unique minimizer, compact periodic geometry, and local positive-definite Lipschitz Hessian; there are no numerical experiments.