Nesterov Smoothing of Structured Nonsmooth Functions

Intuition Beginner

A subgradient method treats a kinked cost as a black box: at each point it asks only for a downhill direction and steps. It works for any convex shape, but it is slow — to cut the error in half you may need four times the steps. The kinks are the problem. A smooth bowl can be descended quickly; a creased one cannot, because near a crease the method keeps zig-zagging across the fold.

Many kinked costs are not arbitrary, though. They are built from a hidden "worst-case" rule: the cost at a point is the largest payoff over a menu of choices an adversary could pick. The absolute value, the largest entry of a vector, the size of the biggest error — each is a maximum over simple options. That hidden menu is extra information the black box throws away.

Nesterov's smoothing uses the menu. Instead of letting the adversary pick the single best option, you charge a small fee for picking an extreme option — a fee that grows the more lopsided the choice. The adversary now prefers a soft blend of options, and the resulting cost is a rounded version of the original: the kinks are buffed out into gentle curves. You control how rounded with one knob.

The payoff is a speed-class jump. Run a fast smooth-problem method on the rounded cost, and tune the rounding to match the accuracy you want. The kinked problem that needed about one-over-error-squared steps now needs about one-over-error steps. You did not break the rule that black-box kinked problems are slow — you stopped treating the problem as a black box and used the menu you knew was there.

Visual Beginner

Picture the absolute-value cost, a sharp V with a corner at zero. Smoothing replaces the corner with a small smooth arc that hugs the V everywhere else. Make the arc tighter and the rounded cost matches the V more closely but curves harder near zero (steeper to descend); make it wider and the cost is easier to descend but sits a little above the true V.

   sharp cost (a kinked V)        smoothed cost (corner rounded)

   |\           /|                 |\           /|
   | \         / |                 | \         / |
   |  \       /  |                 |  \       /  |
   |   \     /   |                 |   \_   _/   |   <- rounded arc
   |    \   /    |                 |     \_/     |      (no kink)
   |     \ /     |                 |              |
   +------V------+                 +------_------+
        corner                        smooth bottom

   error ~ 1/k^2 to descend         error ~ mu (rounding gap)
   (kink forces zig-zag)            balance mu with accuracy -> 1/k overall

approach	kinked problem	rounded problem
steps to reach error	about $1/{\text{error}}^2$	about $1/\text{error}$
extra information used	none (black box)	the hidden max-menu
knob	none	rounding amount $\mu$

Worked example Beginner

Round off the absolute value $f(x)=|x|$. The key fact is that the absolute value is a maximum over a menu: $|x|$ equals the largest of $x\cdot u$ as $u$ ranges over the choices $-1$ to $1$. The adversary picks $u=+1$ when $x>0$ and $u=-1$ when $x<0$, recovering $|x|$, with the kink at $x=0$ where the choice flips.

Step 1. Charge a fee. Subtract a small fee $\frac{\mu }{2}{u}^2$ from the adversary's payoff, with $\mu =1$ for a clean number. The adversary now maximizes $xu-\frac{1}{2}{u}^2$ over $u$ in $-1$ to $1$.

Step 2. Solve the adversary's choice. Ignoring the $-1$ to $1$ limits, the best $u$ sets the slope $x-u$ to zero, so $u=x$. That stays inside the limits when $x$ is between $-1$ and $1$. There the rounded cost is $x\cdot x-\frac{1}{2}{x}^2=\frac{1}{2}{x}^2$ — a smooth bowl.

Step 3. Far from zero. When $x>1$ the unfettered choice $u=x$ exceeds the limit, so the adversary picks $u=1$, giving $x\cdot 1-\frac{1}{2}=x-\frac{1}{2}$. By symmetry, for $x<-1$ the cost is $-x-\frac{1}{2}=|x|-\frac{1}{2}$.

Step 4. Read the rounded cost. It is $\frac{1}{2}{x}^2$ for $|x|\le 1$ and $|x|-\frac{1}{2}$ for $|x|\ge 1$ — a parabola spliced smoothly into the two straight arms of the V. This is the Huber function.

What this tells us. The rounded cost never exceeds the true $|x|$ by more than the fee budget (here $\frac{1}{2}$ at $x=0$), and it has no kink, so a fast smooth-problem method can descend it. Shrink $\mu$ and the rounding gap shrinks too; the whole art is choosing $\mu$ to match the accuracy you need.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $f$ is a structured nonsmooth convex function presented through a saddle (max-type) representation, the conjugate-style modeling form of 44.02.03. Let $Q_1\subseteq {\mathbb{R}}^n$ and $Q_2\subseteq {\mathbb{R}}^m$ be nonempty closed convex sets with $Q_2$ bounded, let $A:{\mathbb{R}}^n\to {\mathbb{R}}^m$ be linear with adjoint $A^{\top }$, and let $\hat{\varphi }:Q_2\to \mathbb{R}$ be continuous convex. The Euclidean inner product is $⟨\cdot ,\cdot ⟩$ and $\Vert A\Vert$ is the operator norm.

Definition (structured nonsmooth model). The objective is

