PaperlayerView exact revision on arXiv

Source-linked AI summary

Statistical Algorithms and a Lower Bound for Detecting Planted Clique

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao

arXiv:1201.1214v6cs.CCcs.DS

TL;DR

The paper addresses the difficulty of proving computational lower bounds for problems over distributions by introducing a statistical-query framework that captures many sample-based algorithms. It applies the framework to planted biclique and dense-subgraph detection, obtaining nearly optimal lower bounds for planted structures of size O(n^1/2−δ).

  • Problem

    Computational lower bounds for problems over samples from unknown distributions are difficult, despite established methods for estimating sample complexity.

  • Method

    The paper develops a statistical-query framework, including SQ and 1-bit sampling oracles, and extends SQ-learning ideas to arbitrary computational problems over distributions.

  • Results

    For k ≤ n^1/2−δ, solving distributional planted k-biclique requires at least n^Ω(log r) queries to VSTAT(n^2/(rk^2)); these bounds also apply to distinguishing planted biclique from uniform distributions.

  • Takeaways & Limitations

    The lower bounds provide concrete evidence supporting hardness assumptions used in related problems and cryptographic applications.

  • Takeaways & Limitations

    The lower bound cannot be superpolynomial against STAT(k/n), because a degree-based algorithm operates at tolerance Ω(k/n), corresponding to O(n^2/k^2) samples.

Abstract

from arXiv · show

We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle. For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution, rather than directly accessing samples. Most natural algorithms of interest in theory and in practice, e.g., moments-based methods, local search, standard iterative methods for convex optimization, MCMC and simulated annealing can be implemented in this framework. Our framework is based on, and generalizes, the statistical query model in learning theory (Kearns, 1998). Our main application is a nearly optimal lower bound on the complexity of any statistical query algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size $O(n^{1/2-δ})$ for any constant $δ> 0$. The assumed hardness of variants of these problems has been used to prove hardness of several other problems and as a guarantee for security in cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.

1 Introduction

The paper introduces an oracle-based framework for unconditional computational lower bounds over distributions and applies it to planted biclique detection. The framework covers many sample-based algorithms and yields nearly optimal bounds below the planted-clique threshold.

  • Motivation: Computational lower bounds for problems over samples from unknown distributions are substantially harder to prove than sample-complexity bounds.Traditional lower bounds rely on reductions and distributions generating instances of conjecturally intractable problems.
  • Framework: The framework analyzes algorithms that access an unknown distribution through statistical queries estimating expectations rather than directly accessing samples.It also supports 1-bit sampling algorithms, whose oracle returns a Boolean function's value on a fresh random sample.
  • Framework: Statistical access captures many practical and theoretical methods, including EM, local search, MCMC, simulated annealing, convex optimization, k-means, PCA, ICA, Naïve Bayes, and neural networks.Gradient descent can use sufficiently accurate coordinate estimates of the expected gradient, enabling implementation through the framework's oracles.
  • Framework: The model generalizes statistical query learning to arbitrary computational problems over distributions and defines a problem parameter that lower-bounds SQ complexity.The lower-bound techniques adapt SQ-learning methods while departing from them in ways needed for the broader setting and applications.
  • Planted biclique application: Planted biclique detection has a quasipolynomial algorithm for k ≥ 2 log n, while no polynomial-time algorithm is known below the Ω(√n) threshold.The quasipolynomial method enumerates subsets of size 2 log n, identifies clique subsets, and takes their common neighbors.

2 Definitions and Overview

The paper generalizes statistical-query lower bounds to search problems over arbitrary distribution classes, introducing statistical dimension and applying it to planted biclique detection. It obtains nearly tight query lower bounds for planted bicliques below the square-root regime, while identifying polynomial-time or sample-based upper bounds at the corresponding scale.

  • Definitions and Overview: The framework treats distributional search problems by defining valid solutions for each input distribution and measuring the complexity of solving them through statistical access.The distributional planted k-biclique problem asks for the unknown planted subset S from samples drawn from D_S.
  • Definitions and Overview: Statistical algorithms access distributions through expectation estimates or 1-bit responses, encompassing many common optimization, sampling, and learning procedures.The framework includes a stronger VSTAT oracle and also covers algorithms using a 1-bit sampling oracle.
  • Statistical Dimension: The statistical dimension extends SQ dimension to arbitrary distribution sets, uses average rather than pairwise correlations, and yields bounds for VSTAT without quadratic parameter loss.Its analysis is based on correlations between normalized density differences such as (D′(x) − D(x))/D(x).
  • Statistical Dimension: Any SQ algorithm requires at least d VSTAT(1/(3γ̄)) queries when the statistical dimension is d, with refinements supporting randomized and 1-bit sampling lower bounds.The refined notion also shows that t samples of 1-STAT can be simulated with VSTAT(O(t)) with high probability.
  • Applications to the Planted Biclique Problem: For constant δ > 0 and k ≤ n^1/2−δ, solving distributional planted biclique requires n^Ω(log r) queries to VSTAT(n^2/(rk^2)), including n^Ω(log n) queries to VSTAT(n^(2−δ)/k^2).The same lower bound applies to distinguishing a planted biclique distribution from the uniform distribution.
  • Applications to the Planted Biclique Problem: The lower bounds are essentially tight: S can be recovered with n VSTAT(16n^2/k^2) queries, while n^O(log n) queries to VSTAT(25n/k) suffice for k ≥ log n.For 1-bit sampling algorithms, the lower bound is Ω(n^2/k^2) fresh samples, matching the easy detection sample scale up to logarithmic factors.

