Search

Generation of diverse VLSI layout patterns is crucial for various downstream tasks in design for manufacturing (DFM) studies. However, the lengthy design cycles often hinder the creation of a comprehensive layout pattern library, and new detrimental patterns may be discovered late in the product development process. Existing training-based ML pattern generation approaches struggle to produce legal layout patterns in the early stages of technology node development due to the limited availability of training samples.To address this challenge, we propose PatternPaint, a training-free framework capable of generating legal patterns with limited DRC Clean training samples. PatternPaint simplifies complex layout pattern generation into a series of inpainting processes with a template-based denoising scheme. Our framework enables even a general pre-trained image foundation model (stable-diffusion), to generate valuable pattern variations, thereby enhancing the library. Notably, PatternPaint can operate with any input size. Furthermore, we explore fine-tuning a pre-trained model with VLSI layout images, resulting in a 2x generation efficiency compared to the base model. Our results show that the proposed model can generate legal patterns in complex 2D metal interconnect design rule settings and achieves a high diversity score. The designed system, with its flexible settings, supports pattern generation with localized changes and design rule violation correction. Validated on a sub-3nm technology node (Intel 18A), PatternPaint is the first framework to generate a complex 2D layout pattern library using only 20 design rule clean layout patterns as input.

Consider a complex random $n\times n$ matrix ${\bf X}_n=(x_{ij})_{n\times n}$, whose entries $x_{ij}$ are independent random variables with zero means and unit variances. It is well-known that Tao and Vu (Ann Probab 38: 2023-2065, 2010) resolved the circular law conjecture, establishing that if the $x_{ij}$'s are independent and identically distributed random variables with zero mean and unit variance, the empirical spectral distribution of $\frac{1}{\sqrt{n}}{\bf X}_n$ converges almost surely to the uniform distribution over the unit disk in the complex plane as $n \to \infty$. This paper demonstrates that the circular law still holds under the more general Lindeberg's condition: $$ \frac1{n^2}\sum_{i,j=1}^n\mathbb{E}|x_{ij}^2|I(|x_{ij}|>\eta\sqrt{n})\to 0,\mbox{as $n \to \infty$}. $$ This paper is a revisit of the proof procedure of the circular law by Bai in (Ann Probab 25: 494-529, 1997). The key breakthroughs in the paper are establishing a general strong law of large numbers under Lindeberg's condition and the uniform upper bound for the integral with respect to the smallest eigenvalues of random matrices. These advancements significantly streamline and clarify the proof of the circular law, offering a more direct and simplified approach than other existing methodologies.

Smart contract developers frequently seek solutions to developmental challenges on Q&A platforms such as Stack Overflow (SO). Although community responses often provide viable solutions, the embedded code snippets can also contain hidden vulnerabilities. Integrating such code directly into smart contracts may make them susceptible to malicious attacks. We conducted an online survey and received 74 responses from smart contract developers. The results of this survey indicate that the majority (86.4%) of participants do not sufficiently consider security when reusing SO code snippets. Despite the existence of various tools designed to detect vulnerabilities in smart contracts, these tools are typically developed for analyzing fully-completed smart contracts and thus are ineffective for analyzing typical code snippets as found on SO. We introduce SOChecker, the first tool designed to identify potential vulnerabilities in incomplete SO smart contract code snippets. SOChecker first leverages a fine-tuned Llama2 model for code completion, followed by the application of symbolic execution methods for vulnerability detection. Our experimental results, derived from a dataset comprising 897 code snippets collected from smart contract-related SO posts, demonstrate that SOChecker achieves an F1 score of 68.2%, greatly surpassing GPT-3.5 and GPT-4 (20.9% and 33.2% F1 Scores respectively). Our findings underscore the need to improve the security of code snippets from Q&A websites.

We are concerned with decentralized optimization over a compact submanifold, where the loss functions of local datasets are defined by their respective local datasets. A key challenge in decentralized optimization is mitigating the communication bottleneck, which primarily involves two strategies: achieving consensus and applying communication compression. Existing projection/retraction-type algorithms rely on multi-step consensus to attain both consensus and optimality. Due to the nonconvex nature of the manifold constraint, it remains an open question whether the requirement for multi-step consensus can be reduced to single-step consensus. We address this question by carefully elaborating on the smoothness structure and the asymptotic 1-Lipschitz continuity associated with the manifold constraint. Furthermore, we integrate these insights with a communication compression strategy to propose a communication-efficient gradient algorithm for decentralized manifold optimization problems, significantly reducing per-iteration communication costs. Additionally, we establish an iteration complexity of $\mathcal{O}(\epsilon^{-1})$ to find an $\epsilon$-stationary point, which matches the complexity in the Euclidean setting. Numerical experiments demonstrate the efficiency of the proposed method in comparison to state-of-the-art approaches., Comment: 25 pages

