We study cold atoms in an optical lattice with synthetic spin-orbit coupling in the Mott-insulator regime. We calculate the parameters of the corresponding tight-binding model using Peierls substitution and "localized Wannier states method" and derive the low-energy spin Hamiltonian for bosons and fermions. The spin Hamiltonian is a combination of Heisenberg model, quantum compass model and Dzyaloshinskii-Moriya interactions and it has a rich classical phase diagram with collinear, spiral and vortex phases. We discuss the state of the art of experiments to realize and detect magnetic orderings in strongly correlated optical lattices.