Scalable Mean-Variance Portfolio Optimization via Subspace Embeddings and GPU-Friendly Nesterov-Accelerated Projected Gradient

Yi-Shuai Niu; Yajuan Wang

math.OCApr 3, 2026

Scalable Mean-Variance Portfolio Optimization via Subspace Embeddings and GPU-Friendly Nesterov-Accelerated Projected Gradient

Authors: Yi-Shuai Niu, Yajuan Wang

Organizations: Beijing Institute of Mathematical Sciences and Applications (BIMSA)

Abstract

We develop a sketch-based factor reduction and a Nesterov-accelerated projected gradient algorithm (NPGA) with GPU acceleration, yielding a doubly accelerated solver for large-scale constrained mean-variance portfolio optimization. Starting from the sample covariance factor $L$ , the method combines randomized subspace embedding, spectral truncation, and ridge stabilization to construct an effective factor $L_{eff}$ . It then solves the resulting constrained problem with a structured projection computed by scalar dual search and GPU-friendly matrix-vector kernels, yielding one computational pipeline for the baseline, sketched, and Sketch-Truncate-Ridge (STR)-regularized models. We also establish approximation, conditioning, and stability guarantees for the sketching and STR models, including explicit $O(\varepsilon)$ bounds for the covariance approximation, the optimal value error, and the solution perturbation under $(\varepsilon,δ)$ -subspace embeddings. Experiments on synthetic and real equity-return data show that the method preserves objective accuracy while reducing runtime substantially. On a 5440-asset real-data benchmark with 48374 training periods, NPGA-GPU solves the unreduced full model in 2.80 seconds versus 64.84 seconds for Gurobi, while the optimized compressed GPU variants remain in the low-single-digit-second regime. These results show that the full dense model is already practical on modern GPUs and that, after compression, the remaining bottleneck is projection rather than matrix-vector multiplication.

Figures & tables

Figure 1: Eigenvalue spectrum of the real-world covariance matrix. The spectrum decays rapidly for the first few dozen components before entering a long, slowly decaying bulk spanning several thousand dimensions.

Figure 2: Cumulative explained variance

E(r)

. Due to the extremely long noisy bulk,

80\%

of the total variance is reached only after more than

2500

eigenvalues, demonstrating the inadequacy of energy-based rank selection for real-world covariance matrices.

Model	$L_{\mathrm{eff}}$	$\gamma$	Cost / iter
Baseline ( 2 )	$L\in\mathbb{R}^{n\times T}$	$0$	$O(nT)$
Sketch ( 3 )	$\tilde{L}\in\mathbb{R}^{n\times s}$	$0$	$O(ns)$
STR ( 4 )	$\tilde{L}_{\ell}\in\mathbb{R}^{n\times\ell}$	$>0$	$O(n\ell)$

Table 1: Per-iteration complexity of NPGA.

Panel of Figure 3 — Figure 3: Approximation quality on synthetic instances as the sketch size grows. Both metrics improve as $s/\ell$ increases, and JL and CountSketch behave similarly once the retained energy level is fixed.

Sketch	Rel. spec. err.	Rel. obj. gap
JL	0.1212	0.0736
CountSketch	0.1192	0.0731

Table 2: Synthetic approximation quality at

\eta=0.98

and

s/\ell=2

Panel of Figure 4 — Figure 4: Synthetic solver behavior. The convex case follows the $k^{-2}$ benchmark, the ridge-stabilized case is close to the linear-rate benchmark, and GPU acceleration becomes substantial on large unreduced factors.

$n$	Gurobi (s)	NPGA-GPU (s)	NPGA gap	STR-NPGA-GPU (s)	STR gap
500	0.16	0.47	0.0006	0.59	0.0014
1000	0.56	0.37	0.0012	0.50	0.0025
2000	2.59	0.33	0.0023	0.42	0.0047
4000	19.69	0.64	0.0065	0.42	0.0108

Table 3: Synthetic solver benchmark against Gurobi on the same training problems.

