AI & ML
Bandit Online Submodular Minimisation Using Zeroth-Order Oracles
arXiv stat.ML0 views
arXiv:2611.22130v1 Announce Type: new Abstract: We consider online submodular minimisation under bandit feedback, where at each round a decision maker plays a subset and observes only its cost, while the cost functions, and hence their minimiser, change over time. Existing bandit methods only guarantee static regret, which compares against a single fixed subset and is a weak benchmark when the minimiser moves. This paper provides, to the best of our knowledge, the first method with guarantees for tracking a moving minimiser in this setting. We propose a zeroth-order method built on a two-point oracle for the Lov\'asz extension whose two evaluations are both subsets that can be played. The perturbed and base points are rounded by a common random threshold, and drawing the smoothing direction from the unit sphere makes the base evaluation a zero-mean control variate, so the oracle is an unbiased estimator of the smoothed gradient. We establish dynamic regret bounds of order $O\big((1+\sqrt{P^\ast_N})N^{3/4}\big)$ in general and $O\big((1+\sqrt{P^\ast_N})N^{2/3}\big)$ under a sufficiently small drift, where $P^\ast_N$ is the path length of the minimiser sequence, together with the corresponding $O(N^{3/4})$ and $O(N^{2/3})$ static regret bounds. Numerically, the method attains lower regret than the algorithm of (Hazan and Kale (2012)), with the advantage growing with the path length.
Source:https://arxiv.org/abs/2611.22130PreviousModeling Document and Section Hierarchies in Embedding SpaceNextBias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in $\ell_p$ Geometries
Related posts
Le Groupe Figaro and OpenAI partner to bring Le Figaro journalism to ChatGPT
0OpenAI Blog
Web 上已经有 GPT-6.2,本地 Codex 却没有?先对入口,再更新客户端
0dev.to
영지식 증명 프라이버시와 규제 준수: 우리는 정말 두 마리 토끼를 다 잡을 수 있을까?
0dev.to
My context grew 6x in three months. That decides the cache question
0dev.to AI
How to connect Joist to any MCP client: Claude, ChatGPT, Cursor
0dev.to AI
Gemini Notebook cria sites interativos a partir de anotações
0dev.to AI