Optimization

Motivation

Two-stage adaptive optimization models decisions taken in two steps: a first-stage decision $x$ is fixed before an uncertain right-hand side $b$ is revealed, and a second-stage decision $y(b)$ is chosen after it, as a function of $b$. The objective protects against the worst $b$ in an uncertainty set $\mathcal U$. Computing an optimal fully adaptable solution is intractable in general (Feige, Jain, Mahdian and Mirrokni, IPCO 2007), so practitioners restrict the second stage to affine policies $y(b)=Pb+q$, introduced in robust optimization by Ben-Tal, Goryashko, Guslitzer and Nemirovski (Math. Program. 2004). An optimal affine policy is computed by a single convex program, but its cost may exceed the adaptive optimum.

Bertsimas and Goyal (Math. Program. Ser. A, 2012) quantify this loss. Earlier, Bertsimas, Iancu and Parrilo (Math. Oper. Res. 2010) proved affine policies optimal for a class of one-dimensional multistage problems. The present paper shows that affine policies are optimal when $\mathcal U$ is a simplex (Theorem 1), that they can lose a factor $\Omega(m^{1/2-\delta})$ in general (Theorem 3), and — the subject of this mission — that when the first-stage constraint matrix is nonnegative they never lose more than $3\sqrt m$ (Theorem 4). Nonnegative first-stage matrices occur in network design, facility location, capacity planning and other covering problems.

Setting

Let $A\in\mathbb R^{m\times n_1}$, $B\in\mathbb R^{m\times n_2}$, $c\in\mathbb R^{n_1}_+$, $d\in\mathbb R^{n_2}_+$, and let $\mathcal U\subseteq\mathbb R^m_+$ be convex, compact and full-dimensional. The problem $\Pi_{Adapt}(\mathcal U)$ is

$$z_{Adapt}(\mathcal U)=\min\; c^Tx+\max_{b\in\mathcal U}d^Ty(b)\quad\text{s.t.}\quad Ax+By(b)\ge b,\ \ x\ge0,\ \ y(b)\ge0\quad\forall b\in\mathcal U,$$

where the minimum is over first-stage vectors $x$ and arbitrary maps $b\mapsto y(b)$. The problem is assumed feasible. The value $z_{Aff}(\mathcal U)$ is the same minimum restricted to affine second stages $y(b)=Pb+q$, which must still satisfy $Pb+q\ge0$ on $\mathcal U$.

For each coordinate $j$ put $\mu_j=\max\{b_j : b\in\mathcal U\}$ and fix a maximizer $\beta^j\in\mathcal U$ with $\beta^j_j=\mu_j$ (display (38)). The scaled sum of $b$ over an index set $J$ is $\sum_{j\in J}b_j/\mu_j$.

Algorithm $\mathcal A$ (Fig. 1 of the paper) starts with $J_1=\{1,\dots,m\}$ and $b^0=0$. While some $b\in\mathcal U$ has scaled sum over $J_1$ larger than $\sqrt m$, it picks a maximizer $u^k\in\mathcal U$ of that scaled sum, adds $u^k$ to the running vector on the coordinates of $J_1$, and moves to $J_2$ every coordinate $j$ whose running value has reached $\mu_j$. It returns the number of iterations $K$, the vectors $u^1,\dots,u^K$, their sum $\beta=u^1+\dots+u^K$, and the partition $J_1,J_2$.

In the $k$-uncertain variant (60)–(63), only $k$ right-hand sides $b\in\mathcal U\subseteq\mathbb R^k_+$ are uncertain and the remaining $m-k$ are fixed at $b^0$; all data are nonnegative. Its values are $z^k_{Adapt}(\mathcal U)$ and $z^k_{Aff}(\mathcal U)$.

Formalization targets

Goal: Theorem 4

If $A\ge0$ entrywise, then a feasible affine solution exists and

$$z_{Aff}(\mathcal U)\le 3\sqrt m\cdot z_{Adapt}(\mathcal U).$$

Milestones

