analiza aiqbench
This paper advances the theoretical foundations of online convex optimization by establishing parameter-free regret bounds that remain robust under heavy-tailed noise conditions. By achieving universal constants without requiring prior knowledge of gradient norms or noise moments, it offers a more resilient framework for stochastic subgradient methods in non-ideal environments. The work bridges information theory and optimization control to provide tighter guarantees for adaptive learning algorithms facing unpredictable data distributions.
Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise
arXiv:2610.02258v1 Announce Type: new Abstract: We study online convex optimization with one unbiased stochastic subgradient per round and an unknown finite conditional $p$th noise moment, $1<p\le2$. For every fixed interval $I$ of length $n$ and comparator path with $\Lambda_I=1+P_I/D$, one learner achieves \[ E[Regret_I(u)]\le\min(GDn, C[GD\sqrt{n(\Lambda_I+\log^2(2T))} +\sigma Dn^{1/p}(\Lambda_I+\log^2(2T))^{(p-1)/p}]). \] The learner uses none of $G,\sigma,p,I,P_I$, and the constant is universal. Interval adaptation adds to comparator complexity, preserving the distinct mean-gradient and noise exponents. The analysis controls calibration in expectation and limits the cost of observation-scale changes. Its general theorem compares to distributions over predictably available experts with relative-entropy dependence on a nonuniform prior. A common prior favors long windows and long restart lengths. With the statistics supplied, the interval cost becomes $1+\log(T/n)$, including the optimal full-horizon static rate. A change-of-measure lower bound identifies the noise power of this logarithm for learners retaining a full-horizon optimal guarantee, under explicit conditions. Static comparisons and deterministic partitions follow from the same decisions.
Abstract:We study online convex optimization with one unbiased stochastic subgradient per round and an unknown finite conditional $p$th noise moment, $1<p\le2$. For every fixed interval $I$ of length $n$ and comparator path with $\Lambda_I=1+P_I/D$, one learner achieves \[ E[Regret_I(u)]\le\min(GDn, C[GD\sqrt{n(\Lambda_I+\log^2(2T))} +\sigma Dn^{1/p}(\Lambda_I+\log^2(2T))^{(p-1)/p}]). \] The learner uses none of $G,\sigma,p,I,P_I$, and the constant is universal. Interval adaptation adds to comparator complexity, preserving the distinct mean-gradient and noise exponents. The analysis controls calibration in expectation and limits the cost of observation-scale changes. Its general theorem compares to distributions over predictably available experts with relative-entropy dependence on a nonuniform prior. A common prior favors long windows and long restart lengths. With the statistics supplied, the interval cost becomes $1+\log(T/n)$, including the optimal full-horizon static rate. A change-of-measure lower bound identifies the noise power of this logarithm for learners retaining a full-horizon optimal guarantee, under explicit conditions. Static comparisons and deterministic partitions follow from the same decisions.
Machine Learning (cs.LG); Information Theory (cs.IT); Optimization and Control (math.OC)
arXiv:2610.02258 [cs.LG]
(or arXiv:2610.02258v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.02258 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 252 cuvinte
Subiecte conexe
Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise
arXiv · 31 iul. 2026
Parameter-Free Heavy-Tailed Bandits
arXiv · 3 aug. 2026
Build a Physical AI model factory with NVIDIA Cosmos 3 on SageMaker HyperPod
AWS · 4 sept. 2026
Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret with Infinite Variance
arXiv · 27 iul. 2026