$$f(x)=\underset{u\in Q_2}{\max }\{⟨Ax,u⟩-\hat{\varphi }(u)\},x\in Q_1.$$

The maximum is a supremum of affine functions of $x$, so $f$ is convex; it is generally nonsmooth, the kinks occurring where the maximiser in $u$ switches. This is exactly the conjugate/saddle form of 44.02.03: $f(x)={\hat{\varphi }}^{\ast }(A^{\top }\cdot )$-type composition, and $f$ is the support-style value of an inner concave maximization in $u$.

Definition (prox-function). A prox-function for $Q_2$ is a continuous function $d_2:Q_2\to \mathbb{R}$ that is ${\sigma }_2$-strongly convex on $Q_2$ (${\sigma }_2>0$), with prox-center $u_0=\arg {\min }_{u\in Q_2}{d}_2(u)$ normalised so $d_2(u_0)=0$, and prox-diameter

$$D_2=\underset{u\in Q_2}{\max }{d}_2(u)<\infty .$$

A symmetric prox-function $d_1$ with parameters ${\sigma }_1,D_1$ is fixed on $Q_1$ for the outer accelerated method.

Definition (smooth approximation). For smoothing parameter $\mu >0$, the Nesterov smoothing of $f$ is

$$f_{\mu }(x)=\underset{u\in Q_2}{\max }\{⟨Ax,u⟩-\hat{\varphi }(u)-\mu d_2(u)\}.$$

Subtracting the strongly convex penalty $\mu d_2$ makes the inner objective strongly concave in $u$, so the maximiser $u_{\mu }(x)$ is unique and depends smoothly on $x$. Write $L_{\mu }=\Vert A{\Vert }^2/(\mu {\sigma }_2)$.

Definition (smoothable function, Beck-Teboulle abstraction). A convex $g$ is $(\alpha ,\beta )$-smoothable if for each $\mu >0$ there is a convex $g_{\mu }$ with $g_{\mu }(x)\le g(x)\le g_{\mu }(x)+\beta \mu$ for all $x$ and $\nabla g_{\mu }$ Lipschitz with constant $\alpha /\mu$. The conjugate-smoothing $f_{\mu }$ above realises this with $\alpha =\Vert A{\Vert }^2/{\sigma }_2$ and $\beta =D_2$ ^{[Beck & Teboulle 2012]}.

Counterexamples to common slips Intermediate+

• "Smoothing beats the nonsmooth lower bound, so the $\Omega (1/{\epsilon }^2)$ subgradient lower bound is wrong." It is not a contradiction. The $\Omega (1/{\epsilon }^2)$ bound of 44.06.01 is for the black-box oracle model, where the method sees only $f$ and a subgradient. Smoothing is not a black-box method: it consumes the explicit max-representation $(A,\hat{\varphi },Q_2)$ as side information the oracle never supplied. The structure is the extra input that escapes the lower bound's hypotheses.

• "Just send $\mu \to 0$ to get the exact problem cheaply." As $\mu \to 0$ the gradient-Lipschitz constant $L_{\mu }=\Vert A{\Vert }^2/(\mu {\sigma }_2)\to \infty$, so an accelerated method's per-target iteration count $\sqrt{L_{\mu }}/\sqrt{\epsilon }$ blows up. The error $\mu D_2$ and the conditioning $L_{\mu }$ pull in opposite directions; the rate comes only from balancing them, $\mu \sim \epsilon$.

• "This is the same as Moreau-Yosida / proximal smoothing." The Moreau envelope $e_{\gamma }f=f\square \frac{1}{2\gamma }\Vert \cdot {\Vert }_2^2$ of 44.06.02 smooths via infimal convolution in the primal variable and needs a computable proximal operator. Nesterov smoothing regularizes the dual/inner variable $u$ in the saddle representation by a prox-function. The two coincide for special $d_2$ but differ in general, and the conjugate route gives the explicit $\nabla f_{\mu }(x)=A^{\top }{u}_{\mu }(x)$ even when ${\mathrm{prox}}_f$ is unavailable.

Key theorem with proof Intermediate+

The result that powers the whole technique is that the regularized inner maximum is not merely continuous but continuously differentiable with a controlled Lipschitz gradient, and that it approximates $f$ uniformly with error governed by the single parameter $\mu$. These two facts let an accelerated smooth-class method run on $f_{\mu }$ and a balance of $\mu$ against accuracy convert its $O(1/k^2)$ rate into $O(1/\epsilon )$ on the nonsmooth $f$.

Theorem (smoothness, approximation, and the $O(1/\epsilon )$ complexity). With the data above, the smoothing $f_{\mu }$ is convex and continuously differentiable on ${\mathbb{R}}^n$ with

$$\nabla f_{\mu }(x)=A^{\top }{u}_{\mu }(x),u_{\mu }(x)=\arg \underset{u\in Q_2}{\max }\{⟨Ax,u⟩-\hat{\varphi }(u)-\mu d_2(u)\},$$