1. $\mu_j>0$ for every $j$ (after (38)).
2. Lemma 9. For every complete run of Algorithm $\mathcal A$: $\sum_{j\in J_1}b_j/\mu_j\le\sqrt m$ for all $b\in\mathcal U$, and $b_j\le\beta_j$ for all $j\in J_2$ and $b\in\mathcal U$.
3. Lemma 10. Algorithm $\mathcal A$ executes at most $K\le2\sqrt m$ iterations.
4. Feasibility (48)–(55). For any feasible $(x^*,y^*)$, the solution $\tilde x=3\sqrt m\,x^*$, $\tilde y(b)=\sum_{j\in J_1}\frac{b_j}{\mu_j}y^*(\beta^j)+\hat y$ with $\hat y=\frac{2\sqrt m}{K}\sum_{k=1}^Ky^*(u^k)$ is feasible.
5. Cost (56)–(59). If $t$ bounds the worst-case cost of $(x^*,y^*)$, then $3\sqrt m\cdot t$ bounds that of $(\tilde x,\tilde y)$.

Companion results

• Algorithm $\mathcal A$ has a complete run when $\mathcal U$ is compact.
• Lemma 11. $z(\Pi_1)\le z^k_{Adapt}(\mathcal U)$ and $z(\Pi_2)\le z^k_{Adapt}(\mathcal U)$ for the uncertain and deterministic parts of the $k$-uncertain problem.
• Theorem 5. $z^k_{Aff}(\mathcal U)\le(3\sqrt k+1)\cdot z^k_{Adapt}(\mathcal U)$, the paper's $O(\sqrt k)$ bound with its proof's constant.
• Special case (39)–(45). If $\sum_{j=1}^m b_j/\mu_j\le\sqrt m$ on $\mathcal U$, then $z_{Aff}(\mathcal U)\le\sqrt m\cdot z_{Adapt}(\mathcal U)$.

Significance

Theorem 4 is an upper bound on the price of restricting to affine policies, and Theorem 3 of the same paper shows it is tight up to a constant factor: for every $\delta>0$ there are instances with $A\ge0$ where the gap is $\Omega(m^{1/2-\delta})$. Together they settle the order of the approximation ratio of affine policies for covering-type two-stage problems. Theorem 5 refines the bound to $O(\sqrt k)$ when only $k$ of the $m$ right-hand sides are uncertain, which is the regime of many applications. The construction is also the template for the paper's Theorem 6, a $4\sqrt m$-approximation for general $A$ obtained from a single dominating simplex.

The results are proved in the paper. To the knowledge of this mission, none of them has a machine-checked proof. Formalizing them produces a reusable model of two-stage adaptive linear programs with affine policies, a verified analysis of a greedy covering procedure (Algorithm $\mathcal A$), and an explicit-constant version of an $O(\cdot)$ statement.

Difficulty

The obvious attempt scales the fully adaptable solution at the extreme points $\beta^j$ linearly in $b$: $\tilde y(b)=\sum_j (b_j/\mu_j)\,y^*(\beta^j)$. This is feasible at cost factor $\sqrt m$ only when the scaled sums $\sum_j b_j/\mu_j$ stay below $\sqrt m$ on $\mathcal U$ (condition (39)); in general they can reach $m$, and the linear rule then costs a factor $m$. The difficulty is to handle the coordinates where $\mathcal U$ has large scaled mass. Algorithm $\mathcal A$ isolates them, and the delicate point is the iteration count: each round must add scaled mass above $\sqrt m$, while the total scaled mass that can be absorbed before every coordinate leaves $J_1$ is at most $2m$. A formal proof must also track the algorithm's state through its recursion, because the argmax choices are not unique and the statements must hold for every run.

Formalization scope

