acceptodds
Under review as a conference paper at ICLR 2027

Smooth or Separable? Sparse Block Acceleration for Entropy-Regularized Linear Programs

Abstract

We study entropy-regularized linear programs with sparse affine constraints and compare two exact dual representations induced by whether a redundant normalization constraint is retained or eliminated. Eliminating it yields a partially separable sum-exp dual with sparse affine factors but unbounded curvature. Our main result is an accelerated randomized block method whose acceleration preserves sparse data-access cost. The key ingredient is a global entropy-specific Hessian–gap bound that remains valid for signed constraint matrices, admits computable block-overlap refinements, and provides deterministic curvature certificates before sampling. This geometry supports square-root importance sampling and an exact lazy implementation in which sparse arithmetic cost is weighted by local curvature rather than by a worst-block factor. We further introduce a gap-dependent curvature dimension that connects the generalized-smooth regime to the classical effective-rank intuition for coordinate methods. Retaining the normalization constraint yields a log-sum-exp dual with globally bounded higher derivatives, enabling gradient-regularized and cubic-regularized Newton methods. Experiments compare the resulting methods in terms of coordinate epochs, arithmetic operations, and wall-clock time, separating the effects of acceleration, touched-data sparsity, and problem-specific structure.

Primary area:
optimization
Keywords:
entropy-regularized linear programming, accelerated coordinate descent, sparse optimization, generalized smoothness, primal–dual methods, tensor methods, optimal transport

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_3ampOpenReview ↗
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
  1. 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.
  2. The idea to upper bound curvature bounds by a separable pre-computed bound is nice.
Critical weaknesses
  1. 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 f⋆f^\star 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 π(0)\pi^{(0)}? 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?
  2. 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 O(1)O(1) bound computation.
  3. 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.
  4. 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 B\mathcal{B}, 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 κB\kappa_B are actually weakly monotone under sub-blocking, and since dBd_B is additive for sub-blocks, it follows that the lowest values for S0,S1S_0,S_1 are actually singletons. I might be missing something here, but this makes the entire claim somewhat awkward.
Questions for authors
  1. See the point about the choice of partition B\mathcal{B}.
  2. 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?
Reviewer_fnnpOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies entropy-regularized linear programs with sparse affine constraints through two dual representations: a globally smooth log-sum-exp dual and a partially separable sum-exp dual with unbounded curvature. Its main contribution is an accelerated randomized block method for the sum-exp dual, supported by an entropy-specific Hessian–gap bound that also applies to signed constraint matrices. A deterministic curvature schedule and an exact lazy implementation preserve sparse data access, with complexity bounds accounting for each block’s access cost. The paper also characterizes the log-sum-exp geometry and compares existing gradient and second-order methods. Experiments on synthetic sparse instances and DOTmark optimal transport problems evaluate convergence, arithmetic work, and runtime. An adaptive variant improves over coordinate baselines on synthetic instances, although it is not covered by the theory; the theoretically justified schedule is conservative, and Sinkhorn remains substantially faster on transport.

Critical strengths

The main strength is showing how acceleration can be made compatible with sparse data access for an entropy dual with unbounded curvature. The paper establishes a global Hessian–gap bound that accommodates signed constraint matrices and provides computable curvature bounds. It then uses these bounds to construct an accelerated block method without requiring per-iteration global-gap evaluations or auxiliary line minimizations, together with a lazy implementation and arithmetic bounds that account for each block’s curvature and access cost. This addresses a concrete obstacle to accelerating sparse entropy duals, since the auxiliary computations needed to control curvature can otherwise negate the savings from local updates.

Critical weaknesses

My main concern is the gap between the algorithm covered by the theory and the variant responsible for the empirical gains. The adaptive variant modifies the curvature constants in a way not covered by the analysis. With the proved constants, even using an oracle radius, the method requires 2,735 epochs to reach a relative dual gap of 10−610^{-6} on the main synthetic instance, compared with 185 for nonaccelerated RCD using the same exact coordinate step. The experiments therefore do not establish a practical computational advantage for the method that retains the theoretical guarantees, which limits the demonstrated practical significance of the proposed sparse acceleration framework.

Questions for authors

Could the authors isolate the benefit of acceleration by comparing the adaptive method with a nonaccelerated counterpart using the same curvature-adaptation rule, sampling rule, and exact coordinate solver? The existing exact-step RCD comparison does not fully isolate these factors, while the adaptive variant responsible for the reported gains is outside the theoretical guarantees. A matched comparison would materially affect my assessment of whether the proposed acceleration mechanism provides a meaningful computational advantage.

