Entropy-Smooth Convex Optimization Cannot Be Accelerated

Technical Summary: Entropy-Smooth Convex Optimization Cannot Be Accelerated

Problem Statement
This paper investigates the convergence rates of first-order optimization methods for minimizing convex functions that are $L$-smooth relative to the negative Shannon entropy on the standard $d$-simplex, $\Delta_d$. Specifically, the authors consider the class of functions $\text{Ent}_d(L)$, defined by the condition that the Bregman divergence of the objective function $f$ with respect to the negative entropy $h(x) = \sum x_k \log x_k$ is bounded by $L$ times the Bregman divergence of $h$ itself.

While standard mirror descent achieves a convergence rate of $O(L \log d / T)$ for this class, a natural question arises whether "accelerated" methods (analogous to Nesterov's acceleration in Euclidean settings) can achieve an $O(1/T^2)$ rate. Previous work by Dragomir et al. (2022) suggested acceleration might be impossible under relative smoothness, but their counterexamples relied on pathological prox-functions constructed adversarially alongside the hard instances. The central question addressed here is whether acceleration is impossible for the specific, highly structured prox-function of negative entropy, which is widely used in practice.

Methodology
The authors employ a black-box complexity framework, constructing a "resisting oracle" to prove a lower bound on the convergence rate for any deterministic first-order method. The core of their methodology involves:

1. Hard Instance Construction: They construct a sequence of "backbone" functions, defined as the maximum of shifted coordinate atoms ($g(u) = \max_k \{-u_{j_k} - b_k\}$).
2. Smoothing via Right Bregman-Moreau Envelope: To ensure the hard instances belong to the class $\text{Ent}_d(L)$ (which requires relative smoothness but allows non-differentiability on the boundary), the authors apply the right Bregman-Moreau envelope to these non-smooth backbones. This smoothing mechanism relies crucially on the joint convexity of the Kullback-Leibler (KL) divergence, a property unique to the Euclidean and KL cases among Bregman divergences.
3. Adaptive Query Response: The resisting oracle interacts with an arbitrary algorithm by selecting a new coordinate atom at each step corresponding to the coordinate with the smallest mass in the algorithm's current query point. The offsets of these atoms are incremented to ensure that new atoms remain "locally invisible" (strictly dominated) near the proximal points of previous queries.
4. Transcript Consistency: Using the locality properties of the Bregman-Moreau envelope (Lemma 4), the authors prove that the smoothed function constructed at the final step is consistent with all previous oracle responses, ensuring the lower bound applies to the entire interaction.

Key Results
The paper establishes the following main theorems:

• Lower Bound for Simplex Optimization (Theorem 1 & 5): For any deterministic first-order method making $T$ queries, there exists a function $f \in \text{Ent}_d(L)$ such that the suboptimality gap satisfies:
  $$f(x_{T+1}) - \min_{x \in \Delta_d} f(x) > \frac{L}{4(T+1)}$$
  provided the dimension $d = \Omega(T^2)$. This result demonstrates that accelerated $O(1/T^2)$ convergence is unattainable for this class. Consequently, the standard mirror descent rate of $O(L \log d / T)$ is optimal up to a logarithmic factor when the dimension is sufficiently large.
• Quantum Extension (Theorem 11): The result extends to the non-commutative setting of the spectrahedron (density matrices). For functions $L$-smooth relative to the negative von Neumann entropy, the same $\Omega(L/T)$ lower bound holds. This is proven by embedding the diagonal hard instances into the matrix space and utilizing Lindblad's data processing inequality.
• Interpolation Conditions (Section 5): The authors derive explicit pointwise minimal interpolants for the class $\text{Ent}_d(L)$, generalizing results from Dragomir's PhD thesis. These conditions are necessary for the existence of a function in the class that fits given first-order data.

Significance and Claims
The paper claims to resolve the open question of whether acceleration is possible for entropy-smooth optimization. The authors argue that their result is significant because:

• It rules out acceleration for a specific, favorable prox-function (negative entropy) rather than a pathological one. This contrasts with prior negative results where the potential function was constructed specifically to defeat acceleration.
• It confirms the optimality of Mirror Descent for this class, suggesting that the logarithmic gap between the upper bound ($O(L \log d / T)$) and the lower bound ($O(L/T)$) is likely due to the dimensionality of the problem rather than a flaw in the algorithm.
• It highlights the limitations of Performance Estimation Programs (PEP) in non-Euclidean geometries, noting that while PEPs can construct pathological counterexamples, they struggle with structured settings like the simplex with entropy.

The authors modestly note that a logarithmic gap ($\log d$) remains between their lower bound and the known upper bound. They suggest that the derived interpolation conditions in Section 5, combined with recent primal-dual frameworks, might be leveraged to recover this missing factor, but they do not claim to have closed this gap in the current work. Furthermore, they note that for extremely high dimensions ($d = \exp(T)$), acceleration is not formally ruled out, though such regimes are of limited practical interest.