We study efficient algorithms for realizing the first-order oracle complexity of optimization of $G$-Lipschitz convex functions with respect to the $\ell_{q}$-norm over an $\ell_{p}$-ball of radius $R$, where $1\leq p,q\leq \infty$. For $p<q$, we obtain error $\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)_{+}})$ after $T$ oracle queries, efficiently realizing the nearly optimal rates of (MBG+26), thereby resolving the nonsmooth end of the COLT 2015 open problem (Guz15b).
arXiv:2609. 20701v1 Announce Type: cross Abstract: We study efficient algorithms for realizing the first-order oracle complexity of optimization of $G$-Lipschitz convex functions with respect to the $\ell_{q}$-norm over an $\ell_{p}$-ball of radius $R$, where $1\leq p,q\leq \infty$.
By David Mart\'inez-Rubio, Crist\'obal Guzm\'an
arXiv:2605. 21107v2 Announce Type: replace Abstract: We study constrained online convex optimization with adversarial time-varying constraints.
By Dhruv Sarkar, Abhishek Sinha
arXiv:2608. 25182v1 Announce Type: cross Abstract: In this paper, we study alternating regret in online convex optimization (OCO), motivated by the success of alternating learning dynamics in two-player games.
By Mengxiao Zhang
Bakhtiari, Lattimore and Szepesvári (COLT 2025) proved that Thompson sampling (TS) has Bayesian regret $\tilde O(d^{5/2}\sqrt n)$ for bandit convex optimisation with convex \emph{monotone} ridge losse...
arXiv:2603. 25029v4 Announce Type: replace Abstract: We study online convex optimization (OCO) with two-point bandit feedback against a non-anticipating adaptive adversary.
By Haishan Ye
The paper investigates how the choice of geometry in online mirror descent affects performance, particularly when loss gradients are sparse. It introduces randomized block‑norm mirror maps that interpolate between Euclidean and entropic geometries, achieving polynomial‑in‑dimension regret improvements over standard methods for various convex sets. The authors also demonstrate that naive alternation between mirror maps can lead to linear regret and propose a Hedge‑based meta‑algorithm that competes with the best mirror map in a finite portfolio, achieving near‑optimal regret for random block geometries.
By Swati Gupta, Jai Moondra, Mohit Singh
arXiv:2603. 28956v2 Announce Type: replace-cross Abstract: The minimum-norm interpolator (MNI) framework has recently attracted considerable attention as a tool for understanding generalization in overparameterized models, such as neural networks.
By Gil Kur, Pierre Bizeul
We establish a $\widetildeΩ(d^{5/4}\sqrt T)$ lower bound on the minimax expected regret of stochastic bandit convex optimization of $1$-Lipschitz functions on the Euclidean ball. This presents the first nontrivial regret lower bound that grows faster than $d\sqrt{T}$ for this problem, establishing that stochastic bandit convex optimization is fundamentally harder than linear bandits.
arXiv:2609. 10981v1 Announce Type: new Abstract: Bakhtiari, Lattimore and Szepesv\'ari (COLT 2025) proved that Thompson sampling (TS) has Bayesian regret $\tilde O(d^{5/2}\sqrt n)$ for bandit convex optimisation with convex \emph{monotone} ridge losses $f(x)=\ell(\ip{x}{\theta})$, and asked whether monotonicity of the link is necessary.
By Xuan Li
arXiv:2602. 06257v2 Announce Type: replace Abstract: Online strategic classification studies settings in which agents strategically modify their features to obtain favorable predictions.
By Chase Hutton, Adam Melrod, Han Shao
arXiv:2606. 14640v1 Announce Type: new Abstract: We study Online Convex Optimization (OCO) over a convex set $K\subseteq \mathbb R^d$, where in each round $t$ the learner selects $x_t\in K$ and then observes a convex loss $f_t:K\to[0,1]$, with the goal of minimizing regret to the best fixed decision in hindsight.
By Simone Di Gregorio, Anupam Gupta, Stefano Leonardi, Matteo Russo