检索结果-内蒙古大学图书馆

The Power of Two Matrices in spectral algorithms for Community Recovery

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第5期70卷 3599-3621页

作者： Dhara, Souvik Gaudio, Julia Mossel, Elchanan Sandon, Colin Purdue Univ Sch Ind Engn W Lafayette IN 47907 USA Northwestern Univ Dept Ind Engn & Management Sci Evanston IL 60208 USA Massachussetts Inst Technol Dept Math Cambridge MA 02139 USA Ecole Polytech Fed Lausanne Chair Math Data Sci CH-1015 Lausanne Switzerland

spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. spectral algorithms have been successfully used for graph partitioning, hidden clique recovery and graph coloring. In this paper, we study the power of spectral algorithms using two matrices in a graph partitioning problem. We use two different matrices resulting from two different encodings of the same graph and then combine the spectral information coming from these two matrices. We analyze a two-matrix spectral algorithm for the problem of identifying latent community structure in large random graphs. In particular, we consider the problem of recovering community assignments exactly in the censored stochastic block model, where each edge status is revealed independently with some probability. We show that spectral algorithms based on two matrices are optimal and succeed in recovering communities up to the information theoretic threshold. Further, we show that for most choices of the parameters, any spectral algorithm based on one matrix is suboptimal. The latter observation is in contrast to our prior works (2022a, 2022b) which showed that for the symmetric Stochastic Block Model and the Planted Dense Subgraph problem, a spectral algorithm based on one matrix achieves the information theoretic threshold. We additionally provide more general geometric conditions for the (sub)-optimality of spectral algorithms.

关键词： Encoding Stochastic processes Partitioning algorithms Symmetric matrices Classification algorithms Clustering algorithms Optimization Stochastic block model spectral algorithms information-theoretic boundary

来源：评论

学校读者我要写书评

暂无评论

spectral algorithms for learning with dependent observations

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2024年 437卷

作者： Tong, Hongzhi Ng, Michael Univ Int Business & Econ Sch Stat Beijing 100029 Peoples R China Univ Hong Kong Inst Data Sci Pokfulam Hong Kong Peoples R China Univ Hong Kong Dept Math Pokfulam Hong Kong Peoples R China

We study a class of spectral learning methods with dependent observations, including popular ridge regression, Landweber iteration, spectral cut-off and so on. We derive an explicit risk bound in terms of the correlation of the observations, regularity of the regression function, and effective dimension of the reproducing kernel Hilbert space. By appropriately choosing regularization parameter according to the sample size, the risk bound yields a nearly optimal learning rate with a logarithmic term for strongly mixing sequences. We thus extend the applicable range of spectral algorithm to non-i.i.d. sampling process. Particularly, it is shown that the learning rates for i.i.d. samples in the literature refer to our special case, i.e., the mixing condition parameter tends to zero.& COPY;2023 Elsevier B.V. All rights reserved.

关键词： spectral algorithms Regularization Reproducing kernel Hilbert space Strongly mixing sequence Learning rates

来源：评论

学校读者我要写书评

暂无评论

On the optimality of misspecified spectral algorithms

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2024年第1期25卷 8898-8947页

作者： Haobo Zhang Yicheng Li Qian Lin Center for Statistical Science Department of Industrial Engineering Tsinghua University Beijing China

In the misspecified spectral algorithms problem, researchers usually assume the underground true function f*ρ ∈ [ℌ]s, a less-smooth interpolation space of a reproducing kernel Hilbert space (RKHS) ℌ for some s ∈ (0, 1). The existing minimax optimal results require ||f*ρ||L∞ < ∞ which implicitly requires s > α0 where α0 ∈ (0, 1) is the embedding index, a constant depending on ℌ. Whether the spectral algorithms are optimal for all s ∈ (0, 1) is an outstanding problem lasting for years. In this paper, we show that spectral algorithms are minimax optimal for any α0 - 1/β < s < 1, where β is the eigenvalue decay rate of ℌ. We also give several classes of RKHSs whose embedding index satisfies α0 = 1/β. Thus, the spectral algorithms are minimax optimal for all s ∈ (0, 1) on these RKHSs.

关键词： kernel methods spectral algorithms misspecified reproducing kernel Hilbert space minimax optimality

来源：评论

学校读者我要写书评

暂无评论

Online algorithms for spectral Hypergraph Sparsification 25th

Online Algorithms for Spectral Hypergraph Sparsification

