Search

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) 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: improved writing

Additional file 1: Figure S1. Location of sampling sites in the gas hydrate zone of Shenhu area (SH) and Qiongdongnan (QDN) Basin from the South China Sea.All the four drilling sites werelocated above deep subsurface gas chimneys. They wereretrieved from the Shenhu area (n =1; SH-W20A) and Qiongdongnan Basin (n =3; QDN-W01B, W03B and W04B). The drilling depths of sediments are between 100and 188 mbsf in water depths ranging from 1000 to 1500 meters. Figure S2. Comparison of Chao1 and Shannon indices of the microbial community between sedimentsabove and below the SMI in the gas hydrate zone. Chao1 and Shannon indices werecalculated based on the SingleM ((https://github.com/wwood/singlem) OTU tablesfor 14 universal single-copy genes. P-values of differences between redox zones were calculated using Wilcoxon rank sum test. Asterisks denote significance (*** for P < 0.001). Figure S3. Relative abundances of each class from the Halobacterota phylum inferredfrom 16S rRNA gene fragments in metagenomes. Figure S4. MAG recovery information across differenttaxonomic levels. A Sankey diagram based on assigned GTDB taxonomy showing archaeal (a) and bacterial (b) MAGs at different phylogenetic levels. Numbers indicate the number of MAGs recovered for this lineage. (c) Total MAGs unclassified by GTDB-Tk at each taxonomic level. MAGs were dereplicated at strain level (i.e., 95% ANI). Detailed statistics for 578 MAGs are provided in Table S3. Figure S5. Phylogenetic placement of 349 MAGs for microbial communities in the deep subsurface sediments from the gas hydrate zone. Branches in red indicate unclassified MAGs. The maximum-likelihood phylogenomic tree was built based on concatenated amino acid sequences of 43 conserved single-copy genes using RAxML with the PROTCATLG model. The scale bar represents the average number of substitutions per site. Relative abundances of those microorganisms can be found in Table S4. Figure S6. Carbohydrate-active enzyme composition of the deep subseafloor microbiome from the gas hydrate zone. GTs: glycosyltransferases; GHs: glycoside hydrolases; CEs: carbohydrate esterases; CMBs: carbohydrate-binding modules; AA: auxiliary activities; PLs: polysaccharide lyases. Figure S7. Percentage of extracellular carbohydrate-activeenzymes (CAZymes) encoded in each phylogenetic cluster. The number of MAGs per phylogenetic cluster is shown in brackets. CMBs: carbohydrate-binding modules; CEs: carbohydrate esterases; GHs: glycoside hydrolases; GTs: glycosyltransferases; PLs: polysaccharide lyases. Figure S8. Percentage of extracellular peptidases encoded in each phylogenetic cluster. The number of MAGs per phylogenetic cluster is shown in brackets. Figure S9. Presence and absence of genes in sulfate-reducing pathway for recovered sulfate reducers reported in this study. Figure S10. Phylogenomic placement of MCR-containing MAGs based on 43 conserved protein sequences. Black dots indicate bootstrap values of 70–100%. Scale bars indicate the average number of substitutions per site. Figure S11. Co-localization of mcr with genes nearby. Genes are colored according to their functions. Red: Mcr complex; Purple: Methane/Alkane metabolism-related; Brown: Methanol utilization; Pink: Methylamine utilization; Orange: ABC transporter; Green: Cas protein; Greenyellow: tRNA/rRNA; Grey: Others. Figure S12. Predicted pathways of hydrogen-dependent methylotrophic methanogenesis. Grey colors indicate the absence of the enzyme or pathway. mWL pathway, methyl-branch of the Wood–Ljungdahl pathway. The percentages between brackets indicate the estimated completeness of the corresponding MAGs. A complete list of metabolic information can be found in Table S11. Figure S13. Relative abundances of hydrocarbon-metabolizing archaea and sulfate reducers inferred from metabolic pathway reconstructions. The MAG with the highest genome quality from each species cluster is picked as the representative. Details on species clusters and their relative abundances are presented in Table S4. Figure S14. Predicted pathways of anaerobic oxidation of methane. Grey colors indicate the absence of the enzyme or pathway. The percentages between brackets indicate the estimated completeness of the corresponding MAGs. A complete list of metabolic information can be found in Table S11.

The ADMM-based interior point method (ABIP, Lin et al.\ 2021) is a hybrid algorithm which effectively combines the iterior point method and the first-order method to achieve performance boost in large-scale linear programming. Different from the standard interior point method which relies on a costly Newton step, ABIP applies the alternating direction method of multipliers (ADMM) to approximately solve the barrier penalized problem. In this paper, we provide a new version of ABIP with several improvements. First, we develop some new implementation strategies to accelerate ABIP's performance for linear programming. Next, we extend ABIP to solving the more general linear conic programming and establish the associated iteration complexity of the algorithm. Finally, we conduct extensive numerical experiments in both synthetic and real-world datasets to demonstrate the empirical advantage of our developments. In particular, the enhanced ABIP achieves a 5.8x reduction in the geometric mean of run time on $105$ LP instances from Netlib and it compares favorably against state-of-the-art open-source solvers in a wide range of large-scale problems. Moreover, it is even comparable to the commercial solvers in some particular datasets.

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

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 be implemented. 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 a line-search version