Let the objective function <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$ f$</EquationSource> <EquationSource Format="MATHML"><math> <mi>f</mi> </math></EquationSource> </InlineEquation> depends on the target variable <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$ \varvec{x}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> </math></EquationSource> </InlineEquation> along with a nuisance variable <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$ \varvec{s}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">s</mi> </mrow> </math></EquationSource> </InlineEquation>: <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$ f(\varvec{\upsilon }) = f(\varvec{x},\varvec{s}) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>f</mi> <mo stretchy="false">(</mo> <mrow> <mi mathvariant="bold-italic">υ</mi> </mrow> <mo stretchy="false">)</mo> <mo>=</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mo>,</mo> <mrow> <mi mathvariant="bold-italic">s</mi> </mrow> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Consider the task of identifying the marginal solution <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$ \varvec{x}^{}= \mathop {\text {arginf}}\nolimits _{\varvec{x}} \inf _{\varvec{s}} f(\varvec{x},\varvec{s}) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mrow> <mrow /> <mo>∗</mo> </mrow> </msup> <mo>=</mo> <msub> <mtext>arginf</mtext> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> </msub> <msub> <mo movablelimits="true">inf</mo> <mrow> <mi mathvariant="bold-italic">s</mi> </mrow> </msub> <mi>f</mi> <mrow> <mo stretchy="false">(</mo> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mo>,</mo> <mrow> <mi mathvariant="bold-italic">s</mi> </mrow> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. This paper discusses three related problems. The plug-in approach, widely used, e.g., in inverse problems, suggests using a preliminary guess (pilot) <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$ \widehat{\varvec{s}} $</EquationSource> <EquationSource Format="MATHML"><math> <mover accent="true"> <mrow> <mi mathvariant="bold-italic">s</mi> </mrow> <mo stretchy="false">^</mo> </mover> </math></EquationSource> </InlineEquation> and apply the solution of the partial optimization <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$ \widehat{\varvec{x}} = \mathop {\text {arginf}}\nolimits _{\varvec{x}} f(\varvec{x},\widehat{\varvec{s}}) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mo stretchy="false">^</mo> </mover> <mo>=</mo> <msub> <mtext>arginf</mtext> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> </msub> <mi>f</mi> <mrow> <mo stretchy="false">(</mo> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mo>,</mo> <mover accent="true"> <mrow> <mi mathvariant="bold-italic">s</mi> </mrow> <mo stretchy="false">^</mo> </mover> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. The main question to address within this approach is the required quality of the pilot, ensuring the prescribed accuracy of <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$ \widehat{\varvec{x}} $</EquationSource> <EquationSource Format="MATHML"><math> <mover accent="true"> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mo stretchy="false">^</mo> </mover> </math></EquationSource> </InlineEquation>. The popular alternating optimization approach suggests the following procedure: given a starting guess <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$ \varvec{x}_{0} $</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mn>0</mn> </msub> </math></EquationSource> </InlineEquation>, for <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$ t \ge 1 $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, define <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$ \varvec{s}_{t} = \mathop {\text {arginf}}\nolimits _{\varvec{s}} f(\varvec{x}_{t-1},\varvec{s}) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mrow> <mi mathvariant="bold-italic">s</mi> </mrow> <mi>t</mi> </msub> <mo>=</mo> <msub> <mtext>arginf</mtext> <mrow> <mi mathvariant="bold-italic">s</mi> </mrow> </msub> <mi>f</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mrow> <mi>t</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mrow> <mi mathvariant="bold-italic">s</mi> </mrow> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, and then <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$ \varvec{x}_{t} = \mathop {\text {arginf}}\nolimits _{\varvec{x}} f(\varvec{x},\varvec{s}_{t}) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mi>t</mi> </msub> <mo>=</mo> <msub> <mtext>arginf</mtext> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> </msub> <mi>f</mi> <mrow> <mo stretchy="false">(</mo> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mo>,</mo> <msub> <mrow> <mi mathvariant="bold-italic">s</mi> </mrow> <mi>t</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. The main question here is the set of conditions ensuring a convergence of <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$ \varvec{x}_{t} $</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mi>t</mi> </msub> </math></EquationSource> </InlineEquation> to <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$ \varvec{x}^{}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mrow> <mrow /> <mo>∗</mo> </mrow> </msup> </math></EquationSource> </InlineEquation>. Finally, the paper discusses an interesting connection between marginal optimization and sup-norm estimation. The basic idea is to consider one component of the variable <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$ \varvec{\upsilon }$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">υ</mi> </mrow> </math></EquationSource> </InlineEquation> as a target and the rest as nuisance. In all cases, we provide accurate closed-form results under realistic assumptions. The results are illustrated by an example for Bradley–Terry–Luce model of ranking from pairwise comparisons.

Convergence of Alternating Minimization and Sup-norm Accuracy Bounds in Perturbed Optimization

期刊论文
发表日期：

2026年8月1日

查看全文

Vladimir Spokoiny

摘要

Let the objective function $ f$ $f$ depends on the target variable $ \varvec{x}$ $x$ along with a nuisance variable $ \varvec{s}$ $s$ : $ f(\varvec{\upsilon }) = f(\varvec{x},\varvec{s}) $ $f (υ) = f (x, s)$ . Consider the task of identifying the marginal solution $ \varvec{x}^{*}= \mathop {\text {arginf}}\nolimits _{\varvec{x}} \inf _{\varvec{s}} f(\varvec{x},\varvec{s}) $ $x^{*} = {arginf}_{x} {inf}_{s} f (x, s)$ . This paper discusses three related problems. The plug-in approach, widely used, e.g., in inverse problems, suggests using a preliminary guess (pilot) $ \widehat{\varvec{s}} $ $\hat{s}$ and apply the solution of the partial optimization $ \widehat{\varvec{x}} = \mathop {\text {arginf}}\nolimits _{\varvec{x}} f(\varvec{x},\widehat{\varvec{s}}) $ $\hat{x} = {arginf}_{x} f (x, \hat{s})$ . The main question to address within this approach is the required quality of the pilot, ensuring the prescribed accuracy of $ \widehat{\varvec{x}} $ $\hat{x}$ . The popular alternating optimization approach suggests the following procedure: given a starting guess $ \varvec{x}_{0} $ $x_{0}$ , for $ t \ge 1 $ $t \geq 1$ , define $ \varvec{s}_{t} = \mathop {\text {arginf}}\nolimits _{\varvec{s}} f(\varvec{x}_{t-1},\varvec{s}) $ $s_{t} = {arginf}_{s} f (x_{t - 1}, s)$ , and then $ \varvec{x}_{t} = \mathop {\text {arginf}}\nolimits _{\varvec{x}} f(\varvec{x},\varvec{s}_{t}) $ $x_{t} = {arginf}_{x} f (x, s_{t})$ . The main question here is the set of conditions ensuring a convergence of $ \varvec{x}_{t} $ $x_{t}$ to $ \varvec{x}^{*}$ $x^{*}$ . Finally, the paper discusses an interesting connection between marginal optimization and sup-norm estimation. The basic idea is to consider one component of the variable $ \varvec{\upsilon }$ $υ$ as a target and the rest as nuisance. In all cases, we provide accurate closed-form results under realistic assumptions. The results are illustrated by an example for Bradley–Terry–Luce model of ranking from pairwise comparisons.