引用

25th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Soma, Tasuku Tung, Kam Chuen Yoshida, Yuichi Inst Stat Math Tokyo Japan Univ Waterloo Waterloo ON Canada Natl Inst Informat Tokyo Japan

ISBN: (纸本)9783031598340;9783031598357

We provide the first online algorithm for spectral hypergraph sparsification. In the online setting, hyperedges with positive weights are arriving in a stream, and upon the arrival of each hyperedge, we must irrevocably decide whether or not to include it in the sparsifier. Our algorithm produces an (epsilon, delta)-spectral sparsifier with multiplicative error e and additive error delta that has O(epsilon(-2) n log n log r log(1+ epsilon W/delta n)) hyperedges with high probability, where epsilon, delta is an element of (0, 1), n is the number of nodes, r is the rank of the hypergraph, and W is the sum of edge weights. The space complexity of our algorithm is O(n(2)), while previous algorithms required space complexity Omega(m), where m is the number of hyperedges. This provides an exponential improvement in the space complexity since m can be exponential in n.

关键词： Online algorithms Hypergraph Sparsification spectral algorithms Generic Chaining

来源：评论

学校读者我要写书评

暂无评论

algorithms for minclique scheduling problems

引用

DISCRETE APPLIED MATHEMATICS 1997年第1-2期72卷 115-139页

作者： Jurisch, B Kubiak, W Jozefowska, J MEM UNIV NEWFOUNDLAND FAC BUSINESS ADMST JOHNSNF A1C 5S7CANADA POZNAN TECH UNIV INST COMP SCIPL-60965 POZNANPOLAND

We consider a family of well-known scheduling problems that reduce to the problem of finding a minimum weighted clique in a complete weighted graph with negative weights and self-loops allowed. We present a uniform algorithmic approach to finding optimal as well as suboptimal solutions for these problems. Also, we report results of computational tests for suboptimal algorithms developed in the paper.

关键词： single/multiple machine scheduling minimum weighted clique dynamic programming spectral algorithms tabu search

来源：评论

学校读者我要写书评

暂无评论

Tensor Train spectral Method for Learning of Hidden Markov Models (HMM)

引用

COMPUTATIONAL METHODS IN APPLIED MATHEMATICS 2019年第1期19卷 93-99页

作者： Kuznetsov, Maxim A. Oseledets, Ivan, V Skolkovo Inst Sci & Technol Skolkovo Innovat Ctr Moscow Moscow 143025 Russia

We propose a new algorithm for spectral learning of Hidden Markov Models (HMM). In contrast to the standard approach, we do not estimate the parameters of the HMM directly, but construct an estimate for the joint probability distribution. The idea is based on the representation of a joint probability distribution as an N-th-order tensor with low ranks represented in the tensor train (TT) format. Using TT-format, we get an approximation by minimizing the Frobenius distance between the empirical joint probability distribution and tensors with low TT-ranks with core tensors normalization constraints. We propose an algorithm for the solution of the optimization problem that is based on the alternating least squares (ALS) approach and develop its fast version for sparse tensors. The order of the tensor d is a parameter of our algorithm. We have compared the performance of our algorithm with the existing algorithm by Hsu, Kakade and Zhang proposed in 2009 and found that it is much more robust if the number of hidden states is overestimated.

关键词： Multilinear Algebra Tensor Train Decomposition Alternating Least Squares (ALS) Hidden Markov Models (HMM) spectral algorithms

来源：评论

学校读者我要写书评

暂无评论

Detection Thresholds in Very Sparse Matrix Completion

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2023年第5期23卷 1619-1743页

作者： Bordenave, Charles Coste, Simon Nadakuditi, Raj Rao Aix Marseille Univ Inst Math Marseille 39 Rue F Joliot Curie F-13453 Marseille 13 France ENS PSL Dept Informat 45 Rue Ulm F-75005 Paris France Univ Michigan Dept EECS 1301 Beal Ave Ann Arbor MI 48109 USA

