Pith. sign in

REVIEW 3 major objections 5 minor 66 references

SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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$.

desk verdict 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. read the letter →

arxiv 2501.15941 v1 pith:ORCWDXY2 submitted 2025-01-27 stat.ML cs.LG

Jingruo Sun , Zachary Frangella , Madeleine Udell This is my paper · ORCID
classification stat.MLcs.LG MSC 90C2565K0590C06
keywords stochasticvariancereductionpreconditioningsketch-basedpreconditionerscaledproximalmappingcompositeconvexoptimizationregularizedempiricalriskminimizationcondition-number-freeconvergencelasso
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [§3.3, Algorithms 1–2; Lemmas B.1–B.3 and C.3–C.4] 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.
  2. [Theorem 4.2 (§4.3.2)] 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.
  3. [Theorem 4.1, Eq. (7)] 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.
minor comments (5)
  1. [Theorem 4.1] 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.
  2. [Table 3 and §3.2.3] 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.
  3. [Corollary 4.2] The term 'ridge-leverage incoherent' is used without a definition or reference in this paper; please provide one so the corollary is self-contained.
  4. [Algorithms 1–2] 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.
  5. [Throughout] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: SAPPHIRE's rates are derived from stated assumptions and independent published lemmas; the APG truncation is a correctness gap, not a circular reduction.

full rationale

I find no circular step in SAPPHIRE's derivation chain. The convergence theorems (Theorems 4.1, 4.2, and 4.3) are proved in Appendices B and C from the stated Assumptions 1 and 2 together with published lemmas from the authors' prior work, notably Proposition 3.16 and Lemma 27 of [19] and Lemmas 3.1-3.3 of [20]. Those prior results are stated with their own assumptions (smooth or strongly convex objectives, spectral approximation of the Hessian) and do not assume the present paper's composite-proximal convergence claims, so under the review rules they count as independent evidence and do not raise the circularity score. The main structural risk is a correctness gap rather than circularity: Section 3.3 states that the scaled proximal mapping 'does not have a closed form' and proposes to solve it by APG with 'only a few APG iterations required,' whereas Lemma B.1, Lemma B.2, and Lemma C.3 rely on exact optimality and non-expansiveness of the scaled proximal operator (5). A finite-T APG output need not satisfy those identities, so the formal O(n log(1/epsilon)) and O-tilde(n log(1/epsilon)) guarantees cover the exact-prox version of Algorithm 1, not necessarily the truncated implementation in Algorithm 2. This is a theory-practice mismatch, not an equivalence of output to input by construction.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical entities. The central claim rests on standard convex analysis assumptions, a spectral approximation condition on the preconditioner, and several published lemmas from the authors' prior work. The main unquantified freedom is the APG inner iteration count and the preconditioner regularization rho, both of which are not specified in the experimental section.

free parameters (3)
  • Preconditioner regularization rho = not reported
    Appears in SSN (2) and NySSN (4); the theory requires rho > 0 but experiments do not state its value, and it governs the spectral approximation and the effective dimension.
  • APG inner iteration count T = not specified ('a few')
    Algorithm 2 is run for T iterations in practice, but the theory assumes an exact solution; T is a hand-chosen parameter with no error analysis.
  • Learning rate eta and snapshot length m = eta=1/(16 L_P), m=100 L_P/((1-zeta) gamma_l) in Theorem 4.1; eta=1, m=10 in Theorem 4.3
    Chosen by the theory to guarantee contraction; in experiments practical values differ, creating the acknowledged theory-practice gap in Section 4.3.2.
