{"id":"df401478-e571-4c57-b9c9-4d69f111c12a","arxiv_id":"2501.15941","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"SAPPHIRE is a new preconditioned variance-reduced stochastic method with provable linear convergence for composite convex problems, achieving large speedups on regularized ERM.","lead":"Researchers propose SAPPHIRE, an optimization algorithm that combines sketching-based preconditioning with variance-reduced stochastic gradients to solve large-scale machine learning problems with non-smooth regularizers. It converges at rates that do not depend on the data's condition number in the strongly convex and local regimes, and often runs about 20 times faster than standard solvers on large datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Inexact APG for the scaled proximal mapping breaks the contraction proofs; the theory covers an idealized exact-prox algorithm.","rationale":"","tokens_in":29426,"tokens_out":7246,"duration_ms":70047,"concrete_test":"Re-derive Lemma C.3 with the T-th APG iterate replacing the exact proximal map. Let e_T be the P-norm suboptimality of the APG output for (5). Derive the one-step bound as ||Delta_{k+1}||_P <= (c + C e_T / ||Delta_k||_P) ||Delta_k||_P + beta_g ||Delta_0||_P, and compute the minimal T needed to keep the contraction factor below 1 using APG's linear rate (sqrt(kappa(P))-1)/(sqrt(kappa(P))+1). If the required T grows as Omega(sqrt(kappa(P)) log(1/epsilon_sub)) and cannot be chosen independent of kappa(P), then the condition-number-free O~(n log(1/epsilon)) complexity fails for finite T.","verdict_should_be":"UNCHANGED","load_bearing_attack":"All convergence results (Lemma B.1, Theorems 4.1-4.3) treat the scaled proximal mapping (5) as an exact operator, yet Algorithm 2 approximates it by a finite number T of accelerated proximal-gradient iterations, with no theorem bounding T or the resulting subproblem error. The key inequalities fail under approximation: Lemma B.1 uses the exact optimality condition P(eta^{-1}(w-wtilde)) - v + xi = 0, and Lemma B.2/B.3 and Lemma C.3 use non-expansiveness of the exact proximal operator in the P-norm. A finite-T APG output need not satisfy either property, so the contraction factors (3/4 and 7/48 in Lemma C.3, the 2/3 factor in Lemma C.4, and the 1/((1-zeta)gamma_l eta(1-4eta L_P)m) term in Lemma B.3) are not guaranteed for the implemented method. Since Contribution 2 states only empirically that 'a few APG iterations are required,' the formal O~(n log(1/epsilon)) and O(n log(1/epsilon)) claims (Theorem 4.3 and Corollary 4.1) are not established for Algorithm 1 as executed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SAPPHIRE, a stochastic variance-reduced proximal-gradient algorithm for regularized empirical risk minimization. It combines SSN or NySSN sketch-based preconditioners with a scaled proximal mapping for the nonsmooth regularizer and a variance-reduced stochastic gradient estimator. The paper claims global linear convergence under quadratic regularity, global sublinear convergence for smooth convex objectives, and local condition-number-free linear convergence with total gradient-query complexity O~(n log(1/epsilon)) in the local regime, and it supports these claims with large-scale experiments on lasso, logistic regression, SCAD, and MCP problems.","tokens_in":29684,"tokens_out":10873,"duration_ms":105249,"significance":"If the proofs cover the method as implemented, this is a valuable extension of the PROMISE/SketchySGD framework to composite nonsmooth problems, and the local condition-number-free rate would be a meaningful advance over existing stochastic second-order methods with nonsmooth regularizers. The paper's derivations are detailed and largely self-contained in the appendices, and the experiments benchmark against external tuned baselines (Catalyst, SAGA, ProxSVRG, MB-SVRP) rather than only against the authors' prior algorithms. The main risk is that the core convergence theorems apply to an idealized exact scaled-proximal oracle, whereas Algorithm 2 computes only a finite number of approximate APG steps.","major_comments":[{"comment":"The convergence theory treats the scaled proximal mapping (5) as an exact operator, but the implemented algorithm evaluates it by a finite number T of APG iterations in Algorithm 2, with no error bound or stopping criterion. Lemma B.1 starts from the exact optimality condition P(eta^{-1}(w-wtilde)) - v + xi = 0, and Lemmas B.2, B.3, and C.3 rely on nonexpansiveness of the exact scaled proximal mapping in the P-norm. A finite-T APG output need not satisfy either property, so the contraction factors used in the proofs (for example 2/3 in Lemma C.4 and 3/4 and 7/48 in Lemma C.3) are not guaranteed for the method actually run. Consequently, Theorems 4.1–4.3 and Corollary 4.1, including the O~(n log(1/epsilon)) and O(n log(1/epsilon)) complexity claims, do not currently cover Algorithm 1 as executed. Please add an inexact-prox analysis or prove a sufficient bound on T and incorporate the resulting subproblem error into the contraction estimates.","section":"§3.3, Algorithms 1–2; Lemmas B.1–B.3 and C.3–C.4"},{"comment":"The theorem statement says to run Algorithm 1 with Option 2, which outputs the last inner iterate as the new snapshot, but the displayed bound is for the ergodic average (1/(Sm)) sum over all inner iterates across outer iterations, not for the last-snapshot output of Option 2. The proof uses convexity to bound that averaged sequence, so as written the theorem does not establish the stated convergence for Algorithm 1's output. In addition, the proof's step-size choice gives S = O(m L_P^2/epsilon), and the authors themselves state that the practically used step size eta = O(1/L_P) is not covered by Theorem 4.2. Please restate the theorem for the actual output produced by the algorithm, or define the output as the ergodic average and make the algorithm consistent with that definition.","section":"Theorem 4.2 (§4.3.2)"},{"comment":"The gradient-query complexity displayed in Eq. (7) appears algebraically inconsistent with Lemma 4.3. The per-stage cost in the proof is n + 2 m b_g, and with m = O(L_P/((1-zeta) gamma_l)) the second term should scale as b_g L_P, giving terms of order n(b_g-1)/(n-1) q and tau_star (n-b_g)/(n-1) q_max (up to constants), rather than the displayed tau_star n(n-b_g)/(b_g(n-1)) q_max inside the O(n/(1-zeta)) factor. The displayed expression changes the claimed complexity in the small-b_g regime and should be corrected or the derivation shown.","section":"Theorem 4.1, Eq. (7)"}],"minor_comments":[{"comment":"The theorem does not state which output option of Algorithm 1 is used; the proof in Lemma B.3 appears to rely on Option 1 (the averaged snapshot). This should be stated explicitly.","section":"Theorem 4.1"},{"comment":"Table 3 says the SSN preconditioner is 'Best for sparse data', while the text following Table 3 says NySSN shows 'especially strong performance on sparse data'. These statements conflict and should be reconciled.","section":"Table 3 and §3.2.3"},{"comment":"The term 'ridge-leverage incoherent' is used without a definition or reference in this paper; please provide one so the corollary is self-contained.","section":"Corollary 4.2"},{"comment":"Algorithm 1's input list does not include the APG iteration count T or a stopping tolerance for Algorithm 2, so the implemented method is not fully specified as written.","section":"Algorithms 1–2"},{"comment":"There are several typographical errors, including 'we compare compare' and 'total number number' in Section 5, 'weak quadratic regular conditions' in Section 6, and inconsistent capitalization of 'SAPPHIRE' as 'Sapphire' in Section 5.2.1.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The central idea is promising and the proofs are largely careful, but the exact-proximal gap is load-bearing: the finite-T APG approximation used in the implementation is not covered by the stated contraction proofs, and the main complexity claims therefore outrun the theory. The theorem-output mismatch in Theorem 4.2 and the apparent arithmetic issue in Eq. (7) should also be fixed. If the authors can supply a valid inexact-prox analysis or prove a sufficient bound on T, I would view the paper favorably."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. The algorithmic idea is real: SAPPHIRE extends the PROMISE line to composite problems with non-smooth regularizers via a scaled proximal mapping, and it gives the first variance-reduced stochastic second-order method with a local condition-number-free linear rate for such problems. That is a genuine gap in the literature, and the paper fills it. Second, the core theory has a gap that matters: every convergence theorem treats the scaled proximal mapping (5) as an exact operator, but Algorithm 2 computes it with a finite number T of APG iterations. The proofs use exact optimality (Lemma B.1) and non-expansiveness of the exact proximal map (Lemmas B.2, B.3, C.3). A finite-T output need not satisfy either. So the stated O~(n log(1/eps)) and O(n log(1/eps)) results are established only for the idealized version, not the algorithm as run. The authors say \"a few APG iterations are required\" empirically, but there is no bound on T and no error analysis. This is the load-bearing weakness. What the paper does well: the derivation is detailed, the contraction machinery is largely consistent, and the authors are honest about the conservative sublinear rate in Theorem 4.2 and the theory-practice gap in the step size. The experiments are extensive and the speedups are plausible, though they lack error bars and no code is shipped. The reliance on lemmas from the authors' prior PROMISE/SketchySGD papers is not a red flag—those are published results and the dependency is explicit. A referee should ask for (a) an inexact-proximal analysis—standard tools should bound the APG error and propagate it through the contraction factors—or at least a theorem specifying T; and (b) release of code. With that, the paper would be a solid contribution. As it stands, it is a promising but incompletely supported claim for the implemented method. This is for optimization researchers working on stochastic second-order methods and variance reduction. It deserves a serious referee, because the gap is repairable and the algorithmic contribution is substantial. I would recommend sending it out, with the explicit request that the inexact-proximal issue be addressed.","headline":"A genuinely new algorithm with a substantial theory contribution, but the central convergence proofs assume the scaled proximal map is solved exactly; the implemented finite-APG inner loop is not covered by the theorems.","tokens_in":30205,"tokens_out":1240,"would_cite":true,"duration_ms":14698,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","65K05","90C06"],"pacs":[],"model":"deepseek-v4-flash","headline":"SAPPHIRE combines sketch-based preconditioning with variance-reduced gradients and a scaled proximal map, aiming to make linear convergence independent of the condition number even with nonsmooth regularizers such as $\\ell_1$.","keywords":["stochastic variance reduction","preconditioning","sketch-based preconditioner","scaled proximal mapping","composite convex optimization","regularized empirical risk minimization","condition-number-free convergence","lasso"],"falsifier":"Take a synthetic lasso instance with strongly correlated features, run Algorithm 1 exactly as implemented, and record the residual of the scaled proximal subproblem after the finite APG iterations. If the Hessian-norm contraction in Lemma C.3 holds even when this residual is larger than the variance-reduction and Taylor errors, the theory can tolerate inexact prox; if the linear phase only appears when the subproblem residual is small, then the implemented algorithm does not enjoy the advertised condition-number-free rate.","tokens_in":29230,"feed_emoji":"⚡","tokens_out":8368,"duration_ms":72604,"temperature":0.7,"pith_summary":"The paper introduces SAPPHIRE, a stochastic variance-reduced algorithm for regularized empirical risk minimization where the data-fit term is smooth but the regularizer may be nonsmooth, as in lasso or elastic-net. Its central claim is that curvature information from sketched Hessians, combined with variance-reduced gradients and a scaled proximal map, removes the condition number from the local linear convergence rate, so that reaching $\\epsilon$-accuracy in the Hessian norm costs $\\tilde{O}(n \\log(1/\\epsilon))$ stochastic gradient queries. The authors further show global linear convergence when the loss is quadratically regular, with the rate governed by quadratic regularity ratios rather than the condition number, and global sublinear convergence for merely convex losses. An attentive reader would care because existing stochastic second-order methods either cannot handle nonsmooth regularizers or require batch sizes tied to the condition number. The paper also reports that on large-scale click-prediction data, SAPPHIRE reduces the objective roughly 20 times faster than common tuned stochastic optimizers.","feed_headline":"20x faster convergence on ill-conditioned sparse learning","feed_subtitle":"A sketched-Hessian preconditioner plus variance-reduced gradients removes the condition-number bottleneck in nonsmooth problems.","key_machinery":"The argument is carried by three mechanisms working together. First, a sketch-based preconditioner approximates the smooth-part Hessian: the Subsampled Newton preconditioner averages $\\nabla^2 \\ell_i(w)$ over a mini-batch and adds $\\rho I$, while the Nyström Subsampled Newton preconditioner forms a low-rank approximation; both are shown to satisfy a $\\zeta$-spectral approximation $\\nabla^2 L(w) \\preceq (1+\\zeta)P$ (and a two-sided version under quadratic regularity). Second, the variance-reduced gradient $v_k = \\widehat{\\nabla} L(w_k) - \\widehat{\\nabla}L(\\tilde{w}) + \\nabla L(\\tilde{w})$ has its preconditioned variance controlled by a preconditioned expected smoothness constant $L_P$. Third, the nonsmooth regularizer is applied through a scaled proximal map $\\mathrm{prox}^{\\,P}_{\\eta r}(w - \\eta P^{-1} v)$, defined as the minimizer of $r(\\cdot)$ plus a quadratic in the $P$-norm, which is solved by accelerated proximal gradient steps. The analysis substitutes the condition number with the quadratic regularity ratios $q$ and $q_{\\max}$ (or, for convex-only losses, their $\\rho$-weak counterparts), and the local proofs use the $\\varepsilon_0$-neighborhood where these constants are close to unity.","core_discovery":"The paper's key discovery claim is a stochastic variance-reduced method that achieves condition-number-free local linear convergence on composite convex problems with a nonsmooth regularizer. Within a neighborhood of the optimum defined by $\\|w - w_*\\|^2_{\\nabla^2 L(w_*)} \\leq \\nu^{3/2}/(2M)$, each outer iteration contracts the Hessian-norm distance by a constant factor, so only $\\tilde{O}(n \\log(1/\\epsilon))$ stochastic gradient evaluations are needed to reach $\\epsilon$-accuracy (Theorem 4.3). Globally, under quadratic regularity, SAPPHIRE converges linearly with the rate expressed through the quadratic regularity ratios $q$ and $q_{\\max}$ instead of the condition number, and when $q, q_{\\max} = O(1)$ the total query count is $O(n \\log(1/\\epsilon))$ (Theorem 4.1 and Corollary 4.1). For merely convex losses the method retains an ergodic $O(1/\\epsilon)$ sublinear rate. The authors position this as closing a gap: previous stochastic second-order methods required smooth strongly convex objectives (or interpolation) for such guarantees, while SAPPHIRE handles regularizers like $\\ell_1$, SCAD, and MCP.","pith_inferences":["The theory assumes the scaled proximal map is solved exactly, whereas the implementation truncates the APG solver after a finite number of iterations; an implicit testable claim is that the number of APG steps needed to preserve the contraction is small and insensitive to the global condition number.","Because the global convex-rate theorem carries an extra $m^2$ factor, the paper implicitly bets that the practically used stepsize $\\eta = O(1/L_P)$ is what matters; extending the analysis to that regime would likely remove the gap.","The same preconditioned-proximal mechanism should transfer to other nonsmooth structures such as group lasso or fused lasso, where the scaled proximal map has no closed form; verifying that the local rate remains condition-number-free there would test the framework beyond generalized linear models."],"forward_implications":["If Theorem 4.3 is correct, SAPPHIRE becomes the first variance-reduced stochastic second-order method whose local linear rate is independent of the condition number while allowing a nonsmooth convex regularizer; the cost per stage is a full-gradient pass plus two small batches.","Under quadratic regularity with $q, q_{\\max} = O(1)$, global linear convergence implies that ill-conditioned datasets can be solved in $O(n \\log(1/\\epsilon))$ gradient queries without any condition-number-dependent stepsize.","For Lasso-like convex problems, the ergodic sublinear guarantee plus manifold identification predicts an initial sublinear phase followed by fast linear convergence once the support of the solution is found, matching the observed behavior on the paper's datasets.","The batch-size requirement $\\widetilde{O}(\\tau^\\nu(N_{\\varepsilon_0}(w^*)))$ is never larger than the condition number or $n$, and under spectral decay of the data covariance it can be as small as $\\widetilde{O}(\\sqrt{n})$, which is what makes the method practical at internet scale."],"supporting_citations":[{"why":"Defines quadratic regularity and establishes the framework of preconditioned expected smoothness and local $\\varepsilon_0$-neighborhood analysis that SAPPHIRE generalizes to composite problems.","marker":"[19]"},{"why":"Supplies the $\\rho$-Hessian dissimilarity, the $\\zeta$-spectral approximation guarantees for SSN and NySSN preconditioners, and the analysis style used for the local neighborhood.","marker":"[20]"},{"why":"Is the ProxSVRG algorithm whose snapshot-and-inner-loop template SAPPHIRE adopts and extends to preconditioned updates.","marker":"[55]"},{"why":"Is a representative variance-reduced incremental method that serves as a baseline and benchmark that SAPPHIRE must improve upon.","marker":"[13]"},{"why":"Catalyst acceleration is the strongest first-order baseline in the experiments that SAPPHIRE is claimed to beat by roughly 20x.","marker":"[34]"},{"why":"Prior method that handles composite problems with proxable regularizers but requires full gradients and smooth strong-convexity analysis; SAPPHIRE extends the setting.","marker":"[30]"},{"why":"The stochastic second-order baseline that uses second-order information but whose analysis excludes nonsmooth regularizers and requires larger gradient batches.","marker":"[54]"},{"why":"Provides the numerically stable fixed-rank Nyström approximation (Algorithm 3) required to construct the NySSN preconditioner reliably.","marker":"[52]"},{"why":"Establishes the expectation-smoothness inequality that Lemma 4.3 generalizes to the preconditioned composite setting.","marker":"[24]"},{"why":"The accelerated proximal-gradient method used as the inner solver for the scaled proximal mapping, determining the practical cost of each update.","marker":"[39]"}],"fun_headline_variants":["SAPPHIRE: 20x faster convergence on ill-conditioned learning","Sketch-based preconditioning accelerates stochastic optimization","Condition-number-free convergence for nonsmooth learning","Variance reduction meets preconditioned proximal steps"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convergence theorems require the scaled proximal mapping to be evaluated exactly, but the implemented algorithm approximates it with a finite number of accelerated proximal gradient iterations, and no bound is proved on the error this truncation introduces.","fun_headline_variants_meta":{"raw":{"variants":["SAPPHIRE: 20x faster convergence on ill-conditioned learning","Sketch-based preconditioning accelerates stochastic optimization","Condition-number-free convergence for nonsmooth learning","Variance reduction meets preconditioned proximal steps"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000165,"raw_usage":{"total_tokens":1306,"prompt_tokens":1057,"completion_tokens":249,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":673,"completion_tokens_details":{"reasoning_tokens":187}},"tokens_in":673,"tokens_out":249,"duration_ms":2761,"temperature":1.0,"reasoning_tokens":187,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T13:49:58.450634+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a synthetic lasso instance with strongly correlated features, run Algorithm 1 exactly as implemented, and record the residual of the scaled proximal subproblem after the finite APG iterations. If the Hessian-norm contraction in Lemma C.3 holds even when this residual is larger than the variance-reduction and Taylor errors, the theory can tolerate inexact prox; if the linear phase only appears when the subproblem residual is small, then the implemented algorithm does not enjoy the advertised condition-number-free rate.","supporting_citations":[{"cited_title":"PROMISE: Preconditioned stochastic optimization methods by incorporating scalable curvature estimates.Journal of Machine Learning Research, 25(346):1–57, 2024","cited_arxiv_id":null,"evidence_quote":"Defines quadratic regularity and establishes the framework of preconditioned expected smoothness and local $\\varepsilon_0$-neighborhood analysis that SAPPHIRE generalizes to composite problems."},{"cited_title":"Sketchysgd: reliable stochastic opti- mizationviarandomizedcurvatureestimates","cited_arxiv_id":null,"evidence_quote":"Supplies the $\\rho$-Hessian dissimilarity, the $\\zeta$-spectral approximation guarantees for SSN and NySSN preconditioners, and the analysis style used for the local neighborhood."},{"cited_title":"A proximal stochastic gradient method with progressive variance reduction","cited_arxiv_id":null,"evidence_quote":"Is the ProxSVRG algorithm whose snapshot-and-inner-loop template SAPPHIRE adopts and extends to preconditioned updates."},{"cited_title":"SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives.Advances in Neural Information Processing Systems, 27, 2014","cited_arxiv_id":null,"evidence_quote":"Is a representative variance-reduced incremental method that serves as a baseline and benchmark that SAPPHIRE must improve upon."},{"cited_title":"Catalyst acceleration for first-order convex optimization: from theory to practice.Journal of Machine Learning Research, 18(212):1–54, 2018","cited_arxiv_id":null,"evidence_quote":"Catalyst acceleration is the strongest first-order baseline in the experiments that SAPPHIRE is claimed to beat by roughly 20x."},{"cited_title":"Do subsampled newton methods work for high-dimensional data? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4723–4730, 2020","cited_arxiv_id":null,"evidence_quote":"Prior method that handles composite problems with proxable regularizers but requires full gradients and smooth strong-convexity analysis; SAPPHIRE extends the setting."},{"cited_title":"Utilizing second order information in minibatch stochastic variance reduced proximal iterations","cited_arxiv_id":null,"evidence_quote":"The stochastic second-order baseline that uses second-order information but whose analysis excludes nonsmooth regularizers and requires larger gradient batches."},{"cited_title":"Fixed-rank approximation of a positive- semidefinite matrix from streaming data.Advances in Neural Information Processing Systems, 30, 2017","cited_arxiv_id":null,"evidence_quote":"Provides the numerically stable fixed-rank Nyström approximation (Algorithm 3) required to construct the NySSN preconditioner reliably."},{"cited_title":"SGD: General analysis and improved rates","cited_arxiv_id":null,"evidence_quote":"Establishes the expectation-smoothness inequality that Lemma 4.3 generalizes to the preconditioned composite setting."},{"cited_title":"Gradientmethodsforminimizingcompositefunctions","cited_arxiv_id":null,"evidence_quote":"The accelerated proximal-gradient method used as the inner solver for the scaled proximal mapping, determining the practical cost of each update."}],"review_version":1}