and $\nabla f_{\mu }$ is Lipschitz with constant $L_{\mu }=\Vert A{\Vert }^2/(\mu {\sigma }_2)$. Moreover $f_{\mu }$ approximates $f$ uniformly,

$$f_{\mu }(x)\le f(x)\le f_{\mu }(x)+\mu D_2\text{for all }x.$$

Running the optimal accelerated gradient method of 44.06.03 on $f_{\mu }$ over $Q_1$ for $N$ steps and choosing

$$\mu =\frac{2\Vert A\Vert }{N+1}\sqrt{\frac{D_1}{{\sigma }_1{\sigma }_2{D}_2}}$$

yields

$$f(x_N)-f^{\star }\le \frac{4\Vert A\Vert }{N+1}\sqrt{\frac{D_1{D}_2}{{\sigma }_1{\sigma }_2}}=O\left(\frac{1}{N}\right),$$

so $N=O(1/\epsilon )$ iterations suffice for an $\epsilon$-accurate value.

Proof. Differentiability and gradient formula. Fix $x$. The inner objective ${\psi }_x(u)=⟨Ax,u⟩-\hat{\varphi }(u)-\mu d_2(u)$ is strongly concave in $u$ with modulus $\mu {\sigma }_2$ (since $\hat{\varphi }$ is convex and $\mu d_2$ is $\mu {\sigma }_2$-strongly convex), so its maximiser $u_{\mu }(x)$ over the closed convex $Q_2$ is unique. The value $f_{\mu }(x)={\max }_{u\in Q_2}{\psi }_x(u)$ is a maximum of functions affine in $x$, hence convex. Danskin's theorem for a unique maximiser gives differentiability with $\nabla f_{\mu }(x)={\nabla }_x{\psi }_x(u){|}_{u=u_{\mu }(x)}=A^{\top }{u}_{\mu }(x)$.

Gradient Lipschitz constant. Let $x,x^{\prime }\in {\mathbb{R}}^n$ with maximisers $u=u_{\mu }(x)$, $u^{\prime }=u_{\mu }(x^{\prime })$. First-order optimality of the strongly concave inner problem on $Q_2$ gives, for the supergradient $Ax-\nabla \hat{\varphi }(u)-\mu \nabla d_2(u)$ pointing out of $Q_2$ at $u$,

$$⟨Ax-\partial \hat{\varphi }(u)-\mu \nabla d_2(u),u^{\prime }-u⟩\le 0,⟨A{x}^{\prime }-\partial \hat{\varphi }(u^{\prime })-\mu \nabla d_2(u^{\prime }),u-u^{\prime }⟩\le 0.$$

Adding the two and using monotonicity of $\partial \hat{\varphi }$ ($⟨\partial \hat{\varphi }(u)-\partial \hat{\varphi }(u^{\prime }),u-u^{\prime }⟩\ge 0$) and $\mu {\sigma }_2$-strong monotonicity of $\mu \nabla d_2$,

$$⟨A(x-x^{\prime }),u-u^{\prime }⟩\ge \mu {\sigma }_2\Vert u-u^{\prime }{\Vert }^2.$$

By Cauchy-Schwarz the left side is $\le \Vert A\Vert \Vert x-x^{\prime }\Vert \Vert u-u^{\prime }\Vert$, so $\Vert u-u^{\prime }\Vert \le \frac{\Vert A\Vert }{\mu {\sigma }_2}\Vert x-x^{\prime }\Vert$. Then

$$\Vert \nabla f_{\mu }(x)-\nabla f_{\mu }(x^{\prime })\Vert =\Vert A^{\top }(u-u^{\prime })\Vert \le \Vert A\Vert \Vert u-u^{\prime }\Vert \le \frac{\Vert A{\Vert }^2}{\mu {\sigma }_2}\Vert x-x^{\prime }\Vert =L_{\mu }\Vert x-x^{\prime }\Vert .$$

Uniform approximation. For every $x$, since $d_2\ge 0$ on $Q_2$ (as $d_2(u_0)=0$ is the minimum), subtracting $\mu d_2\ge 0$ inside the max can only lower the value: $f_{\mu }(x)\le f(x)$. Conversely, evaluating the $f$-defining max at $u_{\mu }(x)$ and using $0\le d_2\le D_2$,

$$f(x)\ge ⟨Ax,u_{\mu }(x)⟩-\hat{\varphi }(u_{\mu }(x))=f_{\mu }(x)+\mu d_2(u_{\mu }(x))\le f_{\mu }(x)+\mu D_2,$$

and taking the maximiser in $f$ gives $f(x)\le f_{\mu }(x)+\mu D_2$. Hence $f_{\mu }\le f\le f_{\mu }+\mu D_2$.