$n$	Gurobi (s)	NPGA-CPU (s)	NPGA gap	STR-NPGA-CPU (s)	STR gap	STR annualized return (%)	STR annualized volatility (%)
300	0.22	1.28	0.0025	0.03	0.1348	36.15	14.66
600	0.62	2.10	0.0053	0.07	0.0937	39.30	14.26
1000	1.78	4.22	0.0045	0.12	0.0675	39.99	12.79

Table 4: Subset benchmarks on the real 5-minute A-share data.

Method	Factor cols	Build (s)	Solve (s)	Total (s)	Full-model gap	Annualized return (%)	Annualized volatility (%)
Gurobi	48374	0.00	64.84	64.84	0.0000	36.04	11.00
NPGA-CPU	48374	0.00	26.77	26.77	0.0095	36.02	11.12
NPGA-GPU	48374	0.00	2.80	2.80	0.0080	36.04	11.12
Sketch-NPGA-GPU	948	1.15	2.53	3.68	0.2380	35.09	11.32
STR-NPGA-CPU	474	1.15	0.83	1.99	0.3203	35.24	11.17
STR-NPGA-GPU	474	1.15	2.16	3.31	0.3203	35.24	11.17

Table 5: Full-scale benchmark on the 5-minute A-share data with

n=5440

assets and

T=48374

periods.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: The Sketch–Truncate–Ridge (STR) pipeline for constructing a stable covariance approximation.

Figure 6: Condition number and smallest-eigenvalue uplift under ridge regularization on a representative synthetic instance. The Sketch and STR curves coincide on this instance and therefore appear as a single trajectory.

Panel of Figure 7 — Figure 7: Convergence behavior of the GPU variants on the full 5440-asset real-data problem. The three GPU variants require nearly the same number of outer iterations, whereas their wall-clock times differ substantially.

Portfolio Optimization

Portfolio optimization selects asset weights to balance expected return, risk, diversification, and trading constraints.

See all 63 papers

Randomized Subspace Nesterov Accelerated Gradient
May 1, 2026Gaku Omiya, Pierre-Louis Poirion, Akiko TakedaGradient Descent Randomized Sketching
Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan
Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling
Sep 11, 2026Xinchen Du, Elizaveta Rebrova, Michał Dereziński +1Stochastic Approximation Second-Order Optimization
School of Industrial and Systems Engineering, Georgia Institute of Technology · Department of Operations Research and Financial Engineering, Princeton University
Sparsity Regularized and Robust Mean Variance Portfolio Selection Under Ellipsoidal Uncertainty
Sep 10, 2026Deniz Akkaya, Emre Can Yayla, Buse Şen +1Branch and Bound Portfolio Optimization
Department of Industrial Engineering, Bilkent University, Ankara, Türkiye · Risk Analytics and Optimization Chair, EPFL, Lausanne, Switzerland

May 1, 2026J/K move · Enter open · S save

Randomized Subspace Nesterov Accelerated Gradient

Gaku Omiya, Pierre-Louis Poirion, Akiko Takeda

Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan

Gradient Descent Randomized Sketching Accelerated Gradient Methods Subspace Optimization

Open paper AskPDF arXiv

Randomized-subspace methods reduce the cost of first-order optimization by using only low-dimensional projected-gradient information, a feature that is attractive in forward-mode automatic differentiation and communication-limited settings. While Nesterov acceleration is well understood for full-gradient and coordinate-based methods, obtaining accelerated methods for general subspace sketches that use only projected-gradient information and can improve over full-dimensional Nesterov acceleration in oracle complexity is technically nontrivial. We develop randomized-subspace Nesterov accelerated gradient methods for smooth convex and smooth strongly convex optimization under matrix smoothness and generic sketch moment assumptions. The key technical ingredient is a three-sequence formulation tailored to matrix smoothness, which recovers the corresponding classical Nesterov methods in the full-dimensional case. The resulting theory establishes accelerated oracle-complexity guarantees and makes explicit how matrix smoothness and the sketch distribution enter the complexity. It also provides a unified basis for comparing sketch families and identifying when randomized-subspace acceleration improves over full-dimensional Nesterov acceleration in oracle complexity.

Abstract

Portfolio Optimization

Explore similar work

Randomized Subspace Nesterov Accelerated Gradient

Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling

Sparsity Regularized and Robust Mean Variance Portfolio Selection Under Ellipsoidal Uncertainty