Determining the starting point of gradient descent

Yes, for a general objective function, the starting point of gradient descent determines the ending point. This is complicating, gradient descent may get stuck in suboptimal local minima. What can we do about that:

• Convex optimization: Things are better if the objective is a convex function being optimized on a convex domain, namely, then any local minimum is also a global minimum. So gradient descent on a convex function won't get trapped in suboptimal local minima. Better yet, if the objective is strictly convex, then there is (at most) one global minimum. For these reasons, optimization-based methods are frequently formulated as convex optimizations when it is possible. Logistic regression for instance is a convex optimization problem.

• As Tarik said, a good meta-strategy is to do gradient descent multiple times from different random starting positions. This is sometimes called a "random restart" or "shotgun" gradient descent approach.

• Twists on the basic gradient descent idea can also be helpful in avoiding local minima. Stochastic gradient descent (SGD) (and similarly, simulated annealing) makes noisier steps. This noise has a cumulative effect like optimizing a smoothed version of the objective, hopefully smoothing over smaller valleys. Another idea is to add a momentum term to gradient descent or SGD, with the intention that momentum will allow the method to roll through and escape local minima.

• Finally, an interesting and practical attitude is simply to surrender and accept that gradient descent's solution may be suboptimal. A local minimum solution may yet be useful. For instance, if that solution represents trained weights for a neural network, what really counts is that the network generalizes and performs well on the test set, not that it is optimal on the training set.