3 Lower Bounds from Statistical Dimension

The paper derives unconditional lower bounds for statistical algorithms from statistical dimension, an information-theoretic measure based on correlations among distributions. The framework also transfers bounds between SQ and 1-bit sampling oracles.

  • Statistical dimension: Statistical dimension with average correlation lower-bounds deterministic algorithms using VSTAT(1/(3γ̄)).The parameter is defined through a reference distribution and a large family of distributions that remain difficult for every solution.
  • General lower bound: Randomized SQ algorithms solving with success probability α > η require at least (α − η)d/(1 − η) VSTAT queries.The proof uses a distribution over inputs and Yao’s minimax principle to extend the deterministic argument.
  • Pairwise correlations: Pairwise statistical dimension gives a simpler correlation-based lower bound and is related to SQ-DIM from learning theory.The paper introduces this notion for applications where pairwise correlations suffice.
  • Pairwise correlations: SQ algorithms require at least mγ′/(β − γ) queries to STAT(√(γ + γ′)) or VSTAT(1/(3(γ + γ′))) under the pairwise-dimension conditions.A corresponding specialization requires at least m^(1/3)/2 queries to VSTAT(m^(2/3)/3) or STAT(m^(-1/3)).
  • 1-bit sampling: Lower bounds extend to 1-bit sampling through oracle simulations between 1-STAT and VSTAT.A 1-STAT algorithm using m samples can be simulated with VSTAT(m/δ^2) while losing at most δ success probability; conversely, VSTAT(t) queries can be answered using O(qt · log(q/δ)) 1-STAT calls.

4 Warm-up: MAX-XOR-SAT

The warm-up analyzes distributional MAX-XOR-SAT, showing that its statistical dimension is exponential and therefore ruling out efficient statistical-query solutions at the stated approximation level.

  • Motivation: Local search heuristics motivate studying whether distributional MAX-XOR-SAT is hard for algorithms that improve assignments by variable flips.The paper presents this as evidence supporting hardness of locally improving approaches.
  • Connection to learning: The bound restates the known SQ lower bound for learning parities, since parity learning is a special case of distributional MAX-XOR-SAT.The correspondence connects the warm-up to earlier SQ learning results.
  • Problem formulation: MAX-XOR-SAT asks for an assignment maximizing the fraction of satisfied clauses under an unknown clause distribution.The approximate version accepts assignments within additive error ε of the optimum.
  • Lower bound: 2^(n/3) − 1 queries to STAT(2^(-n/3)) are required by any SQ algorithm for the stated approximation problem.This follows from the statistical-dimension bound through the paper’s general reduction.
  • Statistical dimension: 2^n − 1 is a lower bound on the statistical dimension of (1/2 − δ)-approximate MAX-XOR-SAT.The construction uses distributions indexed by assignments and pairwise correlation parameters (γ, β) = (0, 1).

5 Planted Biclique and Densest Subgraph

The paper applies statistical dimension to planted biclique and planted densest-subgraph detection. For planted size k ≤ n^(1/2−δ), it obtains strong SQ and 1-bit sampling lower bounds, matching known upper bounds in the biclique setting.

  • Planted biclique: The planted k-biclique distribution mixes uniform vectors with probability 1 − k/n and vectors whose k coordinates in S are fixed to 1 with probability k/n.The task is to recover the unknown k-subset S from random samples.
  • Planted biclique: For δ ≥ 1/log n and k ≤ n^(1/2−δ), the biclique problem has SDA at least n^(2ℓδ)/3 at correlation threshold 2^(ℓ+1)k^2/n^2.This holds for every integer ℓ ≤ k and also for the corresponding decision formulation relative to the uniform distribution.
  • Planted biclique: For constant δ > 0 and k ≤ n^(1/2−δ), some t = n^Ω(log r) queries to VSTAT(n^2/(rk^2)) are required for decision success 1/2 + 1/t.The paper states that these bounds match known upper bounds.
  • Planted biclique: Any 1-bit sampling algorithm succeeding with probability at least 2/3 requires Ω(n^2/k^2) queries to 1-STAT for the planted biclique decision problem.The reduction simulates such an algorithm using VSTAT and contradicts the planted-biclique SQ lower bound for suitable m.
  • Planted densest subgraph: For planted densest subgraphs, the reference distribution is a product of n Bernoulli(q) variables, with planted coordinates having bias p.The biclique case is recovered at p = 1 and q = 1/2.
  • Planted densest subgraph: When q = 1/2 and p = 1/2 + α, the lower bound becomes n^Ω(ℓ) against VSTAT(n^2/(48ℓα^2k^2)) for ℓ ≤ 1/(4α^2).The same lower-bound framework also applies to the decision version.
  • Planted densest subgraph: For p = 1/2 + 1/n^c and k ≤ n^(1/2−δ), 1-bit sampling requires Ω((n^(2+2c))/k^2) queries for decision success at least 2/3.This is stated for constants c, δ > 0.