The random self-reinforcement mechanism, characterized by the principle of ``the rich get richer'', has demonstrated significant utility across various domains. One prominent model embodying this mechanism is the random reinforcement urn model. This paper investigates a multicolored, multiple-drawing variant of the random reinforced urn model. We establish the limiting behavior of the normalized urn composition and demonstrate strong convergence upon scaling the counts of each color. Additionally, we derive strong convergence estimators for the reinforcement means, i.e., for the expectations of the replacement matrix's diagonal elements, and prove their joint asymptotic normality. It is noteworthy that the estimators of the largest reinforcement mean are asymptotically independent of the estimators of the other smaller reinforcement means. Additionally, if a reinforcement mean is not the largest, the estimators of these smaller reinforcement means will also demonstrate asymptotic independence among themselves. Furthermore, we explore the parallels between the reinforced mechanisms in random reinforced urn models and multi-armed bandits, addressing hypothesis testing for expected payoffs in the latter context.

Many machine learning tasks, such as principal component analysis and low-rank matrix completion, give rise to manifold optimization problems. Although there is a large body of work studying the design and analysis of algorithms for manifold optimization in the centralized setting, there are currently very few works addressing the federated setting. In this paper, we consider nonconvex federated learning over a compact smooth submanifold in the setting of heterogeneous client data. We propose an algorithm that leverages stochastic Riemannian gradients and a manifold projection operator to improve computational efficiency, uses local updates to improve communication efficiency, and avoids client drift. Theoretically, we show that our proposed algorithm converges sub-linearly to a neighborhood of a first-order optimal solution by using a novel analysis that jointly exploits the manifold structure and properties of the loss functions. Numerical experiments demonstrate that our algorithm has significantly smaller computational and communication overhead than existing methods.

In this paper, we investigate the asymptotic behaviors of the extreme eigenvectors in a general spiked covariance matrix, where the dimension and sample size increase proportionally. We eliminate the restrictive assumption of the block diagonal structure in the population covariance matrix. Moreover, there is no requirement for the spiked eigenvalues and the 4th moment to be bounded. Specifically, we apply random matrix theory to derive the convergence and limiting distributions of certain projections of the extreme eigenvectors in a large sample covariance matrix within a generalized spiked population model. Furthermore, our techniques are robust and effective, even when spiked eigenvalues differ significantly in magnitude from nonspiked ones. Finally, we propose a powerful statistic for hypothesis testing for the eigenspaces of covariance matrices.

In this paper, we present two novel manifold inexact augmented Lagrangian methods, \textbf{ManIAL} for deterministic settings and \textbf{StoManIAL} for stochastic settings, solving nonsmooth manifold optimization problems. By using the Riemannian gradient method as a subroutine, we establish an $\mathcal{O}(\epsilon^{-3})$ oracle complexity result of \textbf{ManIAL}, matching the best-known complexity result. Our algorithm relies on the careful selection of penalty parameters and the precise control of termination criteria for subproblems. Moreover, for cases where the smooth term follows an expectation form, our proposed \textbf{StoManIAL} utilizes a Riemannian recursive momentum method as a subroutine, and achieves an oracle complexity of $\tilde{\mathcal{O}}(\epsilon^{-3.5})$, which surpasses the best-known $\mathcal{O}(\epsilon^{-4})$ result. Numerical experiments conducted on sparse principal component analysis and sparse canonical correlation analysis demonstrate that our proposed methods outperform an existing method with the previously best-known complexity result. To the best of our knowledge, these are the first complexity results of the augmented Lagrangian methods for solving nonsmooth manifold optimization problems., Comment: 30 pages

