acceptodds
Under review as a conference paper at ICLR 2027

Multinomial policies for large-scale bandit convex optimization on the simplex: algorithm design and performance analysis

Abstract

Optimization over the simplex arises in a wide range of large-scale resource and workload allocation problems. We study an unknown convex objective through noisy one-point feedback and develop a multinomial-policy method that samples feasible allocations. A geometry-adapted stochastic mirror descent update learns the policy mean, while first-order comparisons connect its gradients to regret for the original objective even when the policy value is nonconvex. We prove sublinear regret with explicit dimension dependence for general convex objectives, sharper bounds under smoothness and, with additional structure, optimizer sparsity, and guarantees for boundary optima. Numerical experiments compare fixed-reference multinomial updates with simplex baselines.

Primary area:
optimization
Keywords:
online optimization, bandit convex optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_RB1YOpenReview ↗
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 ΔK−1\Delta_{K-1}, with one noisy function value per round and an ℓ1\ell_1-Lipschitz convex objective VV. The learner deploys multinomial policies, X=N/nX = N/n with N∼Mult(n,m)N \sim \mathrm{Mult}(n, m), so that every action is feasible and the policy value FV,n(m)=E[V(N/n)]F_{V,n}(m) = \mathbb{E}[V(N/n)] is the multivariate Bernstein polynomial of VV. The policy mean mm is updated by entropic (Fisher-matched) mirror descent on a floored simplex using the unbiased one-point score estimator gt,k=(Yt+1−Yref)(Nt,k/mt,k−n)g_{t,k} = (Y_{t+1} - Y_{\mathrm{ref}})(N_{t,k}/m_{t,k} - n). Since FV,nF_{V,n} need not be convex even when VV is, the analysis relies on first-order "bridge" inequalities that link policy gradients to the original objective: a replace-one argument for smooth VV and, for general convex VV, a scaled comparison whose error is absorbed by an implicit correction term ρTΦn\rho_T \Phi_n in the update. The resulting guarantees are O~(K1/2T3/4)\tilde{O}(K^{1/2} T^{3/4}) for convex Lipschitz objectives and O~(K1/3T2/3)\tilde{O}(K^{1/3} T^{2/3}) under smoothness; given a known support bound ss, the paper further obtains O~(KT)\tilde{O}(\sqrt{KT}) for vertex optima and O~((Ks)1/4T3/4)\tilde{O}((Ks)^{1/4} T^{3/4}) under "MP convexity" (convexity of FV,nF_{V,n} for every nn), 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
  1. A natural and elegant construction. Multinomial sampling yields feasibility by construction, an exactly unbiased score estimator with a clean second-moment bound B2n(K−1)B^2 n (K-1), 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.

  2. Careful treatment of a nonconvex policy value. The replace-one bridge (Lemma E.4) gives an O(β/n)O(\beta/n) error without convexity of FV,nF_{V,n}, 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.

  3. 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
  1. Significance of the rates. The horizon exponents (T3/4T^{3/4} in general and T2/3T^{2/3} under smoothness) match those of classical one-point methods, while O~(poly(K)T)\tilde{O}(\mathrm{poly}(K)\sqrt{T}) 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 KK: ignoring logarithmic factors, the general bound improves on K3/2TK^{3/2}\sqrt{T} and remains nontrivial only when T1/4≲K≲T1/2T^{1/4} \lesssim K \lesssim T^{1/2}. For instance, at K=1000K = 1000 and T=4×104T = 4 \times 10^4 (Figure 3), the explicit bound already exceeds the trivial bound 2LT2LT. Stating this regime explicitly would give a more accurate picture than the "large-scale" framing.

  2. 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 n=1n = 1 the vertex result in Theorem 3.2(i) reduces to a standard KK-armed bandit over the vertices. Presenting these results as refinements may better reflect their role in the paper.

  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 K=1000K = 1000 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 T\sqrt{T}-type baseline would strengthen the empirical section.

Questions for authors
  1. Why is the correction weight set to ρT=max⁡{2/π−cT−1/8 0}\rho_T = \max\lbrace \sqrt{2/\pi} - c T^{-1/8}\, 0\rbrace with default c=1c = 1? By Eq. (95), choosing ρ=2/π\rho = \sqrt{2/\pi} (i.e., c=0c = 0) gives sρ=0s_\rho = 0 and removes the 2Lsρ/nδ2L s_\rho/\sqrt{n\delta} term, whereas in the final bound (108) c>0c > 0 only contributes the additional term cL(K−1)1/4(log⁡K)1/8T3/4cL(K-1)^{1/4}(\log K)^{1/8} T^{3/4}. 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?

  2. Table 1 lists "Negative-entropy MD (Flaxman et al., 2005; Hazan et al., 2016)" with O~(KT3/4)\tilde{O}(KT^{3/4}); please clarify whether this is a published result or the authors' own instantiation.

6 comments
AuthorsOpenReview ↗

For the first weakness

W3.1. Significance of the rates and the “large-scale” framing

