Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents a framework for exactly solving optimization problems of the form $\min_{Ax=b} \sum_{i=1}^m f(x_i)$, where $f$ is a 1-dimensional quasi-self-concordant convex function, which means that its second derivative doesn't change multiplicatively by more than $O(1)$ in any interval of size $1$. Examples of quasi-self-concordant functions include the logistic loss, softmax, and $\ell_p$ regression.

The main contribution of the paper is a general algorithm for this problem that works by solving a sequence of $\widetilde{O}(m^{1/3} R \log \frac{1}{\epsilon})$ linear systems where $R = \left\Vert x^*\right\Vert_\infty$. It is based on approximately optimizing a series of $\ell_{\infty}$-constrained quadratic objectives, which is done by a width-reduced multiplicative weights approach [CKM+11] that has been previously been used for max flow, $\ell_p$ regression, and matrix scaling.
main_review: The problem studied is fundamental and important, as can be witnessed by the fact that it contains logistic regression as a special case. On the other hand, the fact that it has an $O(m^{1/3})$ runtime overhead might make it less intriguing to the machine learning community. This could be mitigated if it were accompanied by numerical experiments that would show that this $m^{1/3}$ doesn't arise in practice, but currently there is no evidence that this is the case.

While the general ideas presented are not new and have arisen in previous work, the authors aim to unify all of these approaches by presenting a general all-encompassing analysis. This is a worthy goal, although currently I cannot say that the writing of the paper is clear enough to warrant the status of a go-to reference for the width-reduction approach. In particular, the intuition (both high-level and technical) behind the analysis could be explained much better. In this paper a clearer comparison to previous work, with clean explanations and proofs would go a long way.

Specific comments:

* I would expect to have seen a comparison of the authors' analysis to that of [AZLOW17] for matrix scaling. In fact, it seems to me that the approach is exactly the same: take $\ell_\infty$-constrained steps by using width-reduced multiplicative weights update. What are the technical differences (e.g. significant simplifications in the analysis)? The authors should definitely elaborate on this.

* For clarity, the use of the potentials $\Phi$ and $\Psi$ should be explained. Also, what do their changes mean for the algorithm?

* Page 6 contains a number of technical lemmas but no explanation on each of them.

* The objective function in Section 5.2 does not seem quasi-self-concordant to me. The second derivative is $p(p-1) (Px)^{p-2}$ which can be as much as $p(p-1) R^{p-2}$. As the problem is constrained, the $\ell_2$ regularization term doesn't necessarily help in making $R$ small (e.g. I can scale down $A$ and $b$ in the linear system $Ax=b$ to force $R$ to be arbitrarily large) 

* For $\ell_\infty$ regression, how does the authors' approach compare to that of e.g. [EV19], who obtain a better error dependence?
limitations_and_societal_impact: -
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper provides novel, simpler algorithms that match (or come close to matching) the best known results for the minimization of linearly constrained problems of the form $\min_{Ax = b} \sum_i f((Px)_i),$ where $f$ is convex, quasi-self-concordant and $\Px^*|_\infty \leq R$ for the optimum solution. The main contribution is the extension of width-reduction techniques, that previously were confined to l_p-regression problems, to this more general class.


main_review: The strength of this paper relies in its originality, i.e., applying width-reduction techniques to a much wider class of problems than previously done, quasi-self-concordant function.. It is nice that this can be done in a unified way. On the other hand, one would hope that a unified presentation of this approach would allow for some simplification and abstraction of the fundamental steps. On the contrary, the paper feels like a lifting of CKM+11 to a much more general setting without much additional understanding of the width-reduction phenomenon. 
Specifically, it would be nice if the authors better motivated the significance of the second derivatives of $f''$, which appears to replace the natural generalization of the MWU of CKM+11, which would be $f'$.

More generally, the paper suffers from a lack of clarity that makes it very difficult to approach for readers well-versed in optimization, but not very familiar with precedent results. For instance, I am very familiar with the seminal result of CKM+11, on which the paper approach is based, but had a very hard time reconciling my knowledge with the current paper because of the poor presentation. Specific points that need to be clarified include:
- make the application of width reduction explicit: in the current version of the paper, the authors do not even mention which variables are performing MWU (presumably the $f''(w)$) and which width is being reduced (that of the flow P\Delta). This clarification would immediately motivate the introduction of the potential function $\Phi.$
- the dual potential CKM+11 is also poorly motivated and should be directly related to typical dual quantities, just as was done in CKM+11. While this is implicitly done in Lemma 2.4, its current presentation remains fairly obscure.

Minor Issues:
- Theorem 5.1 and line 53 appear to use two different notions of the variable $\epsilon$
- line 134: clarify the introduction of the coordinate-wise monotonic property for $f''$.

