Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the proportionally fair optimization problem (i.e., $\max f(x) = \sum_i \log x_i$) under packing constraints ($A x \leq 1$ for a matrix A of nonnegative entries). The main contribution is a distributed accelerated algorithm for fair packing. The algorithm is width independent and produces (additively) approximate solutions for both primal and dual.

Width is defined as max ratio of positive entries in the matrix A. First order width-dependent methods don't readily lead to polynomial-time algorithms because smoothness constants do not scale logarithmically with width. In addition, approximate solutions of primal and dual are not easily translatable. In light of this, designing width-independent approximation algorithms for both primal and dual sounds challenging.

This is done by extending a general technique for packing LPs and exploiting problem structure to design a distributed algorithm. Distributed width-independent algorithms for general packing LPs are not yet known. Unlike prior work, the new algorithm is determinstic, has additive (not multiplicative) error, and uses a different regularization. The new algorithm uses $O(n/\epsilon)$ iterations, a factor n smaller than the best prior method.
strengths_and_weaknesses: Strengths:
- Primal and dual algorithms are both width independent. (Translating approximate solutions between primal & dual is not easy.)

Weaknesses:
- No discussion of concrete applications, hence no experimental study to show practical benefits, runtime and error bounds.
questions: none
limitations: n/a
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: **The problem and its importance** 

The paper presents an *accelerated, width-independent algorithm* for the $\alpha$-fair-packing problem with $\alpha = 1$, in the distributed model of computation. The problem is motivated by that of fair allocation of (non-negative) resources and falls under the broad umbrella of $\alpha$-fair-packing problems, which are an important problem class encompassing, for example, the standard packing LP, which has seen a long line of work (for example, by Luby-Nisan, Fleischer, Plotkin-Shmoys-Tardos, Awerbuch-Khandekar, Young, Koufogiannakis-Young, Allen-Zhu-Orecchia, Wang, Mahoney-Rao-Wang-Zhang, etc.) in both theoretical computer science (most significantly in the context of multicommodity flow problems) and machine learning that have led to developments of techniques that are now widely used in optimization in general. Therefore, this paper definitely studies a very important problem. 

The paper further studies the dual of this algorithm and applies it to obtain an improved analysis of the classical Yamnitsky-Levin algorithm. 

**The technical outline** 

The paper solves the primal problem by building upon the work of Diakonikolas-Fazel-Orecchia and AllenZhu-Orecchia. Specifically, the problem reformulation and parts of analysis (the gradient descent progress) is drawn from DFO, whereas the framework of ``truncated gradients in mirror descent coupled with gradient descent'' comes from AZO. We explain these a bit more next. 

The notion of ``fairness'' is captured in the objective via maximizing the *product* of allocated resources (and taking the log to formulate it as a convex minimization problem), which results in the problem $\max_{x\geq 0, Ax \leq 1} \, \sum_{i = 1}^n \log x_i$. The final reformulated problem involves the following modifications to this problem: (1) reparametrizing the problem variable to make the (initial) objective linear; (2) moving the packing constraints into the objective via an exponential penalty; (3) adding a box constraint based on properties of the optimal point. We note that these modifications were first done in DFO. 

For this reformulated problem, the gradients lie (coordinatewise) in $[-1, \infty)$. The algorithm proceeds as follows. It takes a mirror descent step using the squared-loss mirror map and on the linear term defined by the *truncated* gradient. The truncation is essential for obtaining a regret that is independent of the width of the problem, and this idea stems from AZO. Next, the algorithm takes a ``gradient descent step'' with the amount of update scaled proportional to the amount of movement via the mirror descent step. Following the gradient descent analysis of DFO, the paper shows a minimum bound on the progress via this step. Finally, the iterates obtained via the mirror descent and gradient descent steps are coupled in a convex combination (and their analysis performed analogous to that in AZO). This gives a primal algorithm with $\epsilon$-additive optimal point in $O(n/\epsilon)$ iterations. 

**Contributions** 

1. The paper's main result is an $O(n/\epsilon)$ iteration algorithm for the stated primal problem. The previous best result by DFO was $O(n^2/\epsilon^2)$, making this paper's contribution in terms of results very clearcut. Further, in achieving this iteration count, the paper becomes the first to achieve both width-independence and acceleration for the $1$-fair-packing problem, which is quite a significant and a highly non-trivial contribution in this line of work. 