We study the matrix completion problem: an underlying m x n matrix P is low rank, with incoherent singular vectors, and a random m x n matrix A is equal to P on a (uniformly) random subset of entries of size dn. All other entries of A are equal to zero. The goal is to retrieve information on P from the observation of A. Let A(1) be the random matrix where each entry of A is multiplied by an independent (0, 1)-Bernoulli random variable with parameter 1/2. This paper is about when, how and why the non-Hermitian eigen-spectra of the matrices A(1) (A - A(1))* and (A - A(1))*A(1) captures more of the relevant information about the principal component structure of A than the eigen-spectra of AA* and A*A. We show that the eigenvalues of the asymmetric matrices A (A - A(1))* and (A - A(1))* A(1) with modulus greater than a detection threshold are asymptotically equal to the eigenvalues of P P* and P* P and that the associated eigenvectors are aligned as well. The central surprise is that by intentionally inducing asymmetry and additional randomness via the A(1) matrix, we can extract more information than if we had worked with the singular value decomposition (SVD) of A. The associated detection threshold is asymptotically exact and is non-universal since it explicitly depends on the element-wise distribution of the underlying matrix P. We show that reliable, statistically optimal but not perfect matrix recovery, via a universal data-driven algorithm, is possible above this detection threshold using the information extracted from the asymmetric eigen-decompositions. Averaging the left and right eigenvectors provably improves estimation accuracy but not the detection threshold. Our results encompass the very sparse regime where d is of order 1 where matrix completion via the SVD of A fails or produces unreliable recovery. We define another variant of this asymmetric principal component analysis procedure that bypasses the randomization step and has a detection threshold that

关键词： Matrix completion Sparse random graphs Eigenvalues spectral algorithms Non-Hermitian matrices

来源：评论

学校读者我要写书评

暂无评论

Community Detection and Stochastic Block Models: Recent Developments

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2018年第1/2期18卷 1-170页

作者： Abbe, Emmanuel Princeton Univ Program Appl & Computat Math Princeton NJ 08544 USA Princeton Univ Dept Elect Engn Princeton NJ 08544 USA

The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences. This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds. The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.

关键词： Community detection clustering stochastic block models random graphs unsupervised learning spectral algorithms computational gaps network data analysis

来源：评论

学校读者我要写书评

暂无评论

On R-linear convergence analysis for a class of gradient methods

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2022年第1期81卷 161-177页

作者： Huang, Na China Agr Univ Coll Sci Dept Appl Math Beijing 100083 Peoples R China

Gradient method is a simple optimization approach using minus gradient of the objective function as a search direction. Its efficiency highly relies on the choices of the stepsize. In this paper, the convergence behavior of a class of gradient methods, where the stepsize has an important property introduced in (Dai in Optimization 52:395-415, 2003), is analyzed. Our analysis is focused on minimization on strictly convex quadratic functions. We establish the R-linear convergence and derive an estimate for the R-factor. Specifically, if the stepsize can be expressed as a collection of Rayleigh quotient of the inverse Hessian matrix, we are able to show that these methods converge R-linearly and their R-factors are bounded above by 1 - 1 1/x, where x is the associated condition number. Preliminary numerical results demonstrate the tightness of our estimate of the R-factor.

关键词： Quadratic optimization Gradient methods spectral algorithms R-linear convergence analysis R-factor

来源：评论

学校读者我要写书评

暂无评论

Ranking and synchronization from pairwise measurements via SVD

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2021年第1期22卷 1-63页

作者： d'Aspremont, Alexandre Cucuringu, Mihai Tyagi, Hemant CNRS Paris France Ecole Normale Super Paris France Univ Oxford Dept Stat Alan Turing Inst London England Univ Oxford Math Inst Alan Turing Inst London England Univ Lille INRIA CNRS UMR 8524Lab Paul Painleve F-59000 Lille France

Given a measurement graph G = (V, E) and an unknown signal r is an element of R-n, we investigate algorithms for recovering r from pairwise measurements of the form r(i) - r(j);{i, j} is an element of E. This problem arises in a variety of applications, such as ranking teams in sports data and time synchronization of distributed networks. Framed in the context of ranking, the task is to recover the ranking of n teams (induced by r) given a small subset of noisy pairwise rank offsets. We propose a simple SVD-based algorithmic pipeline for both the problem of time synchronization and ranking. We provide a detailed theoretical analysis in terms of robustness against both sampling sparsity and noise perturbations with outliers, using results from matrix perturbation and random matrix theory. Our theoretical findings are complemented by a detailed set of numerical experiments on both synthetic and real data, showcasing the competitiveness of our proposed algorithms with other state-of-the-art methods.

关键词： ranking angular synchronization spectral algorithms matrix perturbation theory singular value decomposition random matrix theory low-rank matrix completion

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：