  We formulate learning of a binary autoencoder as a biconvex optimization
problem which learns from the pairwise correlations between encoded and decoded
bits. Among all possible algorithms that use this information, ours finds the
autoencoder that reconstructs its inputs with worst-case optimal loss. The
optimal decoder is a single layer of artificial neurons, emerging entirely from
the minimax loss minimization, and with weights learned by convex optimization.
All this is reflected in competitive experimental results, demonstrating that
binary autoencoding can be done efficiently by conveying information in
pairwise correlations in an optimal fashion.
