Extracting Dual Solutions via Primal Optimizers

We give a general framework which obtains an $ϵ$-optimal solution to (D) via a sequence of calls to two black-box oracles: (i) an oracle for obtaining an $ϵ$-optimal point of a regularized version of (P), and (ii) an oracle for obtaining a dual best response $y_x≔{argmax}_{y\in 𝒴}\psi (x,y)$ for a given $x\in 𝒳$. In particular, we show it is always possible to obtain an $ϵ$-optimal point to (D) with at most a logarithmic number of calls to each of these oracles, where the regularized primal optimization oracle is always called to an accuracy of $ϵ$ over a logarithmic factor. We also provide an alternate scheme (or more specifically choice of parameters) for applications where the cost of obtaining an $ϵ$-optimal point of the regularized primal problem decreases sufficiently as the regularization level increases. In such cases, e.g., in our stationary point application, it is possible to avoid even logarithmic factor increases in computational complexity for approximately solving (D) relative to the complexity of approximately solving (P).

In this application, $\psi (x,y)≔x^{\top }Ay$ for a matrix $A\in {ℝ}^{d\times n}$, $𝒴$ is the simplex ${\mathrm{\Delta }}^n$, and $𝒳$ is either the simplex ${\mathrm{\Delta }}^d$ or the unit Euclidean ball $B^d$. Recently, [8] gave a new state-of-the-art runtime in certain parameter regimes of $\tilde{O}(nd+n{(d/ϵ)}^{2/3}+d{ϵ}^{-2})$ for obtaining an expected $ϵ$-optimal point for the primal problem (P) for this setup. However, unlike previous algorithms for bilinear matrix games (see Section 1.3 for details), their algorithm does not return an $ϵ$-optimal solution for the dual (D), and their runtime is not symmetric in the dimensions $n$ and $d$. As a result, it was unclear whether the same runtime is achievable for obtaining an $ϵ$-optimal solution of the dual (D). We resolve this question by applying our general framework to achieve an expected $ϵ$-optimal point of (D) with runtime $\tilde{O}(nd+n{(d/ϵ)}^{2/3}+d{ϵ}^{-2})$. We then observe (see Corollary 22) that in the setting where $𝒳={\mathrm{\Delta }}^d$, our result can equivalently be viewed as a new state-of-the-art runtime of $\tilde{O}(nd+d{(n/ϵ)}^{2/3}+n{ϵ}^{-2})$ for obtaining an $ϵ$-optimal point of the primal (P) due to the symmetry of $\psi$ and the constraint sets.

In this application, $\psi (x,y)≔{\sum }_{i=1}^n{y}_i{f}_i(x)$ for convex, bounded, and Lipschitz loss functions $f_i:{ℝ}^d\to ℝ$, $𝒳$ is a convex, compact set, and $𝒴≔\{y\in {\mathrm{\Delta }}^n:{\Vert y\Vert }_{\mathrm{\infty }}\le \frac{1}{\alpha n}\}$ is the CVaR at level $\alpha$ uncertainty set for $\alpha \in [1/n,1]$. The primal (P) is a canonical and well-studied DRO problem, and corresponds to the average of the top $\alpha$ fraction of the losses. We consider this problem given access to a first-order oracle that, when queried at $x\in {ℝ}^d$ and $i\in [n]$, outputs $(f_i(x),\nabla f_i(x))$. Ignoring dependencies other than $\alpha$, the target accuracy $ϵ>0$, and the number of losses $n$ for brevity, [29] gave a matching upper and lower bound (up to logarithmic factors) of $\tilde{O}({\alpha }^{-1}{ϵ}^{-2})$ queries to obtain an expected $ϵ$-optimal point of the primal (P). However, the best known query complexity for obtaining an expected $ϵ$-optimal point of the dual (D) was $\tilde{O}(n{ϵ}^{-2})$ prior to this paper (see Section 1.3 for details). Applying our general framework to this setting, we obtain an algorithm with a new state-of-the-art query complexity of $\tilde{O}({\alpha }^{-1}{ϵ}^{-2}+n)$ for obtaining an expected $ϵ$-optimal point of the dual (D). In particular, note that this complexity is nearly linear in $n$ when $ϵ\ge {(\alpha n)}^{-2}$.