Reviewer_Fb4XOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper develops an accelerated BCD for solving the dual to sparse entropy-regularized LP. Besides the usual dual involving log-sum-exp function, they consider also an alternative (under a natural assumption) dual with the logarithm dropped. The former has advantage in good existing estimates of curvature (needed in accelerated BCD) bud drawback that its gradients have a normalization denominator which makes it nonseparable and prevents fully using sparsity. The block gradient of the latter is separable and cheaper to compute, as it fully uses sparsity, but curvature can be unbounded. To develop an acceletated BCD scheme for the latter faces the problem that its curvature is unbounded (hence it is not Lipschitz-smooth). So we have a dilemma: either give up smoothness, or give up full use of sparsity. The paper focuses on the latter, aiming to design a accelerated BCD for the latter dual with provable guarantee of usual asymptotic rates of accelerated BCDs, despite unbounded sparsity.

The main part is a technical and mathematical nontrivial analysis (main part of the long apendix) of the curvature of the dual function. A central result of the analysis is (4), showing that the block curvature (the block Hessian of the dual objective) is bounded by an affine function of the global objective gap, over the entire domain. This is then used to design a theoretically sound accelerated BCD, Algoritm 1. However, the algorithm is not fully faithful to the proved theory, it actually adapts curvatures during its run, which empirically leads to better convergence rate.

Simple experiments compare the method against baselines on synthetic entropy-regularized LPs. The results are not very convincing, showing that the method is just a bit better than simple randomized CD (using the same estimated curvatures, to my understanding). The authors honestly admit that their curvature upper bound can be very loose, which is confirmed by experiments in the suipplement, where it is sometimes 10410^4 times greater than the true curvature. This shows a big gap between the presented theoretical results and their utility for actual algorithms.

Critical strengths

First let me admit that accelerated BCD is not my exact field of research. But, after quite an effort, I have some understanding of the paper.

The theoretical analysis is nontrivial and I tend to believe it is correct (though I was not able to check all the proofs in detail - many pages in the supplement). The central result, global upper bound (4) on the curvature, has a compact and clear form.

In fact, the theory directly applies not only to exp-sum dual of regularized LP, but to any function that is a linear term plus a positive combination of exponentials of affine functions. Regularized LPs are just a motivation and could possibly be skipped (I am not sure, though, how this motivation is novel itself). Eg, there is a link to geometric programming (by Boyd).

Critical weaknesses

The paper is written such that it is understandable only to readers very familiar with the topic. It would be helpful to be more elementary and explicit in many places. The text is very compressed (as is the habit nowadays).

In particular, I struggled with the paper's motivation. At the first sight, gradient of ϕlse\phi_{lse} is not separable (due to the normalizing denominator), so full use sparsity is impossible. But the denominator (the sum of exps) can be kept as a running sum and updated incrementally. However, this is (to my understanding) easy in the raw BCD but much more complicated in its accelerated versions, right? The paper is very quick and brief on this, which leaves me unsure. Similarly, Proposition 2.1 suggests that B-updates in BCD could be interleaved with t-updates, bridging the gap between ϕse\phi_{se} and ϕlse\phi_{lse}. But this is probably impossible from a similar reason.

As the authors admit, the theoretical upper bound on curvature (4) can be very loose. This very negatively affects the algorithm, since the gradient step size factors are reciprocals of the curvature. This makes the impression that the theory (despite its mathematical beauty) is currently not very useful in practice.

In experiments, even the "vanilla" randomized CD is almost as fast (in wall-clock time, right-most plot in Figure 1) as the proposed method.

Moerover, if the initial goal is to solve sparse LPs, there is another appriximation gap caused by the entropy regularizer. This is made worse by the fact that with smaller γ\gamma the curvature will grow rapidly in some places near the polytope's boundary, which is probably so also for the upper bound gap (but I am not sure). Thus, there is a trade-off between making the entropy approximation good enough and the properties of the algorithm. The experiments report only the objective values of the regularized LP, it would be interesting to compare also to the initial unregularized LP.

Practical utility may be further weakened by the abundance of sparse LP solvers in the literature. A quick idea would be to empirically compare with the popular algorithm by Chambolle-Pock [https://link.springer.com/article/10.1007/s10851-010-0251-1], which has been adapted to LP [https://research.google/pubs/practical-large-scale-linear-programming-using-primal-dual-hybrid-gradient].

Questions for authors

See weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.