- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper presents an algorithm for solving entropy regularized LPs. The first step is showing that under the sum-exp dual, blocks satisfy generalized smoothness, meaning that curvature grows with the optimality gap. The second step is showing that curvature constants can be computed (approximately) from the data itself, before starting iterations. The paper then suggests an algorithm based on a potential bounding the optimality gap, and a separable importance sampling scheme that can be pre-computed.
The main contributions as I understand:
- (Low value contribution) showing the generalized smoothness bound on the sum-exp block function.
- keeping the block access sparse by sampling blocks according to a modified mixture distribution (instead of the standard importance sampling), and using a potential to bound the gap thus eliminating the need to evaluate the gap at each iteration.
- (low value) showing that the sum-exp function is quasi-self-concordent, thus GRN can be applied.
The resulting algorithm has theoretical guarantees that can exploit block smoothness and sparsity. The authors then perform numerical experiments after establishing how other methods can be applied to the problem, although the actual algorithm used in the experiments is a variation of the theoretically analyzed algorithm, with adaptive schedule.
Critical strengths
- The paper addresses an open gap in ELP optimization and proposes an algorithm that can utilize low access cost as well as low effective dimension.
- The idea to upper bound curvature bounds by a separable pre-computed bound is nice.
Critical weaknesses
- Very bad presentation. Looks written with a lot of LLM assistance. The paper is very hard to follow, notation / terms are used before they are defined and the flow of the paper is incredibly entangled and unclear. The related work section should be clearly presented, to allow easy comparison with contemporary work. There is no preliminaries section where notation is defined (for example, I assume denotes the conjugate dual, but this was never defined. In other places this seems to denote the optimal solution??). The theorems should include the link to the proof, and many results are not even stated but rather mentioned in passing with a link to the appendix. In algorithm 1 - what is ? It was never defined. Bad presentation of the results - some of the contributions mentioned in the intro are never mentioned again in the paper (only in the supp material). If a result is important enough to be mentioned in THE contributions paragraph, why isn’t it properly presented?
- Limited novelty - the generalized smoothness technique is not novel, although not used before for this problem. The more general algorithm is somewhat novel, and the main ingredient as I understand it is the separable bounds, which allow pre-computing and bound computation.
- Paper narrative - the paper starts with the notion that one has to choose between smoothness or sparsity, and then proposes a way to overcome (partially) this tradeoff. Section 5 however depicts a different picture - the sum-exp is quasi-self-concordant, so the GRN method applies, and in practice outperforms the paper’s method (at least the theoretically backed schedule). Since the examples are synthetic and fairly limited, it does not support a broader claim that the paper’s method needs less arithmetic operations compared with GRN. Moreover, the wall-clock measurement is not very convincing since it does not take parallelism into account, or other implementation details.
- Limited applicability - the upper bounds on the curvature constants that the paper proposes are very loose, and may render them trivial. It is unclear, at least when reading the paper, if these constants can be efficiently approximated. Furthermore, there is no proposed way to choose a block partition , or how such a choice might alter the results (i.e., a principled, theoretically justified way to choose a partition). The emphasis on block acceleration is thus somewhat misleading, at least in the empirical part, as all the experiments used very naive and trivial block partitions. Moreover, the constants are actually weakly monotone under sub-blocking, and since is additive for sub-blocks, it follows that the lowest values for are actually singletons. I might be missing something here, but this makes the entire claim somewhat awkward.
Questions for authors
- See the point about the choice of partition .
- How does parallelism affect the trade-off picture between sparsity and separability? In particular, if the "heavy" block operations (taking cubic time) can be parallelized, isn't it better with respect to wall-clock time?