In this application, we show that our framework yields an alternative optimal approach for computing an approximate critical point of a smooth convex function given a gradient oracle. Specifically, for $\gamma >0$ and convex and $\beta$-smooth $h:{ℝ}^n\to ℝ$, in Section 5, we give an algorithm which computes $x\in {ℝ}^n$ such that ${\Vert \nabla h(x)\Vert }_2\le \gamma$ using $O\left(\sqrt{\beta \mathrm{\Delta }}/\gamma \right)$ gradient queries, where $\mathrm{\Delta }≔h(x_0)-{inf}_{x\in {ℝ}^n}h(x)$ is the initial suboptimalityf. While this optimal complexity has been achieved before [24, 37, 15, 28, 27], that we achieve it is a consequence of our general framework illustrates its broad applicability.

For this application, we instantiate our framework with $\psi (x,y)≔⟨x,y⟩-h^{\ast }(y)$, where $h^{\ast }:{ℝ}^n\to ℝ$ denotes the convex conjugate of $h$. (For reasons discussed in Section 5, we actually first substitute $h$ for an appropriately regularized version of $h$, call it $f$, before applying the framework, but the following discussion still holds with respect to $f$.) This objective function $\psi$ is known as the Fenchel game and has been used in the past to recover classic convex optimization algorithms (e.g., the Frank-Wolfe algorithm and Nesterov’s accelerated methods) via a minimax framework [1, 43, 12, 23]. In the Fenchel game, a dual best response corresponds to a gradient evaluation:

and we show that approximately optimal points for the dual objective (D) must have small norm. As a result, obtaining an approximately optimal dual point $y$ as a best response to a primal point $x$ yields a bound on the norm of $y=\nabla f(x)$. Furthermore, we note that in this setting, adding regularization to $\psi$ with respect to an appropriate choice of distance-generating function (namely $h^{\ast }$) is equivalent to rescaling and recentering the primal function $f$, as well as the point at which a gradient is taken in the dual best response computation (cf. Lemma 14 in the full version). Thus, the properties of the Fenchel game extend naturally to appropriately regularized versions of $\psi$.

In particular, Lemma 1 suggests the following approach: Define “dual-regularized” versions of $\psi ,\varphi ,f$ as follows for $\lambda >0$ and $y_0\in 𝒴$:

(Here, the subscript 1 denotes one level of regularization and will be extended later.) For any $x\in 𝒳$, note that $-{\psi }_1(x,\cdot )$ is $\lambda$-strongly convex relative to $r$, in which case Lemma 1 applied to ${\psi }_1$ yields

for $y_1^{\star }≔{argmax}_{y\in 𝒴}{\varphi }_1(y)$, $x_1^{\star }\in {argmin}_{x\in 𝒳}{f}_1(x)$, and $y_x≔{argmax}_{y\in 𝒴}{\psi }_1(x,y)$. Then note

where the first inequality follows since $\varphi \ge {\varphi }_1$ pointwise. Then by the $L$-Lipschitzness of $\varphi$ and ${\mu }_r$-strong convexity of $r$, it is straightforward to bound the suboptimality of $y_x$ as

Consequently, an $ϵ$-optimal point for (D) can be obtained via our oracles as follows: Set $\lambda \leftarrow \frac{ϵ}{2V_{y_0}\left(y^{\star }\right)}$, and use the DRPO oracle on the regularized primal problem to obtain $x\in 𝒳$ such that

