Acceleration Meets Inverse Maintenance: Faster ${\mathrm{\ell }}_{\mathrm{\infty }}$-Regression

The ${\mathrm{\ell }}_2$-oracles of MWUs and IPMs can be implemented by applying the inverse of a matrix, and inverse maintenance can be used to solve the sequence of ${\mathrm{\ell }}_2$-oracle calls faster than simply performing a full matrix inversion or linear equation solve on each call. Two key phenomena drive inverse maintenance: stability and robustness. Stability is the property that the inputs to the ${\mathrm{\ell }}_2$-oracle only change slowly. In the MWU case, this means the weights $\{r_e^{(i)}\}$ change slowly. We say an optimizer is robust if it can make progress using answers from ${\mathrm{\ell }}_2$-oracles with somewhat inaccurate inputs. The combination of stability and robustness is especially powerful. Together, these properties ensure that we can delay making small coordinate updates to inputs until they build up to a large cumulative update, and that we only get few large cumulative updates, enabling the use of coordinate-sparse update techniques. This approach of batching together small updates is known as lazy inverse updating. Obtaining further speed-ups using sketching also crucially relies on robustness. Because of robustness, we can afford to use sketching to estimate ${𝒙}^{(i)}$, as long as our estimates allow sufficiently accurate updates to the weights $\{r_e^{(i)}\}$.

The IPM of [12] first achieved a running time of $\tilde{O}(n^{2+1/6}+n^{\omega })$ by introducing a method with excellent stability and robustness, which in turn allowed them to implement a powerful inverse maintenance approach using lazy updates and sketching. Later, [5] showed that the same running time can be obtained deterministically using only lazy updates, and finally [16] gave an improved running time of $\tilde{O}(n^{2+1/18}+n^{\omega })$ using both lazy updates and sketching. The approach of [16] can be thought of as a two-level inverse maintenance, and the use of the randomized sketching techniques is crucial for them to efficiently implement the query operation of this data structure. It remains open if there exists any deterministic IPM that can run faster than $\tilde{O}(n^{2+1/6}+n^{\omega })$.

In oracle-based optimization, there is a long history of developing accelerated methods, which reduce the iteration count compared to more basic approaches. This can be traced back to accelerated solvers for quadratic objectives [19, 15] and first-order acceleration for gradient Lipschitz functions ([27] and earlier works by Nemirovski). Christiano et al. [11] developed an acceleration method for multiplicative weight methods that reduces the iteration count for solving ${\mathrm{\ell }}_{\mathrm{\infty }}$ regression with ${\mathrm{\ell }}_2$-oracles from $\tilde{O}(\sqrt{n}\cdot \text{poly}(1/ϵ))$ to $\tilde{O}(n^{1/3}\cdot \text{poly}(1/ϵ))$. An alternative approach to acceleration for ${\mathrm{\ell }}_{\mathrm{\infty }}$-regression can be obtained via the methods of Monteiro and Svaiter [26], and has also been a major research topic, but is beyond the scope of our discussion. For simplicity of our remaining discussion, we ignore $ϵ$ dependencies. A rough outline of the MWU acceleration approach of [11] is as follows: The MWU solves a sequence of ${\mathrm{\ell }}_2$-oracle problems returning iterates ${𝒙}^{(i)}$. If we scale the problem so that ${\Vert {\mathrm{𝑪𝒙}}^{\star }-𝒅\Vert }_{\mathrm{\infty }}\le 1$, then weights ensure that (a) in each iteration, ${\Vert {\mathrm{𝑪𝒙}}^{(i)}-𝒅\Vert }_{\mathrm{\infty }}\lesssim \sqrt{n}$ and (b) after $T=\tilde{O}(\sqrt{n})$ iterations, $\widetilde{𝒙}=\frac{1}{T}{\sum }_i{𝒙}^{(i)}$ has ${\Vert 𝑪\widetilde{𝒙}-𝒅\Vert }_{\mathrm{\infty }}\le 1+ϵ$. [11] made an important modification: if in some iteration we have ${\Vert {\mathrm{𝑪𝒙}}^{(i)}-𝒅\Vert }_{\mathrm{\infty }}\ge \rho \approx n^{1/3}$, then instead of using ${𝒙}^{(i)}$, we will adjust the weights $\{r_e^{(i)}\}$ in order to reduce the value of ${\Vert {\mathrm{𝑪𝒙}}^{(i^{\prime })}-𝒅\Vert }_{\mathrm{\infty }}$ for future iterates ${𝒙}^{(i^{\prime })}$. Using this method, an approximately optimal $\widetilde{𝒙}=\frac{1}{T}{\sum }_i{𝒙}^{(i)}$ can be found in $T=\tilde{O}(n^{1/3})$ iterations. The parameter $\rho$ measures the ${\mathrm{\ell }}_{\mathrm{\infty }}$-norm ${\Vert {\mathrm{𝑪𝒙}}^{(i)}-𝒅\Vert }_{\mathrm{\infty }}$ of each iterate, sometimes known as the width, and the weight-adjustment steps of Christiano et al. are hence known as width reduction steps. When the oracle width can be reduced in this way, we will say our method is width-reducible. This acceleration has never been developed for ${\mathrm{\ell }}_{\mathrm{\infty }}$-regression in the high-accuracy regime (i.e. running times that scale as $\mathrm{polylog}(1/ϵ)$), and whether this is possible is one of the major open questions in convex optimization.

