关于不同误差定义下最速下降法收敛速率可比性的技术问询

Great question—this is a common point of confusion when first diving into optimization convergence rates, since different problem scenarios naturally call for different error metrics. Let’s break this down clearly:

Why Different Error Metrics Are Used #

First, let’s clarify the reasoning behind the two error measures in the book:

• General L-smooth functions (non-convex): For non-convex problems, we can’t guarantee convergence to a global minimum (or even that one exists). The most meaningful progress we can measure is reaching a stationary point where the gradient is small. Hence, using $\lVert \nabla f(x^{k}) \rVert \leq \epsilon$ as the convergence criterion makes sense.
• Convex/strongly convex functions: In convex settings, any stationary point is a global minimum. So we can directly track progress toward the optimal function value $f^$ using $f(x^k) - f^ \leq \epsilon$, which aligns better with the core goal of minimizing the function.

Can We Still Compare the Rates? #

Absolutely—we can translate all rates to a common error metric to make a fair, apples-to-apples comparison:

1. Translate All Rates to Gradient Norm ($\lVert \nabla f(x^{k}) \rVert \leq \epsilon$) #

• General L-smooth: The original rate is $k \geq \frac{2L(f(x^0)-f*)}{\epsilon^2}$ (quadratic in $1/\epsilon$, sublinear).
• Convex + L-smooth: Using the convexity and L-smoothness relation $f(x^k)-f* \leq \frac{\lVert \nabla f(x^k) \rVert^2}{L}$, to hit $\lVert \nabla f(x^k) \rVert \leq \epsilon$ we need $f(x^k)-f* \leq \frac{\epsilon^2}{L}$. Substituting into the convex rate gives $k \geq \frac{L^2\lVert x^0 - x^* \rVert^2}{2\epsilon2}$—still quadratic in $1/\epsilon$, same asymptotic order as the general case but with a worse constant.
• Strongly convex + L-smooth: For strongly convex functions with modulus $m$, we have $f(x^k)-f* \leq \frac{\lVert \nabla f(x^k) \rVert^2}{2m}$. To reach $\lVert \nabla f(x^k) \rVert \leq \epsilon$, we need $f(x^k)-f* \leq \frac{\epsilon^2}{2m}$. Plugging into the linear rate gives $k \geq \frac{L}{m}\log\left(\frac{2m(f(x^0)-f*)}{\epsilon^2}\right)$—this is logarithmic in $1/\epsilon$, which is asymptotically far faster than the quadratic rates of the other two cases.

2. Translate All Rates to Function Value Gap ($f(x^k)-f* \leq \epsilon$) #

• General L-smooth: This metric isn’t meaningful here—non-convex functions might get stuck in a local minimum where $f(x^k)-f*$ is large even if the gradient is small.
• Convex + L-smooth: Original rate is $k \geq \frac{L\lVert x^0 - x^* \rVert^2}{2 \epsilon}$ (linear in $1/\epsilon$, sublinear).
• Strongly convex + L-smooth: Original rate is $k \geq \frac{L}{m}\log\left(\frac{f(x^0)-f*}{\epsilon}\right)$ (logarithmic in $1/\epsilon$, linear)—again, way faster than the convex-only case.

Key Takeaway #

Even though the book uses different error metrics, when we convert all rates to a common measure, the strongly convex case still has an asymptotically faster convergence rate than both the general L-smooth and convex-only cases. The linear (logarithmic) rate of strongly convex problems means the error shrinks exponentially with iterations, whereas sublinear rates mean error shrinks polynomially. So yes, we can definitively say steepest descent converges faster on strongly convex functions.

备注：内容来源于stack exchange，提问作者Song