The horizon exponents match those of classical one-point methods, while O~(poly(K)T)\widetilde O(\mathrm{poly}(K)\sqrt T) rates are known. The gain therefore lies in the dependence on KK. Stating the dimension–horizon regime explicitly would give a more accurate picture than 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/2K^{3/2}T^{1/2}. Ignoring constants, logarithmic factors, and confidence factors, our general convex expression K1/2T3/4K^{1/2}T^{3/4} is no larger than both TT and K3/2T1/2K^{3/2}T^{1/2} in the window K2≲T≲K4,K^2\lesssim T\lesssim K^4, equivalently T1/4≲K≲T1/2T^{1/4}\lesssim K\lesssim T^{1/2}, as the reviewer observes. Under smoothness, our expression K1/3T2/3K^{1/3}T^{2/3} gives the wider comparison window K≲T≲K7.K\lesssim T\lesssim K^7. 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≍K3T\asymp K^3, whereas our general convex bound reaches it at T≍K2T\asymp K^2. Our dependence on dimension therefore allows a useful guarantee at a smaller horizon relative to KK.

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 2LT2LT, 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≥2K,T\ge2. 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$.
AuthorsOpenReview ↗

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 n=1n=1 the vertex result in Theorem 3.2(i) reduces to a standard KK-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.
AuthorsOpenReview ↗

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 K=1000K=1000 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 T\sqrt{T}-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 T\sqrt{T}-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: fslogf_{\mathrm{slog}}, fsabsf_{\mathrm{sabs}}, and fpwaf_{\mathrm{pwa}}, whose coupling terms involve xk−xpj,kx_k-x_{p_{j,k}} 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 FV,2F_{V,2} restricted to the simplex tangent space is at most −0.01-0.01. Thus, every retained instance in these three families has a nonconvex multinomial policy value at resolution two.

