Cover Image

Sketch-and-Project Meets Newton Method: Global $\mathcal O(k^{-2})$ Convergence with Low-Rank Updates

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Hanzely, Slavomír
Format:	Preprint
Published:	2023
Subjects:	Optimization and Control Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Newton Method Revisited: Global Convergence Rates up to $\mathcal {O}\left(k^{-3} \right)$ for Stepsize Schedules and Linesearch Procedures
by: Hanzely, Slavomír, et al.
Published: (2024)

Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees
by: Agafonov, Artem, et al.
Published: (2025)

Preconditioned Norms: A Unified Framework for Steepest Descent, Quasi-Newton and Adaptive Methods
by: Veprikov, Andrey, et al.
Published: (2025)

$ψ$DAG: Projected Stochastic Approximation Iteration for DAG Structure Learning
by: Ziu, Klea, et al.
Published: (2024)

Loss-Transformation Invariance in the Damped Newton Method
by: Shestakov, Alexander, et al.
Published: (2025)

Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence
by: Jiang, Ruichen, et al.
Published: (2024)

Inference of Online Newton Methods with Nesterov's Accelerated Sketching
by: Wang, Haoxuan, et al.
Published: (2026)

Gradient Regularized Newton Boosting Trees with Global Convergence
by: Zozoulenko, Nikita, et al.
Published: (2026)

A Regularized Hessian-Free Inexact Newton-Type Method with Global $\mathcal{O}(k^{-2})$ Convergence
by: Maia, Leandro Farias, et al.
Published: (2026)

Incremental Gauss--Newton Methods with Superlinear Convergence Rates
by: Zhou, Zhiling, et al.
Published: (2024)

Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates
by: Liu, Zhuanghua, et al.
Published: (2024)

A Smoothing Newton Method for Rank-one Matrix Recovery
by: Maunu, Tyler, et al.
Published: (2025)

Online Covariance Matrix Estimation in Sketched Newton Methods
by: Kuang, Wei, et al.
Published: (2025)

Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods
by: Chayti, El Mahdi, et al.
Published: (2023)

Convergence of Muon with Newton-Schulz
by: Kim, Gyu Yeol, et al.
Published: (2026)

Federated Dynamical Low-Rank Training with Global Loss Convergence Guarantees
by: Schotthöfer, Steffen, et al.
Published: (2024)

Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems
by: Garber, Dan, et al.
Published: (2022)

Greedy Low-Rank Gradient Compression for Distributed Learning with Convergence Guarantees
by: Chen, Chuyan, et al.
Published: (2025)

qNBO: quasi-Newton Meets Bilevel Optimization
by: Fang, Sheng, et al.
Published: (2025)

Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate
by: Jiang, Ruichen, et al.
Published: (2024)

A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees
by: Zhou, Yuhao, et al.
Published: (2025)

Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project
by: Rathore, Pratik, et al.
Published: (2025)

Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing
by: Romanov, Elad, et al.
Published: (2024)

Convergence for Discrete Parameter Update Schemes
by: Wilson, Paul, et al.
Published: (2025)

A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithms
by: Goldshlager, Gil, et al.
Published: (2025)

Low-Rank Extragradient Methods for Scalable Semidefinite Optimization
by: Garber, Dan, et al.
Published: (2024)

Unbiased Gradient Low-Rank Projection
by: Pan, Rui, et al.
Published: (2025)

Convergence of Distributed Adaptive Optimization with Local Updates
by: Cheng, Ziheng, et al.
Published: (2024)

Drop-Muon: Update Less, Converge Faster
by: Gruntkowska, Kaja, et al.
Published: (2025)

From Saddle Points Toward Global Minima: A Newton-Type Method on Wasserstein Space
by: Lascu, Razvan-Andrei, et al.
Published: (2026)

Stochastic Newton Proximal Extragradient Method
by: Jiang, Ruichen, et al.
Published: (2024)

GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs
by: Liu, Jiachang, et al.
Published: (2026)

Adam Converges Without Any Modification On Update Rules
by: Zhang, Yushun, et al.
Published: (2026)

From PowerSGD to PowerSGD+: Low-Rank Gradient Compression for Distributed Optimization with Convergence Guarantees
by: Xie, Shengping, et al.
Published: (2025)

Polyak Stepsize: Estimating Optimal Functional Values Without Parameters or Prior Knowledge
by: Abdukhakimov, Farshed, et al.
Published: (2025)

AdaGrad Meets Muon: Adaptive Stepsizes for Orthogonal Updates
by: Zhang, Minxin, et al.
Published: (2025)

Sharpened Lazy Incremental Quasi-Newton Method
by: Lahoti, Aakash, et al.
Published: (2023)

Online Newton Method for Bandit Convex Optimisation
by: Fokkema, Hidde, et al.
Published: (2024)

Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems
by: Garber, Dan, et al.
Published: (2022)

On the Global Convergence of Risk-Averse Natural Policy Gradient Methods with Expected Conditional Risk Measures
by: Yu, Xian, et al.
Published: (2023)