The gradient gives you the optimal improvement direction....if you have 10 positions the gradient of all 10 will point in different directions...so if you take a step after each point you'll zig zag arround a lot. You might even backtrack a bit. If you however take the average of all 10 and do a step you won't be optimal in regards to all points individually, but the path you'll take will be smoother.

So it depends on your dataset. Usually you want to have some smoothing because otherwise you won't converge that easily.

​

The same is true for your example....the center point might not be a good estimate of the surrounding. It could however be that it is close to the average and there isn't that big of a difference.

[deleted]

besides being extremely computationally expensive, how would one define the size of the volume? it's similar to the problem of defining a step size which oversteps when too large or takes forever when too small. likewise defining a very small volume might get us caught in local minima.

i guess this thought is similar to smoothing like another poster mentioned.

I suppose it is a bit closer to a secant method like BFGS, which approximates the Hessian required for a Newton step. In other words, these methods use a linear combination of adjacent gradient computations to estimate curvature, which enables more effective updates. The combination is not an average though, and also they integrate gradient computations over successive iterations rather than stopping at each iteration to compute a bunch within some volume.

I don't think your proposed volume-averaging has any theoretical utility as a convex optimizer, especially because there are much better well-known things to do with adjacent gradient computations. The closest common practice I can think of to averaging are GD+momentum type optimizers, which lowpass-filter the GD dynamic along its trajectory. These provide heuristic benefits in the context of nonconvex optimization.

Do you have any links about the volume-averaging or was it just a random thought? Also, make sure not to confuse "averaging gradients from different points in parameter space" with "averaging gradients from different sample losses at the same point in parameter space" (called "batching").

Since you're asking about theory, if you're optimizing a non-smooth convex function with a stochastic subgradient method, you usually require something like O(G^2/epsilon^2 + V/epsilon^2) iterations to get an epsilon accurate solution where G is a bound on the true subgradient norm and V is the variance of the estimator. If you use a batch size of B your variance is reduced by a factor of 1/B (under standard assumptions). So, if you run for T iterations your accuracy is roughly O(sqrt(G^2/T + V/(BT))). Often times in practice this bound is pessemistic, especially wrt B.

If your function is smooth, sometimes you can do better. Roughly you get a bound something like O(L/T + sqrt(V/T)) where L is the gradient's Lipschitz constant. Basically you can get a faster rate until you get close enough to the solution to be within the variance and at that point you have no choice but to average out the noise. It is usually the case that the variance term here dominates though even when you make efforts to reduce it. e.g., you need L >= sqrt(VT/B) for the smooth term to dominate, so B needs to be O(T).

There are a bunch of different variance reduction methods that can do better than simply averaging the gradients. There are some examples here https://www.cs.cmu.edu/~pradeepr/convexopt/Lecture_Slides/stochastic_optimization_methods.pdf that work when you are minimizing a function that is the sum of convex functions. They can sometimes be more expensive than just batching the gradient, but if your gradient is expensive to compute they might be useful. It is often pretty easy to come up with domain specific control variates too that can be useful to reduce variance.

This sounds like maybe mini-batch gradient descent, where you use the average or sum of a batch of points, or maybe something like Adam, where you use averaging over epochs to give your gradient descent some "momentum".

Instead of the average, would it be possible to compute the divergence (or laplacian) very quickly? That might lead to a faster higher order optimization method compared to simple gradient descent.

This is interesting. So over what can you average over in practice? any point + the points of an axis parallel cube? if so, can you rotate the cube? scale it non-uniformly in different axes? can you average over non-linear measurements, like the length of the gradient? I am highly interested in geometry and optimization, so happy to talk about this, feel free to direct message me.

Wouldn't you be better off using the parallel computation to calculate gradient at lots of random points and then see if you can find a better local minima? Ie do they all converge to different points.

In addition to providing a smoother descend, computing the average gradient over many samples is very parallelizable. So on a modern GPU, taking the gradient at a single point vs 50 points is not 50 times more expensive. In fact, if your model is small enough, they could take roughly the same amount of time.

Yes, since the input point is uncertain due to measurement noise if nothing else, averaging over that distribution would be superior.

If you can average over other interesting distributions, like shifts or rotations or such for images, or even under a local approximation thereof, that would be amazing. Is that possible with quantum?

My take from your question is basically the difference between SGD and mini-batch SGD. Batch SGD in general provides a more robust (less overfitting) and smoother ( less zig-zag) solution; but it really differs between different data. More homogenous data usually work better with SGD; otherwise mini-batch SGD will perform better.

Batching does this, generally and it's a good thing for stability. Reduces the variance of the gradient update proportional to the batch size.

sgd vs gd

Are you not talking about batch size?