limitations_and_societal_impact: The authors should provide a closer comparison to CJJ+20 in terms of running times. The dependence on the norm of the optimum solution appears to be different there.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Width-reduced methods have been used to solve specific optimization problems like maximum folw and lp regression with a small number of iteration $O(m^{1/3})$. However, the design of such methods is tedious because of the need to design specific potentials and analyses. This work aims to give a unified analysis of these methods in the case of quasi-self-concordant functions. This general setting allows to consider new applications like logistic regression.
main_review: This paper is quite technical and assume a good knowledge of previous works. The theoretical results are well stated and seems strong. However, I am not familiar enough with width-reduced methods to be able to check the results.

The quality of the writing is good but I found a lack of informal explanations and motivations of the setting. I am certain to find them in the references given but it would be great to recall them. I hope the following remarks will help to improve the clarity of the paper to non-experts.

- What is the main idea of reduced methods in a simple setting like maximum flow ? In this abstract setting is not even obvious why it is called "with-reduced".
- Why this method first developed for maximum flow is suitable for other settings which seems quite different like logistic regression ?
- What is the intuition behind those potential functions ?
- The use of big O in algorithms is a bit weird. Can't you give a precise value for tau and alpha ?
- I understand that the motivation to go from $O(m^{1/2})$ to $O(m^{1/3})$ in terms of number of call to a linear solver is important in some problems like maximum flow. However, it is quite unusual in logistic regression for example. Is it still a good way to measure computational complexity ? Could you compare to other work considering logistic regression optimization like (Marteau-Ferey 2019) ?
limitations_and_societal_impact: -
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors give an algorithm for solving optimization problems of the form $\min_{x \in \mathbb{R}^m, Ax =b } \sum_i f( (Px)_i)$, where $A,b,P$ are given and $f$ is convex and $\textit{quasi-self concordant}$. This property, introduced by Bach in [Bac10], is an alternative notion to the standard notion of self-concordance and implies that the Hessian of f(x) is multiplicatively stable inside of a box. As several standard regression objectives (softmax, logistic loss, l_p norms) are quasi-self concordant, the study of algorithms for such objective functions is of obvious theoretical and practical importance. The previous state of the art algorithm by [CJJ+20] solves qSC regression problems in $O(m^{1/3})$ linear system solves-- this improves upon previous work of [Bac10] which achieved a complexity of $O(m^{1/2})$ . However, [CJJ+20]'s algorithm (which combines an accelerated gradient method of [MS13] with an efficient algorithm to solve trust region problems) is fairly complex and inherently requires multiple iterative loops.

The present work improves upon [CJJ+20] by providing a simple $O(m^{1/3})$-iteration algorithm for this problem, based on a framework of [CKMST11] and [EV19]. 

main_review: This analysis is well written. and extends the scope of problems iterative refinement-least squares approaches can solve significantly (previous work on this area has focused on $\ell_p$-norm, softmax, and logistic regression) to the set of all qSC functions. The authors do this by a clever extension of previous techniques-- this allows them to incorporate second derivative information about the function $f$ in the least-squares problems they solve in each iteration. Further, the approach suggested here may achieve significant practical performance gains over previous work (IRLS approaches have been very successfully used for various regression tasks in practice, and converge much faster than the theoretical iteration bounds would indicate). 
limitations_and_societal_impact: Although the algorithm obtains an alternative to [CJJ+20] which matches the $O(m^{1/3})$ iteration complexity for quasi-self concordant optimization, its theoretical guarantee is still inferior even for the restricted case of qSC functions considered in this paper. For the important special case of softmax regression, the algorithm here obtains a $(1+\nu)$-approximate solution in $O(m^{1/3} \nu^{-5/3})$ iterations-- the result of [CJJ+20] uses $O(m^{1/3} \nu^{-2/3})$ iterations. This gap is surprising, as the algorithm of [EV19] (which the paper borrows heavily from) achieves  $O(m^{1/3} \nu^{-2/3})$ iterations for the related problem of $(1+\nu)$-approximate $\ell_\infty$ regression. Some discussion of why this gap exists (or an improved analysis which closes this gap) would strengthen the result significantly. 

In addition, the algorithm of [CJJ+20] actually achieves a stronger result: the iteration complexity improves if the $2$-norm of the optimal solution $x^\star$ is small. Does the algorithm given here achieve a similar result? 

Finally, the algorithm given more than superficially resembles the IRLS procedure of [EV19]. I would appreciate some discussion of the ideas borrowed from previous work in the introduction.
review_title: null

Meta-review: The reviewers and area chair agree that the technical contribution of the paper is significant as it yields a simpler algorithm for an important class of problems and extends the applicability of the width-reduced approach of [CKM+11]. The main weakness of the paper is the lack of clear explanations behind the technical analysis and comparison with existing similar methods.  However, the authors have addressed the reviewers' questions and provided some explanation in the rebuttal phase. Assuming these explanations will find their way in the final version, I believe the submission should be accepted.
Decision: Accept (Poster)