Is it fair to say that most of the 'success' of deep learning comes from the fact we do not need to optimize exactly? There seems to be two types of research papers in optimization:


*

*papers that characterize the solution of some optimization problem extremely precisely (existence, uniqueness, mixed/continuous/discrete, closed/compact/open, convex/non-convex/saddle...), and then design an algorithm that solves for the exact minimizer of those optimization problems with guaranteed convergence rate, etc. 

*papers that do not care too much about the structure of the optimization problem, just use some popular method (GD, SGD, SGD + momentum, etc.) to update some parameters. 
It seems that almost all the deep learning, supervised learning, neural network, autonomous driving applications fall into the second category. No effort is made what so ever to characterize these problems, and when challenged, just say "the problem is highly non-convex and optimization is hard". For example, the ADAM paper is well known to be wrong. And multiple papers have said that SGD + Nesterov + Momentum + ... doesn't really work. 
But in practice works pretty well!
I am arguing with someone whether if it is justified to say that all of the success of deep learning comes from the fact we do not care about solving a problem precisely, or even care about whether if our solution is good. The point is, the moment you toss out rigor, and rigor doesn't even seem to matter, your problem becomes pretty easy to solve. It is easy to achieve success on easy problems.
Is this assertion justified?
 A: I don't think this is a useful viewpoint. 
Computation with real numbers is, in a technical sense, impossible (most real numbers are uncomputable). However most computer programs use and manipulate (representations of) real numbers. In most cases, these are imperfect floating point numbers. Therefore is all the success of computing derived from the fact that we don't care about real numbers and/or how precise our floating point computations are?
This is kind of an absurd conclusion. The success of computing comes from a large number of factors, such as the ubiquity of computers, the scalability of software, the usefulness of automation, the rise of the internet, etc. To blame it all on the imperfection of floating point numbers seems... quite forced.
Likewise, it probably makes more sense to blame the success of neural networks on years of careful research and engineering effort rather than optimizers which don't necessarily arrive at the global minimum.
A: 
when challenged, just say "the problem is highly non-convex and optimization is hard"

However handwavy that may sound, that is actually very precise description of the problem. When facing such a problem, you have two options: Try hard to come up with some convex relaxation to (at least a part of) the problem where you can guarantee desirable properties like convergence and optimality, or go ahead with the tools you have and see how far it gets you.
In the case of deep learning, simple tools like SGD got us surprisingly far. Is that a bad research? I don't think so, for two reasons:

*

*Deep learning research has produced large number of experimental results in a particular type of high-dimensional non-convex optimization, and these experimental observations inspire research of theoretical foundations, such as [1]. This is not a unique to DL—I dare to say in most science fields experimental observations come first and later  theories are proposed that explain these observations.


*Deep learning research has produced large number of practical applications, pushing forward the state-of-the-art of tasks that computers can do. Solving actual problems is one of the most important goals of research. Problems like driving cars and diagnosing diseases are by no means easy problems, and researchers very much care about whether the solutions are good. However, "good" is measured in different terms than in other fields. If a solution works in actual real-life scenario and solves an actual problem, it is only fair to consider it good.
Finally, to answer your question in the title,

Is it fair to say that most of the 'success' of deep learning comes from the fact we do not need to optimize exactly?

It is wrong. The most success of DL comes from having vast amounts of data, vast computational power, and simple but very general models and methods. The fact that we can get good solutions with simple SGD is rather an implication of these conditions.

[1]: Choromanska, Anna, et al. "The loss surfaces of multilayer networks." Artificial intelligence and statistics. 2015.
