- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies stationary stochastic bandit convex optimization over the probability simplex , with one noisy function value per round and an -Lipschitz convex objective . The learner deploys multinomial policies, with , so that every action is feasible and the policy value is the multivariate Bernstein polynomial of . The policy mean is updated by entropic (Fisher-matched) mirror descent on a floored simplex using the unbiased one-point score estimator . Since need not be convex even when is, the analysis relies on first-order "bridge" inequalities that link policy gradients to the original objective: a replace-one argument for smooth and, for general convex , a scaled comparison whose error is absorbed by an implicit correction term in the update. The resulting guarantees are for convex Lipschitz objectives and under smoothness; given a known support bound , the paper further obtains for vertex optima and under "MP convexity" (convexity of for every ), for which a score–Hessian characterization and a sufficient subset-sum-plus-quadratic (SSQ) class are provided. Experiments on separable regularized quadratics with $K \in \lbrace 10, 100, 1000\rbrace $ compare against four one-point baselines.
Critical strengths
-
A natural and elegant construction. Multinomial sampling yields feasibility by construction, an exactly unbiased score estimator with a clean second-moment bound , and a mirror map that coincides with the normalized multinomial Fisher geometry. Connecting bandit convex optimization on the simplex with Bernstein-polynomial theory is an appealing perspective.
-
Careful treatment of a nonconvex policy value. The replace-one bridge (Lemma E.4) gives an error without convexity of , and in the general convex case the correction is placed inside an implicit composite update so that its contribution telescopes (Lemma F.5). Proposition F.1 shows that the uncorrected first-order comparison cannot hold with a uniformly vanishing error, which motivates the correction. I verified the main lemmas and found no errors.
-
Explicit treatment of dimension and boundaries. The analysis tracks dimension dependence and permits boundary optima. The numerical results show improvements over the included baselines.
Critical weaknesses
-
Significance of the rates. The horizon exponents ( in general and under smoothness) match those of classical one-point methods, while rates are known for the same stochastic setting (e.g., Fokkema et al., 2024, listed in Table 1). The gain therefore lies in the dependence on : ignoring logarithmic factors, the general bound improves on and remains nontrivial only when . For instance, at and (Figure 3), the explicit bound already exceeds the trivial bound . Stating this regime explicitly would give a more accurate picture than the "large-scale" framing.
-
Role of MP convexity and of the sparse results. Cases (i) and (ii) of Theorem 3.1 achieve the same rate, and the smooth case does not require MP convexity, so MP convexity and the SSQ class mainly serve to remove the correction term and to enable the sparse refinement. In addition, with the vertex result in Theorem 3.2(i) reduces to a standard -armed bandit over the vertices. Presenting these results as refinements may better reflect their role in the paper.
-
Experimental evaluation. Both test families are separable and therefore MP convex, so the corrected update for general convex objectives, a central component of the method, is not evaluated. Moreover, at several baselines remain nearly flat throughout, and the tuning ranges are not reported, which makes the comparison harder to interpret. Including a non-MP-convex objective and a -type baseline would strengthen the empirical section.
Questions for authors
-
Why is the correction weight set to with default ? By Eq. (95), choosing (i.e., ) gives and removes the term, whereas in the final bound (108) only contributes the additional term . Is there a reason to under-correct deliberately? Could the authors also evaluate the corrected update on a non-MP-convex objective, such as those in Example A.1 or Proposition F.1?
-
Table 1 lists "Negative-entropy MD (Flaxman et al., 2005; Hazan et al., 2016)" with ; please clarify whether this is a published result or the authors' own instantiation.
6 comments
For the second weakness
W3.2. Role of MP convexity and of the support-size refinements
Cases (i) and (ii) of Theorem 3.1 achieve the same rate, and the smooth case does not require MP convexity, so MP convexity and the SSQ class mainly serve to remove the correction term and to enable the sparse refinement. In addition, with the vertex result in Theorem 3.2(i) reduces to a standard -armed bandit over the vertices. Presenting these results as refinements may better reflect their role in the paper.
We agree with this assessment of their role in the original submission. The revision makes the distinction clearer: Theorem 3.1 gives the main guarantees without MP convexity, while Theorem 3.2 provides refinements based on the support size of a minimizer.
The revised main theorem does not require MP convexity. Unlike the two cases mentioned in the review, the revised Theorem 3.1 distinguishes general convex objectives from smooth convex objectives and gives different rates:
\quad\text{and}\quad \widetilde O(K^{1/3}T^{2/3}),$$ respectively. Both use Algorithm 1 with their prescribed parameter rules. Neither requires the objective to be MP convex or its multinomial policy value to be convex. **The self-normalized score removes the correction-term choice.** The revised update removes the choice between $\Phi=0$ and $\Phi=\Phi_n$. It uses the weighted score (13), combining the count score (11) with the self-normalized score (12), and has no branch based on whether the objective is MP convex. The analytical change is that the two scores estimate different quantities. The count score estimates the tangent derivatives of the policy value. Proposition B.1 identifies an obstruction to using these derivatives for a uniform first-order comparison with vanishing additive error over general convex Lipschitz objectives. The self-normalized score instead estimates the shift field defined through scaled one-sample reassignment differences. Appendix B.3 shows how to estimate this field from the same single noisy observation, without additional evaluations at neighboring actions. Lemma B.6 then supplies the required first-order comparison with controlled error, even when the policy value is nonconvex. The general convex rule uses only this score ($\lambda=1$); under smoothness, the prescribed weighted score exploits the sharper comparison available for the count score. The revised method also performs well empirically: Table 2 reports the lowest mean for both performance measures in every row, averaging equally over the five objective families, including non-MP-convex ones. **The support-size refinement now extends beyond MP convexity.** For $s\ge2$, Theorem 3.2(ii) gives $$\mathcal R(T)=\widetilde O((Ks)^{1/4}T^{3/4})$$ under the support-size parameter rule (20), whenever the convex Lipschitz objective admits $$V=V_1+V_2,$$ where $V_1$ is MP convex, possibly nonsmooth, and $V_2$ is convex and smooth, possibly not MP convex. This includes MP-convex objectives ($V_2=0$), smooth objectives ($V_1=0$), and objectives that are neither MP convex nor smooth. Our generated $f_{\mathrm{sabs}}$ instances exemplify the last case (Section 4.1 and Appendix F.1). The decomposition is used only in the analysis and need not be supplied to the algorithm. Relative to the general convex bound, this replaces the dimension factor $K^{1/2}$ by $(Ks)^{1/4}$. MP convexity therefore supplies a sufficient structural condition for exploiting a smaller optimizer support, including in nonsmooth problems. The SSQ class provides explicit, checkable examples of this condition, including separable convex functions, convex quadratics, and functions with subset-sum couplings. The SSQ sufficient condition and its applications are now presented in Appendix A.2, with the relationship among classes illustrated in Figure 2. **The vertex case recovers the finite-armed setting.** We agree that, when $s=1$, rule (20) gives $n=1$ and, after the initial reference evaluation, the sampled actions are the $K$ vertices. In particular, $$F_{V,1}(m)=\sum_{k=1}^K m_kV(e_k).$$ Since a minimizer is a vertex, the best vertex attains $V^\star$, so the sampling problem is a $K$-armed bandit problem. Theorem 3.2(i) recovers the familiar regret order up to a $\sqrt{\log K}$ factor, without MP convexity. Its role is to show that the same framework recovers this limiting case, alongside the support-size refinements for minimizers on higher-dimensional faces of the simplex.For the third weakness
W3.3. Experimental evaluation
Both test families are separable and therefore MP convex, so the corrected update for general convex objectives, a central component of the method, is not evaluated. Moreover, at several baselines remain nearly flat throughout, and the tuning ranges are not reported, which makes the comparison harder to interpret. Including a non-MP-convex objective and a -type baseline would strengthen the empirical section.
We have substantially expanded the experiments in response to these suggestions. Section 4 and Appendix F now include nonseparable, non-MP-convex objectives, two -type baselines, detailed tuning protocols, and performance curves across dimensions and optimizer support sizes.
Non-MP-convex objectives and the general convex update. The experiments use the revised Algorithm 1, whose weighted update (13) includes the self-normalized score with positive weight in every experimental configuration. As explained in W3.2, this update removes the earlier correction-term choice and applies without requiring MP convexity.
The evaluation now covers five objective families. Three are nonseparable: , , and , whose coupling terms involve with randomly selected partners. The first is smooth; the latter two are nonsmooth. Appendix F.2 verifies non-MP-convexity instance by instance: an instance is retained only if the smallest eigenvalue of the Hessian of restricted to the simplex tangent space is at most . Thus, every retained instance in these three families has a nonconvex multinomial policy value at resolution two.
Across their 27 family-setting combinations at (Tables 9–11), our method achieves the lowest final mean best-so-far gap in every case and the lowest mean pseudo-regret in 26 cases. The exception is at , –, where its mean pseudo-regret is comparable to Simplex ZO-PGD: 0.1530 versus 0.1521. These results directly evaluate the revised algorithm beyond the MP-convex setting.
Two -type baselines. The comparison now includes the surrogate-loss ellipsoid method (Lattimore & György, 2021) and Online Newton (Fokkema et al., 2024), alongside four methods based on gradient estimates. All seven methods receive one noisy objective value per round, use an initial observation at the simplex center as their reference, and are tuned on separate tuning functions. At the tested horizons, Ellipsoid and Online Newton have the two largest mean pseudo-regrets in every row of the aggregate results in Table 2(a). Tables 7–11 provide the results for individual objective families.
Interpreting the learning curves and the revised experiment. We now report results separately for three support-size groups at each dimension: , , and . Figures 4–12 show both and the best-so-far gap, with bands representing one standard error across test functions.
Appendix F.6 discusses the observed differences. Simplex ZO-PGD continues to improve in higher dimensions and with smaller optimizer supports. For the other baselines, substantial improvement is largely confined to with full or moderately large support; at , or with smaller supports, their curves are nearly flat over much of the tested horizon. This describes their progress within the reported evaluation budgets.
At , Figure 1 uses the longer horizon and compares our method with Simplex ZO-PGD, the strongest baseline in Table 2. Our final average pseudo-regret is at most 60% of its value. On the three non-MP-convex families, our final best-so-far gaps are 2–11%, compared with 11–33% for Simplex ZO-PGD.
Tuning ranges and computational costs. Appendix F.4 and Table 5 report the tuned parameters and initial grids for all seven methods. Searches start from these grids and refine the best candidate by local search. Tuning is performed separately for each objective family, pair, and support-size group, minimizing mean on tuning functions. The selected configuration is then fixed on separate testing functions; Table 4 reports their numbers.
Appendix F.4 also reports per-iteration times in Figure 3 and Table 6 and explains the implementation costs. At , the measured times are 0.0804 ms for our method, 6.83 ms for Ellipsoid, and 1.57 s for Online Newton. The latter uses dense matrix decompositions and linear solves, with an additional constrained quadratic solve when needed.
For the first weakness
W3.1. Significance of the rates and the “large-scale” framing
We agree that the significance of our rates lies in their dimension–horizon tradeoff, and that its relevant regimes should be explicit. The revised manuscript clarifies this through Table 1, matching algorithm-specific lower bounds in Theorem 3.1, and minimax lower bounds in Appendix E.
1. The regimes where our rate expressions are favorable. Table 1 of the revised manuscript reports an Online Newton bound with polynomial dependence K3/2T1/2. Ignoring constants, logarithmic factors, and confidence factors, our general convex expression K1/2T3/4 is no larger than both T and K3/2T1/2 in the window K2≲T≲K4, equivalently T1/4≲K≲T1/2, as the reviewer observes. Under smoothness, our expression K1/3T2/3 gives the wider comparison window K≲T≲K7. These are comparisons of polynomial dependence; constants and logarithmic factors matter near the crossover scales. Beyond the respective upper crossover, the smaller horizon exponent of the Online Newton bound becomes favorable.
The lower crossover is also significant. Ignoring logarithms, the Online Newton and negative-entropy MD bounds in Table 1 reach the linear scale at T≍K3, whereas our general convex bound reaches it at T≍K2. Our dependence on dimension therefore allows a useful guarantee at a smaller horizon relative to K.
2. Worst-case theoretical bounds and actual experimental performance must be distinguished. The theoretical bounds provide uniform guarantees over an entire class of objectives and feedback laws. The experiments measure the regret actually attained on the tested instances. If an explicit upper bound exceeds 2LT, that bound is less informative than the trivial guarantee at that horizon. This does not imply that the algorithm actually incurs linear regret or performs poorly. Similarly, comparing two upper bounds alone does not determine which method performs better on a particular instance.
Accordingly, the windows above characterize where the stated rate expressions are favorable; they do not delimit where the algorithm can perform well empirically. The upper bounds in Theorem 3.1 remain valid for every K,T≥2. The theory characterizes worst-case behavior, while the experiments assess actual performance at finite evaluation budgets.
3. The new lower bounds explain the significance of the tradeoff. Theorem 3.1 now establishes matching worst-case rates for Algorithm 1 under its prescribed parameter rules:
\quad\text{for }T\gtrsim K^2\log K,$$ and, under smoothness, $$\widetilde\Theta(K^{1/3}T^{2/3}) \quad\text{for }T\gtrsim K\log K.$$ Thus, these exponents are intrinsic to Algorithm 1 with those rules. Theorem E.1 further proves $$\mathcal R_{\mathrm{minimax}}(T,\mathcal I_{\mathrm{cvx}}) =\Omega\left(\min\{T,K\sqrt T\}\right).$$ Consequently, when $T\lesssim K^2$, every algorithm has worst-case regret of order $T$ over the general convex class. Our general convex guarantee reaches this necessary horizon scale up to a logarithmic factor. The requirement for a sufficiently large horizon therefore reflects the difficulty of the problem itself. For smooth objectives, Theorems 3.1(ii) and E.2 establish minimax optimality up to logarithmic factors for $K\lesssim T\lesssim K^4$. This minimax conclusion is distinct from the wider comparison window against the Online Newton bound. Appendix E.2 also discusses the remaining gaps at longer horizons. **4. The practical meaning of “large-scale.”** For a given dimension $K$, the favorable comparison window covers substantial evaluation budgets: $T=K^4=10^8$ at $K=100$ and $T=K^4=10^{12}$ at $K=1000$. The revised introduction therefore motivates the method through its mild dependence on dimension when function evaluations are limited. Its computational cost supports this motivation: for fixed resolution, our implementation uses $O(K\log K)$ work and $O(K)$ working memory per round, excluding objective evaluation (Appendix F.4). Its measured per-iteration time increases only from approximately 0.036 ms at $K=10$ to 0.080 ms at $K=1000$.