Many MWU methods are designed to have an important property, which we call weight monotonicity. Concretely, in [11] and many other MWUs, the oracle weights $\{{𝒓}_e^{(i)}\}$ are only growing. This often simplifies analyses greatly, and helps establish other properties including stability, robustness, and width-reducibility. Referring back to our oracle queries introduced above in (2), let us define ${\widetilde{𝒙}}^{(i)}=\frac{1}{T}{\sum }_{j\le i}{𝒙}^{(j)}$. Weight monotonicity arises because we choose the weights based on an overestimate of $|{(𝑪{\widetilde{𝒙}}^{(i)}-𝒅)}_e|$ given by ${\gamma }_i=\frac{1}{T}{\sum }_{j\le i}|{({\mathrm{𝑪𝒙}}^{(j)}-𝒅)}_e|$. In particular, choosing ${𝒓}_e^{(i)}=\exp (\alpha {\gamma }_i)$ for some scaling factor $\alpha$ will ensure the weights only grow. As we will discuss later, weight monotonicity seems inherently incompatible with sketching, and thus we will need to develop a non-monotone MWU. Prior work by Madry [24, 25] introduced non-monotone weights in a highly specialized IPM for unit-capacity maximum flow. This IPM of Madry has MWU-like properties and allows for some acceleration. The method has other drawbacks including low stability and robustness, but nonetheless inspired some of our design choices.

We are aware of a single prior work which combined lazy inverse updates with an accelerated MWU to obtain a running time of $\tilde{O}(n^{2+1/3}+n^{\omega })$ for ${\mathrm{\ell }}_p$-regression [2]. This approach is relatively naive, falling short of the $\tilde{O}(n^{2+1/6}+n^{\omega })$ running time which can be achieved using only lazy inverse updates.

[2] showed how to obtain stability, robustness, and width-reducibility together, with a monotone MWU. However, this work only established a weak notion of stability and hence comparatively slow running time of $\tilde{O}(n^{2+1/3})$. In contrast, one can show that by directly using stability and robustness in a monotone accelerated MWU, one can adapt the data structure approach of [5] to achieve a running time of $\tilde{O}(n^{2+1/9})$, yielding a faster MWU.

Our first result Theorem 1 is based on the observation that monotone MWU also enables a new, stronger notion of stability, which we call ${\mathrm{\ell }}_3$-stability. This allows us to further reduce the number of lazy updates we make and lets us achieve a deterministic running time of $\tilde{O}(n^{2+1/12})$.

As we described above, it is relatively easy to improve the running time of low-accuracy ${\mathrm{\ell }}_{\mathrm{\infty }}$-regression among deterministic algorithms, by designing a monotone, robust, width-reducible MWU with a novel ${\mathrm{\ell }}_3$-stability.