6 Applications to Statistical Query Learning

The paper extends statistical-query lower bounds to learning and shows that SQ-DIM-based bounds arise as special cases of its framework. It also derives related lower bounds for weak learning and 1-bit sampling algorithms.

  • Framework connection: The framework generalizes statistical query lower bounds from decision problems to learning problems.The paper explicitly states that its lower bounds generalize SQ-DIM-based results and strengthen them in learning settings.
  • SQ-DIM reduction: SQ-DIM(C, D′) = d′ yields statistical dimension at least d′ for distinguishing labeled examples from random labels.The reference distribution is D′ × {1/2, 1/2}, where points follow D′ and labels are unbiased random bits.
  • SQ learning: Any SQ learner with error ǫ < 1/2 −1/(2d′1/3) requires at least d′1/3/2 −1 queries to STAT(1/d′1/3).This is the stated distribution-specific learning lower bound attributed to Yang (2005).
  • Weak learning: Any SQ learner with error ǫ < 1/2 −1/d′1/3 requires at least 2d′1/3 −1 queries to STAT(1/d′1/3).The bound follows by converting weak learning into a decision procedure that distinguishes concept-labeled examples from random labels.
  • 1-bit sampling: Any 1-bit sampling algorithm achieving error ǫ = 1/2−1/d′1/4 with probability at least 2/3 requires Ω(d′) queries to 1-STAT.The paper relates 1-STAT to the Honest SQ oracle and notes that the resulting bound is stronger in most cases than the cited Ω(d′/ log d′) result.
  • Scope of the framework: The learning lower-bound variant separates tolerance from query count and also captures sample complexity through average correlations and VSTAT.The paper states that these features are relevant to attribute-efficient learning and can imply bounds for stronger oracles through reductions.

A Average-case vs Distributional Planted Bipartite Clique

This appendix establishes reductions between average-case planted biclique recovery and the distributional biclique problem. Each reduction uses randomized replacement of planted rows or columns, with controlled running-time and success-probability losses.

  • Problem correspondence: The distributional biclique problem gives n independent samples from DS and asks the algorithm to recover an unknown planted set S of size k.Samples can be represented as adjacency vectors, connecting the distributional problem to planted bipartite graphs.
  • APBC to DPBC: An APBC solver gives a DPBC solver with T(n, k) = O(nkT′(n, k/2)) and p(n, k) = p′(n, k/2) −n2−Ω(k).The construction runs the APBC algorithm across intermediate matrices and verifies candidate bicliques before returning a planted set.
  • From samples to matrices: A planted biclique in the sample matrix has left size k′ distributed as B(n, k/n), and k/2 ≤ k′ ≤ 2k with probability at least 1 −2e−k/8.A random column permutation makes the planted set uniformly distributed among coordinates before the reduction proceeds.
  • Row reduction: Replacing planted rows by random vectors one at a time produces an intermediate matrix with a k × k biclique, yielding an APBC instance.Conditioned on the number of remaining planted rows, each intermediate matrix has the corresponding average-case planted biclique distribution.
  • Correctness: The recovery procedure succeeds because, conditioned on the reduction event, any output k × k biclique must use the planted right side.For the reverse direction, an additional nonplanted vertex joins all vertices in the planted left side with probability at most n · 2−k.
  • Unknown planted size: When k′ is unknown, testing k1 = k −1, k −2, . . . , k/2 gives running time O(nkT′(n, k/2)) and success probability p′(n, k/2) −n2−Ω(k).The analysis assumes that finding smaller planted bicliques is no easier than finding larger ones.
  • DPBC to APBC: A DPBC solver gives an APBC solver with T′(n, k′) = O(nk′T(n, k′/2)) and p′(n, k′) ≥p(n, k′/2) −n2Ω(−k′).The reverse reduction replaces planted columns and reconstructs the full planted right-side set from the surviving biclique.
Loading 1201.1214v6…