assumptions (4)
  • domain assumption The regularizer r is lower semi-continuous, convex, with closed effective domain (Assumption 1).
    Standard for convex regularizers; used throughout the analysis.
  • domain assumption For each preconditioner update j in U, P_j satisfies (1-zeta)P_j <= grad^2 L(w_j) <= (1+zeta)P_j (or the appropriate one-sided version) (Assumption 2).
    Conditions on the good event; Lemmas 3.2-3.3 from [20] show it holds with high probability for SSN and NySSN.
  • domain assumption Each loss l_i is quadratically regular (or rho-weakly quadratically regular) (Definitions 2-3).
    Needed for global linear (Theorem 4.1) and sublinear (Theorem 4.2) convergence; holds for smooth strongly convex losses but only with moderate constants on bounded domains for general GLMs.
  • standard math External lemmas from prior work: Proposition 3.16 and Lemma 27 of [19], Lemmas 3.2 and 3.3 of [20].
    The proof of Lemma 4.3 and Lemma C.2 rely on these published results; the concentration argument is not reproduced in the appendix.

how reviews work

0 comments
Cite this review

Pith. "Pith review of SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning." pith.science (2026). https://pith.science/paper/ORCWDXY2

@misc{pith2026250115941,
  author       = {Pith},
  title        = {Pith review of: SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ORCWDXY2}},
  note         = {Machine review of arXiv:2501.15941}
}
abstract

Regularized empirical risk minimization (rERM) has become important in data-intensive fields such as genomics and advertising, with stochastic gradient methods typically used to solve the largest problems. However, ill-conditioned objectives and non-smooth regularizers undermine the performance of traditional stochastic gradient methods, leading to slow convergence and significant computational costs. To address these challenges, we propose the $\texttt{SAPPHIRE}$ ($\textbf{S}$ketching-based $\textbf{A}$pproximations for $\textbf{P}$roximal $\textbf{P}$reconditioning and $\textbf{H}$essian $\textbf{I}$nexactness with Variance-$\textbf{RE}$educed Gradients) algorithm, which integrates sketch-based preconditioning to tackle ill-conditioning and uses a scaled proximal mapping to minimize the non-smooth regularizer. This stochastic variance-reduced algorithm achieves condition-number-free linear convergence to the optimum, delivering an efficient and scalable solution for ill-conditioned composite large-scale convex machine learning problems. Extensive experiments on lasso and logistic regression demonstrate that $\texttt{SAPPHIRE}$ often converges $20$ times faster than other common choices such as $\texttt{Catalyst}$, $\texttt{SAGA}$, and $\texttt{SVRG}$. This advantage persists even when the objective is non-convex or the preconditioner is infrequently updated, highlighting its robust and practical effectiveness.

Figures

Figures reproduced from arXiv: 2501.15941 by the authors.

Figure 1
Figure 1. SAPPHIRE significantly outperforms competing stochastic optimizers on a large-scale click prediction problem with the avazu dataset (n = 12, 642, 186, p = 999, 990). A traditional way to mitigate ill-conditioning in optimization is to use second-order methods, such as Newton’s method or BFGS, which incorporate curvature information. These methods are robust and can achieve local superlinear convergence. While these … view at source ↗
Figure 2
Figure 2. L1-logistic regression: SAPPHIRE vs. competing methods on rcv1 and covtype 5.1 Convergence on convex objectives This section describes experiments on convex objective functions R, including logistic regression and least-square regression with the Lasso and elastic-net regularizers. 5.1.1 Medium-Scale Convex Problems L1-Logistic regression and Lasso. Every method was given a maximum runtime of 120 seconds and a limit… view at source ↗
Figure 3
Figure 3. Lasso: SAPPHIRE vs. competing methods on rna-seq and yearmsd Similar to the medium-scale experiments, we observe that SAPPHIRE exhibits the best performance on both datasets. On avazu SAPPHIRE exhibits dramatic gains over its competitors—achieving a suboptimality that reaches machine precision. The next best competitor Catalyst only obtains a suboptimality of around 10−3 − 10−4 . Moreover, we see SAPPHIRE exhibits g… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Logistic regression: SAPPHIRE vs. competing methods on avazu and url The SCAD penalty is given by r(w) =    λ|w| |w| ≤ λ − |w| 2−2aλ|w|+λ 2 2(a−1) λ < |w| < aλ (a+1)λ 2 2 |w| > aλ, (8) where λ > 0, a > 2 are the regularization parameters controlling sparsity and c…
Figure 5
Figure 5. Figure 5: Least-Square regression with SCAD regularization [PITH_FULL_IMAGE:figures/full_fig_p019_5.png]
Figure 6
Figure 6. Figure 6: Logistic regression with MCP regularization [PITH_FULL_IMAGE:figures/full_fig_p020_6.png]
Figure 7
Figure 7. Figure 7: Test Loss for avazu References [1] Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(221):1–51, 2018. [2] Zeyuan Allen-Zhu. Natasha 2: Faster non-convex optimization than sgd. Advances in …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

