Quasi-Self-Concordant Optimization with $\ell_{\infty}$ Lewis Weights

We thank the reviewer their work and encouraging feedback, and the suggestions for improving the paper. We would also like to refer the reviewer to our response to Reviewer Gv4i for the summary of our contribution.

Weakness/Questions

The $\ell_2$-regularized $\ell_p$ regression problem is a key application of QSC optimization, and the authors include it in their experiments. How does the complexity result in this paper compare to existing results specifically for this setting?

The improvement in our paper implies a direct improvement in logistic regression and regularized $\ell_{p}$ regression. More specifically, for logistic regression, the number of calls to a system solver by our algorithm is $\tilde{O}\left(d^{1/3}R\right)$ compared with $\tilde{O}\left(n^{1/3}R\right)$ by ABS21. For $\ell_{2}$-regularized $\ell_{p}$ regression, the number of calls to a system solver by our algorithm is $\tilde{O}\left(d^{1/3}Rp^{2}\mu^{-\frac{1}{p-2}}\right)$ compared with $\tilde{O}\left(n^{1/3}Rp^{2}\mu^{-\frac{1}{p-2}}\right)$ by ABS21.

Removing the binary search.

Using binary search has been a commonly used approach in solving this problem. We agree with the reviewer that removing the binary search is an important direction. In practice, we can use a variant of the algorithm that updates the values of $\nu$ and $M$ during the algorithm without using binary search, and we provided such a variant in the code. However, currently we do not have a theoretical analysis for this variant and we leave it for future work.

Suggestions

We thank the reviewer for the suggestions. We will incorporate them in the next revision of the paper. We will also add further discussion on our contribution and comparison with prior work as discussed in our response to Reviewer Gv4i.

We thank the reviewer for their work and helpful comments. We would like to refer the reviewer to our response to Reviewer Gv4i for the clarification of our contribution in comparison with prior works. We would like to address the reviewer's concerns below.

Weakness

How much of the analysis is new is unclear as similar ideas have been used before in JLS22 where they use a similar change in weights to recover a similar improvement to AKPS19.

We would like to first clarify that the improvement that the reviewer mentioned is for $\ell_{p}$ regression problems with finite $p$ and does not apply to the QSC or the $\ell_{\infty}$ regression problems we consider in our work. JLS22 provides two very different algorithms: the algorithm the reviewer mentioned is for finite $p$ that builds on the regression algorithm of AKPS19 and does not work for $p=\infty$, and a separate algorithm for $p=\infty$ that builds on the algorithm of CJJ+20. Since it cannot handle $p=\infty$, the former algorithm cannot be combined with existing trust region templates for QSC optimization such as those used in our work or the prior work of ABS21 (see also our response to Reviewer Gv4i). Since the latter algorithm uses a completely different approach from AKPS19, it is not clear how one could leverage it for QSC optimization. We refer the reader to our response to Reviewer Gv4i for a more detailed discussion.

Q1. What is new in the analysis that allows for the incorporation of Lewis weights into EV’19? It seems like reducing to solve to $d\times d$ systems is new but I am not sure.

There are two new ideas that allow for the incorporation of Lewis weights into EV19, which does not come from sparsifying the problem using Lewis weights or a direct application of the ideas from previous works. First, our algorithm differ from EV19 in the initialization using Lewis weights instead of a uniform initialization. Second, in Case 1 in the algorithm 1, we need a different update where we only update one coordinate but with a large additive step. Uniform initialization is critical in EV19's algorithm which relies on the fact that each $r_{i}$ is sufficiently large. Initialization using Lewis weights breaks this condition and thus requires a different update scheme and a new analysis.

Q2. I am not sure how much easier this is than ABS’21 for simple cases of softmax regression or $\ell_{\infty}$ norm regression. Do the authors have a sense of why their algorithm might be better in practice?

Our algorithm has an iteration complexity $\tilde{O}(d^{1/3})$ while it is $\tilde{O}(n^{1/3})$ for ABS21, which we expect it will directly translate to faster running time in practice on overdetermined instances. This improvement does not come readily from prior work. For example, the improvement for softmax and $\ell_{\infty}$ regression is shown in JLS22, which is built on top of CJJ+20, which needs a complex acceleration scheme. Our work, on the other hand, provides a very simple method that does not use any acceleration, which has several advantages in practice as we discuss next.