To further accelerate the algorithm by using a two-level inverse maintenance data structure, we need to use randomized sketching techniques to efficiently implement the query operation, which is required in every iteration of the MWU algorithm. Unfortunately, weight monotonicity is in conflict with sketching, because monotonicity arises from ignoring cancellations in ${(𝑪{\widetilde{𝒙}}^{(i)}-𝒅)}_e$ between different iterations.²²2Recall that the final output of our MWU is the last averaged iterate ${\widetilde{𝒙}}^{(T)}$. In contrast, when using sketching, we want to crucially rely on cancellation between different iterations, as we sometimes overestimate ${({\mathrm{𝑪𝒙}}^{(i)}-𝒅)}_e$ and sometimes underestimate it, but get it right on average. Because of this, we design an MWU with non-monotone weights. This in turn makes width-reducibility, robustness, and stability much harder to obtain.

To allow us to work with non-monotone weights and still obtain acceleration, we introduce a more delicate width-reduction scheme, inspired by [25]. We also provide a tighter analysis of the sketching technique (it was named coordinate-wise embedding by [21, 16]) that upper bounds its total noise across different iterations using martingale concentration inequalities. This tighter analysis is necessary to control the overall error introduced by the sketching technique in our MWU algorithm. We believe this tighter analysis could also provide a simpler analysis for the IPM results of [12, 16].

This new width-reduction approach in turn also requires us to estimate an ${\mathrm{\ell }}_3$-norm associated with each iterate ${𝒙}^{(i)}$, and to do this quickly, we need to employ new sketching tools. To implement this approach, we also need an additional heavy-hitter sketch that allows us to identify which weights to adjust during width reduction.

Stability and robustness are crucial when we want to use lazy updates and sketching for inverse maintenance. Standard techniques for acceleration by width-reduction are unstable in the context of non-monotone MWU. Thus, to combine stability, width-reduction, and non-monotonicity, we have to further change our width-reduction strategy.

A central challenge is that width-reducibility is inherently in tension with the other properties. To simultaneously achieve stability and width-reducibility, we introduce a new and rather different approach to width-reduction, which we call stable width-reduction. This approach is more conservative than existing methods, and uses smaller width-reduction steps to achieve stability.

Combining width-reducibility with robustness is also difficult. Width-reduction relies on identifying too-large entries of the oracle outputs and making adjustments to the corresponding weights. But, robustness requires us to operate with inaccurate weights. We want to allow for weights that are inaccurate up to a factor $(1\pm 1/\mathrm{polylog}(n))$, and this is enough to completely change which oracle outputs are too large. In fact, we do not achieve general robust, but instead show that our method is robustness to (1) the errors induced by our specific lazy update scheme and (2) the errors induced by sketching.

It remains open to design any algorithm for low-accuracy ${\mathrm{\ell }}_{\mathrm{\infty }}$ regression beyond $\tilde{O}(n^{2+1/22.5})$ when $\omega =2+o(1)$. We remark that if it were possible to use ${\mathrm{\ell }}_3$-stability with the two-level data structure and an algorithm that converges in $n^{1/3}$ iterations, then we would achieve a runtime of $\tilde{O}(n^{2+1/48})$. However, the current techniques for inverse maintenance and acceleration are not sufficient to achieve $\tilde{O}(n^{2+o(1)}+n^{\omega })$, which we believe would require substantially new techniques. On the other hand, even obtaining slight improvements in the runtime would require more robust acceleration and inverse maintenance frameworks which would be of independent interest.

In this paper, we analyze our algorithms in the RealRAM model. Establishing a similar analysis in finite precision arithmetic is an interesting open problem. Inverse maintenance-based IPM with finite precision arithmetic was studied by [14].

We have demonstrated that acceleration techniques for MWU can be efficiently combined with inverse maintenance methods. For linear programming, no similar acceleration techniques exist and it is a major open problem to design these or rule out the possibility in various computational models. If acceleration can be achieved for linear programming, deploying it in conjunction with inverse maintenance will likely require techniques similar to those we introduce in this work.