Complexity balance. Accelerated gradient on $f_{\mu }$ over $Q_1$ (the prox-function $d_1$ supplying the distance term) attains, after $N$ steps, $f_{\mu }(x_N)-f_{\mu }^{\star }\le \frac{2L_{\mu }{D}_1}{{\sigma }_1(N+1{)}^2}$ — the $O(1/k^2)$ rate of 44.06.03 specialized to the $L_{\mu }$-smooth $f_{\mu }$, with $D_1/{\sigma }_1$ bounding the squared distance to the optimum via the outer prox-function. Pass the rate to $f$ using the approximation bound: $f(x_N)-f^{\star }\le (f_{\mu }(x_N)-f_{\mu }^{\star })+\mu D_2\le \frac{2L_{\mu }{D}_1}{{\sigma }_1(N+1{)}^2}+\mu D_2$. Substitute $L_{\mu }=\Vert A{\Vert }^2/(\mu {\sigma }_2)$:

$$f(x_N)-f^{\star }\le \frac{2\Vert A{\Vert }^2{D}_1}{\mu {\sigma }_1{\sigma }_2(N+1{)}^2}+\mu D_2.$$

The right side is convex in $\mu$ and minimized at ${\mu }^{\star }=\frac{2\Vert A\Vert }{N+1}\sqrt{\frac{D_1}{{\sigma }_1{\sigma }_2{D}_2}}$, where both terms equal $\frac{2\Vert A\Vert }{N+1}\sqrt{\frac{D_1{D}_2}{{\sigma }_1{\sigma }_2}}$, summing to the stated bound $\frac{4\Vert A\Vert }{N+1}\sqrt{\frac{D_1{D}_2}{{\sigma }_1{\sigma }_2}}$. This is $O(1/N)$, so $N=O(1/\epsilon )$. $\square$

Bridge. The two halves of the theorem — the $L_{\mu }=\Vert A{\Vert }^2/(\mu {\sigma }_2)$ smoothness from strong concavity of the regularized inner max, and the $\mu D_2$ uniform error — are the foundational reason structure beats the black-box barrier; this builds toward the excessive-gap technique and the entropy/${\ell }_1$/${\ell }_{\infty }$ smoothings of the Advanced results, where the same balance reappears with explicit prox-functions. This is exactly the conjugate/saddle representation of 44.02.03 with the inner variable regularized rather than the primal, and it is dual to the Moreau smoothing of 44.06.02, which regularizes the primal; putting these together, the central insight is that the per-step accuracy of the accelerated method 44.06.03 and the smoothing error are two error sources balanced at $\mu \sim \epsilon$, which generalises the single-error analysis of smooth problems to the structured-nonsmooth class and appears again in primal-dual saddle-point solvers 44.06.04.

Exercises Intermediate+

Advanced results Master

The smoothing $f_{\mu }(x)={\max }_{u\in Q_2}\{⟨Ax,u⟩-\hat{\varphi }(u)-\mu d_2(u)\}$ over $x\in Q_1$ admits a self-contained development: the structured complexity bound that beats the black-box barrier, the resolution of the apparent conflict with the nonsmooth lower bound, the excessive-gap primal-dual scheme that drops the need to fix $\mu$, the entropy smoothing as the canonical instance, and the placement against Moreau-Yosida smoothing.

Theorem 1 (structured $O(1/\epsilon )$ complexity). With prox-functions $d_1,d_2$ of parameters $({\sigma }_1,D_1)$, $({\sigma }_2,D_2)$, the accelerated method on $f_{\mu }$ with $\mu =\frac{2\Vert A\Vert }{N+1}\sqrt{D_1/({\sigma }_1{\sigma }_2{D}_2)}$ produces $x_N\in Q_1$ with $f(x_N)-f^{\star }\le \frac{4\Vert A\Vert }{N+1}\sqrt{D_1{D}_2/({\sigma }_1{\sigma }_2)}$ ^{[Nesterov 2005]}. Equivalently $N(\epsilon )=\lceil 4\Vert A\Vert \sqrt{D_1{D}_2/({\sigma }_1{\sigma }_2)}/\epsilon \rceil$ iterations reach value accuracy $\epsilon$, each costing one gradient $A^{\top }{u}_{\mu }(x)$ — one inner maximization over $Q_2$. The complexity is $O(\Vert A\Vert /\epsilon )$, linear in $\Vert A\Vert$ and in $1/\epsilon$, against the $O(1/{\epsilon }^2)$ of the subgradient method.

Theorem 2 (structure versus the black-box lower bound). The $\Omega (1/{\epsilon }^2)$ first-order lower bound for the nonsmooth convex class 44.06.01 is an information bound in the black-box oracle model: the method is charged only with calls returning $f(x)$ and one subgradient, and the bound exhibits a function on which any such method is slow. Smoothing operates in a structured model: the triple $(A,\hat{\varphi },Q_2)$ and the prox-function $d_2$ are inputs, so the method can compute $f_{\mu }$ and its exact gradient $A^{\top }{u}_{\mu }(x)$ — information no subgradient oracle returns. The $O(1/\epsilon )$ rate therefore lives outside the lower bound's hypothesis class; there is no contradiction, only a strictly more informative model ^{[Nesterov 2005]}. The boundary between $\Theta (1/\epsilon )$ and $\Theta (1/{\epsilon }^2)$ is exactly the boundary between structured and black-box access.

