数据结构与算法研究快报

用 AI 跟踪日新月异的数据结构与算法领域进展

通过功率迭代方法进行局部微分私有图集

我们提出了一个局部差分私有图聚类算法。 以前的工作已经探讨了这个问题,包括将光谱聚类应用于通过随机响应算法生成的图形的方法。 但是,这些方法只有在隐私预算为Ω(log n)时才能达到准确的结果,这不适合许多实际应用。 作为回应,我们提出了一个基于功率迭代方法的交互式算法。 鉴于最大的特征向量常数引入的噪声可能很大,我们采用了一种技术来消除这种常数。 因此,我们的算法在图形优砥如缀且 Ω̃(√(n) 的最小度)时,通过恒定的隐私预算获得本地差分隐私。 相比之下,虽然随机响应已被证明在相同的最小度条件下产生准确的结果,但它仅限于从随机块模型生成的图形。 我们进行实验以证明我们的方法优于应用于随机反应结果的光谱聚类。

数据结构与算法 社会与信息网络

Nonlinear Laplacians: Tunable principal component analysis under directional prior information

We introduce a new family of algorithms for detecting and estimating a rank-one signal from a noisy observation under prior information about that signal's direction, focusing on examples where the signal is known to have entries biased to be positive. Given a matrix observation 𝐘, our algorithms construct a nonlinear Laplacian, another matrix of the form 𝐘 + diag(σ(𝐘1)) for a nonlinear σ: ℝ→ℝ, and examine the top eigenvalue and eigenvector of this matrix. When 𝐘 is the (suitably normalized) adjacency matrix of a graph, our approach gives a class of algorithms that search for unusually dense subgraphs by computing a spectrum of the graph "deformed" by the degree profile 𝐘1. We study the performance of such algorithms compared to direct spectral algorithms (the case σ = 0) on models of sparse principal component analysis with biased signals, including the Gaussian planted submatrix problem. For such models, we rigorously characterize the critical threshold strength of rank-one signal, as a function of the nonlinearity σ, at which an outlier eigenvalue appears in the spectrum of a nonlinear Laplacian. While identifying the σ that minimizes this critical signal strength in closed form seems intractable, we explore three approaches to design σ numerically: exhaustively searching over simple classes of σ, learning σ from datasets of problem instances, and tuning σ using black-box optimization of the critical signal strength. We find both theoretically and empirically that, if σ is chosen appropriately, then nonlinear Laplacian spectral algorithms substantially outperform direct spectral algorithms, while avoiding the complexity of broader classes of algorithms like approximate message passing or general first order methods.

机器学习 (统计) 数据结构与算法 机器学习

BOLT:用于跟踪矩阵函数估计的块-正态Lanczos

高效的矩阵跟踪估计对于可扩展的log-determinants、矩阵规范和分布差异的计算至关重要。 在许多大规模应用中,所涉及的矩阵太大,无法完全存储或访问,甚至使单个矩阵向量(mat-vec)产品不可行。 相反,通常只能访问限制索引集上的矩阵或本地化矩阵向量产品的小子块。 Hutch++实现了最佳的收敛率,但依赖于随机SVD并假设完全的mat-vec访问,因此很难在这些受限设置中应用。 我们提出了Block-Orthonormal Stochastic Lanczos Quadrature(BOLT),它将Hutch++的准确性与基于正畸块探针和Lanczos迭代的更简单的实现相匹配。 BOLT建立在Stochastic Lanczos Quadrature(SLQ)框架的基础上,该框架将随机探测与Krylov子空间方法相结合,以有效地近似矩阵函数的痕迹,并且在近平谱机制中比Hutch++表现更好。 为了解决内存限制和部分访问限制,我们引入了Subblock SLQ,这是BOLT的一个变体,仅在小主基子矩阵上运行。 因此,该框架产生了代理KL发散估计器和计算高斯人之间的Wasserstein-2距离的有效方法 - 两者都与低内存和部分访问机制兼容。 我们提供理论保证,并在一系列高维设置中展示强大的经验性能。

数值分析 数据结构与算法 机器学习

通过截断进行私人统计估计

我们引入了一种新的框架,用于通过数据截断进行微分私有(DP)统计估计,当数据支持不受限制时,解决DP估计中的一个关键挑战。 传统方法依赖于特定于问题的敏感性分析,限制了其适用性。 通过利用截断统计的技术,我们开发计算高效的DP估计器用于指数型家族分布,包括高斯均值和协方差估计,实现近乎最优的样本复杂性。 以前关于指数家庭的作品只考虑有界限或一维的家庭。 我们的方法通过截断减轻灵敏度,同时使用最大概率估计和DP随机梯度下降仔细纠正引入的偏置。 在此过程中,我们建立了改进的统一收敛保证,为指数家庭的可能性函数,这可能是独立的兴趣。 我们的结果通过截断的统计为DP算法设计提供了通用蓝图。

机器学习 密码学与安全 数据结构与算法

Lasso and Partially-Rotated Designs

We consider the sparse linear regression model 𝐲 = X β +𝐰, where X ∈ℝ^n × d is the design, β∈ℝ^d is a k-sparse secret, and 𝐰∼ N(0, I_n) is the noise. Given input X and 𝐲, the goal is to estimate β. In this setting, the Lasso estimate achieves prediction error O(k log d / γ n), where γ is the restricted eigenvalue (RE) constant of X with respect to support(β). In this paper, we introduce a new semirandom family of designs – which we call partially-rotated designs – for which the RE constant with respect to the secret is bounded away from zero even when a subset of the design columns are arbitrarily correlated among themselves. As an example of such a design, suppose we start with some arbitrary X, and then apply a random rotation to the columns of X indexed by support(β). Let λ_min be the smallest eigenvalue of 1/n X_support(β)^⊤ X_support(β), where X_support(β) is the restriction of X to the columns indexed by support(β). In this setting, our results imply that Lasso achieves prediction error O(k log d / λ_min n) with high probability. This prediction error bound is independent of the arbitrary columns of X not indexed by support(β), and is as good as if all of these columns were perfectly well-conditioned. Technically, our proof reduces to showing that matrices with a certain deterministic property – which we call restricted normalized orthogonality (RNO) – lead to RE constants that are independent of a subset of the matrix columns. This property is similar but incomparable with the restricted orthogonality condition of [CT05].

统计理论 数据结构与算法 机器学习 (统计)

Previous slideNext slide