This paper introduces a new stochastic approximation (SA) algorithm, the randomized stochastic gradient (RSG) method, for solving nonlinear stochastic programming (SP) problems. The RSG method is designed to find an approximate stationary point of a nonlinear programming problem, and it achieves nearly optimal convergence rates when the problem is convex. The method is also modified to improve its large-deviation properties through a two-phase randomized stochastic gradient (2-RSG) method, which includes a post-optimization phase to evaluate a short list of solutions generated by multiple independent runs of the RSG method. This modification significantly enhances the reliability of the algorithm. The RSG method uses stochastic first-order information, obtained through a stochastic first-order oracle (SFO), to iteratively update the solution. The algorithm randomly selects a solution from the generated sequence of iterates, and it is shown that this solution satisfies a certain expected gradient norm bound after a specified number of iterations. For convex problems, the method also guarantees a bound on the expected objective function value difference from the optimal value. The 2-RSG method further improves the large-deviation properties by combining multiple runs of the RSG method and selecting the best solution from the resulting candidates. This approach allows for a tighter complexity bound when computing an $(\epsilon, \Lambda)$-solution, which is a point that satisfies a certain probability condition on the gradient norm. The paper also extends the RSG method to handle stochastic zeroth-order information, where only function values are available. This is achieved through a randomized stochastic gradient free (RSGF) method that uses a Gaussian smoothing technique to approximate the gradient. The RSGF method is shown to have a complexity bound that is nearly optimal for nonconvex problems and is also effective for convex problems. The theoretical analysis of the RSG and 2-RSG methods demonstrates their convergence properties and complexity bounds under various assumptions, including light-tail conditions on the stochastic first-order oracle. The results show that the RSG and 2-RSG methods are effective for solving a wide range of nonconvex and convex stochastic programming problems, with the 2-RSG method providing improved reliability and performance in terms of large-deviation properties.This paper introduces a new stochastic approximation (SA) algorithm, the randomized stochastic gradient (RSG) method, for solving nonlinear stochastic programming (SP) problems. The RSG method is designed to find an approximate stationary point of a nonlinear programming problem, and it achieves nearly optimal convergence rates when the problem is convex. The method is also modified to improve its large-deviation properties through a two-phase randomized stochastic gradient (2-RSG) method, which includes a post-optimization phase to evaluate a short list of solutions generated by multiple independent runs of the RSG method. This modification significantly enhances the reliability of the algorithm. The RSG method uses stochastic first-order information, obtained through a stochastic first-order oracle (SFO), to iteratively update the solution. The algorithm randomly selects a solution from the generated sequence of iterates, and it is shown that this solution satisfies a certain expected gradient norm bound after a specified number of iterations. For convex problems, the method also guarantees a bound on the expected objective function value difference from the optimal value. The 2-RSG method further improves the large-deviation properties by combining multiple runs of the RSG method and selecting the best solution from the resulting candidates. This approach allows for a tighter complexity bound when computing an $(\epsilon, \Lambda)$-solution, which is a point that satisfies a certain probability condition on the gradient norm. The paper also extends the RSG method to handle stochastic zeroth-order information, where only function values are available. This is achieved through a randomized stochastic gradient free (RSGF) method that uses a Gaussian smoothing technique to approximate the gradient. The RSGF method is shown to have a complexity bound that is nearly optimal for nonconvex problems and is also effective for convex problems. The theoretical analysis of the RSG and 2-RSG methods demonstrates their convergence properties and complexity bounds under various assumptions, including light-tail conditions on the stochastic first-order oracle. The results show that the RSG and 2-RSG methods are effective for solving a wide range of nonconvex and convex stochastic programming problems, with the 2-RSG method providing improved reliability and performance in terms of large-deviation properties.