Recent advancements in large-scale pretrained models have significantly improved performance across a variety of tasks in natural language processing and computer vision. However, the extensive number of parameters in these models necessitates substantial memory and computational resources for full training. To adapt these models for downstream tasks or specific application-oriented datasets, parameter-efficient fine-tuning methods leveraging pretrained parameters have gained considerable attention. However, it can still be time-consuming due to lots of parameters and epochs. In this work, we introduce AdaFish, an efficient algorithm of the second-order type designed to expedite the training process within low-rank decomposition-based fine-tuning frameworks. Our key observation is that the associated generalized Fisher information matrix is either low-rank or extremely small-scaled. Such a generalized Fisher information matrix is shown to be equivalent to the Hessian matrix. Moreover, we prove the global convergence of AdaFish, along with its iteration/oracle complexity. Numerical experiments show that our algorithm is quite competitive with the state-of-the-art AdamW method.

In this paper, we focus on the BDS test, which is a nonparametric test of independence. Specifically, the null hypothesis $H_{0}$ of it is that $\{u_{t}\}$ is i.i.d. (independent and identically distributed), where $\{u_{t}\}$ is a random sequence. The BDS test is widely used in economics and finance, but it has a weakness that cannot be ignored: over-rejecting $H_{0}$ even if the length $T$ of $\{u_{t}\}$ is as large as $(100,2000)$. To improve the over-rejection problem of BDS test, considering that the correlation integral is the foundation of BDS test, we not only accurately describe the expectation of the correlation integral under $H_{0}$, but also calculate all terms of the asymptotic variance of the correlation integral whose order is $O(T^{-1})$ and $O(T^{-2})$, which is essential to improve the finite sample performance of BDS test. Based on this, we propose a revised BDS (RBDS) test and prove its asymptotic normality under $H_{0}$. The RBDS test not only inherits all the advantages of the BDS test, but also effectively corrects the over-rejection problem of the BDS test, which can be fully confirmed by the simulation results we presented. Moreover, based on the simulation results, we find that similar to BDS test, RBDS test would also be affected by the parameter estimations of the ARCH-type model, resulting in size distortion, but this phenomenon can be alleviated by the logarithmic transformation preprocessing of the estimate residuals of the model. Besides, through some actual datasets that have been demonstrated to fit well with ARCH-type models, we also compared the performance of BDS test and RBDS test in evaluating the goodness-of-fit of the model in empirical problem, and the results reflect that, under the same condition, the performance of the RBDS test is more encouraging.

In this paper, we develop a novel primal-dual semismooth Newton method for solving linearly constrained multi-block convex composite optimization problems. First, a differentiable augmented Lagrangian (AL) function is constructed by utilizing the Moreau envelopes of the nonsmooth functions. It enables us to derive an equivalent saddle point problem and establish the strong AL duality under the Slater's condition. Consequently, a semismooth system of nonlinear equations is formulated to characterize the optimality of the original problem instead of the inclusion-form KKT conditions. We then develop a semismooth Newton method, called ALPDSN, which uses purely second-order steps and a nonmonotone line search based globalization strategy. Through a connection to the inexact first-order steps when the regularization parameter is sufficiently large, the global convergence of ALPDSN is established. Under the regularity conditions, partial smoothness, the local error bound, and the strict complementarity, we show that both the primal and the dual iteration sequences possess a superlinear convergence rate and provide concrete examples where these regularity conditions are met. Numerical results on the image restoration with two regularization terms and the corrected tensor nuclear norm problem are presented to demonstrate the high efficiency and robustness of our ALPDSN., Comment: 27 pages

The proliferation of science and technology has led to the prevalence of voluminous data sets that are distributed across multiple machines. It is an established fact that conventional statistical methodologies may be unfeasible in the analysis of such massive data sets due to prohibitively long computing durations, memory constraints, communication overheads, and confidentiality considerations. In this paper, we propose distributed estimators of the spiked eigenvalues in spiked population models. The consistency and asymptotic normality of the distributed estimators are derived, and the statistical error analysis of the distributed estimators is provided as well. Compared to the estimation from the full sample, the proposed distributed estimation shares the same order of convergence. Simulation study and real data analysis indicate that the proposed distributed estimation and testing procedures have excellent properties in terms of estimation accuracy and stability as well as transmission efficiency.

