U1. Topic Models: find better topic models — rigorous, practical relevant and efficient.
U2. Analyze EM for learning mixture models.
U3. The complexity of a learning a spherical Gaussian mixture with separation .
U4. Learn general Gaussian mixtures in time or prove a lower bound.
U5. Learn a mixture of spherical Gaussians in time , for any k.
Model fitting/agnostic unsupervised learning:
U6. ICA with arbitrary noise.
U7. k-means with noisy assumptions.
U8. Learn a mixture of arbitrary Gaussians with linearly independent means.
U9. Clustering from assumptions on the pairwise similarities.
U10. Give a probabilistic model for which k-means converges to the “right” clustering, possibly with some pre-processing.
P1. PAC-Learn an intersection of 2 halfspaces
P2. Learn DNF over nonproduct distributions with membership queries
P3. Learn DNF over the uniform distribution (on the Boolean hypercube) without membership queries.
P4. (Valiant) Learn decision lists of k out of n variables in polynomial-time, using examples.
P5. Agnostically learn intersections of halfspaces over logconcave distributions.
P6. (A. Blum) Learn a parity of k out of n variables.
S1. Prove a tight lower bound for planted k-SAT.
S2. Prove a lower bound for planted clique (not bipartite clique).
S3. (Montanari) Lower bound for finding a planted vector:
S4. Prove an exponential lower bound for learning a decision list of k variables using only examples.
O1. What learning algorithms are efficient when applied to a sequence of learning tasks? (multitask/transfer/lifelong learning)
O2. For what nonconvex optimization problems can we achieve near-optimal regret?
O3. What is the communication/space complexity of distributed/stream learning a halfspace?
O4. When does the multiplicative update method work (fail)?
O5. 2-player approximate-Nash with polynomial convergence.
E1. Computational theories of cortex.
E2. Non i.i.d. models of example distributions motivated by real-life learning.
E3. Give a class of distributions for which a deep neural net is provably effective with an algorithm that is close to one used in practice.
E4. Give a nonconvex optimization problem for which gradient descent fails but stochastic gradient descent succeeds.