2. While the paper definitely builds upon the work of DFO and AZO (as described above), the way it combines them is novel (which is what gives it its new, improved result). 





strengths_and_weaknesses: **Strengths** 

1. Achieving both width-independence and acceleration for $1$-fair-packing is quite a significant result. In my opinion, just the first component of the paper (the primal result) is a strong result in itself. 

2. The paper's primal algorithm is very clean, with very clearcut operations (mirror descent, gradient descent, and coupling) along with their corresponding analyses. The *reasons* for various steps in the algorithm (example, gradient truncation) and why the analysis works (example, the progress by gradient descent compensating the regret bound via the truncated gradient) is also all explained very transparently. 

3. The previous best result on this problem (DFO) achieves their result by a different technique (approximate dual gap technique), so it is quite nice that this follow-up work follows a different technique.  

**Weaknesses** 

1. Given that the paper greatly builds upon the work of DFO (for the primal algorithm), I think one way to make this paper even more transparent would be to (if possible) try and frame DFO's algorithm in this paper's language. More concretely, can you write DFO's algorithm in the ``coupling'' framework of this paper (which in turn draws this from AZO) and show exactly what steps of DFO (in this framework) were changed to achieve this paper's result? 

2. I think the main body (the primal section) could do a slightly better job of giving more complete justifications/attributions. As examples, 

    * it's not immediate from the algorithm in the main body that the iterates all lie in the box (though this is justified in the appendix); perhaps a pointer to this lemma would be good. 

    * Further, I think it's important to clearly state in the main body what parts of the problem formulation and analysis are derived from DFO and AZO (for example, Lemma 2.3 is basically that of DFO). Having these attributions clearly stated will more clearly shine a light on the paper's novelty, without taking away the contributions of DFO and AZO. 

3. I found the dual algorithm/analysis way more dense than the primal part. Is it possible to simplify this section's exposition? 

**My overall verdict** 

I think this is a worthy problem, with a simple, clean algorithm for the primal case, a creative one for the dual case, and an interesting application to a classical algorithm (Yamnitsky-Levin) that I had been unaware of. 

In addition to its primary contributions (the primal and dual algorithms and analysis), the final contribution adds value to the optimization/ML literature by bringing to fore a (possibly) less-known classical algorithm. This would therefore be a nice contribution to NeurIPS '22. 
questions: 0. Please see the **Weaknesses** section above for other questions. 

1. My first obvious question is, why doesn't this algorithm extend to the case $\alpha \neq 1$? Or, if it does, then what is the iteration complexity? It would make the paper more complete to explain this as well. 
limitations: I very much appreciate the authors being upfront about the paper not generalizing to the $\alpha \neq 1$ case. Given that this is a theoretical paper, I do not foresee any negative societal impact of the paper and have no suggestions to this end.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper solves the so-called 1-fair packing problem via first-order methods. The main results are computational complexity of O(n/epsilon) for the primal problem and O(n^2/epsilon) for the dual problem. These results are not width dependent (where the width is the ratio of largest to smallest elements in matrix A), which is a plus.
strengths_and_weaknesses: The strength is that the paper studies a fairly important problem in resource allocation. I like the results overall. The weakness is that the method developed follows closely to Allen-Zhu and Orecchia (Math. Prog. 2019). It seems that it simply customized their approach to this specific setting. The computational complexity results are good but at the expense of solving more difficult oracles.
questions: I am not too familar with the literature on this problem; perhaps a in-depth discussion about pros and cons of the developed algorithms compared to the state-of-the-art would be helpful to readers.
limitations: The authors did not address the limitations and potential negative societal impact of their work but it is okay given the nature of this work.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies proportional fair resource allocation problem and develops first-order methods
strengths_and_weaknesses: Strengths: The analysis is solid and the problem is interesting.

Weakness: The developed first-order method is limited to the problem itself.
questions: Can the algorithms be generalized to other optimization/learning problems?

Theorem 2.5 depends on big constants, which can be exponential in n?
limitations: The developed first-order method is limited to the problem itself.
review_title: null

Meta-review: metareview: The paper proposes fast algorithms for computing proportional fair allocations, which is one of the most widely defs of fairness. Although reviews were mixed, we believe that importance of the problem makes this a worthy paper to include in NeurIPS. However, we encourage the authors to incorporate the comments of the reviewers to make it more interesting for the ML audience.
confidence: Less certain
Decision: Accept