Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases (Extended Abstract)

摘要

We revisit the problem of estimating k linear regressors in d dimensions from samples affected by self-selection bias under the maximum selection rule. Our main result is an algorithm with sample complexity O(d)·poly(k,1/ε) and running time poly(d,k,1/ε)+(klog k)^O(k) for recovering the regressors up to joint squared error ε^2. The key ingredient is the first local-convergence algorithm for the maximum self-selection model. Our approach reduces self-selection to estimation from coarse observations, where the learner observes only the cell of a partition containing the latent sample. The self-selection reduction induces a structured non-convex partition. We prove that this partition preserves enough information locally and that the resulting negative log-likelihood is locally convex around the true parameters. These two geometric properties allow projected stochastic gradient descent, initialized from an existing warm start, to obtain the stated end-to-end guarantee.