Efficient computational methods with proven guarantees are needed to handle the complexity and nonlinearity of many real-world systems. Practitioners often develop heuristic algorithms for specific applications, but the theoretical foundations of these methods are not well understood, which limits their use in safety-critical systems. In this presentation, we will focus on addressing this issue for certain machine learning problems. We will examine methods for certifying the robustness of neural networks against adversarial inputs and investigate when simple local search algorithms can solve a class of nonlinear problems to global optimality. We will present our recent findings on these topics and provide examples of their application in tensor decomposition with outliers and video processing.