In practice, our method is robust and exhibits numerical stability. In contrast, accelerated methods require careful adjustments to their step sizes to handle precision errors, or errors from the least-squares solver (see e.g., http://blog.mrtz.org/2014/08/18/robustness-versus-acceleration.html, Devolder-Glineur-Nesterov '23), and even algorithms that have a good theoretical behavior in fixed-point arithmetic may encounter difficulties when executed on real-life floating point numerical architecture. Additionally, the algorithm by ABS21 includes several parameters ($\tau$, $\zeta$, $\alpha$). In practice, these parameters require tuning which degrade the practicality of the algorithm.

Q3: I believe prior works on QSC optimization including ABS’21 and CJJ+’20 also work for hessian stable functions. They just seem to not explicitly write it but the proofs are done for hessian stable functions.

Yes, these works extend to Hessian stable objectives, as they use the same trust region template that only requires Hessian stability. We note that the main challenge is to solve the resulting subproblems. CJJ+20 provide such an algorithm for only smooth functions, and both algorithms have iteration complexity scales with $n$. Our algorithm is for general (non-smooth) functions and its iteration complexity scales with $d$ instead of $n$.

We thank the reviewer for their work and helpful feedback. We would like to address the reviewer's concerns below.

Weakness

The reduction to $\ell_{\infty}$ regression seems fairly standard in light of prior work related to quasi-self-concordance that the paper cites (and the paper “Matrix Scaling...” which is not cited but seems relevant to this reduction and may be good to discuss). As the authors note, $\ell_{\infty}$ regression is then solve-able more efficiently than the method the paper proposes for it (at least in terms of not having an extra factor, though potentially in a more complicated fashion

We cite and briefly discuss this work (CMTV17) on lines 80-89. We would like to clarify that this and other prior work do not provide a reduction to $\ell_{\infty}$ regression, and there is currently no known way to directly apply $\ell_{\infty}$ regression algorithms to QSC optimization. Building on these works, we reduce the QSC problem to a sequence of subproblems where we are optimizing a quadratic function subject to an $\ell_{\infty}$ box constraint (in addition to the linear system constraint). This problem is related to but distinct from $\ell_{\infty}$ regression and the prior work on regression is not sufficient to solve these problems even if we are only aiming for $n^{1/3}$ iterations, as we can see from e.g. ABS21. CMTV17 (and AZLOW17) provide an algorithm for these subproblems only for the specific function arising in matrix balancing, and it does not apply to general QSC functions (in addition to its iterations scaling with n instead of d). The main contribution of our work is to design a new solver for these subproblems for general QSC functions that significantly departs from ABS21 and other prior work. We would like to highlight some distinctions

• Comparison with JLS22: While JLS22 introduces a new algorithm with Lewis weight for $\ell_{p}$-regression, this algorithm does not include $p=\infty$. There is a fundamental reason for this. This algorithm follows the line of works for $\ell_{p}$-regression that use the Taylor expansion to approximate the $\ell_{p}$-norm. This does not work for $\ell_{\infty}$ norm. As a consequence, for $\ell_{\infty}$-regression, JLS22 use softmax as a proxy, and Monteiro-Svaiter acceleration with a ball oracle to obtain $\tilde{O}(d^{1/3})$ rate. Monteiro-Svaiter acceleration is a complex acceleration method, and there have been multiple attempts (eg. Carmon et al. 2022) to simplify it (for example, this method requires to solve an implicit equation to find the coefficients), but the practicality of this method remains unclear. Our work on the other hand uses the dual formulation of the problem, which is fundamentally a different approach. We show a simple algorithm that incorporates Lewis weights, without any complicated acceleration scheme and allows for an efficient implementation.

• Comparison with ABS21. Our work reduces the iteration complexity for solving the subproblems from $\tilde{O}(n^{1/3})$ to $\tilde{O}(d^{1/3})$ with a new insight from solving $\ell_{\infty}$ regression. As pointed out by JLS22, the approach to gain the improvement does not simply stem from sparsification with Lewis weights. Instead, this requires a new and clever way of using Lewis weights in the algorithm, which is not at all an apparent application of prior approaches. In particular, our algorithm for solving $\ell_{\infty}$-regression with Lewis weights departs from prior approaches as explained above. From the practical side, the algorithm of ABS21 uses several different parameters ($\tau,\zeta , \alpha$). In practice, this algorithm requires to tune these parameters to obtain a fast runtime, which makes it not a practical algorithm.

• Comparison with EV19. While the framework of EV19 provides the basis for our algorithm, their framework requires very specifically that the solution is initialized (close to) uniformly. A significantly different initialization using Lewis weights immediately breaks EV19's convergence analysis. While being simple in hindsight, our algorithm requires a subtle use of the new energy lemma by JLS22 in a fundamentally different approach. Moreover, we cannot use the algorithm of EV19 to solve the subproblems of QSC since it is specifically designed for only pure $\ell_{\infty}$ objectives, whereas we need an algorithm that solves $\ell_{\infty} + \ell_2$ objectives

they only compare against a limited set of methods

The set of implementable algorithms beyond first order methods (which are not apt for high-precision) is very limited. For reasons mentioned above and below, existing algorithms such as ABS21 do not provide a practical implementation.

Questions

Q1. The paper asserts that it is simpler than ABS21 and that JLS22 is complex. In what way is that true?

We would like to stress again that the algorithm by JLS22 for $\ell_{p}$-regression does not include $p=\infty$. Their algorithm for $\ell_{\infty}$-regression relies on a complex acceleration scheme. On the other hand, the algorithm by ABS21 uses a number of parameters that need to be tuned in practice, which makes it difficult to be efficiently implementable.

Q2. “can handle more general functions”.

Our claim here is that our approach generalizes to $\sum f\_{i}((Ax-b)\_{i})$, where each $f_{i}$ is QSC. This generalizes the setting in ABS21 where the objective is $\sum f((Ax-b)_{i})$ for a QSC function $f$.

Suggestions and comments

We thank the reviewers for the suggestions and comments. We will incorporate them in the next revision of the paper. We will also add the above clarifications and comparison with prior work.

Thank you for replying. I appreciate the response and ultimately the discussions are elevating my view of the substance of the submission. However, from the responses, I am concerned about the extent to which the substance of the reviews and the source of the concerns raised will be reflected in the final version. To respond to the particular points made:

• I think stating that the solver “relies on” $\ell_\infty$-regression is different than saying that it is “related to” their algorithm for $\ell_\infty$-regression and I think this is important to clarify clearly.
• I think there is a difference between asserting that the result is not readily applicable and providing compelling evidence, e.g., a technical fact that the proofs use that seem difficult to circumvent. Again, I agreed that the prior work does not apply immediately, however it is not clear to me that the techniques underlying the prior work cannot be applied in a straightforward way. To be clear, ultimately, I think that the paper is providing an interesting approach that is great to share with the community, however I would be hesitant to assert too strongly that it overcomes too large a barrier (at least without more compelling evidence).
• To clarify, I think what was stated in the reviewer response is incorrect. I believe JLS22 provides more than 2 distinct algorithms; it provides 2 distinct algorithms for $\ell_p$-regression as well as 1 additional algorithm for $\ell_\infty$-regression. The $\ell_\infty$-regression algorithm in the paper is indeed a MS-acceleration based method, but it is closely connected to one the paper’s algorithms for $\ell_p$ regression. Consequently, I find the assertions made by the authors about JLS22 a bit confusing or perhaps, misleading.
• That is an interesting point about the experimental results in Carmon et al. (and perhaps worth noting when explain experimental decision in the submission), however I still feel this discussion regarding the complexity of methods and their practicality warrants more careful phrasing and consideration in the submission.

I also want to add that I feel that there was at least one aspect of my previous response were not responded to, e.g., my comment about the reduction from softmax to $\ell_\infty + \ell_2$ regression being straightforward from prior work.