Then the best response to $x$ with respect to ${\psi }_1$, namely $y_x≔{argmax}_{y\in 𝒴}{\psi }_1(x,y)$, is $ϵ$-optimal by (3). However, a typical setting in our applications is $V_{y_0}\left(y^{\star }\right)=\mathrm{\Omega }(1)$, ${\mu }_r=1$, and $L\ge 1$, in which case ensuring (4) requires solving the regularized primal problem to $O({ϵ}^3)$ error.

To lower the accuracy requirements, we apply dual regularization recursively. A key issue with the preceding argument is that it required a nontrivial bound on $V_{y_0}\left(y^{\star }\right)$. However, it provided us with a nontrivial bound $(\text{<a href="\#S1.E1" title="Equation 1 ‣ A first try ‣ 1.2 Overview of the framework and analysis ‣ 1 Introduction ‣ Extracting Dual Solutions via Primal Optimizers" class="ltx\_ref ltx\_font\_italic"><span class="ltx\_text ltx\_ref\_tag">1</span></a>})$ on $V_{y_x}\left(y_1^{\star }\right)$, the “level-one equivalent” of $V_{y_0}\left(y^{\star }\right)$. This suggests solving $f_1$ to lower accuracy while still obtaining a bound on $V_{y_x}\left(y_1^{\star }\right)$ due to (1), and then adding regularization centered at $y_x$ with a larger value of $\lambda$. Indeed, our framework recursively repeats this process until the total regularization is large enough so that (a term similar to) the right-hand side of (3) can be bounded by $ϵ$, despite never needing to solve a regularized primal problem to high accuracy.

To more precisely describe our approach, let ${\psi }_0≔\psi ,f_0≔f,{\varphi }_0≔\varphi$. Over iterations $k=1,2,\mathrm{\dots },K$, our framework implicitly constructs a sequence of convex-concave games ${\psi }_k:{ℝ}^d\times {ℝ}^n\to ℝ$, along with corresponding primal and dual functions $f_k:𝒳\to ℝ$ and ${\varphi }_k:𝒴\to ℝ$ respectively, as follows:

Here, ${\left({\lambda }_k\in {ℝ}_{>0}\right)}_{k=0}^{K-1}$ is a dual-regularization schedule given as input to the framework, and ${\left(y_k\in 𝒴\right)}_{i=0}^K$ is a sequence of dual-regularization “centers” generated by the algorithm, with $y_0$ given as input. For $k\in \left\{0\right\}\cup [K]$, it will be useful to let $y_k^{\star }$ denote a maximizer of ${\varphi }_k$ over $𝒴$ and $x_k^{\star }$ denote a minimizer of $f_k$ over $𝒳$, with $y_0^{\star }≔y^{\star }$ and $x_0^{\star }≔x^{\star }$ in particular.

Over the $K$ rounds of recursive dual regularization, we aim to balance two goals:

• $\mathrm{■}$

  On the one hand, we want ${\lambda }_k$ to increase quickly so that $-{\psi }_k(x,\cdot )$ is very strongly convex relative to $r$, thereby allowing us to apply Lemma 1 with a larger strong convexity constant.

• $\mathrm{■}$

  On the other hand, we want to maintain the invariant that, roughly speaking, $y_k^{\star }$ is always $ϵ/2$-optimal for the original dual $\varphi$. Indeed, we were constrained in choosing $\lambda$ in (2) to be on the order of $ϵ/V_{y_0}\left(y^{\star }\right)$ to ensure $y_1^{\star }$ is $ϵ/2$-optimal for $\varphi$. A similar “constraint” on the dual-regularization schedule ${({\lambda }_k)}_{k=0}^{K-1}$ appears when (2) is extended to additional levels of regularization. This prevents us from increasing ${\lambda }_k$ too quickly.

In all the applications in this paper we choose ${\lambda }_k\approx 2{\lambda }_{k-1}$. ${\lambda }_0$ typically must remain on the order of $ϵ/V_{y_0}\left(y^{\star }\right)$ due to the second point.