Vectors are Fin m → ℝ with the componentwise order, indices are 0-based, and matrices are Matrix (Fin m) (Fin n) ℝ. Nonnegativity of a matrix is stated entrywise. $z_{Adapt}$ and $z_{Aff}$ are infima of the set of worst-case cost bounds achieved by feasible solutions; the goal and Theorem 5 assert the existence of a feasible affine solution, which rules out the trivializing reading in which $z_{Aff}$ is the infimum of an empty set (Lean's junk value $0$) and the inequality holds for free. The goal does not mention $\mu$, $\beta^j$ or Algorithm $\mathcal A$; these appear only in milestones.

$\mu$ and $\beta^j$ are given with their defining properties ($\mu_j$ is the greatest value of $b_j$ on $\mathcal U$, and $\beta^j\in\mathcal U$ with $\beta^j_j=\mu_j$). Algorithm $\mathcal A$ is encoded as a recursion on a choice sequence $u$, with step 2(d) read as $J_1^k=\{j\in J_1^{k-1}: b^k_j<\mu_j\}$. A complete run requires the loop test and the argmax property at each iteration and the failure of the loop test at the end. The milestones on the constructed policy are stated for every feasible $(x^*,y^*)$ and every cost bound $t$, so that no attainment of the optimum is assumed.

Standing assumptions of (1) carried by the goal: $c,d\ge0$; $\mathcal U\subseteq\mathbb R^m_+$ convex, compact, with nonempty interior; feasibility. Milestones drop the ones they do not use. Theorem 5 carries compactness and full-dimensionality of $\mathcal U$, which §5.1 does not repeat but its proof uses through Theorem 4. Lemma 11 assumes that $z^k_{Adapt}(\mathcal U)$ is finite, since the paper's inequality is between extended reals.

A complete development needs: finite-dimensional linear programming facts (existence of optimal solutions is not needed), compactness arguments for the argmax in Algorithm $\mathcal A$, and manipulation of finite sums over Finset. The model of (1) and the analysis of Algorithm $\mathcal A$ are reusable by the companion mission on Theorem 6. Contributions of proofs of any milestone, and of supporting lemmas about the recursion of Algorithm $\mathcal A$, are welcome.

Selected references

• D. Bertsimas and V. Goyal, On the power and limitations of affine policies in two-stage adaptive optimization, Math. Program. Ser. A, 2012. https://doi.org/10.1007/s10107-011-0444-4
• A. Ben-Tal, A. Goryashko, E. Guslitzer and A. Nemirovski, Adjustable robust solutions of uncertain linear programs, Math. Program. 99(2), 351–376, 2004. https://doi.org/10.1007/s10107-003-0454-y
• D. Bertsimas, D. A. Iancu and P. A. Parrilo, Optimality of affine policies in multistage robust optimization, Math. Oper. Res. 35(2), 363–394, 2010.
• U. Feige, K. Jain, M. Mahdian and V. Mirrokni, Robust combinatorial optimization with exponential scenarios, Lect. Notes Comput. Sci. 4513, 439–453, 2007.

Motivation

Two-stage adaptive optimization models decisions made in two steps: a first-stage decision is fixed before an uncertain parameter is revealed, and a second-stage (recourse) decision may then depend on the realized value. In the robust version, the uncertain parameter ranges over an uncertainty set and the objective is the worst-case cost. Such models arise in capacity planning, network design and inventory problems with uncertain demand, where the demand is the right-hand side of the constraints.

Computing an optimal fully adaptable second-stage policy is intractable in general: the recourse is an arbitrary function of the uncertain parameter. The standard tractable surrogate, introduced by Ben-Tal, Goryashko, Guslitzer and Nemirovski (Math. Program. 99, 2004), restricts the recourse to an affine policy $y(b) = Pb + q$, whose optimization is a finite convex program. Practitioners report that affine policies often perform well, which raises the question of when they are optimal and how much they can lose.

Bertsimas and Goyal (Math. Program. Ser. A, 2012) answer this for problems with an uncertain right-hand side. Their Theorem 1 shows that affine policies are optimal when the uncertainty set is a simplex, that is, the convex hull of $m+1$ affinely independent points of $\mathbb R^m_+$. Their Theorem 2, the subject of this mission, shows that this is almost tight: one additional extreme point can make the best affine policy almost twice as expensive as the optimum.

Setting

Let $A \in \mathbb R^{m\times n_1}$, $B \in \mathbb R^{m\times n_2}$, $c \in \mathbb R^{n_1}_+$, $d \in \mathbb R^{n_2}_+$ and let $\mathcal U \subseteq \mathbb R^m_+$ be an uncertainty set. The problem $\Pi_{\mathrm{Adapt}}(\mathcal U)$ is

$$z_{\mathrm{Adapt}}(\mathcal U)=\min\ c^{T}x+\max_{b\in\mathcal U} d^{T}y(b)\quad\text{s.t.}\quad Ax+By(b)\ge b,\ \ x\ge 0,\ \ y(b)\ge 0\quad\forall b\in\mathcal U .$$

Here $x$ is the first-stage decision and $y : \mathcal U \to \mathbb R^{n_2}$ is the second-stage policy; all inequalities between vectors are componentwise. The value $z_{\mathrm{Aff}}(\mathcal U)$ is the same minimum restricted to affine policies $y(b) = Pb + q$ with $P \in \mathbb R^{n_2\times m}$ and $q \in \mathbb R^{n_2}$; an affine policy must still satisfy $Pb + q \ge 0$ for every $b \in \mathcal U$. Always $z_{\mathrm{Adapt}}(\mathcal U) \le z_{\mathrm{Aff}}(\mathcal U)$.

The instance $\mathcal I$ of (6) is defined for $\delta > 0$ and an even integer $m > 200/\delta^2$. It has $n_1 = n_2 = m$, $c = 0$, $d = (1,\dots,1)^T$, $A = 0$, and

$$B_{ij}=\begin{cases}1,& i=j,\\ 1/\sqrt m,& i\ne j,\end{cases}\qquad \mathcal U=\operatorname{conv}\{b^0,b^1,\dots,b^{m+2}\},$$

where $b^0 = 0$, $b^j = e_j$ is the $j$-th unit vector for $j = 1,\dots,m$, $b^{m+1}$ has entries $1/\sqrt m$ in its first $m/2$ coordinates and $0$ in the others, and $b^{m+2}$ has $0$ in its first $m/2$ coordinates and $1/\sqrt m$ in the others. Thus $\mathcal U$ is generated by $m+2$ nonzero points. The last two are also extreme points when $m\ge 6$; for $m=2$ or $4$ they lie in the convex hull of $0,e_1,\dots,e_m$.

For a permutation $\tau$ of $\{1,\dots,m\}$, write $x^\tau = (x_{\tau(1)},\dots,x_{\tau(m)})$. A set $U$ is permutation-invariant with respect to $\tau$ if $x \in U \iff x^\tau \in U$ (Definition 2), and $\Gamma$ is the set (10) of permutations with $i \le m/2 \iff \tau(i) \le m/2$.

Formalization targets

Goal: Theorem 2

$$z_{\mathrm{Aff}}(\mathcal U)>(2-\delta)\cdot z_{\mathrm{Adapt}}(\mathcal U)\qquad\text{for the instance }\mathcal I\text{ of (6), every }\delta>0\text{ and every even }m>200/\delta^2 .$$

Milestones

1. Lemma 1. On $\mathcal I$ there is a feasible fully adaptable solution with worst-case cost $1$, so $z_{\mathrm{Adapt}}(\mathcal U) \le 1$.
2. Lemma 2. The set $\mathcal U$ of (6) is permutation-invariant with respect to every $\tau \in \Gamma$.
3. Lemma 3. There is an optimal affine solution $\hat y(b) = \hat Pb + \hat q$ whose intercept is constant: $\hat q_i = \hat q_j$ for all $i, j$.
4. First Claim of the proof of Theorem 2. For any feasible affine solution with intercept $\hat q \equiv \beta$ and worst-case cost at most $2-\delta$: $\beta \le (2-\delta)/m$.
5. Second Claim. Under the same assumption, $\hat P_{jj} \ge 1 - 2/\sqrt m - 2/m$ for every $j$.
6. Third Claim. Under the same assumption, $\hat P_{ij} \ge -(2-\delta)/m$ for all $i, j$.

Significance

Together with Theorem 1 of the same paper, Theorem 2 delimits exactly where affine policies are optimal for right-hand-side uncertainty: for a simplex they are, and with one more nonzero extreme point the gap can approach $2$. The ratio is measured against the fully adaptable optimum, which is the quantity a practitioner gives up by choosing affine recourse. Later sections of the paper push the same construction to $m^{1/2-\delta}$ for sets with polynomially many extreme points and prove a matching $O(\sqrt m)$ upper bound; Theorem 2 is the simplest member of this family and isolates the mechanism.

The result is proved in the paper; to our knowledge it has not been machine-checked. The mission produces a formal model of two-stage adaptive linear optimization with uncertain right-hand side, the values $z_{\mathrm{Adapt}}$ and $z_{\mathrm{Aff}}$, and a verified lower-bound instance. The symmetrization statement (Lemma 3) is an instance of a general principle, that a convex problem invariant under a group has an invariant optimum, which is reusable well beyond this paper.

Difficulty

The upper bound $z_{\mathrm{Adapt}} \le 1$ requires a feasible policy, which can be written down. The lower bound on $z_{\mathrm{Aff}}$ is a statement about all affine policies, an $m^2 + m$ dimensional family, and cannot be checked policy by policy. The obvious attempt, testing an arbitrary affine policy against a few extreme points, fails because an asymmetric policy can trade cost between coordinates. The argument needs an optimal policy that is symmetric, which in turn needs both the existence of an optimal affine solution (attainment of a minimum over a non-compact set of policies) and the invariance of the instance under the permutations of $\Gamma$ and the swap of the two halves. Without the attainment step, a contradiction for every policy of cost at most $2-\delta$ yields only $z_{\mathrm{Aff}} \ge 2-\delta$, not the strict inequality.

Formalization scope

Vectors are Fin m → ℝ with the componentwise order, matrices are Matrix (Fin m) (Fin n) ℝ, $Bx$ is B *ᵥ x and $d^Ty$ is d ⬝ᵥ y. Indices are 0-based: the paper's coordinate $i$ is index $i - 1$, so "$i \le m/2$" is (i : ℕ) < m / 2, with natural-number division (exact since $m$ is even). $x^\tau$ is x ∘ τ for τ : Equiv.Perm (Fin m).

$z_{\mathrm{Adapt}}$ and $z_{\mathrm{Aff}}$ are the infima of the sets of real numbers $t$ for which some feasible (respectively feasible affine) solution satisfies $c^Tx + d^Ty(b) \le t$ for all $b \in \mathcal U$. This epigraph form avoids a supremum of a possibly unbounded function; on an infeasible instance the infimum would be Lean's junk value $0$, which is why Lemma 1 also asserts the existence of the feasible solution of cost $1$. Optimal solutions are stated by IsOptimalAff: feasible, with worst-case cost bounded by every bound achieved by any feasible affine solution. Affine policies must be nonnegative on $\mathcal U$, as in (1).

The instance is concrete, so the standing assumptions of (1) (nonnegative costs, compact convex full-dimensional $\mathcal U \subseteq \mathbb R^m_+$, feasibility) are properties of the data rather than hypotheses. The goal adds no hypothesis to the page: $\delta > 0$, $m$ even and $m > 200/\delta^2$. For $\delta \ge 2$ the statement is easy but still true. The three Claims are stated for any feasible affine solution with constant intercept and worst-case cost at most $2-\delta$, which is exactly what the paper's proof uses about the symmetric optimal solution under its contradiction hypothesis (12). Lemma 1 drops the unused hypothesis $m > 200/\delta^2$. Definition 2 prints "$x \in P \iff x^\tau \in P$"; the formalization reads $P$ as the set $U$.

Replacing $z_{\mathrm{Aff}}$ by the cost of one particular affine policy, stating the goal with $\ge$, or bounding only policies with constant intercept would not be Theorem 2, and is ruled out: the goal compares the two optimal values with a strict inequality.

A complete development needs convex hulls of finite point sets in Fin m → ℝ, the existence of a minimizer for the affine problem (a linear program in $(x, P, q)$ with infinitely many constraints indexed by $\mathcal U$, reducible to the extreme points), averaging of optimal solutions over a permutation group, and elementary estimates with $\sqrt m$. Contributions of general lemmas on attainment of semi-infinite linear programs and on symmetrization of convex programs are welcome.

Selected references

• D. Bertsimas, V. Goyal, On the power and limitations of affine policies in two-stage adaptive optimization, Mathematical Programming Ser. A (online first 2011; received 31 Oct 2009, accepted 17 Jan 2011). https://doi.org/10.1007/s10107-011-0444-4
• A. Ben-Tal, A. Goryashko, E. Guslitzer, A. Nemirovski, Adjustable robust solutions of uncertain linear programs, Mathematical Programming 99 (2004) 351–376. https://doi.org/10.1007/s10107-003-0454-y
• D. Bertsimas, D. A. Iancu, P. A. Parrilo, Optimality of affine policies in multistage robust optimization, Mathematics of Operations Research 35 (2010) 363–394. https://doi.org/10.1287/moor.1100.0444

Motivation

Large-scale nonsmooth convex problems, such as minimising a Lipschitz convex function over a probability simplex with millions of coordinates, are routinely solved by first-order methods that use one subgradient per iteration. The classical projected subgradient method reaches accuracy $\varepsilon$ after $O(L^2 R^2/\varepsilon^2)$ iterations, where $L$ and $R$ are measured in the Euclidean norm; on the simplex this hides a factor of order $n$ in the dimension. Nemirovski and Yudin's mirror descent algorithm (MDA) replaces the Euclidean geometry by one adapted to the feasible set and, on the simplex, reduces the dimension dependence to $\ln n$.

Beck and Teboulle (Oper. Res. Lett. 31 (2003) 167–175, doi:10.1016/S0167-6377(02)00231-6) showed that mirror descent is a projected subgradient method in which the squared Euclidean distance is replaced by a Bregman-type distance $B_\psi$. This viewpoint gives a short convergence proof, and with the entropy as $\psi$ it yields a fully explicit method on the simplex, the entropic mirror descent algorithm (EMDA), the same multiplicative update that underlies exponentiated-gradient and Hedge-type algorithms in online learning.

Timeline. Nemirovski and Yudin (1983) introduce mirror descent with a $O(\sqrt{\ln n}/\sqrt k)$ rate on the simplex. Ben-Tal, Margalit and Nemirovski (SIAM J. Optim. 12 (2001)) analyse MDA with the $\ell_p$ potential $\tfrac12\|x\|_p^2$, $p = 1 + 1/\ln n$, whose conjugate requires a one-dimensional root-finding at each step. Beck and Teboulle (2003) derive MDA as a nonlinear projected subgradient method (SANP), prove its efficiency estimate for an arbitrary norm, and show that the entropy gives the same $\sqrt{2\ln n}\,L_f/\sqrt k$ rate with a closed-form update.

Setting

Let $E$ be $\mathbb R^n$ with an arbitrary norm $\|\cdot\|$, and $\|z\|_* = \max\{\langle x, z\rangle : \|x\| \le 1\}$ the dual norm. The problem is $\min\{f(x) : x \in X\}$ under Assumption A: $X$ is closed and convex; $f$ is convex on $X$ and Lipschitz there, $|f(x) - f(y)| \le L_f\|x - y\|$; $f$ has a minimiser $x^* \in X$; and a subgradient $f'(x)$ can be computed at every $x \in X$.

Let $\psi : X \to \mathbb R$ be strongly convex with parameter $\sigma > 0$ and differentiable. The distance-like function (3.10) is

$$B_\psi(x, y) = \psi(x) - \psi(y) - \langle x - y, \nabla\psi(y)\rangle .$$

The subgradient algorithm with nonlinear projections (SANP, (3.11)) starts from $x^1$ and sets, with step sizes $t_k > 0$,

$$x^{k+1} = \operatorname*{argmin}_{x \in X}\Big\{\langle x, f'(x^k)\rangle + \tfrac{1}{t_k} B_\psi(x, x^k)\Big\}.$$

With $\psi = \tfrac12\|\cdot\|_2^2$ this is the projected subgradient method.

On the unit simplex $\Delta = \{x \in \mathbb R^n : x \ge 0,\ \sum_j x_j = 1\}$ take the entropy $\psi_e(x) = \sum_j x_j \ln x_j$ (5.27), with $0\ln0 = 0$. SANP becomes the entropic descent algorithm (EDA):

$$x^{k+1}_j = \frac{x^k_j\,e^{-t_k f'_j(x^k)}}{\sum_{i=1}^n x^k_i\,e^{-t_k f'_i(x^k)}} .$$

Formalization targets

Goal: Theorem 5.1 (p. 174)

If $f$ is convex and $L_f$-Lipschitz on $\Delta$ for $\|\cdot\|_1$, with subgradients satisfying $\|f'(x)\|_\infty \le L_f$, and the EDA is started at $x^1 = n^{-1}e$ with step $t = \sqrt{2\ln n}/(L_f\sqrt k)$ for a horizon $k \ge 1$, then

$$\min_{1 \le s \le k} f(x^s) - \min_{x \in \Delta} f(x) \le \frac{\sqrt{2\ln n}\;L_f}{\sqrt k}.$$

The general estimate: Theorems 4.1 and 4.2 (pp. 171–172)

For any norm, any $\sigma$-strongly convex $\psi$ and any SANP run,

$$\min_{1 \le s \le k} f(x^s) - \min_X f \le \frac{B_\psi(x^*, x^1) + (2\sigma)^{-1}\sum_{s=1}^k t_s^2\|f'(x^s)\|_*^2}{\sum_{s=1}^k t_s},$$

and with the optimal constant step this gives $L_f\sqrt{2B_\psi(x^*, x^1)/\sigma}/\sqrt k$.

The milestones follow the paper's proof: the three-point identity (Lemma 4.1), the optimality condition (4.16), the lower bound $B_\psi \ge \tfrac\sigma2\|\cdot\|^2$, the one-step inequality (4.21), Theorem 4.1(a), Proposition 4.1 (optimal step), Theorem 4.2 and its version with an upper bound on $B_\psi(x^*, x^1)$; then for the simplex, the 1-strong convexity of $\psi_e$ for $\|\cdot\|_1$ (Proposition 5.1(a), Remark 5.1), the bound $B_{\psi_e}(x^*, n^{-1}e) \le \ln n$ (Proposition 5.1(c)), and the identification of the EDA with SANP.

Significance

The result shows that for nonsmooth convex minimisation over the simplex an explicit first-order method attains accuracy $\varepsilon$ in $O(L_f^2\ln n/\varepsilon^2)$ iterations, with $L_f$ measured in the $\ell_\infty$ dual norm. The general estimate of Theorem 4.2 applies to any norm and any strongly convex potential, and is the template for later analyses of mirror descent, its stochastic and online variants, and mirror-prox methods.

Formalizing the paper produces a norm-agnostic, machine-checked proof of the mirror descent efficiency estimate, in which subgradients are dual-space objects and the dual norm is explicit, and a verified link between the entropy, the $\ell_1$ geometry and the multiplicative-weights update. To our knowledge none of these statements is formalized; existing formal developments of online mirror descent work in Euclidean space with Legendre potentials and bound regret for linear losses, which is a different statement.

Difficulty

The algebra of Theorem 4.1 is short, but it rests on facts that are not available off the shelf. The first-order optimality condition (4.16) must be derived for a minimiser over a convex set without assuming the set has interior (the simplex has none in $\mathbb R^n$). The bound $B_\psi(u, y) \ge \tfrac\sigma2\|u - y\|^2$ must be obtained from the chord definition of strong convexity for an arbitrary norm. On the simplex, strong convexity of the entropy with respect to $\|\cdot\|_1$ is a form of Pinsker's inequality, and it must hold on the closed simplex, where the entropy is not differentiable at the boundary. Finally, the EDA must be shown to be the exact minimiser of the SANP subproblem over $\Delta$, which is a Gibbs variational principle. A tempting shortcut, working throughout in Euclidean space, fails: it changes the dual norm of the subgradients from $\ell_\infty$ to $\ell_2$ and the strong convexity constant of the entropy, and loses the $\ln n$ rate.

Formalization scope

Sections 3–4 live in a general real normed space; a subgradient is a continuous linear functional, $\langle u, f'(x)\rangle$ is its value at $u$, and $\|\cdot\|_*$ is the operator norm. $\nabla\psi$ is the Fréchet derivative. Iterates are indexed from $1$. A SANP run is a predicate on sequences: each step size is positive, each iterate lies in $X$, $\psi$ is differentiable there, and the next iterate minimises the SANP objective. This encodes the paper's standing assumption that SANP is well defined, and replaces "$X$ has nonempty interior" and "$x^1 \in \operatorname{int} X$". Section 5 works on $\mathbb R^n$ as functions $\{1, \dots, n\} \to \mathbb R$ with explicit $\ell_1$ and $\ell_\infty$ sums; $\operatorname{int}\Delta$ is the relative interior, and the entropy formula is evaluated on $\Delta$ only. "$\min_{1\le s\le k} f(x^s) - \min_X f \le R$" is stated as the existence of $s \in \{1, \dots, k\}$ with $f(x^s) - f(x^*) \le R$.

Added hypotheses, each disclosed in the item: a bound $\|f'(x)\|_* \le L_f$ on the oracle (used by the proofs of Theorems 4.1(b), 4.2 and 5.1, not implied by the Lipschitz condition for subgradients relative to $X$); $D^{-1}b > 0$ in Proposition 4.1, without which the proposition as printed is false; $L_f > 0$ in the step sizes. The step sizes of (4.23) and of the EDA are constant over a fixed horizon $k$, which is what the proof chooses; Theorem 5.1 is stated with $L_f$, since the free index in the printed bound (5.28) cannot be bound, and $L_f$ is what the proof yields.

Trivializing formalizations are ruled out: $B_\psi$ is never evaluated where fderiv is a junk value (the run requires differentiability at every iterate), the SANP step is never chosen by Classical.epsilon, the bound of Theorem 5.1 is not stated with a maximum of $\|f'(x^s)\|_\infty$ over the run, and the step is not an anytime schedule $t_s \propto 1/\sqrt s$.

A complete development needs first-order optimality conditions over convex sets, strong convexity and Bregman distances in normed spaces, Pinsker-type inequalities for finite distributions, and the Gibbs variational principle. These are reusable beyond this mission; proofs of any milestone, and general lemmas that serve several of them, are welcome.

Selected references

• A. Beck, M. Teboulle, Mirror descent and nonlinear projected subgradient methods for convex optimization, Oper. Res. Lett. 31 (2003) 167–175. https://doi.org/10.1016/S0167-6377(02)00231-6
• A. Ben-Tal, T. Margalit, A. Nemirovski, The ordered subsets mirror descent optimization method with applications to tomography, SIAM J. Optim. 12 (2001) 79–108. https://doi.org/10.1137/S1052623499354564
• A. Nemirovsky, D. Yudin, Problem Complexity and Method Efficiency in Optimization, Wiley, 1983.
• G. Chen, M. Teboulle, Convergence analysis of a proximal-like minimization algorithm using Bregman functions, SIAM J. Optim. 3 (1993) 538–543. https://doi.org/10.1137/0803026