For simplicity, we only show the runtime of our algorithm when $\omega =2$ in this section and omit polylogarithmic factors. Let us choose the parameter $a_0=3/4$, so that we perform a reset operation whenever we accumulate more than $n^{a_0}=n^{3/4}$ updates to $\overline{𝒓}$. From our low-rank update scheme under the ${\mathrm{\ell }}_3$ stability guarantee, this only happens in every $n^{1/4}$ iterations. So we perform a reset operation with cost $O(n^2)$ (since $\omega =2$) in every $O(n^{1/4})$ iterations, and over the total $O(n^{1/3})$ iterations this gives a total reset time of $O(n^{2-1/4}\cdot n^{1/3})=O(n^{2+1/12})$.

We perform a query operation in every iteration with cost $O(n^{2a_0}+n^{1+a_0})=O(n^{1+3/4})$. Over all $O(n^{1/3})$ iterations this gives a total query time of $O(n^{1+3/4}\cdot n^{1/3})=O(n^{2+1/12})$. Therefore, the total runtime is the sum of the reset time and the query time, which is $O(n^{2+1/12})$ as claimed in Theorem 1.

Similar to [16], in our work we also query a sketch of the maintained vector in every iteration. More precisely, in each iteration we use a random matrix $\mathrm{SS}\in {ℝ}^{n^{1/2+\eta }\times n}$ where $\eta$ is the acceleration that we get, i.e., the total number of iterations is $O(n^{1/2-\eta })$, and we compute an approximate step ${\mathrm{SS}}^{\top }\cdot \mathrm{SS}\cdot ({𝑪}^{\top }{\mathrm{\Delta }}^{(i,k)}-𝒅)$. Using the coordinate-wise embedding guarantee of the random matrix $\mathrm{SS}$, we can ensure that for each coordinate we have

We now require to change Line 11 of Algorithm 1 to update the weights by

Note that we lose monotonicity of the weights with this new primal step. We have to use this non-monotone update because the absolute values $|{\mathrm{SS}}^{\top }\mathrm{SS}({𝑪}^{\top }{\mathrm{\Delta }}^{(i,k)}-𝒅)|$ would result in an error that is around the standard deviation of the estimator in every update of ${𝒘}^{(i,k)}$’s, and this would add up over iterates. Since the entire analysis of the MWU methods depends on tracking potentials which are functions of the weights, we would incur a large error. To circumvent this issue we require a version of the MWU method where the weights are not updated monotonically, and the random noise introduced by the sketching matrix $\mathrm{SS}$ can cancel out with each other across different coordinates $e$ and across different iterations $i$.

Monotonicity is crucial in accelerating MWU methods and it is non-trivial to achieve accelerated rates without it. A few works in graph algorithms have been successful in obtaining accelerated rates without monotonicity [25, 23] for specific algorithms. In this paper, we extend the algorithm of [25] to regression and obtain an algorithm with non-monotone updates that also converges in $n^{1/3}$ iterations and is robust (please refer to the full version for the complete algorithm and analysis).

Interior point methods directly control the solution quality of the last iterate. In contrast, MWU algorithms only measure the quality of the average of the primal iterates ${\mathrm{\Delta }}^{(i,k)}$. As a result, our bound on the final solution requires a new MWU analysis that can handle cancellations between iterates of the errors arising from using sketching. We achieve this by developing a tighter analysis that upper bounds the sum of the sketching error over multiple iterations:

We prove this bound using Freedman’s concentration bound for martingales. We also believe this tighter analysis can simplify the sketching analysis for the previous IPM papers [12, 21, 16].