Pseudocode of the framework is given in Algorithm 1. Each successive dual-regularization center $y_k$ is computed via the DRBR oracle (Line 5) as a best response to a primal point $x_k$ obtained via the DRPO oracle (Line 4). In Section 3, we generalize Algorithm 1 (cf. Algorithm 2) in several ways: (i) we allow for stochasticity in the DRPO oracle; (ii) we allow for distance-generating functions $r$ such that $domr\ne {ℝ}^n$; (iii) we give different but equivalent characterizations of $x_k$ and $y_k$ which facilitate the derivation of explicit expressions for the DRPO and DRBR oracles in applications.

Theorem 2 is our main result for Algorithm 1. We then instantiate Theorem 2 with two illustrative choices of parameters in Corollaries 5 and 7, and defer the proofs of the latter to their general versions in Section 3. All of the remarks below (Remarks 3, 5, 7) are stated with reference to the specialized results in this section (Theorem 2 and Corollaries 4, 6 resp.), but extend immediately to the corresponding general versions (Theorem 15 and Corollaries 16, 17 resp.).

Our main contribution can be viewed as a black-box reduction from (regularized) primal optimization to dual optimization. Similar black-box reductions exist in the optimization literature. For example, [3] develops reductions between various fundamental classes of optimization problems, e.g., strongly convex optimization and smooth optimization. In a similar vein, the line of work [30, 18, 7] reduces convex optimization to approximate proximal point computation (i.e., regularized minimization).

Consider the bilinear objective $\psi (x,y)=x^{\top }Ay$ where $𝒳$ and $𝒴$ are either the simplex, ${\mathrm{\Delta }}^k≔\{x\in {ℝ}_{\ge 0}^k:{\Vert x\Vert }_1=1\}$, or the Euclidean ball, $B^k≔\{x\in {ℝ}^k:{\Vert x\Vert }_2\le 1\}$. State-of-the-art methods in regard to runtime for obtaining an approximately optimal primal and/or dual solution can be divided into second-order interior point methods [11, 42] and stochastic first-order methods [22, 10, 9, 8]; see Table 2 in [8] for a summary of the best known runtimes as well as other references. Of importance to this paper, all state-of-the-art algorithms other than that of [8] are either (i) primal-dual algorithms which return both an $ϵ$-optimal primal and dual solution simultaneously, and/or (ii) achieve runtimes which are symmetric in the primal dimension $d$ and dual dimension $n$, meaning the cost of obtaining an $ϵ$-optimal dual solution is the same as that of obtaining an $ϵ$-optimal primal solution. The algorithm of [8], on the other hand, only returns an $ϵ$-optimal primal point and further has a runtime which is not symmetric in $n$ and $d$ (see the footnote on the first page of that paper). As a result, solving the dual by simply swapping the roles of the primal and dual variables may be more expensive than solving the primal. (In fact, swapping the variables in this way may not even always be possible without further modifications due to restrictions on the constraint sets.)

The DRO objectives we study are of the form $\psi (x,y)={\sum }_{i=1}^n{y}_i{f}_i(x)$, where the functions $f_i:{ℝ}^d\to ℝ$ are convex, bounded, and Lipschitz, and $𝒴$, known as the uncertainty set, is a subset of the simplex. This objective corresponds to a robust version of the empirical risk minimization (ERM) objective where instead of taking an average over the losses (namely, $y_i$ is fixed at $1/n$), larger losses may be given more weight. In particular, in this paper we focus on a canonical DRO setting, CVaR at level $\alpha$, where the uncertainty set is given by $𝒴≔\{y\in {\mathrm{\Delta }}^n:{\Vert y\Vert }_{\mathrm{\infty }}\le \frac{1}{\alpha n}\}$ for a choice of $\alpha \in [1/n,1]$. CVaR DRO, along with its generalization $f$-divergence DRO, has been of significant interest over the past decade; see [29, 5, 13, 32, 16] and the references therein. [29] is the most relevant to this paper – omitting parameters other than $\alpha$, the number of losses $n$, and the target accuracy $ϵ>0$, they give a matching upper and lower bound (up to logarithmic factors) of $\tilde{O}({\alpha }^{-1}{ϵ}^{-2})$ first-order queries of the form $(\nabla f_i(x),f_i(x))$ to obtain an expected $ϵ$-optimal point of the primal objective. Their upper bound is achieved by a stochastic gradient method where the gradient estimator is based on a multilevel Monte Carlo (MLMC) scheme [19, 20]. However, the best known complexity for obtaining an expected $ϵ$-optimal point of the dual of CVaR at level $\alpha$ is $O(n{ϵ}^{-2})$ via a primal-dual method based on [33]; see also [13, 32] as well as [5, Appendix A.1], the last of which obtains complexity $\tilde{O}(n{ϵ}^{-2})$ in the more general setting of the uncertainty set being an $f$-divergence ball.

