Maximum likelihood estimators are often of limited practical use due to the\nintensive computation they require. We propose a family of alternative\nestimators that maximize a stochastic variation of the composite likelihood\nfunction. Each of the estimators resolve the computation-accuracy tradeoff\ndifferently, and taken together they span a continuous spectrum of\ncomputation-accuracy tradeoff resolutions. We prove the consistency of the\nestimators, provide formulas for their asymptotic variance, statistical\nrobustness, and computational complexity. We discuss experimental results in\nthe context of Boltzmann machines and conditional random fields. The\ntheoretical and experimental studies demonstrate the effectiveness of the\nestimators when the computational resources are insufficient. They also\ndemonstrate that in some cases reduced computational complexity is associated\nwith robustness thereby increasing statistical accuracy.\n