Search

Optimization problems with access to only zeroth-order information of the objective function on Riemannian manifolds arise in various applications, spanning from statistical learning to robot learning. While various zeroth-order algorithms have been proposed in Euclidean space, they are not inherently designed to handle the challenging constraints imposed by Riemannian manifolds. The proper adaptation of zeroth-order techniques to Riemannian manifolds remained unknown until the pioneering work of \cite{li2023stochastic}. However, zeroth-order algorithms are widely observed to converge slowly and be unstable in practice. To alleviate these issues, we propose a Riemannian accelerated zeroth-order algorithm with improved robustness. Regarding efficiency, our accelerated algorithm has the function query complexity of $\mathcal{O}(\epsilon^{-7/4}d)$ for finding an $\epsilon$-approximate first-order stationary point. By introducing a small perturbation, it exhibits a function query complexity of $\tilde{\mathcal{O}}(\epsilon^{-7/4}d)$ for seeking a second-order stationary point with a high probability, matching state-of-the-art result in Euclidean space. Moreover, we further establish the almost sure convergence in the asymptotic sense through the Stable Manifold Theorem. Regarding robustness, our algorithm requires larger smoothing parameters in the order of $\tilde{\mathcal{O}}(\epsilon^{7/8}d^{-1/2})$, improving the existing result by a factor of $\tilde{\mathcal{O}}(\epsilon^{3/4})$., Comment: Accepted by ICML 2024

This paper presents a universal trust-region method simultaneously incorporating quadratic regularization and the ball constraint. We introduce a novel mechanism to set the parameters in the proposed method that unifies the analysis for convex and nonconvex optimization. Our method exhibits an iteration complexity of $\tilde O(\epsilon^{-3/2})$ to find an approximate second-order stationary point for nonconvex optimization. Meanwhile, the analysis reveals that the universal method attains an $O(\epsilon^{-1/2})$ complexity bound for convex optimization and can be accelerated. These results are complementary to the existing literature as the trust-region method was historically conceived for nonconvex optimization. Finally, we develop an adaptive universal method to address practical implementations. The numerical results show the effectiveness of our method in both nonconvex and convex problems.

For a graph $G$, let $S_2(G)$ be the sum of the first two largest signless Laplacian eigenvalues of $G$, and $f(G)=e(G)+3-S_2(G)$. Oliveira, Lima, Rama and Carvalho conjectured that $K^+_{1,n-1}$ (the star graph with an additional edge) is the unique graph with minimum value of $f(G)$ on $n$ vertices. In this paper, we prove this conjecture, which also confirm a conjecture for the upper bound of $S_2(G)$ proposed by Ashraf et al., Comment: 15 pages, 5 figures

This paper proposes a homogeneous second-order descent framework (HSODF) for nonconvex and convex optimization based on the generalized homogeneous model (GHM). In comparison to the Newton steps, the GHM can be solved by extremal symmetric eigenvalue procedures and thus grant an advantage in ill-conditioned problems. Moreover, GHM extends the ordinary homogeneous model (OHM) (Zhang et al. 2022) to allow adaptiveness in the construction of the aggregated matrix. Consequently, HSODF is able to recover some well-known second-order methods, such as trust-region methods and gradient regularized methods, while maintaining comparable iteration complexity bounds. We also study two specific realizations of HSODF. One is adaptive HSODM, which has a parameter-free $O(\epsilon^{-3/2})$ global complexity bound for nonconvex second-order Lipschitz continuous objective functions. The other one is homotopy HSODM, which is proven to have a global linear rate of convergence without strong convexity. The efficiency of our approach to ill-conditioned and high-dimensional problems is justified by some preliminary numerical results., Comment: significantly improve the paper

A stronger interlayer magnetic coupling (ILMC) can open up new opportunities in spintronics devices for Fe$_5$GeTe$_2$ (F5GT), a demonstrated two-dimensional (2D) van der Waals (vdW) material with high Currie temperature. Here we observe an extraordinary ILMC spike in F5GT, jumping from 1.15 to 12.79 meV/f.u, by applying a 3% in-plane strain. This spike is mainly ascribed to a significant increase in the magnetic moment of the Fe5 ion. Moreover, the applied in-plane strain can also significantly enhance the magnetic anisotropy energy (MAE) of the system, triggering the transition between the in/off-plane configurations in multi-layer F5GT., Comment: 25 pages, 9 figures

In this paper, we introduce a Homogeneous Second-Order Descent Method (HSODM) using the homogenized quadratic approximation to the original function. The merit of homogenization is that only the leftmost eigenvector of a gradient-Hessian integrated matrix is computed at each iteration. Therefore, the algorithm is a single-loop method that does not need to switch to other sophisticated algorithms and is easy to implement. We show that HSODM has a global convergence rate of $O(\epsilon^{-3/2})$ to find an $\epsilon$-approximate second-order stationary point, and has a local quadratic convergence rate under the standard assumptions. The numerical results demonstrate the advantage of the proposed method over other second-order methods., Comment: Add inexactness, significantly improve the paper

This paper outlines the establishment of a generic cryogenic CMOS database in which key electrical parameters and transfer characteristics of the MOSFETs are quantified as functions of device size, temperature/frequency responses. Meanwhile, comprehensive device statistical study is conducted to evaluate the influence of variation and mismatch effects at low temperatures. Furthermore, by incorporating the Cryo-CMOS compact model into the process design kit (PDK), the cryogenic 4 Kb SRAM, 5-bit flash ADC and 8-bit current steering DAC are designed, and their performance is readily investigated and optimized on the EDA-compatible platform, hence laying a solid foundation for large-scale cryogenic IC design.

In this paper, we propose a Dimension-Reduced Second-Order Method (DRSOM) for convex and nonconvex (unconstrained) optimization. Under a trust-region-like framework, our method preserves the convergence of the second-order method while using only curvature information in a few directions. Consequently, the computational overhead of our method remains comparable to the first-order such as the gradient descent method. Theoretically, we show that the method has a local quadratic convergence and a global convergence rate of $O(\epsilon^{-3/2})$ to satisfy the first-order and second-order conditions if the subspace satisfies a commonly adopted approximated Hessian assumption. We further show that this assumption can be removed if we perform a corrector step using a Krylov-like method periodically at the end stage of the algorithm. The applicability and performance of DRSOM are exhibited by various computational experiments, including $L_2 - L_p$ minimization, CUTEst problems, and sensor network localization., Comment: Considerable changes in the main text

The first metallic glass of Au-Si alloy has been discovered for over half a century, but its atomic structure is still puzzling. Herein, Au 8 Si dodecahedrons with local five-fold symmetry are revealed as building blocks in Au-Si metallic glass, and the interconnection modes of Au 8 Si dodecahedrons determine the medium-range order. With dimensionality reduction, the surface ordering is attributed to the motif transformation of Au 8 Si dodecahedrons into planar Au 5 Si pyramids with five-fold symmetry, and thus the self-assembly of Au 5 Si pyramids leads to the formation of the ordered Au 2 Si monolayer with the lowest energy. Furthermore, the structural similarity analysis is performed to unveil the physical origin of structural characteristics in different dimensions. The amorphism of Au-Si is due to the smooth energy landscape around the global minimum, while the ordered surface structure occurs due to the steep energy landscape.