66 extracted references · 61 canonical work pages

  1. [1]

    Katyusha: The first direct acceleration of stochastic gradient methods.Journal of Machine Learning Research, 18(221):1–51, 2018

    Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods.Journal of Machine Learning Research, 18(221):1–51, 2018

    work page 2018

  2. [2]

    Natasha 2: Faster non-convex optimization than sgd

    Zeyuan Allen-Zhu. Natasha 2: Faster non-convex optimization than sgd. Advances in neural information processing systems, 31, 2018

    work page 2018

  3. [3]

    Optimal black-box reductions between optimization objectives.Advances in Neural Information Processing Systems, 29, 2016

    Zeyuan Allen-Zhu and Elad Hazan. Optimal black-box reductions between optimization objectives.Advances in Neural Information Processing Systems, 29, 2016

    work page 2016

  4. [4]

    Variance reduction for faster non-convex optimization

    Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. InInternational conference on machine learning, pages 699–707. PMLR, 2016

    work page 2016

  5. [5]

    A fast iterative shrinkage-thresholding algorithm for linear inverse problems

    Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183–202, 2009

    2009

  6. [6]

    On the convergence of block coordinate descent type methods.SIAM Journal on Optimization, 23(4):2037–2060, 2013

    Amir Beck and Luba Tetruashvili. On the convergence of block coordinate descent type methods.SIAM Journal on Optimization, 23(4):2037–2060, 2013

    work page 2013

  7. [7]

    A multi-batch l-bfgs method for machine learning

    Albert S Berahas, Jorge Nocedal, and Martin Takác. A multi-batch l-bfgs method for machine learning. Advances in Neural Information Processing Systems, 29, 2016

    work page 2016

  8. [8]

    Convergence rate analysis of a stochas- tic trust-region method via supermartingales.INFORMS Journal on Optimization, 1(2):92–119, 2019

    Jose Blanchet, Coralia Cartis, Matt Menickelly, and Katya Scheinberg. Convergence rate analysis of a stochas- tic trust-region method via supermartingales.INFORMS Journal on Optimization, 1(2):92–119, 2019

    work page 2019

