BLOC: A Global Optimization Framework for Sparse Covariance Estimation with Non-Convex Penalties

Priyam Das · 2026

Read BLOC: A Global Optimization Framework for Sparse Covariance Estimation with Non-Convex Penalties by Priyam Das (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-2603-29169.txt.

Introduction

Das and co-authors present BLOC, a tool for sparse covariance estimation with non-convex penalties. It works on correlation matrices. An angular Cholesky map turns the hard constraints into a plain box search. That lets a pattern search find global optima, even for rough or black-box losses. Restarts help it escape poor local minima. Each step stays a valid correlation matrix. The team proves convergence and consistency results for the method. In tests, SCAD and MCP penalties beat top rival tools on error and sparsity.

Catalog record

CREATORPriyam Das
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE124658
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

BLOC: A Global Optimization Framework for Sparse Covariance Estimation with Non-Convex Penalties Priyam Das Abstract We introduce BLOC (Black-box Optimization over Correlation matrices), a general framework for sparse covariance estimation with non-convex penalties. BLOC operates on the manifold of correlation matrices and reparameterizes it via an angular Cholesky mapping, transforming the positive-definite, unit-diagonal constraint into an unconstrained search over a Euclidean hyperrectangle. This enables gradient-free global optimization of diverse objectives, including non-differentiable or black-box losses, using a pattern search routine with adaptive coordinate polling, run-wise restarts to escape local minima, and leveraging up to d ⁡ ( d − 1 ) d(d-1) parallel threads when optimizing a d d -dimensional correlation matrix. The method is penalty-agnostic and ensures that every iterate is a valid correlation matrix, from which covariance estimates are obtained. We establish convergence guarantees, including stationarity, probabilistic escape from poor local minima, and sublinear rates under smooth convex losses. From a statistical perspective, we prove consistency, convergence rates, and sparsistency for penalized correlation estimators under general conditions, extending sparse covariance theory beyond the Gaussian setting. Empirically, BLOC with nonconvex penalties such as SCAD and MCP outperforms leading estimators in both low- and high-dimensional regimes, achieving lower estimation error and improved sparsity recovery. A parallel implementation enhances scalability, and a proteomic network application demonstrates robust, positive-definite sparse covariance estimation. Keywords: Sparse covariance estimation; Nonconvex penalization; Global optimization; High-dimensional inference; Sparsistency. 1 Introduction The population covariance matrix \bm{\Sigma}_{0} of a random vector is a fundamental object in multivariate statistics, and its estimation plays a central role in a wide range of scientific applications. Reliable estimation of \bm{\Sigma}_{0} underlies problems in financial factor analysis ( 26 ) , high-dimensional compositional data analysis ( 35 ) , and functional genomics and transcriptome analysis ( 42 ) , among many others. As the data dimension grows, however, covariance estimation becomes increasingly challenging: the number of free parameters in \bm{\Sigma}_{0} grows quadratically with dimension, rendering classical estimators unstable or ill-conditioned in modern high-dimensional regimes. Consequently, a large body of literature has focused on regularized covariance estimation strategies that reduce effective model complexity, including eigenvalue regularization, shrinkage methods, and sparsity-inducing approaches; see 6 for a comprehensive review. Among these strategies, estimating \bm{\Sigma}_{0} under sparsity assumptions, where only a small fraction of off-diagonal entries are nonzero, has emerged as the dominant paradigm in high-dimensional covariance estimation. Early work includes banding and tapering estimators ( 4 ) , thresholding-based procedures ( 12 ) , and positive-definite modifications thereof ( 13 ) . Penalized likelihood formulations further unified these ideas by framing covariance estimation as an optimization problem with explicit sparsity-inducing penalties on off-diagonal elements. To enforce sparsity, the \ell_{1} penalty is by far the most widely used regularizer, owing to its simplicity, interpretability, and the availability of scalable optimization routines in related settings. However, it is well known that \ell_{1} penalization induces systematic shrinkage bias in nonzero estimates, particularly when true correlations are moderate or large ( 25 ) . To mitigate this bias, non-convex penalties such as the smoothly clipped absolute deviation (SCAD) penalty ( 25 ) and the minimax concave penalty (MCP) ( 50 ) have been proposed and studied extensively. In the context of covariance and correlation estimation, 32 established that non-convex penalization can achieve both consistency and sparsistency under suitable conditions, while reducing estimation bias relative to \ell_{1} -based methods. More recent work has further extended these theoretical guarantees to broader classes of losses and penalties ( 46 ) . Despite these strong statistical guarantees, existing computational approaches for covariance estimation with non-convex penalties suffer from several important limitations. First, many algorithms are tightly coupled to specific penalty functions ( 46 ) or likelihood-based objectives ( 5 ) , making them difficult to adapt when applications require alternative penalties or user-defined loss functions. Second, methods based on convex relaxations or majorization–minimization schemes typically rely on objective-specific constructions, such as Gaussian likelihoods ( 5 ) or Frobenius-norm ( 48 ) fitting criteria, and it is unclear how these techniques extend to more general, possibly non-differentiable or black-box objectives. Finally, most existing algorithms for covariance estimation under non-convex penalties or parameterizations are inherently local optimization procedures ( 41 ; 36 ; 47 ) . Once trapped in poor local minima, they lack principled mechanisms for global exploration, a limitation that becomes increasingly severe as dimensionality increases. In this paper, we propose a general framework for sparse covariance estimation with non-convex penalties, termed BLOC ( Black-box Optimization over Correlation Matrices ). Rather than developing algorithms tailored to specific penalties or objective functions, BLOC formulates covariance estimation as a black-box optimization problem over the space of correlation matrices, requiring only that the objective function be evaluable. Our approach exploits two key ideas. First, instead of optimizing directly over covariance matrices, BLOC operates on the corresponding correlation matrix. This strategy is advantageous because the correlation matrix shares the sparsity structure of \bm{\Sigma}_{0} while typically being easier to estimate and numerically more stable ( 32 ) . We leverage the geometric structure of the correlation matrix space: full-rank correlation matrices form a smooth nonlinear manifold characterized by positive definiteness and unit diagonal constraints. By employing an angular Cholesky reparameterization, BLOC maps this constrained manifold bijectively onto an unconstrained Euclidean hyperrectangle, ensuring that every iterate produced by the algorithm corresponds to a valid correlation matrix. Second, BLOC couples this reparameterization with a derivative-free global optimization strategy based on a recursive modified pattern search ( 45 ; 20 ; 24 ; 29 ) . In contrast to gradient-based or convex-relaxation methods, this approach explicitly balances local refinement with global exploration through coordinate-wise polling, adaptive step-size control, and systematic restart mechanisms. These features provide a principled means of escaping poor local optima and enable reliable exploration of highly non-convex objective landscapes, even when the loss function is non-differentiable, discontinuous, or specified implicitly through a black-box procedure. As a result, BLOC enjoys several distinct advantages over existing methods. It is objective-agnostic and penalty-agnostic, providing a unified framework for covariance estimation under a wide class of non-convex penalties without requiring penalty-specific algorithmic derivations. Our theoretical analyses provide guarantees on stationarity, global reachability, convergence in probability under mild assumptions, and sublinear convergence rates for smooth convex objectives. The remainder of the article is organized as follows. In Section 2 , we describe the problem setup and provide background on global optimization. Section 3 presents the BLOC framework in detail, while Section 4 develops its theoretical properties. Benchmark comparisons and simulation studies are reported in Section 5 , respectively. In Section 6 , we apply BLOC to pathway-informed correlation estimation in a pan-gynecologic proteomics study. The article concludes with a discussion in Section 7 , with proofs and technical details deferred to the Supplementary Material. 2 Penalized Correlation Estimation 2.1 Statistical model and correlation-based formulation Let \bm{X}\in\mathbb{R}^{d} be a random vector with positive definite covariance matrix \bm{\Sigma}_{0} . Given n i.i.d. observations \bm{X}_{1},\ldots,\bm{X}_{n} , our objective is to estimate \bm{\Sigma}_{0} under the assumption that it is sparse. Following a common strategy in high-dimensional covariance estimation ( 32 ) , we focus on estimation of the corresponding correlation matrix \bm{\Gamma}_{0} , which preserves the sparsity pattern of \bm{\Sigma}_{0} while having a fixed and known diagonal structure. An

Read the complete text