Speaker: Mark Sellke (Harvard)

Title: : Algorithmic threshold for perceptron models

Abstract:

We consider the problem of efficiently optimizing random (spherical or Ising) perceptron models with bounded Lipschitz activations. We focus on a class of algorithms with Lipschitz dependence on the disorder: this includes constant-order methods such as gradient descent, Langevin dynamics, and AMP on dimension-free time-scales. Our main result exactly characterizes the optimal value ALG such algorithms can attain in terms of a one-dimensional stochastic control problem. Qualitatively, ALG is the largest value whose level set contains a certain "dense solution cluster." Quantitatively, this characterization yields both improved algorithms and hardness results for a variety of asymptotic regimes, which are sharp up to absolute constant factors. Joint work (in progress) with Brice Huang and Nike Sun.