  Using machine learning to solve combinatorial optimization (CO) problems is
challenging, especially when the data is unlabeled. This work proposes an
unsupervised learning framework for CO problems. Our framework follows a
standard relaxation-plus-rounding approach and adopts neural networks to
parameterize the relaxed solutions so that simple back-propagation can train
the model end-to-end. Our key contribution is the observation that if the
relaxed objective satisfies entry-wise concavity, a low optimization loss
guarantees the quality of the final integral solutions. This observation
significantly broadens the applicability of the previous framework inspired by
Erdos' probabilistic method. In particular, this observation can guide the
design of objective models in applications where the objectives are not given
explicitly while requiring being modeled in prior. We evaluate our framework by
solving a synthetic graph optimization problem, and two real-world applications
including resource allocation in circuit design and approximate computing. Our
framework largely outperforms the baselines based on na\"{i}ve relaxation,
reinforcement learning, and Gumbel-softmax tricks.
