Research map / Learning theory and algorithms / Sample complexity

Efficient Algorithms for Non-gaussian Single Index Models with Generative Priors

AAAI 2024 · Learning theory and algorithms › Sample complexity · approach: Minimax estimation rates · 3 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes projected gradient descent and projected power methods, built on first- and second-order Stein's identities with score-function-valued sensing vectors, to recover signals in a generative model's range from single index model measurements with non-Gaussian sensing vectors.

Problem

High-dimensional single index models with non-Gaussian sensing vectors and unknown differentiable link functions, where the signal lies in the range of a Lipschitz generative model; prior guarantees were for global optima or Gaussian sensing vectors.

Approach

Uses first- and second-order Stein's identities with the score function of the sensing vector density, so that the truncated score-function-based estimates are optimized over the generative range via projected gradient descent (including a non-iterative variant) and a projected power method, with near-optimal statistical guarantees.

Key results

• On MNIST with first-order link (17), the score-function non-iterative estimator (1st-S) outperforms the sensing-vector version (1st-A) across m in {100,...,500} for Gamma and Rayleigh sensing vectors.
• On MNIST with second-order links (19) and (20), the projected power method on score functions (2nd-S) gives significantly higher cosine similarity than 2nd-A.
• Theory gives error bound sqrt(k log(Lr/δ)/m) for projected gradient descent and projected power method, implying roughly O(k/ε² log L) measurements for ε-accurate recovery.

Measured effects reported in the paper

Surprising findings

• A single non-iterative projection step (with zero initialization) suffices to reach the near-optimal statistical rate for first-order links.

Limitations

• Assumes the projection onto the generative range can be computed accurately, approximated in practice by gradient descent.
• Second-order guarantees require a nonzero initial correlation c0 > 0 with the true signal.
• Experiments limited to MNIST (main text) with 10 test images and synthetic link functions and noise.

Experimental setup

Datasets: MNIST CelebA

Benchmarks: MNIST CelebA

Metrics: cosine similarity

Baselines: 1st-A (non-iterative estimator with sensing vectors directly) 2nd-A (projected power method on sensing vectors directly)

Builds on: Wei, Yang, and Wang 2019 (SIMs with Stein's identity and generative priors) Bora et al. 2017 (compressed sensing with generative priors) Yang, Balasubramanian, and Liu 2017 (thresholded score function estimators) Liu et al. 2022 (projected power method for phase retrieval)

Closest papers by meaning

• Non-Iterative Recovery From Nonlinear Observations Using Generative Models (CVPR 2022 · similarity 0.90)
• The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models (NeurIPS 2025 · similarity 0.89)
• Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.86)
• Sparse Bayesian Generative Modeling for Compressive Sensing (NeurIPS 2024 · similarity 0.85)
• Information Theoretic Learning for Diffusion Models with Warm Start (NeurIPS 2025 · similarity 0.85)
• Robustly Learning Monotone Single-Index Models (NeurIPS 2025 · similarity 0.85)