Theorem 3 (excessive-gap technique). Fix smoothings of both the primal $f_{{\mu }_2}(x)={\max }_u\{⟨Ax,u⟩-\hat{\varphi }(u)-{\mu }_2{d}_2(u)\}$ and the dual ${\varphi }_{{\mu }_1}(u)={\min }_x\{⟨Ax,u⟩+\hat{f}(x)+{\mu }_1{d}_1(x)\}$, where $\hat{f}$ is the primal part. A pair $(x,u)$ satisfies the excessive-gap condition if $f_{{\mu }_2}(x)\le {\varphi }_{{\mu }_1}(u)$. Nesterov's primal-dual scheme generates $(x_k,u_k)$ keeping the excessive-gap condition invariant while shrinking ${\mu }_1^{(k)},{\mu }_2^{(k)}=O(1/k)$, yielding

$$0\le f(x_k)-\varphi (u_k)\le {\mu }_1^{(k)}{D}_1+{\mu }_2^{(k)}{D}_2=O(1/k),$$

a genuine primal-dual gap certificate of size $O(1/\epsilon )$ in $k$, without committing $\mu$ in advance ^{[Nesterov 2005]}. The scheme alternates a gradient step on the smoothed primal and a gradient step on the smoothed dual, each step decreasing the relevant $\mu$, so the method self-tunes the smoothing as it converges and returns a verifiable duality gap rather than only a primal value.