The Segment Anything Model (SAM), a foundation model for general image segmentation, has demonstrated impressive zero-shot performance across numerous natural image segmentation tasks. However, SAM's performance significantly declines when applied to medical images, primarily due to the substantial disparity between natural and medical image domains. To effectively adapt SAM to medical images, it is important to incorporate critical third-dimensional information, i.e., volumetric or temporal knowledge, during fine-tuning. Simultaneously, we aim to harness SAM's pre-trained weights within its original 2D backbone to the fullest extent. In this paper, we introduce a modality-agnostic SAM adaptation framework, named as MA-SAM, that is applicable to various volumetric and video medical data. Our method roots in the parameter-efficient fine-tuning strategy to update only a small portion of weight increments while preserving the majority of SAM's pre-trained weights. By injecting a series of 3D adapters into the transformer blocks of the image encoder, our method enables the pre-trained 2D backbone to extract third-dimensional information from input data. The effectiveness of our method has been comprehensively evaluated on four medical image segmentation tasks, by using 10 public datasets across CT, MRI, and surgical video data. Remarkably, without using any prompt, our method consistently outperforms various state-of-the-art 3D approaches, surpassing nnU-Net by 0.9%, 2.6%, and 9.9% in Dice for CT multi-organ segmentation, MRI prostate segmentation, and surgical scene segmentation respectively. Our model also demonstrates strong generalization, and excels in challenging tumor segmentation when prompts are used. Our code is available at: https://github.com/cchen-cc/MA-SAM.

We propose a novel algorithm for solving the composite Federated Learning (FL) problem. This algorithm manages non-smooth regularization by strategically decoupling the proximal operator and communication, and addresses client drift without any assumptions about data similarity. Moreover, each worker uses local updates to reduce the communication frequency with the server and transmits only a $d$-dimensional vector per communication round. We prove that our algorithm converges linearly to a neighborhood of the optimal solution and demonstrate the superiority of our algorithm over state-of-the-art methods in numerical experiments.

This paper introduces Radiology-Llama2, a large language model specialized for radiology through a process known as instruction tuning. Radiology-Llama2 is based on the Llama2 architecture and further trained on a large dataset of radiology reports to generate coherent and clinically useful impressions from radiological findings. Quantitative evaluations using ROUGE metrics on the MIMIC-CXR and OpenI datasets demonstrate that Radiology-Llama2 achieves state-of-the-art performance compared to other generative language models, with a Rouge-1 score of 0.4834 on MIMIC-CXR and 0.4185 on OpenI. Additional assessments by radiology experts highlight the model's strengths in understandability, coherence, relevance, conciseness, and clinical utility. The work illustrates the potential of localized language models designed and tuned for specialized domains like radiology. When properly evaluated and deployed, such models can transform fields like radiology by automating rote tasks and enhancing human expertise.

Let $ \bbB_n =\frac{1}{n}(\bbR_n + \bbT^{1/2}_n \bbX_n)(\bbR_n + \bbT^{1/2}_n \bbX_n)^* $ where $ \bbX_n $ is a $ p \times n $ matrix with independent standardized random variables, $ \bbR_n $ is a $ p \times n $ non-random matrix, representing the information, and $ \bbT_{n} $ is a $ p \times p $ non-random nonnegative definite Hermitian matrix. Under some conditions on $ \bbR_n \bbR_n^* $ and $ \bbT_n $, it has been proved that for any closed interval outside the support of the limit spectral distribution, with probability one there will be no eigenvalues falling in this interval for all $ p $ sufficiently large. The purpose of this paper is to carry on with the study of the support of the limit spectral distribution, and we show that there is an exact separation phenomenon: with probability one, the proper number of eigenvalues lie on either side of these intervals.

The various benefits of multi-tenanting, such as higher device utilization and increased profit margin, intrigue the cloud field-programmable gate array (FPGA) servers to include multi-tenanting in their infrastructure. However, this property makes these servers vulnerable to power side-channel (PSC) attacks. Logic designs such as ring oscillator (RO) and time-to-digital converter (TDC) are used to measure the power consumed by security critical circuits, such as advanced encryption standard (AES). Firstly, the existing works require higher minimum traces for disclosure (MTD). Hence, in this work, we improve the sensitivity of the TDC-based sensors by manually placing the FPGA primitives inferring these sensors. This enhancement helps to determine the 128-bit AES key using 3.8K traces. Secondly, the existing defenses use ROs to defend against PSC attacks. However, cloud servers such as Amazon Web Services (AWS) block design with combinatorial loops. Hence, we propose a placement-based defense. We study the impact of (i) primitive-level placement on the AES design and (ii) additional logic that resides along with the AES on the correlation power analysis (CPA) attack results. Our results showcase that the AES along with filters and/or processors are sufficient to provide the same level or better security than the existing defenses.

