We consider a class of parametric regression problems where the parameter of interest is observed through random nonlinear functions with a difference of convex(DC) form. This model describes a broad subset of nonlinear regression problems that includes familiar special cases such as phase retrieval/quadratic regression and blind deconvolution/bilinear regression. Given the DC decomposition of the observation functions as well as an approximate solution, we formulate a convex program as an estimator that operates in the natural space of the signal. Our approach is computationally superior to the methods based on semidefinite/sum-of-squares relaxation—tailored for polynomial observation functions—and can compete with the non-convex methods studied in special regression problems. Furthermore, under mild moment assumptions, we derive the sample complexity of the proposed convex estimator using a PAC-Bayesian argument. We instantiate our results with bilinear regression with Gaussian factors and provide a method for constructing the required initial approximate solution.