Theorem 4 (entropy smoothing of the max / softmax). For $f(x)={\max }_{1\le i\le m}{x}_i={\max }_{u\in {\Delta }_m}⟨x,u⟩$ with entropy prox-function $d_2(u)={\sum }_i{u}_i\log u_i+\log m$ (${\sigma }_2=1$ in ${\ell }_1$ by Pinsker's inequality, $D_2=\log m$), the smoothing is the temperature-$\mu$ log-sum-exp

$$f_{\mu }(x)=\mu \log \sum _{i=1}^m{e}^{x_i/\mu }-\mu \log m,\nabla f_{\mu }(x)=\mathrm{softmax}(x/\mu ),$$

with $\Vert \nabla f_{\mu }(x)-\nabla f_{\mu }(x^{\prime }){\Vert }_{\infty }$ governed by $L_{\mu }=1/\mu$ and uniform error $\mu \log m$ ^{[Beck & Teboulle 2012]}. The $\log m$ (rather than $m$) dependence of $D_2$ under the entropy prox is the discrete-simplex analogue of mirror descent's logarithmic dimension dependence; it is why softmax smoothing is the preferred relaxation of the max in high-dimensional structured-prediction and attention models.

Theorem 5 (smoothing versus Moreau-Yosida). The Moreau envelope $e_{\gamma }f=f\square \frac{1}{2\gamma }\Vert \cdot {\Vert }_2^2$ of 44.06.02 is the special case of conjugate smoothing in which the dual prox-function is the squared norm: $e_{\gamma }f(x)={\max }_u\{⟨x,u⟩-f^{\ast }(u)-\frac{\gamma }{2}\Vert u{\Vert }_2^2\}$, so Moreau smoothing regularizes the conjugate $f^{\ast }$ by $\frac{\gamma }{2}\Vert \cdot {\Vert }_2^2$ on all of ${\mathbb{R}}^n$ ^{[Beck & Teboulle 2012]}. Nesterov smoothing generalizes this in two ways: the prox-function $d_2$ need not be the squared norm (entropy on a simplex, for instance), and the inner domain $Q_2$ may be a proper bounded set, so the prox-diameter $D_2$ and modulus ${\sigma }_2$ can be tuned to the geometry of $Q_2$. The Moreau route needs a computable ${\mathrm{prox}}_f$; the conjugate route needs only a computable inner maximization $u_{\mu }(x)$ — available whenever the max-representation is explicit, even when ${\mathrm{prox}}_f$ is not.

Synthesis. The smoothing $f_{\mu }$ is exactly the conjugate/saddle representation of 44.02.03 with the inner variable regularized by a prox-function, and this single move is the foundational reason the structured nonsmooth class falls to $O(1/\epsilon )$: strong concavity of the regularized inner max delivers $\nabla f_{\mu }=A^{\top }{u}_{\mu }$ with $L_{\mu }=\Vert A{\Vert }^2/(\mu {\sigma }_2)$, the accelerated method 44.06.03 turns that smoothness into an $O(L_{\mu }/N^2)$ value gap, and balancing it against the $\mu D_2$ approximation error at $\mu \sim \epsilon$ is what produces the rate. The two error sources — algorithmic and approximation — are dual faces of one trade-off, and putting these together is what beats the $\Omega (1/{\epsilon }^2)$ black-box barrier of 44.06.01 without contradicting it: the lower bound is a black-box statement and smoothing is a structured method, so the central insight is that the complexity boundary is the boundary of the oracle model, not of convexity. Moreau-Yosida smoothing 44.06.02 is the squared-norm special case, so Nesterov smoothing generalises it; the excessive-gap technique is the primal-dual refinement that self-tunes $\mu$ and certifies a duality gap, and it is the bridge to the saddle-point and operator-splitting solvers 44.06.04 that attack the same min-max structure. The entropy smoothing realises all of this with the softmax, where the $\log m$ prox-diameter is dual to mirror descent's logarithmic geometry and the temperature parameter is exactly $\mu$.

Full proof set Master

Proposition 1 (gradient of the smoothing). Under the standing hypotheses, $f_{\mu }$ is convex and differentiable with $\nabla f_{\mu }(x)=A^{\top }{u}_{\mu }(x)$, where $u_{\mu }(x)$ is the unique maximiser of the regularized inner problem.

Proof. The inner objective ${\psi }_x(u)=⟨Ax,u⟩-\hat{\varphi }(u)-\mu d_2(u)$ is $\mu {\sigma }_2$-strongly concave (convex $\hat{\varphi }$, ${\sigma }_2$-strongly convex $d_2$), so over the closed convex $Q_2$ it has a unique maximiser $u_{\mu }(x)$. As a pointwise maximum of functions affine in $x$, $f_{\mu }$ is convex. Danskin's theorem for a strongly concave inner problem with unique maximiser gives that $f_{\mu }$ is differentiable with $\nabla f_{\mu }(x)={\nabla }_x{\psi }_x(u){|}_{u=u_{\mu }(x)}=A^{\top }{u}_{\mu }(x)$, since ${\psi }_x$ depends on $x$ only through the bilinear term $⟨Ax,u⟩$ whose $x$-gradient is $A^{\top }u$. $\square$

Proposition 2 (gradient Lipschitz constant). $\nabla f_{\mu }$ is Lipschitz with constant $L_{\mu }=\Vert A{\Vert }^2/(\mu {\sigma }_2)$.

Proof. For $u=u_{\mu }(x)$, $u^{\prime }=u_{\mu }(x^{\prime })$, first-order optimality on $Q_2$ gives $⟨Ax-g-\mu \nabla d_2(u),u^{\prime }-u⟩\le 0$ and $⟨A{x}^{\prime }-g^{\prime }-\mu \nabla d_2(u^{\prime }),u-u^{\prime }⟩\le 0$ with $g\in \partial \hat{\varphi }(u)$, $g^{\prime }\in \partial \hat{\varphi }(u^{\prime })$. Summing and using $⟨g-g^{\prime },u-u^{\prime }⟩\ge 0$ (monotonicity of $\partial \hat{\varphi }$) and $⟨\nabla d_2(u)-\nabla d_2(u^{\prime }),u-u^{\prime }⟩\ge {\sigma }_2\Vert u-u^{\prime }{\Vert }^2$ (strong convexity of $d_2$) gives $⟨A(x-x^{\prime }),u-u^{\prime }⟩\ge \mu {\sigma }_2\Vert u-u^{\prime }{\Vert }^2$. Cauchy-Schwarz bounds the left by $\Vert A\Vert \Vert x-x^{\prime }\Vert \Vert u-u^{\prime }\Vert$, so $\Vert u-u^{\prime }\Vert \le \frac{\Vert A\Vert }{\mu {\sigma }_2}\Vert x-x^{\prime }\Vert$, and $\Vert \nabla f_{\mu }(x)-\nabla f_{\mu }(x^{\prime })\Vert =\Vert A^{\top }(u-u^{\prime })\Vert \le \Vert A\Vert \Vert u-u^{\prime }\Vert \le \frac{\Vert A{\Vert }^2}{\mu {\sigma }_2}\Vert x-x^{\prime }\Vert$. $\square$

Proposition 3 (uniform approximation). For all $x$, $f_{\mu }(x)\le f(x)\le f_{\mu }(x)+\mu D_2$.

Proof. Since $d_2(u)\ge d_2(u_0)=0$ on $Q_2$, subtracting $\mu d_2\ge 0$ inside the inner max only decreases it, so $f_{\mu }(x)\le f(x)$. For the upper bound, $f(x)\ge ⟨Ax,u_{\mu }(x)⟩-\hat{\varphi }(u_{\mu }(x))=f_{\mu }(x)+\mu d_2(u_{\mu }(x))$, and $d_2(u_{\mu }(x))\le D_2$, while taking the maximiser of the $f$-defining problem gives $f(x)\le {\max }_u\{⟨Ax,u⟩-\hat{\varphi }(u)-\mu d_2(u)\}+\mu {\max }_u{d}_2(u)=f_{\mu }(x)+\mu D_2$. $\square$

Proposition 4 ($O(1/\epsilon )$ complexity). Accelerated gradient on $f_{\mu }$ over $Q_1$ for $N$ steps with $\mu =\frac{2\Vert A\Vert }{N+1}\sqrt{D_1/({\sigma }_1{\sigma }_2{D}_2)}$ gives $f(x_N)-f^{\star }\le \frac{4\Vert A\Vert }{N+1}\sqrt{D_1{D}_2/({\sigma }_1{\sigma }_2)}$.

Proof. The accelerated method 44.06.03 on the $L_{\mu }$-smooth $f_{\mu }$ with prox-function $d_1$ attains $f_{\mu }(x_N)-f_{\mu }^{\star }\le \frac{2L_{\mu }{D}_1}{{\sigma }_1(N+1{)}^2}$. By Proposition 3, $f(x_N)-f^{\star }\le (f_{\mu }(x_N)-f_{\mu }^{\star })+\mu D_2\le \frac{2L_{\mu }{D}_1}{{\sigma }_1(N+1{)}^2}+\mu D_2$. Insert $L_{\mu }=\Vert A{\Vert }^2/(\mu {\sigma }_2)$ to get $\frac{2\Vert A{\Vert }^2{D}_1}{\mu {\sigma }_1{\sigma }_2(N+1{)}^2}+\mu D_2$. Minimizing the convex-in-$\mu$ expression (Exercise 6) at ${\mu }^{\star }=\frac{2\Vert A\Vert }{N+1}\sqrt{D_1/({\sigma }_1{\sigma }_2{D}_2)}$ equalizes the two terms at $\frac{2\Vert A\Vert }{N+1}\sqrt{D_1{D}_2/({\sigma }_1{\sigma }_2)}$ each, summing to the bound. $\square$

Proposition 5 (entropy smoothing closed form). For $f(x)={\max }_i{x}_i={\max }_{u\in {\Delta }_m}⟨x,u⟩$ and $d_2(u)={\sum }_i{u}_i\log u_i+\log m$, $f_{\mu }(x)=\mu \log {\sum }_i{e}^{x_i/\mu }-\mu \log m$ and $\nabla f_{\mu }(x)=\mathrm{softmax}(x/\mu )$, with ${\sigma }_2=1$ in ${\ell }_1$, $D_2=\log m$.

Proof. The inner problem ${\max }_{u\in {\Delta }_m}\{⟨x,u⟩-\mu {\sum }_i{u}_i\log u_i-\mu \log m\}$ has Lagrangian stationarity (over the simplex constraint ${\sum }_i{u}_i=1$, $u\ge 0$) $x_i-\mu (\log u_i+1)-\nu =0$, giving $u_i\propto e^{x_i/\mu }$, normalised $u_{\mu }(x{)}_i=e^{x_i/\mu }/{\sum }_j{e}^{x_j/\mu }$ — the softmax. Substituting back, the entropy and linear terms combine to $f_{\mu }(x)=\mu \log {\sum }_j{e}^{x_j/\mu }-\mu \log m$ (the conjugate of the negative entropy is log-sum-exp, 44.02.03 Proposition 4). By Proposition 1, $\nabla f_{\mu }(x)=u_{\mu }(x)=\mathrm{softmax}(x/\mu )$. Pinsker's inequality makes the negative entropy $1$-strongly convex in $\Vert \cdot {\Vert }_1$, so ${\sigma }_2=1$; $D_2={\max }_{u\in {\Delta }_m}({\sum }_i{u}_i\log u_i+\log m)=\log m$ at a vertex. $\square$

Proposition 6 (Moreau envelope as squared-norm smoothing). For proper closed convex $f$ with conjugate $f^{\ast }$, the Moreau envelope satisfies $e_{\gamma }f(x)={\max }_u\{⟨x,u⟩-f^{\ast }(u)-\frac{\gamma }{2}\Vert u{\Vert }_2^2\}$, i.e. it is the conjugate smoothing of $f$ with $A=\mathrm{Id}$, $\hat{\varphi }=f^{\ast }$, $d_2=\frac{1}{2}\Vert \cdot {\Vert }_2^2$.

Proof. By definition $e_{\gamma }f(x)={\min }_z\{f(z)+\frac{1}{2\gamma }\Vert x-z{\Vert }_2^2\}$. The infimal-convolution duality of 44.02.03 gives $(f\square \frac{1}{2\gamma }\Vert \cdot {\Vert }_2^2{)}^{\ast }=f^{\ast }+(\frac{1}{2\gamma }\Vert \cdot {\Vert }_2^2{)}^{\ast }=f^{\ast }+\frac{\gamma }{2}\Vert \cdot {\Vert }_2^2$, since the conjugate of $\frac{1}{2\gamma }\Vert \cdot {\Vert }_2^2$ is $\frac{\gamma }{2}\Vert \cdot {\Vert }_2^2$. Biconjugating (both sides closed convex), $e_{\gamma }f=f\square \frac{1}{2\gamma }\Vert \cdot {\Vert }_2^2=(f^{\ast }+\frac{\gamma }{2}\Vert \cdot {\Vert }_2^2{)}^{\ast }={\max }_u\{⟨x,u⟩-f^{\ast }(u)-\frac{\gamma }{2}\Vert u{\Vert }_2^2\}$. This is $f_{\mu }$ with $\mu =\gamma$, $\hat{\varphi }=f^{\ast }$, $d_2=\frac{1}{2}\Vert \cdot {\Vert }_2^2$ (${\sigma }_2=1$), and $\nabla e_{\gamma }f(x)=u_{\gamma }(x)=\frac{1}{\gamma }(x-{\mathrm{prox}}_{\gamma f}(x))$ recovers the standard envelope gradient. $\square$

Connections Master

• The smoothing $f_{\mu }(x)={\max }_{u\in Q_2}\{⟨Ax,u⟩-\hat{\varphi }(u)-\mu d_2(u)\}$ is the conjugate/saddle representation of 44.02.03 with the inner (dual) variable regularized by a prox-function; the support-function and dual-norm conjugate pairs assembled there are exactly the max-representations smoothed here, and the softmax/log-sum-exp smoothing of the max is the temperature-$\mu$ instance of the negative-entropy/log-sum-exp conjugate pair proved in that unit.

• The outer engine is the accelerated gradient method of 44.06.03: smoothing produces an $L_{\mu }$-smooth $f_{\mu }$ precisely so that the optimal $O(1/k^2)$ method applies, and the $O(1/\epsilon )$ complexity is its $O(L_{\mu }/N^2)$ rate balanced against the smoothing error at $\mu \sim \epsilon$. Without the accelerated rate the same balance would give only $O(1/{\epsilon }^2)$ from a plain gradient method on $f_{\mu }$, so the acceleration is load-bearing.

• The optimality story is dual to the lower-bound theory of 44.06.01: that unit proves the $\Omega (1/{\epsilon }^2)$ black-box bound for nonsmooth convex minimization and shows the subgradient method attains it, while this unit shows that admitting the explicit max-structure as side information lets a structured method reach $O(1/\epsilon )$ — the two results partition the nonsmooth landscape by oracle model, structured versus black-box, with the smoothing technique on the structured side.

• Nesterov smoothing generalizes the Moreau-Yosida / proximal smoothing of 44.06.02: the Moreau envelope is the special case in which the dual prox-function is the squared norm and the inner domain is all of the space, so the proximal smoothing of that unit is the squared-norm conjugate smoothing, and the excessive-gap primal-dual scheme is the precursor of the saddle-point and operator-splitting solvers 44.06.04 that attack the same min-max structured model directly.

Historical & philosophical context Master

The smoothing technique was introduced by Yurii Nesterov in 2005 in Smooth minimization of non-smooth functions (Mathematical Programming 103(1), 127-152), which showed that a large class of nonsmooth convex problems with explicit max-structure can be solved in $O(1/\epsilon )$ iterations rather than the $O(1/{\epsilon }^2)$ dictated by the black-box subgradient lower bound of Nemirovski and Yudin ^{[Nesterov 2005]}. The paper's resolution of the apparent conflict — that the lower bound governs the black-box oracle model while smoothing exploits known structure — clarified that complexity in optimization is a property of the access model, not of the function class alone. The same paper introduced the excessive-gap technique as a primal-dual scheme producing the rate with a verifiable duality-gap certificate and without fixing the smoothing parameter in advance.

The unifying abstraction — the notion of a smoothable function with the $\alpha /\mu$ versus $\beta \mu$ trade-off, covering both the conjugate smoothing and the Moreau envelope as instances — was given by Amir Beck and Marc Teboulle in 2012 in Smoothing and First Order Methods: A Unified Framework (SIAM Journal on Optimization 22(2), 557-580), who packaged the smoothing-then-FISTA combination (S-FISTA) and made the constant trade-off explicit for the ${\ell }_1$, ${\ell }_{\infty }$, hinge, and max smoothings ^{[Beck & Teboulle 2012]}. The entropy smoothing of the max, equivalent to the temperature-controlled log-sum-exp, predates the optimization framing in the exponential-family and statistical-mechanics literature and connects the technique to the negative-entropy/log-sum-exp conjugate duality and to mirror descent's logarithmic geometry. Nesterov returned to the technique in the smoothing chapter of his Lectures on Convex Optimization ^{[Nesterov 2018]}.

Bibliography Master

@article{nesterov2005smooth,
  author  = {Nesterov, Yurii},
  title   = {Smooth minimization of non-smooth functions},
  journal = {Mathematical Programming},
  volume  = {103},
  number  = {1},
  pages   = {127--152},
  year    = {2005}
}

@article{nesterov2005excessive,
  author  = {Nesterov, Yurii},
  title   = {Excessive Gap Technique in Nonsmooth Convex Minimization},
  journal = {SIAM Journal on Optimization},
  volume  = {16},
  number  = {1},
  pages   = {235--249},
  year    = {2005}
}

@article{becktebeoulle2012smoothing,
  author  = {Beck, Amir and Teboulle, Marc},
  title   = {Smoothing and First Order Methods: A Unified Framework},
  journal = {SIAM Journal on Optimization},
  volume  = {22},
  number  = {2},
  pages   = {557--580},
  year    = {2012}
}

@book{nesterov2018lectures,
  author    = {Nesterov, Yurii},
  title     = {Lectures on Convex Optimization},
  edition   = {2},
  series    = {Springer Optimization and Its Applications},
  volume    = {137},
  publisher = {Springer},
  year      = {2018}
}

@book{nemirovskiyudin1983,
  author    = {Nemirovski, Arkadi S. and Yudin, David B.},
  title     = {Problem Complexity and Method Efficiency in Optimization},
  publisher = {Wiley-Interscience},
  year      = {1983}
}