We consider the consensus problem in a decentralized network, focusing on a compact submanifold that acts as a nonconvex constraint set. By leveraging the proximal smoothness of the compact submanifold, which encompasses the local singleton property and the local Lipschitz continuity of the projection operator on the manifold, and establishing the connection between the projection operator and general retraction, we show that the Riemannian gradient descent with a unit step size has locally linear convergence if the network has a satisfactory level of connectivity. Moreover, based on the geometry of the compact submanifold, we prove that a convexity-like regularity condition, referred to as the restricted secant inequality, always holds in an explicitly characterized neighborhood around the solution set of the nonconvex consensus problem. By leveraging this restricted secant inequality and imposing a weaker connectivity requirement on the decentralized network, we present a comprehensive analysis of the linear convergence of the Riemannian gradient descent, taking into consideration appropriate initialization and step size. Furthermore, if the network is well connected, we demonstrate that the local Lipschitz continuity endowed by proximal smoothness is a sufficient condition for the restricted secant inequality, thus contributing to the local error bound. We believe that our established results will find more application in the consensus problems over a more general proximally smooth set. Numerical experiments are conducted to validate our theoretical findings., Comment: 25 pages

We consider the problem of decentralized nonconvex optimization over a compact submanifold, where each local agent's objective function defined by the local dataset is smooth. Leveraging the powerful tool of proximal smoothness, we establish local linear convergence of the projected gradient descent method with a unit step size for solving the consensus problem over the nonconvex compact submanifold. This serves as the basis for designing and analyzing decentralized algorithms on manifolds. Subsequently, we propose two decentralized methods: the decentralized projected Riemannian gradient descent (DPRGD) and the decentralized projected Riemannian gradient tracking (DPRGT). We establish their convergence rates of $\mathcal{O}(1/\sqrt{K})$ and $\mathcal{O}(1/K)$, respectively, to reach a stationary point. To the best of our knowledge, DPRGT is the first decentralized algorithm to achieve exact convergence for solving decentralized optimization over a compact submanifold. Beyond the linear convergence results on the consensus, two key tools developed in the proof are the Lipschitz-type inequality of the projection operator and the Riemannian quadratic upper bound for smooth functions on the compact submanifold, which could be of independent interest. Finally, we demonstrate the effectiveness of our proposed methods compared to state-of-the-art ones through numerical experiments on eigenvalue problems and low-rank matrix completion., Comment: 32 pages

The paper discusses a statistical problem related to testing for differences between two sparse networks with community structures. The community-wise edge probability matrices have entries of order $O(n^{-1}/\log n)$, where $n$ represents the size of the network. The authors propose a test statistic that combines a method proposed by Wu et al. \cite{WuTwoSampleSBM2022} and a resampling process. They derive the asymptotic null distribution of the test statistic and provide a guarantee of asymptotic power against the alternative hypothesis. To evaluate the performance of the proposed test statistic, the authors conduct simulations and provide real data examples. The results indicate that the proposed test statistic performs well in practice.

An important issue in many multivariate regression problems is to eliminate candidate predictors with null predictor vectors. In large-dimensional (LD) setting where the numbers of responses and predictors are large, model selection encounters the scalability challenge. Knock-one-out (KOO) statistics hold promise to meet this challenge. In this paper, the almost sure limits and the central limit theorem of the KOO statistics are derived under the LD setting and mild distributional assumptions (finite fourth moments) of the errors. These theoretical results guarantee the strong consistency of a subset selection rule based on the KOO statistics with a general threshold. For enhancing the robustness of the selection rule, we also propose a bootstrap threshold for the KOO approach. Simulation results support our conclusions and demonstrate the selection probabilities by the KOO approach with the bootstrap threshold outperform the methods using Akaike information threshold, Bayesian information threshold and Mallow's C$_p$ threshold. We compare the proposed KOO approach with those based on information threshold to a chemometrics dataset and a yeast cell-cycle dataset, which suggests our proposed method identifies useful models.

