Model-Driven Subspaces for Large-Scale Optimization with Local Approximation Strategy
Yitong He, Pengcheng Xie · 2025
Read Model-Driven Subspaces for Large-Scale Optimization with Local Approximation Strategy by Yitong He, Pengcheng Xie (2025) 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-2509-08256.txt.
Introduction
Huge optimisation problems are shrunk into well-chosen subspaces by Yitong He and Pengcheng Xie in a 2025 optimisation paper. Local approximation subspace methods attack problems too large for direct solvers, a bottleneck across machine learning and scientific computing. The craft lies in picking subspaces that capture where progress actually happens.
New model-driven subspaces are introduced, and an algorithm built on them, called MD-LAMBO, is analysed in full: subspace properties, guaranteed function decrease, and global convergence. Model construction works even without derivatives. Responsible claims about a new optimiser require exactly this package of theory plus tests, because large-scale users cannot afford methods that stall silently on their most expensive problems.
Catalog record
| CREATOR | Yitong He, Pengcheng Xie |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 89 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-08256
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Model-Driven Subspaces for Large-Scale Optimization with Local Approximation Strategy Yitong He, Pengcheng Xie Abstract Solving large-scale optimization problems is a bottleneck and is very important for machine learning and multiple kinds of scientific problems. Subspace-based methods using the local approximation strategy are one of the most important methods. This paper discusses different and novel kinds of advanced subspaces for such methods and presents a new algorithm with such subspaces, called MD-LAMBO. Theoretical analysis including the subspaces’ properties, sufficient function value decrease, and global convergence is given for the new algorithm. The related model construction on the subspaces is given under derivative-free settings. In numerical results, performance profiles, and truncated Newton step errors of MD-LAMBO using different model-driven subspaces are provided, which show subspace-dependent numerical differences and advantages of our methods and subspaces. Keywords: Optimization, Large-Scale, Subspace, Model-Based, Trust-Region 1 Introduction Solving large-scale optimization problems is a fundamental challenge in machine learning and scientific computing. To alleviate the computational burden of full-space optimization, subspace-based methods have gained increasing attention. These methods restrict the search direction to a carefully constructed low-dimensional subspace, thereby reducing per-iteration complexity and improving efficiency. However, this simplification shifts the challenge toward designing subspaces that not only retain key descent information but also ensure theoretical convergence. Most existing algorithms employ subspaces spanned by gradients [ 31 , 32 , 33 ] , historical directions [ 17 , 26 ] , quasi-Newton updates [ 15 , 5 ] as well as other recent methods [ 6 , 7 , 16 , 21 , 29 , 11 , 3 ] . Though effective, such constructions may be insufficient when dealing with nonlinearity or derivative-free scenarios, and only very few of them have theoretical convergence guarantees. In this work, we focus on two-dimensional subspaces as a tractable yet expressive choice. We further enhance subspace design by introducing two key ideas: building subspaces with model gradients and using cubic regularization. The first idea is inspired by the observation that model-driven subspaces typically appear as linear subspaces truncated by certain regions. For this reason, we also call them truncated subspaces, where the truncations are observed to help save the time of solving subproblems. Our motivations of building subspaces with cubic-regularization-based models come from the following aspects. Primarily, though quadratic models are widely used, their gradients only include limited directions compared to the quadratic model with an additional cubic term. Such newly included directions can include previous iterating directions, which may be overlooked by pure quadratic models. Meanwhile, simple observations show that this cubic model preserves the ability to control the model-driven subspaces’ dimension, mainly through carefully selecting the domain of model gradients used for generating subspaces. Our contributions are threefold. First, we propose a novel subspace construction framework applicable to both gradient-based and derivative-free settings (see [ 27 , 24 , 25 , 28 , 9 , 1 ] for more details on related trust-region based derivative-free optimization). Second, we provide a theoretical analysis showing that our method ensures function value reduction under mild assumptions. Third, we present extensive numerical experiments demonstrating that different subspace constructions can have a substantial impact on convergence behavior. These results highlight the importance of subspace design in modern optimization algorithms. The following algorithm presents a general framework of the subspace method for large-scale optimization by Conn et al. 1996 . Such method solves the optimization problem iteratively, while in each iteration, a low-dimensional subspace is generated on which an approximated solution \bm{x}_{k+1} is obtained through solving the subproblem. It should be noted that \bm{x}_{k+1} is not required to be the unique global minimizer though writing “argmin”. In the case where \mathcal{S}_{k} is always 1-dimensional subspace, this method reduces to a line search method. Besides the subspace method, the trust region technique, being introduced in Powell’s [ 19 ] and Moré’s [ 22 ] papers in the 1970s and 1980s of the last century, is also a classic method for optimization. In each iteration, the trust-region algorithm yields an approximate solution close to the current iteration point. The region where the solution lives is called the trust region, where it was originally named “restricted step methods” in Fletcher 2000 and then well-known as “trust region” named by Sorensen 1982 . Algorithm 1 Subspace-based optimization method framework 1: Input f:\mathbb{R}^{n}\to\mathbb{R} , \bm{x}_{0}\in\mathbb{R}^{n} , tolerance \varepsilon , k=0 . 2: for \|\bm{g}_{k}\|\geq\varepsilon do 3: Choose a subspace \mathcal{S}_{k}\subset\mathbb{R}^{n} . 4: Calculate \bm{x}_{k+1}\approx\mathrm{argmin}\{f(\bm{x})\mathrel{:}\bm{x}\in\bm{x}_{k}+\mathcal{S}_{k}\} . 5: Let k\leftarrow k+1 . 6: end for 2 Model-driven subspaces In this section, we introduce the truncated subspace, a novel class of subspaces that is characterized by being model-driven. Algorithm 2 presents a general framework of subspace model-based (derivative-based) optimization in which our truncated subspace is adopted. For the derivative-free case, we provide a class of models as an alternative and prove their efficiency in Section 2.3 . In Section 2.1 , the definition of truncated subspaces as well as their dimensionality is discussed. In Section 2.2 , we show how the classic truncated trust-region method is modified to solve the trust-region subproblem in truncated subspaces. For most of our truncated subspaces, a Cauchy-type sufficient decrease can be achieved by our solution. To define the truncated subspace, we first introduce the following map \mathcal{F} , where \displaystyle\mathcal{F} \displaystyle:\{\text{models}\}\to\{\text{subspaces}\},\ p_{k}(\bm{s})\mapsto\bigcup\limits_{\bm{s}\in\mathcal{W}}{\rm span}\{\nabla p_{k}(\bm{s})\},\text{ or } (1) \displaystyle\mathcal{F} \displaystyle:\{\text{models}\}\to\{\text{subspaces}\},\ p_{k}(\bm{s})\mapsto{\rm span}\{\bigcup\limits_{\bm{s}\in\mathcal{W}}\nabla p_{k}(\bm{s})\}, (2) where \mathcal{W} is a proper set of vectors. The subspace generated by ( 1 ) is called the first type of subspace, and the subspace generated by ( 2 ) is called the second type of subspace. We will show in this section that different choices of \mathcal{W} may yield different subspaces. Then, \mathcal{F} corresponds each model p_{k} to a subspace \mathcal{S}=\mathcal{F}(p_{k}) which consists of directions provided by gradients of p_{k} . A simple observation shows that, compared to subspaces generated by map ( 2 ), which includes every linear combination of function gradients of p_{k} , subspaces generated by map ( 1 ) seem only to include limited directions of function gradients and miss a lot of directions of their linear combination. However, we will show in the following sections that most of these truncated subspaces, though they may fail to span the whole linear subspace, do not exclude the minimizer of the projected model m_{k} in the projected low-dimensional subspace. Hence, such limited subspace processes the advantages of both saving the searching area and ensuring the function value reduction. The following Algorithm 2 provides the framework of Model-Driven Local Approximation Model-Based Optimization (MD-LAMBO) where the subspaces are generated by ( 1 ) and ( 2 ). Notice that parameters \sigma and \sigma_{k} are independent of each other, where \sigma (allowed to be zero, kept unchanged through iterations) is only adopted in subspace-constructing while \sigma_{k} (adapted at each iteration) is involved in subproblem-solving. The reason that we keep using the same \sigma value to build our subspace is, it can be deduced from Theorem 2.1 and 2.2 in Subsection 2.1 that, for positive \sigma , the mathematical expressions of most of our subspaces will not be affected by the exact value of \sigma at all. In the following algorithm, we take the 2-dimensional truncated subspace as an example to explain the framework of MD-LAMBO, where