Globally Convergent Regularization Homotopy and Nyström Newton Method for Generalized Self-Concordant Losses

⚠️ Curated Limitations & Negative Results

• Dependence of Phase-I Stage Count on R ||x_lambda^*|| When No Unregularized Minimizer Exists: In Theorem 1 and Remark 1, the number of Phase-I regularization-decrease stages scales as O((1 + R ||x_lambda^*||) log(R ||nabla f(0)|| / lambda)) (or with sup_{mu >= lambda} R sqrt(mu) ||x_mu^*||_{H_mu^{-1}(x_mu^*)} in Proposition 7). While ||x_lambda^*|| is bounded by a lambda-independent constant whenever an unregularized minimizer x^* exists (as in well-specified RKHS learning under source condition r > 0), in separable parametric logistic regression where no finite unregularized minimizer exists, R ||x_lambda^*|| can grow up to O(R / sqrt(lambda)) in the worst case.
• Conservative Proof Constants in Indirect Empirical-to-Projected Statistical Decomposition: As noted in Remark 5 (Appendix H.3, p. 67), decomposing the statistical excess risk into separate blocks (population to empirical ERM, and empirical ERM to Nyström-projected approximate ERM) inflates the theoretical constants (K_1 <= 6.0e4, K_2 <= 6.0e6, K_3 <= 810 in Propositions 10 and 18), and in practice (Section 5, Appendix F, p. 51) the safe theoretical factor q_{k+1} is replaced by a fast geometric cooling factor (dividing mu by 1000 per stage).
• Primary-Source Typographical Notes in Marteau-Ferey, Bach, & Rudi (2019, arXiv:1907.01771v2): Verified five self-correcting typographical/notational slips across the 77-page manuscript: (1) Theorem 1 (p. 7) writes 'q_k = (1/3 + 7 R ||x_k||)/(1 + 7 R ||x_k||)' with an off-by-one index relative to the loop update 'mu_{k+1} <- q_{k+1} mu_k' in the Proposed Globalization Scheme box, whereas Proposition 6 (p. 31) writes the exact index 'q_{k+1} := (1/3 + 7 R ||x_{k+1}||)/(1 + 7 R ||x_{k+1}||)', and the box header on pp. 7, 26, and 31 prints 'Dikin ellispoid' instead of 'Dikin ellipsoid'; (2) Appendix B (p. 19, inline equation before B.1) writes '||tilde_Delta_t - Delta_lambda(x_t)|| <= rho nu_lambda(x_t) + epsilon_0' omitting the H_lambda(x_t) subscript on the norm, whereas p. 20, Lemmas 8-9, and Proposition 4 write the exact Hessian norm '||tilde_Delta_t - Delta_lambda(x_t)||_{H_lambda(x_t)} <= rho nu_lambda(x_t) + epsilon_0'; (3) Appendix B.3 (p. 24, proof of Lemma 10) repeats 'tilde_nu_lambda(x_t) <= 2^{-(2^t-1)} nu_lambda(x_0)' twice instead of 'nu_lambda(x_t) <= 2^{-(2^t-1)} nu_lambda(x_0), tilde_nu_lambda(x_t) <= 2^{-(2^t-1)} tilde_nu_lambda(x_0)', and Proposition 5 (p. 25, fourth bullet) writes 'x_t . tilde_Delta_t <= (6/7) varepsilon' instead of 'nabla f_lambda(x_t) . tilde_Delta_t <= (6/7) varepsilon' as proved immediately below; (4) Proposition 12 (p. 44) writes 'tau = log(rho/2)/log((sqrt(3)+1)/sqrt(3)-1)' missing the sign flip in 'log(2/rho)' (for rho = 1/7, log(14)/log((sqrt(3)+1)/(sqrt(3)-1)) approx 2.003, yielding tau = 3); and (5) Appendix H.4.2 (p. 72, step 2 of proof of Theorem 9) writes 'beta = 1/(1 + 2r + 1/lambda)' instead of 'beta = 1/(1 + 2r + 1/alpha)' as defined on p. 70.
• All 77 pages of the full-text PDF of Marteau-Ferey, Bach, & Rudi (2019, NeurIPS 32, arXiv:1907.01771v2) were read. Constructed numerical checks in research/discovery/globally-convergent-newton-generalized-self-concordant-boundaries.py verify (1) Appendix A.1 Eq. (13) helper identity phi_over(t)/phi_under(t) = e^t, Lemma 6 function-value equivalence inside D_lambda(1/7), Lemma 10 quadratic exact-Newton convergence, and Proposition 5 linear 1/7-relative ANM convergence, (2) Lemma 3/13 Dikin-ellipsoid inclusion, Proposition 6, and Theorem 1 two-phase regularization homotopy globalization from mu_0 = 7 R ||nabla f(0)|| down to lambda = 1e-4, and (3) Proposition 12 3-step preconditioned conjugate gradient relative error (0.000643 <= 0.038476 <= 1/7) and Proposition 15 Nyström projector capacity bound.