Across their 27 family-setting combinations at K=10,50,100K=10,50,100 (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 fsabsf_{\mathrm{sabs}} at K=10K=10, s=2s=2–44, 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 T\sqrt{T}-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 K=1000K=1000 experiment. We now report results separately for three support-size groups at each dimension: s=Ks=K, 0.6K≤s≤0.8K0.6K\le s\le0.8K, and 0.2K≤s≤0.4K0.2K\le s\le0.4K. Figures 4–12 show both Rt/tR_t/t 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 K=10K=10 with full or moderately large support; at K=50,100K=50,100, 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 K=1000K=1000, Figure 1 uses the longer horizon T=5×106T=5\times10^6 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, (K,T)(K,T) pair, and support-size group, minimizing mean RT/TR_T/T 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 K=1000K=1000, 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.

Reviewer_XeN4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies zeroth-order (bandit) convex optimization over a simplex, with just one noisy function evaluation per round being permitted. The authors propose a novel multinomial policy approach: at each round, they sample a feasible allocation from a multinomial distribution parameterized by a mean vector on the simplex, observe a noisy objective value, and update the mean via a Fisher-geometry mirror descent step. This approach allows them to naturally satisfy the simplex constraint but on the flip side, the the resulting cost landscape can be nonconvex even when the original objective function is convex. This is a tradeoff that the paper recognizes. The paper establishes regret bounds for general convex Lipschitz objectives and under smoothness, with further improvements under MP convexity and sparse optimizer assumptions. Numerical experiments are conducted to compare against several baselines on smooth and nonsmooth test functions and tend to show that the proposed approach always outperforms the baselines.

Critical strengths

The technical contributions of the paper- analyzing the feasiblity vs nonconvexity tradeoff honestly and providing solutions and results that are impressive. The results reported without the MP-convexity condition is a clean and valuable result. The bound improvements also appear to be clearly better than prior approaches.

Critical weaknesses
  1. Technical: MP convexity comes across as a method-specific assumption of limited practical scope.

  2. Numerical: Experiments are limited in scope and do not validate the paper's most important claims.

  • Sparse optimizer results are theoretically interesting but practically limited and experimentally untested.
  • Test objectives are fully separable with zero interaction between allocation variables. This hurts generalizability and we do not know if this algorithm fails against strong baselines when we no longer have such simple settings.
  • The wall-clock times, per-round computational cost, or how these scale with K, etc appear to me missing.

overall, the paper has no discussion of the limitations of the proposed approach- it does not appear to fail in any of the experiments, and settings where it performs better or worse.

Questions for authors
  1. How realistic is the MP convexity assumption?
  2. for what settings and problem types does the algorithm do well and where does it underperform compared to what baselines?
  3. Can you discuss the issues around the discretization cost?
  4. The sparse results require knowing 's' before the run- how realistic is this and what experimental results do we have for the sparse optimizer?
5 comments
AuthorsOpenReview ↗

For the first weakness and the first question

W2.1 & Q2.1. Practical scope of MP convexity

MP convexity comes across as a method-specific assumption of limited practical scope. How realistic is the MP convexity assumption?

The role of MP convexity. MP convexity is defined relative to the multinomial policy: Definition 2.2 requires FV,nF_{V,n} to be convex for every resolution nn. We have clarified its role in the revised manuscript. The main regret guarantees in Theorem 3.1 do not assume MP convexity; this property provides one sufficient condition for the support-dependent refinement in Theorem 3.2. Appendix A.2 gives a directly verifiable sufficient class, and Figure 2 summarizes its relationship with the other objective classes.

1. The algorithm and main guarantees do not require MP convexity. Algorithm 1 uses the count score (Eq. (11)), the self-normalized score (Eq. (12)), and their weighted combination (Eq. (13)). It does not require an MP-convexity test or an indicator specifying whether the objective is MP convex.

The key point is that the self-normalized score estimates a shift field satisfying a first-order comparison with controlled error (Lemmas B.5–B.6). This comparison relates the policy value directly to the original convex objective, even when the policy value is nonconvex. Appendix B.3 explains the construction. Proposition B.1 identifies why the policy-value gradient estimated by the count score cannot provide a uniform comparison with vanishing additive error over the entire convex Lipschitz class.

With the prescribed parameter rules, Theorem 3.1 gives

R(T)=O~(K1/2T3/4)\mathcal R(T)=\widetilde O(K^{1/2}T^{3/4})

for general convex Lipschitz objectives and

R(T)=O~(K1/3T2/3)\mathcal R(T)=\widetilde O(K^{1/3}T^{2/3})

for smooth convex objectives, without assuming MP convexity in either case. Section 4 also evaluates three non-MP-convex objective families. Appendix F.2 verifies nonconvexity of FV,2F_{V,2} for every retained instance, and Tables 9–11 show that our method attains the lowest mean best-so-far gap in every tested setting of these three families. Figure 1 extends the comparison to K=1000K=1000.

2. The support-dependent refinement allows objectives that are not MP convex. For minimizers with support size s≥2s\ge2, Theorem 3.2(ii)(c) requires a decomposition

V=V1+V2,V=V_1+V_2,

where V1V_1 is MP convex, possibly nonsmooth, and V2V_2 is convex and smooth, possibly not MP convex. This includes MP-convex objectives by taking V2=0V_2=0, smooth objectives by taking V1=0V_1=0, and sums that are neither MP convex nor smooth. The decomposition is needed only in the analysis and need not be known to the algorithm.

The non-MP-convex, nonsmooth experimental family fsabsf_{\mathrm{sabs}} illustrates the last case: its separable absolute-value terms form the MP-convex component, while its smooth coupling terms and additive constant form the smooth convex component. Moreover, the vertex-minimizer result in Theorem 3.2(i) does not require MP convexity.

3. A verifiable class covers standard objective structures. Checking Definition 2.2 directly would require checking every resolution. Proposition A.1 instead provides a sufficient condition based on the objective's form. Every subset-sum plus quadratic (SSQ) objective

\sum_{i=1}^I\phi_i\left(\sum_{k\in\mathcal K_i}x_k\right)$$ is MP convex when $Q=Q^\top$ satisfies $$h^\top Qh\ge0 \quad\text{whenever}\quad \mathbf1^\top h=0,$$ each $\phi_i:[0,1]\to\mathbb R$ is convex, and the $\mathcal K_i$ are nonempty proper subsets of $\{1,\ldots,K\}$. The subsets may overlap. The proof uses multinomial second moments, binomial aggregation of subset sums, and preservation of univariate convexity by Bernstein polynomials. This class includes all separable convex objectives and all quadratic objectives that are convex on the simplex. Overlapping subsets also allow coupling through group totals, and the functions $\phi_i$ need not be differentiable. Thus the sufficient condition covers both coupled and nonsmooth objectives. Appendix A.2 identifies applications of these structures in power and resource allocation (Patriksson, 2008; Boyd & Vandenberghe, 2004), mean–variance portfolio selection (Markowitz, 1952), convex aggregation of predictors (Juditsky & Nemirovski, 2000), and single-commodity traffic assignment over paths (Beckmann et al., 1956; Roughgarden & Tardos, 2002). These applications illustrate separable costs, quadratic interactions, and costs depending on group totals. Resource and workload allocation are also the motivating examples developed in the revised introduction.
AuthorsOpenReview ↗

For the second weakness

W2.2. Scope of the experiments

Experiments are limited in scope: the sparse-optimizer results are untested, the test objectives are fully separable, so it is unclear whether the algorithm fails against strong baselines in harder settings, and wall-clock times, per-round costs and their scaling with KK are missing.

We have expanded the experiments in Section 4 and Appendix F to address all three concerns.

(a) Minimizer support sizes. Each objective family is tested at K=10,50,100,1000K=10,50,100,1000, with horizons T=2×103,104,5×104,5×106T=2\times10^3,10^4,5\times10^4,5\times10^6, respectively, and three support-size groups:

s=K,0.6K≤s≤0.8K,0.2K≤s≤0.4K.s=K,\qquad 0.6K\le s\le0.8K,\qquad 0.2K\le s\le0.4K.

The first group has interior minimizers, while the latter two have boundary minimizers. Appendix F.3 generates instances from prescribed minimizers, using optimality conditions to determine the coefficients, so their support sizes are known by construction. Table 4 reports 100, 150, 200, and 300 testing functions per family and support-size group for the four dimensions, respectively.

In the experiments, the resolution nn is tuned directly on separate tuning functions, rather than computed from each test instance's exact ss. Tuning is organized by objective family, (K,T)(K,T) pair, and support-size group, and the selected configurations are held fixed for testing (Appendix F.4). Thus the experiments assess performance with smaller supports using representative tuning tasks from the same group.

(b) Nonseparable objectives and stronger baselines. Appendix F.1 now includes three families with coordinate coupling: fslogf_{\mathrm{slog}}, fsabsf_{\mathrm{sabs}}, and fpwaf_{\mathrm{pwa}}. The first is smooth; the latter two are nonsmooth. Appendix F.2 checks every retained instance and verifies that its policy value FV,2F_{V,2} is nonconvex, so none of these instances is MP convex.

For K=10,50,100K=10,50,100, we compare seven methods: ours, negative-entropy MD, Euclidean PGD, Simplex ZO-PGD, projection-free BCO, surrogate-loss ellipsoid (Lattimore & György, 2021), and online Newton (Fokkema et al., 2024). The last two have T\sqrt{T}-type regret guarantees in their original settings, as summarized in Table 1. Every method receives one noisy objective value per round and is tuned on separate tuning functions before evaluation on held-out testing functions.

Table 2 averages equally over the five families; our method has the lowest mean average pseudo-regret and best-so-far gap in every row. Tables 7–11 give the family-level results: our method has the lowest mean best-so-far gap in every setting, and the lowest mean average pseudo-regret except for fsabsf_{\mathrm{sabs}} at K=10K=10, s=2s=2–44, where it is comparable to Simplex ZO-PGD. Figures 4–12 provide the corresponding learning curves.

At K=1000K=1000, Figure 1 compares our method with Simplex ZO-PGD, the strongest baseline in Table 2. Our final average pseudo-regret is at most 60% of Simplex ZO-PGD's. On the three non-MP-convex families, our final best-so-far gaps are 2–11%, compared with 11–33% for Simplex ZO-PGD.

(c) Computational cost and scaling. Appendix F.4, Figure 3, and Table 6 report per-iteration times for all seven methods at K=10,50,100,1000K=10,50,100,1000. These are single-run measurements on a MacBook Pro with a 10-core Apple M5 CPU and 24 GB of memory, with numerical-library thread limits set to one.

For fixed resolution nn, our implementation computes the scores coordinatewise and performs the floored KL update by sorting KK weights. This requires O(Klog⁡K)O(K\log K) work and O(K)O(K) working memory per iteration, excluding objective evaluation. Each sampled count vector produces one simplex action, so each round uses one objective query regardless of nn.

Our measured per-iteration times are 0.0356, 0.0374, 0.0403, and 0.0804 ms as KK increases from 10 to 50, 100, and 1000. At K=1000K=1000, this is comparable to the four baselines based on gradient estimates (0.0495–0.092 ms), while Ellipsoid takes 6.83 ms and Online Newton takes 1.57 s.

Appendix F.4 explains the latter cost: the implemented Online Newton method performs eigendecompositions, dense matrix reconstructions, and linear solves on (K−1)×(K−1)(K-1)\times(K-1) matrices. These dense operations each require O((K−1)3)O((K-1)^3) work, with O((K−1)2)O((K-1)^2) matrix storage. Extrapolating its measured 1.57 s per iteration to T=5×106T=5\times10^6 gives approximately 91 days for one run, assuming the per-iteration cost remains unchanged.

AuthorsOpenReview ↗

For the third weakness and the second question

W2.3 & Q2.2. Limitations; where the algorithm does well and where it underperforms

W2.3: Overall, the paper has no discussion of the limitations of the proposed approach — it does not appear to fail in any of the experiments, and settings where it performs better or worse.

Q2.2: For what settings and problem types does the algorithm do well and where does it underperform compared to what baselines?

We agree that the original submission did not discuss these distinctions sufficiently. The revised manuscript provides a more detailed picture in Section 4.2, Appendices E.2 and F.5–F.6, and the conclusion.

(1) Where it performs well. In the tested simplex problems, our method performs well across both MP-convex and non-MP-convex objectives, including smooth and nonsmooth families. Table 2 reports the lowest mean average pseudo-regret and best-so-far gap for our method in every row after averaging equally over the five families. Tables 7–11 show the results separately for each family.

The relative advantage is generally larger in the tested settings with smaller support sizes. For example, at K=100K=100 and s=20s=20–4040, Table 2 reports average pseudo-regret 0.17140.1714 for our method versus 0.27060.2706 for Simplex ZO-PGD, and best-so-far gaps of 6.06% versus 11.79%. Smaller support does not make the tested problems easier in absolute terms: Section 4.2 notes that average pseudo-regret increases as ss decreases for every method.

Simplex ZO-PGD is the strongest baseline overall. At K=1000K=1000, our method eventually overtakes it and achieves final average pseudo-regret at most 60% of its value. On the three non-MP-convex families, the final best-so-far gap is 2–11%, versus 11–33% for Simplex ZO-PGD (Figure 1).

(2) Where it underperforms. The revised results identify several qualifications.

  • A slightly worse final mean pseudo-regret in one setting. For the non-MP-convex, nonsmooth family fsabsf_{\mathrm{sabs}} at K=10K=10, s=2s=2–44, our mean RT/TR_T/T is 0.15300.1530, compared with 0.15210.1521 for Simplex ZO-PGD (Table 10(a)). Our best-so-far gap is nevertheless smaller, 2.18% versus 2.63% (Table 10(b)). Thus this exception concerns cumulative performance, not the quality of the best action found.
  • Higher regret during initial exploration. At K=1000K=1000, Figure 1 shows higher average pseudo-regret for our method during an initial exploration phase, before it overtakes Simplex ZO-PGD. Its stronger final performance therefore does not imply dominance throughout the run.

(3) Limits of the experimental evidence. The experiments use five synthetic objective families, with parameters selected on separate tuning functions for each objective family, (K,T)(K,T) pair, and support-size group. The selected configurations are then held fixed for testing. The results therefore concern this tuning protocol and these problem families. The seven-method performance comparison covers K=10,50,100K=10,50,100; at K=1000K=1000.

(4) Scope and future work. The principal limitation of the present work is its focus on simplex-constrained optimization. The multinomial policy naturally produces feasible simplex-valued actions, but it does not automatically enforce additional linear or integer constraints. Extending the approach to such problems would require adapting the sampling policy and establishing corresponding regret guarantees. As stated in Section 5, this extension is an important direction for future work. Our current results therefore establish the method within the simplex setting, while its applicability to more general constrained problems remains to be investigated.

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

This paper studies bandit convex optimization (BCO) and proposes a policy gradient approach to optimizing resource allocations using only noisy function evaluations. The main contributions are three-fold: (1) This work propose to use multinomial policies (MP) for policy parameterization and then connects multinomial policy gradients to regret guarantees for the original convex objective VV, even if the policy expected loss FV,nF_{V,n} is nonconvex. This is one major fundamental challenge of using MP parameterization. (2) This paper proposes a BCO algorithm that combines multinomial sampling with a one-point score estimator and mirror descent. (3) Accordingly, this work provides sharp regret guarantees with explicit dimension dependence for convex, ℓ1\ell_1-Lipschitz problems. The algorithm and the regret analysis are also extended to the case of sparse optimizers. Finally, the proposed algorithm is evaluated through numerical simulations to demonstrate its superior regret performance, especially when the dimension is extremely large.

Critical strengths
  • For the settings of large-scale BCO problems (large KK), the derived regret bounds have improved dependency on KK and nicely address this high dimensionality challenge. As far as I know, this is a new and important contribution to the BCO literature.

  • In terms of regret analysis, this paper addresses a critical theoretical challenge: The original objective is convex, but its multinomial policy value needs not be convex. This work develops comparison inequalities that connect policy gradients to the original regret without assuming convexity on the policy value. This is one important and strong contribution.

Critical weaknesses
  • While the paper provides nice regret bounds of improved dependency on KK, it does not establish whether its dimension-horizon tradeoff is optimal. In fact, it seems still far from the known lower bound Ω(KT)\Omega(\sqrt{KT}) for the general convex Lipschitz problems. It would be helpful if the paper can further explain the dimension-horizon tradeoff and state explicitly the regret lower bounds for the new settings studied in this paper (e.g., MP convexity).

  • While this is mainly a theory paper, the empirical evaluation can be very helpful in showing the empirical dependency of regret on KK, especially in the large-scale regime of interest. That said, the experimental results in its current form are a bit narrow as the paper only focuses on separable convex objectives, which belong to the MP-convex class. The experiments do not test the most distinctive setting of this paper, i.e., convex objectives whose multinomial policy value is non-convex.

  • The sharper sparsity results in Theorem 3.2 require additional prior knowledge about a known upper bound ss on the support size of some optimizer. However, this knowledge is likely not available. This can limit the applicability of the proposed algorithm.

Questions for authors
  1. Can the authors further explain the dimension-horizon tradeoff and state explicitly the regret lower bounds for the new settings studied in this paper?

  2. How does the algorithm perform empirically in the setting where the original objective is convex but the multinomial policy value is non-convex?

  3. Can the authors further justify the assumptions needed in Theorem 3.2?

5 comments
AuthorsOpenReview ↗

For the first weakness and the first question (part 1)

W1.1 & Q1.1 (1/2). Is the dimension–horizon tradeoff optimal, and what are the lower bounds in the new settings?

The bounds seem far from the lower bound Ω(KT)\Omega(\sqrt{KT}); please explain the dimension–horizon tradeoff and state lower bounds for the new settings, e.g., MP convexity.

Worst-case versus minimax regret. Section 2.1 distinguishes instance-wise expected pseudo-regret (Eq. (1)) from worst-case and minimax regret (Eq. (2)):

:=\sup_{I\in\mathcal I}\mathcal R_{\mathcal A,I}(T),\qquad \mathcal R_{\mathrm{minimax}}(T,\mathcal I) :=\inf_{\mathcal A}\mathcal R_{\mathrm{wc},\mathcal A}(T,\mathcal I).$$ Thus we distinguish tightness for our algorithm under its prescribed parameter rules from optimality over all algorithms. Here $\mathcal I_{\mathrm{cvx}}$ is the convex Lipschitz class, $\mathcal I_{\mathrm{sm}}(\beta)$ its smooth subclass, and $\mathcal I_s$ the class whose smallest minimizer support size is exactly $s$ (Eq. (19)); all satisfy the feedback assumptions. **Tightness for our algorithm.** Theorems 3.1–3.2 now give matching worst-case upper and lower bounds for Algorithm 1 under the respective parameter rules. Including logarithmic factors: - $T\gtrsim K^2\log K$: $\mathcal R_{\mathrm{wc}}(T,\mathcal I_{\mathrm{cvx}})=\Theta(K^{1/2}(\log K)^{1/4}T^{3/4})$. - $T\gtrsim K\log K$: $\mathcal R_{\mathrm{wc}}(T,\mathcal I_{\mathrm{sm}}(\beta))=\Theta((K\log K)^{1/3}T^{2/3})$ and $\mathcal R_{\mathrm{wc}}(T,\mathcal I_1)=\Theta(\sqrt{KT\log K})$. - $s\ge2$, $T\gtrsim Ks\log K$: $\mathcal R_{\mathrm{wc}}(T,\mathcal I)=\Theta((Ks\log K)^{1/4}T^{3/4})$ for each subclass in Theorem 3.2(ii)(a)–(c). The constants are independent of $K,T,s$, with dependencies stated in the theorems. Hence sharper analysis alone cannot improve these rates for the prescribed rules. The lower bounds use different mechanisms. Appendices C.1.2, C.2.2, and D.2.2(a,c) use a sampling gap that lower-bounds the **conditional expected regret** in sampling rounds $t\ge1$ (Eq. (108)). Appendix D.1.2 uses the positive coordinate floor; the sampling gap at $n=1$ is zero. For smooth sparse instances, Appendix D.2.2 uses either the active floor cap or a probabilistic, horizon-truncated delay in concentrating the policy mean. The smooth and sparse guarantees differ because their resolution rules differ. For $T\gtrsim Ks\log K$, the ratio of the smooth to sparse rate expressions, including logarithms but omitting constant prefactors, is $$\left(\frac{K\log K}{s^3T}\right)^{1/12}\lesssim s^{-1/3}.$$ Thus smooth tuning gives the better rate guarantee in this range. Part 2 identifies its minimax-optimal regimes. **Minimax lower bounds.** Appendix E allows every algorithm, including randomized algorithms querying arbitrary simplex points and knowing $K,T,s,L,\sigma,\beta$, but not the instance. The hard instances have bounded, conditionally zero-mean noise. For $K\ge2$, $T\ge1$, and $1\le s\le K$, Theorem E.1 gives $$\mathcal R_{\mathrm{minimax}}(T,\mathcal I_s) =\Omega(\min\{T,\sqrt{KsT}\}),$$ and therefore $\mathcal R_{\mathrm{minimax}}(T,\mathcal I_{\mathrm{cvx}})=\Omega(\min\{T,K\sqrt T\})$. Theorem E.2 gives $$\mathcal R_{\mathrm{minimax}}(T,\mathcal I_s\cap\mathcal I_{\mathrm{sm}}(\beta)) =\Omega(\min\{T,K^{1/3}T^{2/3},\sqrt{KsT}\}),$$ and therefore $\mathcal R_{\mathrm{minimax}}(T,\mathcal I_{\mathrm{sm}}(\beta))=\Omega(\min\{T,K^{1/3}T^{2/3},K\sqrt T\})$. Constants depend only on $L,\sigma$, and additionally on $\beta$ in the smooth case. **MP convexity.** The proofs in Appendices E.3.2–E.3.3 use $\ell_1$-distance objectives and separable quadratics (with affine objectives for the smooth vertex case). These objectives are separable convex, hence MP convex by Proposition A.1. The lower bounds therefore also hold on the corresponding MP-convex subclasses, including cases (a) and (c) of Theorem 3.2(ii). MP convexity does not eliminate these obstructions. In our sparse upper bounds, it supplies convexity of the policy value for the MP-convex component, enabling comparison with a sparse minimizer.
AuthorsOpenReview ↗

For the first weakness and the first question (part 2)

W1.1 & Q1.1 (2/2).

Comparison. Appendix E.2 and Table 3 compare our worst-case upper bounds with the minimax lower bounds. The table suppresses constants and logarithmic factors; every rate is capped at TT.

ClassOur upper boundMinimax lower boundOrders agree for
Icvx\mathcal I_{\mathrm{cvx}}K1/2T3/4K^{1/2}T^{3/4}KT1/2KT^{1/2}T≲K2T\lesssim K^2
Ism(β)\mathcal I_{\mathrm{sm}}(\beta)K1/3T2/3K^{1/3}T^{2/3}min⁡{K1/3T2/3,KT1/2}\min\{K^{1/3}T^{2/3},KT^{1/2}\}T≲K4T\lesssim K^4
I1\mathcal I_1(KT)1/2(KT)^{1/2}(KT)1/2(KT)^{1/2}all TT
(a) or (c), s≥2s\ge2(Ks)1/4T3/4(Ks)^{1/4}T^{3/4}(KsT)1/2(KsT)^{1/2}T≲KsT\lesssim Ks
(b), s≥2s\ge2K1/3T2/3K^{1/3}T^{2/3}min⁡{K1/3T2/3,(KsT)1/2}\min\{K^{1/3}T^{2/3},(KsT)^{1/2}\}T≲Ks3T\lesssim Ks^3

The last row uses the smooth rule of Theorem 3.1(ii), whose upper bound applies to every fixed-support smooth subclass.

The benchmark Ω(KT)\Omega(\sqrt{KT}). Theorem E.1 recovers Ω(min⁡{T,KT})\Omega(\min\{T,\sqrt{KT}\}) for vertex minimizers (s=1s=1). Theorem 3.2(i) matches it up to (log⁡K)1/2(\log K)^{1/2}; its matching algorithm-specific lower bound comes from the positive coordinate floor (Appendix D.1.2). For the full convex Lipschitz class, however, Theorem E.1 gives the stronger bound Ω(min⁡{T,KT})\Omega(\min\{T,K\sqrt T\}). Thus KT\sqrt{KT} alone does not characterize the difficulty of that larger class.

General convex objectives. For T≲K2T\lesssim K^2, minimax regret is of order TT. Our threshold T≳K2log⁡KT\gtrsim K^2\log K for sublinear regret is therefore necessary up to logarithms. For fixed problem constants, any uniform upper bound O~(KaTb)\widetilde O(K^aT^b) must satisfy a+2b≥2a+2b\ge2, by evaluating the lower bound at T≍K2T\asymp K^2. Our exponents (1/2,3/4)(1/2,3/4) attain equality. This establishes an exponent tradeoff within this family of bounds, but not minimax optimality at every horizon. For T≳K2log⁡KT\gtrsim K^2\log K, the upper and lower rate expressions differ by (T/K2)1/4(log⁡K)1/4.(T/K^2)^{1/4}(\log K)^{1/4}. Closing this gap requires a different parameter rule or algorithm, or a stronger minimax lower bound; it remains open in our analysis.

Smooth objectives. Theorem 3.1(ii) is minimax optimal up to (log⁡K)1/3(\log K)^{1/3} for K≲T≲K4K\lesssim T\lesssim K^4. For T≫K4T\gg K^4, the ratio of our upper bound to Theorem E.2's lower bound is (T/K4)1/6(log⁡K)1/3(T/K^4)^{1/6}(\log K)^{1/3}.

Sparse minimizers. On subclasses (a) and (c), the minimax lower bound is linear for T≲KsT\lesssim Ks. At T≍KsT\asymp Ks, a uniform upper bound O~((Ks)aTb)\widetilde O((Ks)^aT^b) must satisfy a+b≥1a+b\ge1; our exponents (1/4,3/4)(1/4,3/4) attain equality. For T≳Kslog⁡KT\gtrsim Ks\log K, the upper/lower rate ratio is (T/(Ks))1/4(log⁡K)1/4(T/(Ks))^{1/4}(\log K)^{1/4}.

On smooth subclass (b), minimax regret is Θ~(K1/3T2/3)\widetilde\Theta(K^{1/3}T^{2/3}) for K≲T≲Ks3K\lesssim T\lesssim Ks^3, attained by smooth tuning up to logarithms. Comparison with sparse rule (20) must respect its lower-bound condition: in the overlapping range Kslog⁡K≲T≲Ks3Ks\log K\lesssim T\lesssim Ks^3, its tight rate is Θ~((Ks)1/4T3/4)\widetilde\Theta((Ks)^{1/4}T^{3/4}). Omitting logarithms, its ratio to the smooth rate is (s3T/K)1/12(s^3T/K)^{1/12}.

Where the tradeoff comes from. The fixed-resolution upper bounds (Lemma C.4, Eq. (141), and Lemma D.2) balance learning/stability and approximation terms. Increasing nn reduces approximation error but enlarges the score-estimator second-moment bound, which scales as O(B2nK)O(B^2nK). With the prescribed step size, this contributes a learning term Bn(K−1)Tlog⁡K,B=2(L+σ).B\sqrt{n(K-1)T\log K},\qquad B=2(L+\sigma). The approximation terms decrease with nn:

  • general convex: LT(K−1)/nLT\sqrt{(K-1)/n};
  • smooth: βT/n\beta T/n;
  • sparse decomposition: LT(s−1)/n+βT/nLT\sqrt{(s-1)/n}+\beta T/n, with β=0\beta=0 in the purely MP-convex case.

Balancing these terms motivates resolutions (17) and (20). The proofs also control initial-round, floor, and truncation terms. In particular, the extra floor-related term in Lemma C.4 has the same order under the prescribed resolution and does not change the resulting rate. The matching algorithm-specific lower bounds show that the dimension–horizon dependence is intrinsic to the prescribed rules.

AuthorsOpenReview ↗

For the second weakness and the second question

W1.2 & Q1.2. Convex objective functions whose multinomial policy value is nonconvex

How does the algorithm perform when the objective function is convex but its multinomial policy value is nonconvex?

Expanded experiments. The revised experiments directly address this setting. Section 4 and Appendix F now include five objective families in four classes (Appendix F.1, Eqs. (209)–(213)):

  • MP convex and smooth:

fqlog,j(x):=aj+∑k=1K(qj,k2xk2+bj,kxk+λj,klog⁡(xk+cj,k)).f_{\mathrm{qlog},j}(x):=a_j+\sum_{k=1}^K\left(\frac{q_{j,k}}2x_k^2+b_{j,k}x_k+\lambda_{j,k}\log(x_k+c_{j,k})\right).

  • MP convex and nonsmooth:

fqabs,j(x):=aj+∑k=1K(qj,k2xk2+bj,kxk+ξj,k∣xk−cj,k∣).f_{\mathrm{qabs},j}(x):=a_j+\sum_{k=1}^K\left(\frac{q_{j,k}}2x_k^2+b_{j,k}x_k+\xi_{j,k}|x_k-c_{j,k}|\right).

  • Not MP convex and smooth:

fslog,j(x):=aj+∑k=1K(wj,k(xk−xpj,k−ϕj,k)2+τj,k2+λj,klog⁡(xk+cj,k)).f_{\mathrm{slog},j}(x):=a_j+\sum_{k=1}^K\left(w_{j,k}\sqrt{(x_k-x_{p_{j,k}}-\phi_{j,k})^2+\tau_{j,k}^2}+\lambda_{j,k}\log(x_k+c_{j,k})\right).

  • Not MP convex and nonsmooth:

fsabs,j(x):=aj+∑k=1K(wj,k(xk−xpj,k−ϕj,k)2+τj,k2+ξj,k∣xk−cj,k∣),f_{\mathrm{sabs},j}(x):=a_j+\sum_{k=1}^K\left(w_{j,k}\sqrt{(x_k-x_{p_{j,k}}-\phi_{j,k})^2+\tau_{j,k}^2}+\xi_{j,k}|x_k-c_{j,k}|\right), fpwa,j(x):=aj+∑k=1K(wj,k∣xk−xpj,k−ϕj,k∣+ξj,k∣xk−cj,k∣).f_{\mathrm{pwa},j}(x):=a_j+\sum_{k=1}^K\left(w_{j,k}|x_k-x_{p_{j,k}}-\phi_{j,k}|+\xi_{j,k}|x_k-c_{j,k}|\right).

Here qj,k,cj,k,ξj,k,wj,k,τj,k>0q_{j,k},c_{j,k},\xi_{j,k},w_{j,k},\tau_{j,k}>0 and λj,k<0\lambda_{j,k}<0. All generated objectives are convex and Lipschitz on the simplex. The three non-MP-convex families contain coupling terms, with each partner pj,kp_{j,k} sampled uniformly from {1,…,K}∖{k}\{1,\ldots,K\}\setminus\{k\}.

Verification of nonconvex policy values. Appendix F.2 checks each generated instance using

FV,2(m)=m⊤AVm,(AV)ik:=V((ei+ek)/2).F_{V,2}(m)=m^\top A_Vm,\qquad (A_V)_{ik}:=V((e_i+e_k)/2).

An instance of the last three families is retained only if the smallest eigenvalue of 2AV2A_V restricted to the simplex tangent space is at most −0.01-0.01. Thus every retained instance has a nonconvex policy value at resolution n=2n=2 and is not MP convex. This check is necessary because the separable terms can offset the nonconvexity induced by the coupling terms.

The two nonsmooth families also test different structures. For fsabs,jf_{\mathrm{sabs},j}, the separable absolute-value terms form an MP-convex V1V_1, while the smooth coupling terms together with aja_j form a smooth convex V2V_2. Hence Theorem 3.2(ii)(c) applies; the decomposition is needed only in the analysis. By contrast, fpwa,jf_{\mathrm{pwa},j} does not necessarily have this structure: its coupling terms are nonsmooth and need not be MP convex. Theorem 3.1(i) provides a regret guarantee for all five families under its prescribed parameter rule, without requiring such a decomposition or convexity of the policy value.

Results for K=10,50,100K=10,50,100. Table 2 compares seven methods at horizons T=2×103,104,5×104T=2\times10^3,10^4,5\times10^4, respectively, across three support-size groups: s=Ks=K, 0.6K≤s≤0.8K0.6K\le s\le0.8K, and 0.2K≤s≤0.4K0.2K\le s\le0.4K. The six benchmarks include the surrogate-loss ellipsoid method (Lattimore & György, 2021) and online Newton (Fokkema et al., 2024), both with T\sqrt{T}-type regret guarantees under their respective assumptions. The former includes a two-dimensional experiment (Appendix A, Figure 2); the latter's original full paper does not report numerical experiments. Every method receives one noisy objective value per round. Parameters are tuned on separate functions and then held fixed for testing.

Table 2 averages equally over all five families; our method has the lowest mean average pseudo-regret RT/TR_T/T and best-so-far gap in every row. Tables 9–11 report the three non-MP-convex families separately. Our method has the lowest mean best-so-far gap in every setting and the lowest mean RT/TR_T/T except for fsabs,jf_{\mathrm{sabs},j} at K=10K=10, s=2s=2–44: there, its RT/TR_T/T is comparable to Simplex ZO-PGD (0.15300.1530 versus 0.15210.1521), while its best-so-far gap remains smaller (2.18% versus 2.63%). Figures 4–12 show the learning curves.

Results for K=1000K=1000. Figure 1 reports learning curves at T=5×106T=5\times10^6 for the same three support-size groups. It compares our method with Simplex ZO-PGD, which ranks second in every row of Table 2. Our method initially has higher average pseudo-regret, but overtakes Simplex ZO-PGD early in the run; its final RT/TR_T/T is at most 60% of the benchmark's. On the three non-MP-convex families, its final best-so-far gap is 2–11%, compared with 11–33% for Simplex ZO-PGD.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.