Show all 66 references
  1. [9]

    Exact and inexact subsampled Newton methods for optimization

    Raghu Bollapragada, Richard H Byrd, and Jorge Nocedal. Exact and inexact subsampled Newton methods for optimization. IMA Journal of Numerical Analysis, 39(2):545–578, 2019

    2019

  2. [10]

    A progressive batching l-bfgs method for machine learning

    Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi, and Ping Tak Peter Tang. A progressive batching l-bfgs method for machine learning. InInternational Conference on Machine Learning, pages 620–629. PMLR, 2018

    2018

  3. [11]

    On the use of stochastic Hessian information in optimization methods for machine learning.SIAM Journal on Optimization, 21(3):977–995, 2011

    Richard H Byrd, Gillian M Chin, Will Neveitt, and Jorge Nocedal. On the use of stochastic Hessian information in optimization methods for machine learning.SIAM Journal on Optimization, 21(3):977–995, 2011. 21

    2011

  4. [12]

    SAN: stochastic average Newton algo- rithm for minimizing finite sums

    Jiabin Chen, Rui Yuan, Guillaume Garrigos, and Robert M Gower. SAN: stochastic average Newton algo- rithm for minimizing finite sums. InInternational Conference on Artificial Intelligence and Statistics, pages 279–318. PMLR, 2022

    2022

  5. [13]

    SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives.Advances in Neural Information Processing Systems, 27, 2014

    Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives.Advances in Neural Information Processing Systems, 27, 2014

    2014

  6. [14]

    Stochastic variance-reduced newton: Accelerating finite-sum minimization with large batches

    Michal Derezinski. Stochastic variance-reduced newton: Accelerating finite-sum minimization with large batches. InOPT 2023: Optimization for Machine Learning

    2023

  7. [15]

    Minimizing quasi-self-concordant functions by gradient regularization of newton method

    Nikita Doikov. Minimizing quasi-self-concordant functions by gradient regularization of newton method. arXiv preprint arXiv:2308.14742, 2023

    2023 arXiv

  8. [16]

    Convergence rates of sub-sampled Newton methods.Advances in Neural Information Processing Systems, 28, 2015

    Murat A Erdogdu and Andrea Montanari. Convergence rates of sub-sampled Newton methods.Advances in Neural Information Processing Systems, 28, 2015

    2015

  9. [17]

    Variable selection via nonconcave penalized likelihood and its oracle properties

    Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association, 96(456):1348–1360, 2001

    2001

  10. [18]

    Cronos: Enhancing deep learning with scalable gpu accelerated convex neural networks.arXiv preprint arXiv:2411.01088, 2024

    Miria Feng, Zachary Frangella, and Mert Pilanci. Cronos: Enhancing deep learning with scalable gpu accelerated convex neural networks.arXiv preprint arXiv:2411.01088, 2024

    2024 arXiv

  11. [19]

    PROMISE: Preconditioned stochastic optimization methods by incorporating scalable curvature estimates.Journal of Machine Learning Research, 25(346):1–57, 2024

    Zachary Frangella, Pratik Rathore, Shipu Zhao, and Madeleine Udell. PROMISE: Preconditioned stochastic optimization methods by incorporating scalable curvature estimates.Journal of Machine Learning Research, 25(346):1–57, 2024

    2024

  12. [20]

    Sketchysgd: reliable stochastic opti- mizationviarandomizedcurvatureestimates

    Zachary Frangella, Pratik Rathore, Shipu Zhao, and Madeleine Udell. Sketchysgd: reliable stochastic opti- mizationviarandomizedcurvatureestimates. SIAM Journal on Mathematics of Data Science, 6(4):1173–1204, 2024

    2024

  13. [21]

    Randomized nyström preconditioning.SIAM Journal on Matrix Analysis and Applications, 44(2):718–752, 2023

    Zachary Frangella, Joel A Tropp, and Madeleine Udell. Randomized nyström preconditioning.SIAM Journal on Matrix Analysis and Applications, 44(2):718–752, 2023

    2023

  14. [22]

    Second-order information promotes mini-batch robustness in variance-reduced gradients.arXiv preprint arXiv:2404.14758, 2024

    Sachin Garg, Albert S Berahas, and Michał Dereziński. Second-order information promotes mini-batch robustness in variance-reduced gradients.arXiv preprint arXiv:2404.14758, 2024

    2024 arXiv

  15. [23]

    RSN: Randomized Subspace Newton

    Robert Gower, Dmitry Kovalev, Felix Lieder, and Peter Richtárik. RSN: Randomized Subspace Newton. Advances in Neural Information Processing Systems, 32, 2019

    2019

  16. [24]

    SGD: General analysis and improved rates

    Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. InInternational Conference on Machine Learning, pages 5200–

  17. [25]

    Datamodels: Predicting predictions from training data

    Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc, and Aleksander Madry. Datamodels: Predicting predictions from training data. InProceedings of the 39th International Conference on Machine Learning, 2022

    2022

  18. [26]

    Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization.Advances in Neural Information Processing Systems, 29, 2016

    Sashank J Reddi, Suvrit Sra, Barnabas Poczos, and Alexander J Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization.Advances in Neural Information Processing Systems, 29, 2016

    2016

  19. [27]

    Accelerating stochastic gradient descent using predictive variance reduction

    Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 26, 2013

    2013

  20. [28]

    Global linear convergence of Newton’s method without strong-convexity or Lipschitz gradients.arXiv preprint arXiv:1806.00413, 2018

    Sai Praneeth Karimireddy, Sebastian U Stich, and Martin Jaggi. Global linear convergence of Newton’s method without strong-convexity or Lipschitz gradients.arXiv preprint arXiv:1806.00413, 2018. 22

    2018 arXiv

  21. [29]

    Sub-sampled cubic regularization for non-convex optimization

    Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex optimization. In International Conference on Machine Learning, pages 1895–1904. PMLR, 2017

    1904

  22. [30]

    Do subsampled newton methods work for high-dimensional data? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4723–4730, 2020

    Xiang Li, Shusen Wang, and Zhihua Zhang. Do subsampled newton methods work for high-dimensional data? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4723–4730, 2020

    2020

  23. [31]

    On faster convergence of cyclic block coordinate descent-type methods for strongly convex minimization, 2017

    Xingguo Li, Tuo Zhao, Raman Arora, Han Liu, and Mingyi Hong. On faster convergence of cyclic block coordinate descent-type methods for strongly convex minimization, 2017

    2017

  24. [32]

    Activityidentificationandlocallinearconvergenceofforward– backward-type methods

    JingweiLiang, JalalFadili, andGabrielPeyré. Activityidentificationandlocallinearconvergenceofforward– backward-type methods. SIAM Journal on Optimization, 27(1):408–437, 2017

    2017

  25. [33]

    Local convergence properties of douglas–rachford and al- ternating direction method of multipliers

    Jingwei Liang, Jalal Fadili, and Gabriel Peyré. Local convergence properties of douglas–rachford and al- ternating direction method of multipliers. Journal of Optimization Theory and Applications, 172:874–913, 2017

    2017

  26. [34]

    Catalyst acceleration for first-order convex optimization: from theory to practice.Journal of Machine Learning Research, 18(212):1–54, 2018

    Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. Catalyst acceleration for first-order convex optimization: from theory to practice.Journal of Machine Learning Research, 18(212):1–54, 2018

    2018

  27. [35]

    Controlburn: Featureselectionbysparseforests

    BrianLiu, MiaolanXie, andMadeleineUdell. Controlburn: Featureselectionbysparseforests. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pages 1045–1054, 2021

    2021

  28. [36]

    On the complexity analysis of randomized block-coordinate descent methods

    Zhaosong Lu and Lin Xiao. On the complexity analysis of randomized block-coordinate descent methods. Mathematical Programming, 152:615–642, 2015

    2015

  29. [37]

    Fast and furious convergence: Stochastic second order methods under interpolation

    Si Yi Meng, Sharan Vaswani, Issam Hadj Laradji, Mark Schmidt, and Simon Lacoste-Julien. Fast and furious convergence: Stochastic second order methods under interpolation. InInternational Conference on Artificial Intelligence and Statistics, pages 1375–1386. PMLR, 2020

    2020

  30. [38]

    A linearly-convergent stochastic L-BFGS algorithm

    Philipp Moritz, Robert Nishihara, and Michael Jordan. A linearly-convergent stochastic L-BFGS algorithm. In Artificial Intelligence and Statistics, pages 249–258. PMLR, 2016

    2016

  31. [39]

    Gradientmethodsforminimizingcompositefunctions

    YuNesterov. Gradientmethodsforminimizingcompositefunctions. Mathematical programming, 140(1):125– 161, 2013

    2013

  32. [40]

    Springer, 2018

    Yurii Nesterov.Lectures on Convex Optimization. Springer, 2018

    2018

  33. [41]

    Catalyst for gradient-based nonconvex optimization

    Courtney Paquette, Hongzhou Lin, Dmitriy Drusvyatskiy, Julien Mairal, and Zaid Harchaoui. Catalyst for gradient-based nonconvex optimization. InInternational Conference on Artificial Intelligence and Statistics, pages 613–622. PMLR, 2018

    2018

  34. [42]

    Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks

    Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. InInternational Conference on Machine Learning, pages 7695–7705. PMLR, 2020

    2020

  35. [43]

    Newton sketch: A near linear-time optimization algorithm with linear-quadratic convergence.SIAM Journal on Optimization, 27(1):205–245, 2017

    Mert Pilanci and Martin J Wainwright. Newton sketch: A near linear-time optimization algorithm with linear-quadratic convergence.SIAM Journal on Optimization, 27(1):205–245, 2017

    2017

  36. [44]

    Local convergence properties of saga/prox-svrg and acceleration

    Clarice Poon, Jingwei Liang, and Carola Schoenlieb. Local convergence properties of saga/prox-svrg and acceleration. In International Conference on Machine Learning, pages 4124–4132. PMLR, 2018

    2018

  37. [45]

    Challenges in training pinns: A loss landscape perspective.arXiv preprint arXiv:2402.01868, 2024

    Pratik Rathore, Weimu Lei, Zachary Frangella, Lu Lu, and Madeleine Udell. Challenges in training pinns: A loss landscape perspective.arXiv preprint arXiv:2402.01868, 2024

    2024 arXiv

  38. [46]

    Stochastic variance reduction for nonconvex optimization

    Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. InInternational conference on machine learning, pages 314–323. PMLR, 2016. 23

    2016

  39. [47]

    Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function.Mathematical Programming, 144(1):1–38, 2014

    Peter Richtárik and Martin Takáč. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function.Mathematical Programming, 144(1):1–38, 2014

    2014

  40. [48]

    Newton-mr: Inexact Newton method with minimum residual sub-problem solver.EURO Journal on Computational Optimization, 10:100035, 2022

    Fred Roosta, Yang Liu, Peng Xu, and Michael W Mahoney. Newton-mr: Inexact Newton method with minimum residual sub-problem solver.EURO Journal on Computational Optimization, 10:100035, 2022

    2022

  41. [49]

    Sub-sampled Newton methods.Mathematical Program- ming, 174(1):293–326, 2019

    Farbod Roosta-Khorasani and Michael W Mahoney. Sub-sampled Newton methods.Mathematical Program- ming, 174(1):293–326, 2019

    2019

  42. [50]

    Are we there yet? manifold identification of gradient-related proximal methods

    Yifan Sun, Halyun Jeong, Julie Nutini, and Mark Schmidt. Are we there yet? manifold identification of gradient-related proximal methods. InThe 22nd International Conference on Artificial Intelligence and Statistics, pages 1110–1119. PMLR, 2019

    2019

  43. [51]

    Stochastic cubic regular- ization for fast nonconvex optimization.Advances in Neural Information Processing Systems, 31, 2018

    Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael I Jordan. Stochastic cubic regular- ization for fast nonconvex optimization.Advances in Neural Information Processing Systems, 31, 2018

    2018

  44. [52]

    Fixed-rank approximation of a positive- semidefinite matrix from streaming data.Advances in Neural Information Processing Systems, 30, 2017

    Joel A Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher. Fixed-rank approximation of a positive- semidefinite matrix from streaming data.Advances in Neural Information Processing Systems, 30, 2017

    2017

  45. [53]

    Fixed-rank approximation of a positive- semidefinite matrix from streaming data

    Joel A Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher. Fixed-rank approximation of a positive- semidefinite matrix from streaming data. InAdvances in Neural Information Processing Systems, volume 30, 2017

    2017

  46. [54]

    Utilizing second order information in minibatch stochastic variance reduced proximal iterations

    Jialei Wang and Tong Zhang. Utilizing second order information in minibatch stochastic variance reduced proximal iterations. Journal of Machine Learning Research, 20(42):1–56, 2019

    2019

  47. [55]

    A proximal stochastic gradient method with progressive variance reduction

    Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4):2057–2075, 2014

    2014

  48. [56]

    Newton-type methods for non-convex optimization under inexact Hessian information.Mathematical Programming, 184(1-2):35–70, 2020

    Peng Xu, Fred Roosta, and Michael W Mahoney. Newton-type methods for non-convex optimization under inexact Hessian information.Mathematical Programming, 184(1-2):35–70, 2020

    2020

  49. [57]

    Inexact nonconvex Newton-type methods

    Zhewei Yao, Peng Xu, Fred Roosta, and Michael W Mahoney. Inexact nonconvex Newton-type methods. INFORMS Journal on Optimization, 3(2):154–182, 2021

    2021

  50. [58]

    Inexact newton-cg algo- rithms with complexity guarantees.IMA Journal of Numerical Analysis, 43(3):1855–1897, 2023

    Zhewei Yao, Peng Xu, Fred Roosta, Stephen J Wright, and Michael W Mahoney. Inexact newton-cg algo- rithms with complexity guarantees.IMA Journal of Numerical Analysis, 43(3):1855–1897, 2023

    2023

  51. [59]

    Approximate Newton methods.Journal of Machine Learning Research, 22(66):1–41, 2021

    Haishan Ye, Luo Luo, and Zhihua Zhang. Approximate Newton methods.Journal of Machine Learning Research, 22(66):1–41, 2021

    2021

  52. [60]

    Sketched Newton–Raphson.SIAM Journal on Opti- mization, 32(3):1555–1583, 2022

    Rui Yuan, Alessandro Lazaric, and Robert M Gower. Sketched Newton–Raphson.SIAM Journal on Opti- mization, 32(3):1555–1583, 2022

    2022

  53. [61]

    R 1 Sm S−1X s=0 mX k=1 ˆw(s) k ! − R(w⋆) # ≤ ∥w0 − w⋆∥2 P (0) 0 + (2η − η2) (R(w0) − R(w⋆)) . Rearranging, we find that E

    Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty.The Annals of Statistics, 38(2), April 2010. 24 Appendix In this section, we provide the proof for all the lemmas and theorems we present in the main paper, and some auxiliary results which are hel...

    2010

  54. [62]

    1 1 + ε0 ≤ γlmin (Nε0 (w⋆)) ≤ γumax (Nε0 (w⋆)) ≤ (1 + ε0). 2. (1 − ε0)∇2L(w) ⪯ ∇2L(w′) ⪯ (1 + ε0)∇2L(w). 3. ∥w − w⋆ − ∇2L(w)−1(∇L(w) − ∇L(w⋆)∥∇2L(w) ≤ ε0∥w − w⋆∥∇2L(w). 4. ∥∇Li(w) − ∇Li(w⋆)∥∇2Li(w′)−1 ≤ (1 + ε0)∥w − w⋆∥∇2Li(w′), for all i ∈ [n], ∥∇L(w) − ∇L(w⋆)∥∇2L(w′)−1 ≤ (1 ...

  55. [63]

    ∥∆(s) k+1∥∇2F (w⋆) ≤ 3 4 ∥∆(s) k ∥∇2F (w⋆) + 7 48 ∥∆(s) 0 ∥∇2F (w⋆)

  56. [64]

    w(s) k+1 ∈ Nε0 (w⋆). Proof. Let ∆(s) k+1 = proxP r w(s) k − P −1∇L(w(s) k ) − w⋆. We begin with the following inequality, ∆(s) k+1 P = proxP r wk − P −1v(s) k − w⋆ P = proxP r wk − P −1v(s) k − proxP r w⋆ − P −1∇L(w⋆) P ≤ wk − P −1v(s) k − w⋆ − P −1∇L(w⋆) P = P (wk − w⋆) − (∇L...

  57. [65]

    ˆw(s+1) ∈ N2 3 ε0 (w⋆)

  58. [66]

    ∥ ˆw(s+1) − w⋆∥∇2L(w⋆) ≤ 2 3 ∥ ˆw(s) − w⋆∥∇2L(w⋆). Proof. As ˆw(s) ∈ Nε0 (w⋆), it follows by union bound that the conclusions of Lemma C.3 hold for allw(s) k , where k ∈ {0, . . . , m− 1}, with probability at least 1 − m−1X k=0 δ (m + 1)2 = 1 − m (m + 1)2 δ ≥ 1 − δ. Consequent...

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.