We focus on a class of non-smooth optimization problems over the Stiefel manifold in the decentralized setting, where a connected network of $n$ agents cooperatively minimize a finite-sum objective function with each component being weakly convex in the ambient Euclidean space. Such optimization problems, albeit frequently encountered in applications, are quite challenging due to their non-smoothness and non-convexity. To tackle them, we propose an iterative method called the decentralized Riemannian subgradient method (DRSM). The global convergence and an iteration complexity of $\mathcal{O}(\varepsilon^{-2} \log^2(\varepsilon^{-1}))$ for forcing a natural stationarity measure below $\varepsilon$ are established via the powerful tool of proximal smoothness from variational analysis, which could be of independent interest. Besides, we show the local linear convergence of the DRSM using geometrically diminishing stepsizes when the problem at hand further possesses a sharpness property. Numerical experiments are conducted to corroborate our theoretical findings., Comment: 27 pages, 6 figures, 1 table

The validation process for microprocessors is a very complex task that consumes substantial engineering time during the design process. Bugs that degrade overall system performance, without affecting its functional correctness, are particularly difficult to debug given the lack of a golden reference for bug-free performance. This work introduces two automated performance bug localization methodologies based on machine learning that aims to aid the debugging process. Our results show that, the evaluated microprocessor core performance bugs whose average IPC impact is greater than 1%, our best-performing technique is able to localize the exact microarchitectural unit of the bug $\sim$77\% of the time, while achieving a top-3 unit accuracy (out of 11 possible locations) of over 90% for bugs with the same average IPC impact. The proposed system in our simulation setup requires only a few seconds to perform a bug location inference, which leads to a reduced debugging time., Comment: 12 pages, 6 figures

Community detection is a fundamental problem in complex network data analysis. Though many methods have been proposed, most existing methods require the number of communities to be the known parameter, which is not in practice. In this paper, we propose a novel goodness-of-fit test for the stochastic block model. The test statistic is based on the linear spectral of the adjacency matrix. Under the null hypothesis, we prove that the linear spectral statistic converges in distribution to $N(0,1)$. Some recent results in generalized Wigner matrices are used to prove the main theorems. Numerical experiments and real world data examples illustrate that our proposed linear spectral statistic has good performance.

Let $ \bbB_n =\frac{1}{n}(\bbR_n + \bbT^{1/2}_n \bbX_n)(\bbR_n + \bbT^{1/2}_n \bbX_n)^* $, where $ \bbX_n $ is a $ p \times n $ matrix with independent standardized random variables, $ \bbR_n $ is a $ p \times n $ non-random matrix and $ \bbT_{n} $ is a $ p \times p $ non-random, nonnegative definite Hermitian matrix. The matrix $\bbB_n$ is referred to as the information-plus-noise type matrix, where $\bbR_n$ contains the information and $\bbT^{1/2}_n \bbX_n$ is the noise matrix with the covariance matrix $\bbT_{n} $. It is known that, as $ n \to \infty $, if $ p/n $ converges to a positive number, the empirical spectral distribution of $ \bbB_n $ converges almost surely to a nonrandom limit, under some mild conditions. In this paper, we prove that, under certain conditions on the eigenvalues of $ \bbR_n $ and $ \bbT_n $, for any closed interval outside the support of the limit spectral distribution, with probability one there will be no eigenvalues falling in this interval for all $ n $ sufficiently large., Comment: 26 pages

With a computationally efficient approximation of the second-order information, natural gradient methods have been successful in solving large-scale structured optimization problems. We study the natural gradient methods for the large-scale decentralized optimization problems on Riemannian manifolds, where the local objective function defined by the local dataset is of a log-probability type. By utilizing the structure of the Riemannian Fisher information matrix (RFIM), we present an efficient decentralized Riemannian natural gradient descent (DRNGD) method. To overcome the communication issue of the high-dimension RFIM, we consider a class of structured problems for which the RFIM can be approximated by a Kronecker product of two low-dimension matrices. By performing the communications over the Kronecker factors, a high-quality approximation of the RFIM can be obtained in a low cost. We prove that DRNGD converges to a stationary point with the best-known rate of $\mathcal{O}(1/K)$. Numerical experiments demonstrate the efficiency of our proposed method compared with the state-of-the-art ones. To the best of our knowledge, this is the first Riemannian second-order method for solving decentralized manifold optimization problems., Comment: 17 pages

