Bridging Identification and Second-Order Acceleration: A Fast Alternating Minimization Framework for Composite Optimization

Zihao Xia, Min Tao · 2026

Read Bridging Identification and Second-Order Acceleration: A Fast Alternating Minimization Framework for Composite Optimization by Zihao Xia, Min Tao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24600.txt.

Introduction

Zihao Xia and Min Tao design a faster solver for composite optimisation problems. Such a problem adds a smooth function to a regulariser that may be nonconvex and nonsmooth. These problems sit behind sparse signal recovery, machine learning, and image reconstruction. Their framework alternates between two kinds of step. One is a proximal gradient step. The other is a cubic regularised Newton update, confined to a low dimensional subspace. The subspace is identified on the fly as the run proceeds.

Under a standard condition called the Kurdyka Łojasiewicz property, the method converges globally to a stationary point. An adaptive thresholding rule, guided by the exponent in that property, yields finite identification of the active structure. The proof needs no nondegeneracy assumptions. Local analysis then gives a worst case cost bound for reaching near second order stationarity. Tests on synthetic and real data show the framework runs efficiently in practice.

Catalog record

CREATORZihao Xia, Min Tao
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24600

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Bridging Identification and Second-Order Acceleration: A Fast Alternating Minimization Framework for Composite Optimization Zihao Xia, Min Tao Abstract We consider a class of composite optimization problems involving a smooth function and a proper, lower semicontinuous regularizer, which may be nonconvex and nonsmooth. We propose a novel alternating minimization framework that integrates proximal-gradient steps with cubic-regularized Newton updates restricted to a dynamically identified low-dimensional subspace. Under the Kurdyka–Łojasiewicz (KL) property, we establish global convergence of the proposed method to a stationary point. Moreover, by incorporating an adaptive thresholding strategy guided by the KL exponent, we prove a finite identification property without imposing any nondegeneracy assumptions. We further develop a local convergence analysis and show that the proposed method attains a worst-case iteration complexity of 𝒪 ( ε − 3 / 2 ) \mathcal{O}(\varepsilon^{-3/2}) for achieving approximate second-order stationarity. Numerical experiments on both synthetic and real datasets demonstrate the efficiency of the proposed framework. ∎ MSC 90C26 65K0590C30 1 Introduction In this paper, we consider the following problem: \min_{\mathbf{x}\in\mathbb{R}^{n}}F(\mathbf{x})=g(\mathbf{x})+h(\mathbf{x}), (1) where g:\mathbb{R}^{n}\to\overline{\mathbb{R}}:=\mathbb{R}\cup\{+\infty\} is proper, lower semicontinuous, possibly nonconvex and nonsmooth, and proximal-friendly , i.e., the proximal mapping \prox_{\gamma g} can be computed efficiently, and h:\mathbb{R}^{n}\to\mathbb{R} is twice continuously differentiable with L -Lipschitz continuous gradient for some L\geq 0 . We impose the following assumptions: Assumption 1 (i) For any \mathbf{x}\in\mathbb{R}^{n} , define the manifold \mathcal{M}:=\{\mathbf{z}\in\mathbb{R}^{n}:\supp(\mathbf{z})=\supp(\mathbf{x})\}, and let \mathcal{S}\subseteq\supp(\mathbf{x}) . The restricted Hessian \nabla^{2}_{\mathcal{S}}F is strictly continuous at \mathbf{x} relative to \mathcal{M} with modulus \mathrm{lip}_{\mathcal{M}}\nabla^{2}_{\mathcal{S}}F(\mathbf{x}) . (ii) The function F is bounded below, i.e., \underline{F}:=\inf_{\mathbf{x}\in\mathbb{R}^{n}}F(\mathbf{x})>-\infty . Composite optimization problems of the form ( 1 ) arise ubiquitously in modern applications, including sparse signal recovery, machine learning, image reconstruction, and statistical estimation. In these settings, the nonsmooth term g is typically employed to promote desirable structures such as sparsity, low-rankness, or group sparsity, while the smooth component h represents data fidelity or loss functions derived from observations. These applications often involve large-scale and ill-conditioned data, making it essential to design efficient algorithms that can exploit the composite structure while handling nonconvexity and nonsmoothness. Proximal gradient-type algorithms and their variants have been extensively studied for solving the composite problems of the form ( 1 ) ( Beck 2017 ) . Second-order methods have been recognized as another potential approach for solving nonconvex optimization problems due to their fast local convergence. The cubic regularized Newton (CRN) method, originally proposed by ( Nesterov and Polyak 2006 ) , has attracted significant attention. Under the assumption that the Hessian is globally Lipschitz continuous, CRN achieves the optimal worst-case iteration complexity of order \mathcal{O}(\varepsilon^{-3/2}) for finding an approximate second-order stationary point. This optimal complexity has motivated a series of works aimed at improving its practical efficiency. ( Cartis, Gould, and Toint 2011a ; Cartis, Gould, and Toint 2011b ) proposed the Adaptive Regularization with Cubics (ARC) framework, which adaptively updates the regularization parameter and approximately minimizes a cubic model at each iteration. By exploiting Krylov subspace techniques, ARC achieves favorable scalability while preserving the optimal \mathcal{O}(\varepsilon^{-3/2}) complexity. Subsequent works have further improved the efficiency of solving the cubic subproblem, including accelerated first-order approaches ( Jiang, Yue, and Zhou 2021 ) , convex reformulations ( Jiang, Zhou, and Zhou 2022 ) , and momentum-based variants ( Wang, Zhou, Liang, and Lan 2020 ) . In addition, the asymptotic convergence behavior of CRN has been analyzed under the Kurdyka-Łojasiewicz (KL) framework ( Zhou, Wang, and Liang 2018 ) , revealing refined local convergence properties. However, classical cubic regularization methods require that the objective function is twice continuously differentiable on \mathbb{R}^{n} , they cannot be applied to ( 1 ) directly. They are always computationally demanding in high-dimensional settings due to requiring full gradients and Hessians. These limitations motivate us to develop subspace second-order methods that restrict to a low-dimensional subspace using locally second-order curvature information without the assumption of the objective function twice continuously differentiable. 1.1 Related works ( Bareilles, Iutzeler, and Malick 2023 ) proposed a framework that alternates between proximal gradient steps and Riemannian Newton steps restricted to an identified manifold. Under suitable assumptions, the algorithm identifies the active manifold in finite iteration and subsequently achieves superlinear or quadratic convergence. Similar ideas have been explored for sparse optimization problems with nonconvex regularization. In particular, ( Wu, Pan, and Yang 2023 ) developed a hybrid proximal gradient and subspace Newton method, proving finite support identification and establishing global convergence under the KL property, along with local superlinear convergence under an error bound condition. More recently, ( Tao, Zhang, and Xia 2024 ) studied L_{1}/L_{2} regularization and proposed a two-stage framework that first identifies the active manifold and then applies a semismooth Newton method, achieving superlinear and even quadratic convergence. Another line is based on optimality conditions to choose subspace. For example, ( Chen, Curtis, and Robinson 2017 ) introduced a subspace Newton method for L_{1} -regularized convex problems using the KKT residual to guide subspace selection. ( Wang, Yang, and Zhu 2024 ) proposed the IReNA method for nonconvex sparse optimization with separable concave regularizers. Their approach alternates between reweighted L_{1} steps and subspace Newton updates, and under the nondegeneracy and KL assumptions, they established finite identification and local quadratic convergence. More recently, randomized subspace strategies have been proposed to reduce computational costs. Works such as ( Zhao, Lucchi, and Doikov 2024 ; Chen, Jiang, Lin, and Zhang 2022 ) develop randomized variants of cubic regularization methods, showing that with sufficiently large sample sizes, the optimal \mathcal{O}(\varepsilon^{-3/2}) complexity can be achieved with high probability. 1.2 Motivation and contributions Although these methods demonstrate that restricting second-order updates to a subspace can significantly improve efficiency, existing approaches typically rely on either strong structural assumptions (such as partly smooth, prox-regularity and nondegeneracy conditions), or heuristic subspace selection rules whose theoretical justification remains incomplete. Moreover, most existing frameworks separate the identification phase and the second-order acceleration phase , leading to multi-stage. This raises the following fundamental question: Can we design a unified algorithmic framework that simultaneously performs subspace identification and second-order acceleration, while enjoying global convergence guarantees? In this paper, we provide an affirmative answer to this question by proposing a novel subspace cubic Newton-type framework that seamlessly integrates first-order identification and second-order refinement within a unified iterative scheme. The central idea is to dynamically construct an adaptive low-dimensional subspace based on the current iterate, and to perform a cubic-regularized Newton step restricted to this subspace. Our main contributions can be summarized as follows: • We propose a unified alternating minimization framework that integrates proximal-gradient steps with cubic-regularized Newton updates restricted to a low-dimensional subspace. This unified framework bridges identification and second-order acceleration under weak structure. • We establish global convergence of the proposed method to a first-order stationary point under the Kurdyka–Łojasiewicz (KL) property. • We show that the algorithm identifies the active subspace (or manifold) in a finite number of iterations via an adaptive thresholding strategy driven by the KL exponent of the objective function, without any nondegeneracy conditions. Once identification occurs, we establish fast local convergence, characterized by a local iteration complexity of \mathcal{O}(\varepsilon^{-3/2}) for computing an (\varepsilon_{g},\varepsilon_{H}) -approximate second-order stationary point. Organization. The remainder of this paper is organized as follows. In Section 2 , we introduce the problem formulation

Read the complete text