For $\gamma >0$, convex and $\beta$-smooth $h:{ℝ}^n\to ℝ$ with global minimum $z^{\star }$, and initialization point $z_0$, consider the problem of computing a point $z$ such that ${\Vert \nabla h(z)\Vert }_2\le \gamma$. Two worst-case optimal gradient query complexities for this problem exist in the literature: $O\left(\sqrt{\beta (h(z_0)-h(z^{\star }))}/\gamma \right)$ and $O\left(\sqrt{\beta {\Vert z_0-z^{\star }\Vert }_2/\gamma }\right)$. An algorithm (the OGM-G method) which achieves the former complexity was given in [24], and [37] pointed out that any algorithm which achieves the former complexity can achieve the latter complexity. This is obtainable by running $N$ iterations of any optimal gradient method for reducing the function value, followed by $N$ iterations of a method which achieves the former complexity for reducing the gradient magnitude. In what may be of independent interest, we observe in Section 5.1 that a reduction in the opposite direction is also possible. More broadly, algorithms and frameworks for reducing the gradient magnitude of convex functions have been of much recent interest, and further algorithms and related work for this problem include [25, 27, 26, 28, 15, 37, 21], with lower bounds given in [34, 35].

Whenever we instantiate a dual-extraction setup (Definition 9), we use the following notation and oracles associated with that setup without additional comment. We define the associated primal $f:𝒳\to ℝ$ and dual $\varphi :𝒴\to ℝ$ functions, along with their corresponding primal and dual optimization problems, as they were introduced above in (P) and (D). We let $x^{\star }\in {argmin}_{x\in 𝒳}f(x)$ and $y^{\star }\in {argmax}_{y\in 𝒴}\varphi (y)$ denote arbitrary primal and dual optima. To facilitate the discussion of dual-regularized problems, we define $f_{\lambda ,q}(x):𝒳\to ℝ$ as follows

Assumptions 2, 5, and 6 in Definition 9 guarantee $f(x^{\star })=\psi (x^{\star },y^{\star })=\varphi (y^{\star })$, which we refer to as the minimax principle. See, e.g., [39, 41] as well as Propositions 1.2 and 2.4 in [17, Ch. VI].

Our framework assumes black-box access to $\psi$, $𝒳$, and $𝒴$ via a dual-regularized primal optimization (DRPO) oracle and a dual-regularized dual best response (DRBR) oracle defined below. Note that we generalize the setting of Section 1.2 by allowing the DRPO oracle to return an expected $ϵ$-optimal point; this is used in our applications in Section 4.

We also define a version of the DRPO oracle, called the DRPOSP oracle, which allows for a failure probability. We include this definition here due to its generality and broad applicability, but it is only used in Section 4.1 since the external result we cite to obtain an expected ${ϵ}_{\mathrm{p}}$-minimizer of $f_{\lambda ,q}$ in that application has a failure probability. We also show in Appendix A.4 in the full version how to boost the success probability of a DRPOSP oracle.