This paper aims to develop a Newton-type method to solve a class of nonconvex composite programs. In particular, the nonsmooth part is possibly nonconvex. To tackle the nonconvexity, we develop a notion of strong prox-regularity which is related to the singleton property, Lipschitz continuity, and monotonicity of the associated proximal operator, and we verify it in various classes of functions, including weakly convex functions, indicator functions of proximally smooth sets, and two specific sphere-related nonconvex nonsmooth functions. In this case, the problem class we are concerned with covers smooth optimization problems on manifold and certain composite optimization problems on manifold. For the latter, the proposed algorithm is the first second-order type method. Combining with the semismoothness of the proximal operator, we design a projected semismooth Newton method to find a root of the natural residual induced by the proximal gradient method. Since the corresponding natural residual may not be globally monotone, an extra projection is added on the usual semismooth Newton step and new criteria are proposed for the switching between the projected semismooth Newton step and the proximal step. The global convergence is then established under the strong prox-regularity. Based on the BD regularity condition, we establish local superlinear convergence. Numerical experiments demonstrate the effectiveness of our proposed method compared with state-of-the-art ones., Comment: 26 pages

In this paper, we derive the analytical behavior of the limiting spectral distribution of non-central covariance matrices of the "general information-plus-noise" type, as studied in [14]. Through the equation defining its Stieltjes transform, it is shown that the limiting distribution has a continuous derivative away from zero, the derivative being analytic wherever it is positive, and we show the determination criterion for its support. We also extend the result in [14] to allow for all possible ratios of row to column of the underlying random matrix.

It is well known that most of the existing theoretical results in statistics are based on the assumption that the sample is generated with replacement from an infinite population. However, in practice, available samples are almost always collected without replacement. If the population is a finite set of real numbers, whether we can still safely use the results from samples drawn without replacement becomes an important problem. In this paper, we focus on the eigenvalues of high-dimensional sample covariance matrices generated without replacement from finite populations. Specifically, we derive the Tracy-Widom laws for their largest eigenvalues and apply these results to parallel analysis. We provide new insight into the permutation methods proposed by Buja and Eyuboglu in [Multivar Behav Res. 27(4) (1992) 509--540]. Simulation and real data studies are conducted to demonstrate our results., Comment: Accepted by Bernoulli

In this paper, we establish the central limit theorem (CLT) for linear spectral statistics (LSSs) of a large-dimensional sample covariance matrix when the population covariance matrices are involved with diverging spikes. This constitutes a nontrivial extension of the Bai-Silverstein theorem (BST) (Ann Probab 32(1):553--605, 2004), a theorem that has strongly influenced the development of high-dimensional statistics, especially in the applications of random matrix theory to statistics. Recently, there has been a growing realization that the assumption of uniform boundedness of the population covariance matrices in the BST is not satisfied in some fields, such as economics, where the variances of principal components may diverge as the dimension tends to infinity. Therefore, in this paper, we aim to eliminate this obstacle to applications of the BST. Our new CLT accommodates spiked eigenvalues, which may either be bounded or tend to infinity. A distinguishing feature of our result is that the variance in the new CLT is related to both spiked eigenvalues and bulk eigenvalues, with dominance being determined by the divergence rate of the largest spiked eigenvalues. The new CLT for LSS is then applied to test the hypothesis that the population covariance matrix is the identity matrix or a generalized spiked model. The asymptotic distributions of the corrected likelihood ratio test statistic and the corrected Nagao's trace test statistic are derived under the alternative hypothesis. Moreover, we present power comparisons between these two LSSs and Roy's largest root test. In particular, we demonstrate that except for the case in which the number of spikes is equal to one, the LSSs could exhibit higher asymptotic power than Roy's largest root test., Comment: It is an update version of arXiv:2212.05896

In this paper, we introduce the notion of generalized $\epsilon$-stationarity for a class of nonconvex and nonsmooth composite minimization problems on compact Riemannian submanifold embedded in Euclidean space. To find a generalized $\epsilon$-stationarity point, we develop a family of Riemannian gradient-type methods based on the Moreau envelope technique with a decreasing sequence of smoothing parameters, namely Riemannian smoothing gradient and Riemannian smoothing stochastic gradient methods. We prove that the Riemannian smoothing gradient method has the iteration complexity of $\mathcal{O}(\epsilon^{-3})$ for driving a generalized $\epsilon$-stationary point. To our knowledge, this is the best-known iteration complexity result for the nonconvex and nonsmooth composite problem on manifolds. For the Riemannian smoothing stochastic gradient method, one can achieve the iteration complexity of $\mathcal{O}(\epsilon^{-5})$ for driving a generalized $\epsilon$-stationary point. Numerical experiments are conducted to validate the superiority of our algorithms.