The non-monotone MWU with standard width reduction steps is neither stable nor satisfies a low-rank update per iteration. We propose a new width reduction step that satisfies a low-rank update scheme which is sufficient for our data structure. Our steps, however, do not satisfy ${\mathrm{\ell }}_2$ stability, which is a sufficient condition for the low-rank update scheme. Instead of increasing all weights by a factor of $(1+ϵ)$ as in Line 16 of Algorithm 1, our new width reduction step increases a carefully selected set of weights. As a result, we can ensure that whenever we increase a large set of weights, we also increase the potential by a lot, so this event doesn’t happen very often. This helps ensure that weight updates from width-reduction steps occur on a similar “schedule” to weight updates from our primal update steps, and it allows us to efficiently handle both in the inverse maintenance data structure (please refer to Algorithm 3 for the complete algorithm and refer to the full version for the full analysis). To efficiently find the coordinates $e$ to perform width reduction on, we use an additional heavy-hitter data structure to identify these ${\mathrm{\Delta }}_e$ exactly. We can only afford to find $n^{1/2+\eta }$ such coordinates in each iteration. This restriction on the number of coordinates restricts us to set $\eta$ to be $1/10$, and our final iteration complexity is $n^{1/2-\eta }=n^{2/5}$ instead of $n^{1/3}$. The non-monotone algorithm also requires estimating a weighted ${\mathrm{\ell }}_3$-norm of ${\widehat{\mathrm{\Delta }}}^{(i,k)}$’s for which we use an additional sketch from [34].

Unlike the width reduction steps, the primal steps are stable, and they satisfy the ${\mathrm{\ell }}_2$ stability,

Given the ${\mathrm{\ell }}_2$ stability guarantee, we again use coordinate-wise approximate weights ${\overline{𝒓}}^{(i)}{\approx }_{\delta }{𝒓}^{(i)}$ in each primal step, and only update ${\overline{𝒓}}_e^{(i)}$ to be ${𝒓}_e^{(i)}$ if it differs from ${𝒓}_e^{(i)}$ by more than $\delta$. This again guarantees a low-rank update scheme for the primal steps: for every $\mathrm{\ell }$, in every $2^{\mathrm{\ell }}$ iterations we only perform an update of size $O(2^{2\mathrm{\ell }}\cdot n^{2\eta })$ to ${\overline{𝒓}}^{(i)}$.

It is non-trivial to show that the accelerated non-monotone MWU is robust under such coordinate-wise approximations to the weights. This is because we do not update the weights in every primal step, and we lazily update them in future iterations. We use an amortization argument to show that we can still gain enough changes in the required potentials even when we defer some updates to the future. However, this means our accelerated non-monotone MWU is only robust under the specific approximate weights ${\overline{𝒓}}_e^{(i)}$ that are updated to be ${𝒓}_e^{(i)}$ whenever it differs too much from ${𝒓}_e^{(i)}$. We cannot guarantee robustness if in every iteration we choose an arbitrary coordinate-wise approximation unless we consider the unaccelerated algorithm, which was guaranteed in the IPM algorithms.

Finally, we sketch the time complexity of our non-monotone MWU algorithm using sketching when $\omega =2$. For simplicity, we omit polylogarithmic factors. Using the two-level inverse maintenance data structure of Lemma 5, we perform a reset operation whenever we accumulate more than $n^{a_0}$ updates to $\overline{𝒓}$, and by our low-rank update scheme under the ${\mathrm{\ell }}_2$ stability guarantee, this only happens in every $n^{a_0/2-\eta }$ iterations. Similarly, we perform a partial reset operation whenever we accumulate more than $n^{a_1}$ updates to $\overline{𝒓}$, and this only happens in every $n^{a_1/2-\eta }$ iterations. Finally, note that our query time is bounded by $n^{a_0+a_1}$ since we always ensure that we query for at most $\mathrm{\ell }=O(n^{1/2+\eta })$ coordinates in each iteration. So our total runtime over $T=n^{1/2-\eta }$ iterations is

Choosing the parameters $a_0=1-\frac{1-2\eta }{9}$ and $a_1=1-\frac{1-2\eta }{3}$, we have that the total runtime is bounded by $O(n^{2+1/18-\eta /9})$. Since we achieve an acceleration of $\eta =1/10$ and $n^{1/2-\eta }=n^{2/5}$ iterations, this gives the claimed $O(n^{2+1/18-\eta /9})=O(n^{2+1/22.5})$ time complexity of Theorem 2.