Let $G$ be a finite Abelian group of order $d$. We consider an urn in which, initially, there are labeled balls that generate the group $G$. Choosing two balls from the urn with replacement, observe their labels, and perform a group multiplication on the respective group elements to obtain a group element. Then, we put a ball labeled with that resulting element into the urn. This model was formulated by P. Diaconis while studying a group theoretic algorithm called MeatAxe (Holt and Rees (1994)). Siegmund and Yakir (2004) partially investigated this model. In this paper, we further investigate and generalize this model. More specifically, we allow a random number of balls to be drawn from the urn at each stage in the Diaconis urn model. For such a case, we verify that the normalized urn composition converges almost surely to the uniform distribution on the group $G$. Moreover, we obtain the asymptotic joint distribution of the urn composition by using the martingale central limit theorem.

In this paper, we consider a large class of nonlinear equations derived from first-order type methods for solving composite optimization problems. Traditional approaches to establishing superlinear convergence rates of semismooth Newton-type methods for solving nonlinear equations usually postulate either nonsingularity of the B-Jacobian or smoothness of the equation. We investigate the feasibility of both conditions. For the nonsingularity condition, we present equivalent characterizations in broad generality, and illustrate that they are easy-to-check criteria for some examples. For the smoothness condition, we show that it holds locally for a large class of residual mappings derived from composite optimization problems. Furthermore, we investigate a relaxed version of the smoothness condition - smoothness restricted to certain active manifolds. We present a conceptual algorithm utilizing such structures and prove that it has a superlinear convergence rate., Comment: 29 pages

This paper studies large-scale optimization problems on Riemannian manifolds whose objective function is a finite sum of negative log-probability losses. Such problems arise in various machine learning and signal processing applications. By introducing the notion of Fisher information matrix in the manifold setting, we propose a novel Riemannian natural gradient method, which can be viewed as a natural extension of the natural gradient method from the Euclidean setting to the manifold setting. We establish the almost-sure global convergence of our proposed method under standard assumptions. Moreover, we show that if the loss function satisfies certain convexity and smoothness conditions and the input-output map satisfies a Riemannian Jacobian stability condition, then our proposed method enjoys a local linear -- or, under the Lipschitz continuity of the Riemannian Jacobian of the input-output map, even quadratic -- rate of convergence. We then prove that the Riemannian Jacobian stability condition will be satisfied by a two-layer fully connected neural network with batch normalization with high probability, provided that the width of the network is sufficiently large. This demonstrates the practical relevance of our convergence rate result. Numerical experiments on applications arising from machine learning demonstrate the advantages of the proposed method over state-of-the-art ones.

A fundamental concept in multivariate statistics, sample correlation matrix, is often used to infer the correlation/dependence structure among random variables, when the population mean and covariance are unknown. A natural block extension of it, {\it sample block correlation matrix}, is proposed to take on the same role, when random variables are generalized to random sub-vectors. In this paper, we establish a spectral theory of the sample block correlation matrices and apply it to group independent test and related problem, under the high-dimensional setting. More specifically, we consider a random vector of dimension $p$, consisting of $k$ sub-vectors of dimension $p_t$'s, where $p_t$'s can vary from $1$ to order $p$. Our primary goal is to investigate the dependence of the $k$ sub-vectors. We construct a random matrix model called sample block correlation matrix based on $n$ samples for this purpose. The spectral statistics of the sample block correlation matrix include the classical Wilks' statistic and Schott's statistic as special cases. It turns out that the spectral statistics do not depend on the unknown population mean and covariance. Further, under the null hypothesis that the sub-vectors are independent, the limiting behavior of the spectral statistics can be described with the aid of the Free Probability Theory. Specifically, under three different settings of possibly $n$-dependent $k$ and $p_t$'s, we show that the empirical spectral distribution of the sample block correlation matrix converges to the free Poisson binomial distribution, free Poisson distribution (Marchenko-Pastur law) and free Gaussian distribution (semicircle law), respectively. We then further derive the CLTs for the linear spectral statistics of the block correlation matrix under general setting.