论文检索

General Machine Learning · Online Learning, Active Learning and Bandits

Ricardo N. Ferreira, Joao Xavier, Claudia Soares

Addressing Constrained Online Convex Optimization (COCO), we introduce CLASP (Convex Losses And Squared Penalties), a framework that minimizes cumulative loss together with squared constraint violations. We propose two variants of CLASP, CLASP-I and CLASP-F, allowing for a joint or separate handling of the static decision set and the time-varying constraints, a decoupling flexibility that affords simpler implementations when projections onto the static decision set are easy. Our theoretical analysis departs from prior work by fully leveraging the variety of \emph{cutter operators}, and contraction properties such as the strongly quasi-nonexpansiveness, a proof strategy not previously applied in this setting. For convex losses, both CLASP algorithms achieve regret $O\left(T^{\max\\{\beta,1-\beta\\}}\right)$ and cumulative squared penalty $O\left(T^{\\{1-\beta\\}}\right)$ for any $\beta \in (0,1)$. Most importantly, for strongly convex problems, we provide the first logarithmic guarantees on both regret and cumulative squared penalty: In the strongly convex case, both CLASP algorithms guarantee that the regret is upper bounded by $O( \log T )$ and the cumulative squared penalty is also upper bounded by $O( \log T )$.

General Machine Learning · Online Learning, Active Learning and Bandits

Liangxiao Jiang, Liangxiao Jiang, Chaoqun Li, Shanshan Si

In crowdsourcing scenarios, to mitigate the impact of noisy labels assigned by non-expert workers, each instance is typically annotated multiple times by different workers. However, repeated annotation can introduce instance- or label-level redundancy, thereby inflating annotation costs. Despite its practical importance, research on repeated annotation strategies remains limited, and no existing strategy simultaneously avoids being offline, instance-unaware, and model-centric. In this paper, we propose a model-agnostic active annotation strategy, MA$^3$S, that addresses these limitations: (1) To reduce label redundancy caused by offline procedure, MA$^3$S estimates instance uncertainties with a general Beta distribution and updates them online as new labels arrive. (2) To prevent instance redundancy induced by instance-unaware designs, MA$^3$S constructs a nearest-neighbor graph to propagate instance uncertainties, reducing repeated annotations of similar instances. (3) To avoid being model-centric, MA$^3$S actively selects instances for annotation based solely on the estimated uncertainties, without relying on model feedback. Extensive experiments on synthetic and real-world datasets demonstrate that MA$^3$S consistently outperforms existing annotation strategies.

General Machine Learning · Online Learning, Active Learning and Bandits

MohammadHossein Bateni, Zahra Hadizadeh, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, Shayan Taherijam

We study networked binary classification on a directed acyclic graph (DAG) where each agent observes only a subset of the feature columns of a shared finite dataset. Agents act sequentially along the DAG: each receives prediction columns from its parents (if any), augments its local features with these columns, fits a logistic predictor by minimizing binary cross-entropy (BCE), and forwards its prediction column to its outgoing neighbors. We ask whether this sequential distributed training procedure achieves *information aggregation*, meaning that some agent attains small excess loss compared to the best logistic predictor trained with access to all feature columns. This question was studied for linear regression under squared loss by Kearns, Roth, and Ryu (2026). Extending their guarantees to classification is nontrivial because their analysis relies on quadratic structure that does not directly transfer to BCE with a logistic link. We analyze the resulting sequential logit-passing protocol and prove: (i) an excess loss upper bound of $O(M/\sqrt{D})$ on depth-$D$ paths under the condition that every $M$ contiguous subsequence of $M$ agents collectively observe all features, and (ii) a close lower bound showing instances with excess loss of at least $\Omega(k/D)$ where $k$ is the dimension of the feature space. Together, these results identify network depth as a fundamental bottleneck for information aggregation in networked logistic regression.

Theory · Online Learning and Bandits

Lorenzo Croissant

Linear bandits have long been a central topic in online learning, with applications ranging from recommendation systems to adaptive clinical trials. Their general learnability has been established when the objective is to minimise the inner product between a cost parameter and the decision variable. While this is highly general, this reliance on an inner product structure belies the name of \emph{linear} bandits, and fails to account for problems such as Optimal Transport. Using the Kantorovich formulation of Optimal Transport as an example, this article shows that an inner product structure is \emph{not} necessary to achieve efficient learning in linear bandits. We propose a refinement of the classical OFUL algorithm that operates by embedding the action set into a Hilbertian subspace, where confidence sets can be built via least-squares estimation. Actions are then constrained to this subspace by penalising optimism. The analysis is completed by leveraging convergence results from penalised (entropic) transport to the Kantorovich problem. Up to this approximation term, the resulting algorithm achieves the same trajectorial regret upper bounds as the OFUL algorithm, which we turn into worst-case regret using functional regression techniques. Its regret interpolates between $\tilde{\mathcal O}(\sqrt{T})$ and ${\mathcal O}(T)$, depending on the regularity of the cost function, and recovers the parametric rate $\tilde{\mathcal O}(\sqrt{dT})$ in finite-dimensional settings.

Theory · Online Learning and Bandits

Tomer Gafni, Garud Iyengar, Assaf Zeevi

We consider an online learning problem in environments with multiple change points. In contrast to the single change point problem that is widely studied using classical "high confidence" detection schemes, the multiple change point environment presents new learning-theoretic and algorithmic challenges. Specifically, we show that classical methods may exhibit catastrophic failure (high regret) due to a phenomenon we refer to as endogenous confounding. To overcome this, we propose a new class of learning algorithms dubbed Anytime Tracking CUSUM (ATC). These are horizon-free online algorithms that implement a selective detection principle, balancing the need to ignore "small" (hard-to-detect) shifts, while reacting "quickly" to significant ones. We prove that the performance of a properly tuned ATC algorithm is nearly minimax-optimal; its regret is guaranteed to closely match a novel information-theoretic lower bound on the achievable performance of any learning algorithm in the multiple change point problem. Experiments on synthetic as well as real-world data validate the aforementioned theoretical findings.

General Machine Learning · Online Learning, Active Learning and Bandits

Abdelhamid Ezzerg, Ilija Bogunovic, Jeremias Knoblauch

Bayesian Optimization is critically vulnerable to extreme outliers. Existing provably robust methods typically assume a bounded cumulative corruption budget, which makes them defenseless against even a single corruption of sufficient magnitude. To address this, we introduce a new adversary whose budget is only bounded in the frequency of corruptions, not in their magnitude. We then derive RCGP-UCB, an algorithm coupling the upper confidence bound (UCB) approach with a Robust Conjugate Gaussian Process (RCGP). We present stable and adaptive versions of RCGP-UCB, and prove that they achieve sublinear regret in the presence of up to $O(T^{1/4})$ and $O(T^{1/7})$ corruptions with possibly infinite magnitude. This robustness comes at near zero cost: without outliers, RCGP-UCB's regret bounds match those of the standard GP-UCB algorithm.

General Machine Learning · Online Learning, Active Learning and Bandits

Amith Bhat Hosadurga Anand, Aadirupa Saha, Haipeng Luo

In this paper, we address the standard $K$-armed multi-armed bandit (MAB) with $M$ heterogeneous data sources, each exhibiting unknown and distinct noise variances, $\sigma_j^2$. We propose SOAR (Source-Optimistic Adaptive Regret Minimization), a novel algorithm that adaptively balances exploration and exploitation by jointly constructing upper confidence bounds for arm rewards and lower confidence bounds for data source variances. Our theoretical analysis establishes that SOAR achieves a regret bound of $\tilde{O}\left({\sigma^*}^2 \sum_{i=2}^K \tfrac{1}{\Delta_i}\right),$ along with a preprocessing cost that depends only on the problem parameters $\\{\sigma_j\\}_{j = 1}^M$, $K$, and grows at most logarithmically with the horizon $T$; where ${\sigma^\*}^2$ is the minimum source variance, and $\Delta_i$ denotes the suboptimality-gap of the $i$-th arm reward. The $\tilde O(.)$ notation hides the polylogarithmic factors in these problem parameters. This near-optimal instance dependence regret analysis of SOAR underscores its effectiveness in dynamically managing heteroscedastic noise without incurring significant overhead. Experiments on synthetic problem instances and a real dataset (MovieLens 25M) demonstrate that our method significantly outperforms baseline bandit algorithms in terms of regret performance. Our work opens a new direction for adaptively leveraging multiple heterogeneous data sources, extending beyond traditional bandit frameworks.

Theory · Online Learning and Bandits

Shogo Iwazaki

We study an algorithm-independent, worst-case lower bound for the Gaussian process (GP) bandit problem in the frequentist setting, where the reward function is fixed and has a bounded norm in the known reproducing kernel Hilbert space (RKHS). Specifically, we focus on the squared exponential (SE) kernel, one of the most widely used kernel functions in GP bandits. One of the remaining open questions for this problem is the gap in the *dimension-dependent* logarithmic factors between upper and lower bounds. This paper partially resolves this open question under a hyperspherical input domain. We show that any algorithm suffers $\Omega(\sqrt{T (\ln T)^{d} (\ln \ln T)^{-d}})$ cumulative regret, where $T$ and $d$ represent the total number of steps and the dimension of the hyperspherical domain, respectively. Regarding the simple regret, we show that any algorithm requires $\Omega(\epsilon^{-2}(\ln \frac{1}{\epsilon})^d (\ln \ln \frac{1}{\epsilon})^{-d})$ time steps to find an $\epsilon$-optimal point. We also provide the improved $O((\ln T)^{d+1}(\ln \ln T)^{-d})$ upper bound on the maximum information gain for the SE kernel. Our results guarantee the optimality of the existing best algorithm up to *dimension-independent* logarithmic factors under a hyperspherical input domain.

Theory · Online Learning and Bandits

Emmanuel Esposito, Andrew Jacobsen, Hao Qiu, Mengxiao Zhang

In this paper, we study dynamic regret in unconstrained online convex optimization (OCO) with movement costs. Specifically, we generalize the standard setting by allowing the movement cost coefficients $\lambda_t$ to vary arbitrarily over time. Our main contribution is a novel algorithm that establishes the first comparator-adaptive dynamic regret bound for this setting, guaranteeing $\widetilde{\mathcal{O}}(\sqrt{(1+P_T)(T+\sum_t \lambda_t)})$ regret, where $P_T$ is the path length of the comparator sequence over $T$ rounds. This recovers the optimal guarantees for both static and dynamic regret in standard OCO as a special case where $\lambda_t=0$ for all rounds. To demonstrate the versatility of our results, we consider two applications: *OCO with delayed feedback* and *OCO with time-varying memory*. We show that both problems can be translated into time-varying movement costs, establishing a *novel reduction* specifically for the delayed feedback setting that is of independent interest. A crucial observation is that the first-order dependence on movement costs in our regret bound plays a key role in enabling optimal comparator-adaptive dynamic regret guarantees in both settings.

General Machine Learning · Online Learning, Active Learning and Bandits

Runzhe Gu, Wenguang Sun, Bowen Gang, Xintao Xia

Online evaluation of large language models increasingly relies on sequentially collected pairwise preferences, enabling human-aligned assessment and continuous data collection until closely performing models can be reliably distinguished. However, adaptive sampling and continuous monitoring invalidate classical fixed-sample inference, rendering existing ranking procedures largely heuristic. We propose SERPANT (Sequential E-value Ranking and Pruning via Adaptive Null Testing), a principled framework for online LLM ranking with anytime-valid guarantees. SERPANT formulates model comparison as a collection of pairwise hypothesis tests and constructs e-processes to ensure family-wise error rate control at any monitoring time. Anytime validity provides a theoretical justification for early stopping, enabling substantial cost savings from expensive human annotation. To improve efficiency, we introduce a novel tournament-based sampling strategy that adaptively selects comparisons based on past outcomes. The proposed framework further provides anytime-valid confidence sets for top-k model identification. Theoretical and empirical results on benchmark datasets validate the efficiency and statistical guarantees.

General Machine Learning · Online Learning, Active Learning and Bandits

Haodong Lu, Chongyang Zhao, Minhui Xue, Lina Yao, Kristen Moore, Dong Gong

Continual learning (CL) with large pre-trained models is challenged by task interference and catastrophic forgetting. Existing LoRA-based Mixture-of-Experts (MoE) methods mitigate forgetting by adding new task-specific adapters and freezing old ones, but often suffer from redundancy, interference, and ambiguous routing due to coarse-grained experts and routing. Coarse-grained experts (i.e., full LoRA adapters with large rank) encode low-specialty information. Newly added experts often duplicate or conflict with existing ones, causing redundancy and interference. Their low specialization further confuses the router, accelerating routing degradation and forgetting as experts accumulate. In this work, we propose MoRAM (Mixture of Rank-1 Associative Memory). Grounded in the view that weight matrices function as linear associative memories, MoRAM achieves CL as gradual incrementing of atomic rank-1 memory experts. Each rank-1 adapter acts as a fine-grained MoE expert or an associative memory unit. By viewing rank-1 adapters as key–value pairs, we eliminate explicit routers in MoE-LoRA, using a self-activation mechanism where each memory atom evaluates its own relevance via its intrinsic key. This transforms the adaptation process into robust, content-addressable retrieval. Extensive experiments on CLIP and LLMs demonstrate that \ours significantly outperforms state-of-the-art baselines, achieving superior plasticity-stability trade-offs, improving generalization while mitigating forgetting.

General Machine Learning · Online Learning, Active Learning and Bandits

Gianmarco Genalti, Achraf Azize, Vianney Perchet

Network routers that enforce Quality-of-Service (QoS) guarantees must decide, at every clock cycle, which expiring packet of information to transmit, even when the value of the packet is unknown until it is processed. We frame this problem as the Online Packet Scheduling with Deadlines (OPSD) problem under Partial Feedback: packets arrive at every clock cycle, with different deadlines, but the weights are only observed after execution. Under a stochastic assumption on the unknown weights, we explore different variants of the OPSD problem with bandit feedback. We establish a connection between our setting and the sleeping bandits problem, and set our learning goal to $\alpha$-regret minimization. We provide algorithms with provable $\alpha$-regret guarantees under different spans of slackness, distinguishing systems allowing for randomization and systems that do not. In every scenario, our algorithms achieve an $\alpha$-regret upper bound of $\widetilde{\mathcal{O}}\left(\sqrt{KT}\right)$, matching the lower bound for the standard bandit setting. In the practically relevant case of $2$-bounded deadline instances, where the deadline is set at most one clock cycle away from the arrival, our deterministic algorithm achieves the provably tightest possible competitive ratio. Remarkably, when the number of distinct packet types $K\ge 2$ is finite, it is possible to break the well-established $\Phi = \frac{1+\sqrt{5}}{2}$ competitive ratio barrier and attain a tighter competitive ratio $\theta_K$ ranging in $[\sqrt{2}, \Phi)$.

Theory · Online Learning and Bandits

Mingyi Li, Taira Tsuchiya, Kenji Yamanishi

This work studies online episodic tabular Markov decision processes (MDPs) with known transitions and develops best-of-both-worlds algorithms that achieve refined data-dependent regret bounds in the adversarial regime and variance-dependent regret bounds in the stochastic regime. We quantify MDP complexity using a first-order quantity and several new data-dependent measures for the adversarial regime, including a second-order quantity and a path-length measure, as well as variance-based measures for the stochastic regime. To adapt to these measures, we develop algorithms based on global optimization and policy optimization, both built on optimistic follow-the-regularized-leader with log-barrier regularization. For global optimization, our algorithms achieve first-order, second-order, and path-length regret bounds in the adversarial regime, and in the stochastic regime, they achieve a variance-aware gap-independent bound and a variance-aware gap-dependent bound that is polylogarithmic in the number of episodes. For policy optimization, our algorithms achieve the same data- and variance-dependent adaptivity, up to a factor of the episode horizon, by exploiting a new optimistic $Q$-function estimator. Finally, we establish regret lower bounds in terms of data-dependent complexity measures for the adversarial regime and a variance measure for the stochastic regime, implying that the regret upper bounds achieved by the global-optimization approach are nearly optimal.

Theory · Online Learning and Bandits

Daniel Ezer, Alon Peled-Cohen, Yishay Mansour

We study the stochastic linear bandits with parameter noise model, in which the reward of action $a$ is $a^\top \theta$ where $\theta$ is sampled i.i.d. We show a regret upper bound of $\widetilde{O} (\sqrt{d T \log(K/\delta) \sigma^2_{\max}})$ for a horizon $T$, general action set of size $K$ of dimension $d$, and where $\sigma^2_{\max}$ is the maximal variance of the reward for any action. We further provide a lower bound of $\widetilde{\Omega} (d \sqrt{T \sigma_{\max}^2})$ which is tight (up to logarithmic factors) whenever $\log K \approx d$. For more specific action sets, $\ell_p$ unit balls with $p \leq 2$ and dual norm $q$, we show that the minimax regret is $\widetilde{\Theta} (\sqrt{dT \sigma_q^2})$, where $\sigma_q^2$ is a variance-dependent quantity that is always at most $4$. This is in contrast to the minimax regret attainable for such sets in the classic additive noise model where the regret is of order $d \sqrt{T}$. Surprisingly, we show that this optimal (up to logarithmic factors) regret bound is attainable using a very simple explore-exploit algorithm.

Theory · Online Learning and Bandits

Wenhao Yang, Yibo Wang, Yuanyu Wan, Lijun Zhang

Online convex optimization in non-stationary environments has garnered considerable attention in the literature. Recently, Pasteris et al. (2024) investigate online convex optimization with the optimal switching regret, defined as the sum of the static regret over each segment, where the segmentation is an arbitrary partition of the entire time horizon. For general convex functions, their work has established an optimal switching regret bound. However, it remains open whether similar bounds are attainable for other types of convex functions, such as exponentially concave or strongly convex functions. In this paper, we affirmatively answer this question by proposing a novel meta-algorithm, termed IRESET, which is used to aggregate the decisions from a group of experts. The essence of our method lies in running multiple experts over a set of intervals, and then employing a meta-algorithm equipped with second-order bounds to sequentially combine their decisions. We leverage the segment tree structure to analyze the switching regret over the entire time horizon, and offer new insights into utilizing recursive equations over the segment tree. By choosing appropriate expert-algorithms for IRESET, our methods achieve logarithmic switching regret bounds for exponentially concave or strongly convex functions, respectively.

General Machine Learning · Online Learning, Active Learning and Bandits

Humaira Kousar, Hasnain Irshad Bhatti, Jaekyun Moon

Efficient data selection is crucial for enhancing the training efficiency of deep neural networks and minimizing annotation requirements. Traditional methods often face high computational costs, limiting their scalability and practical use. We introduce PruneFuse, a novel strategy that leverages pruned networks for data selection and later fuses them with the original network to optimize training. PruneFuse operates in two stages: First, it applies structured pruning to create a smaller pruned network that, due to its structural coherence with the original network, is well-suited for the data selection task. This small network is then trained and selects the most informative samples from the dataset. Second, the trained pruned network is seamlessly fused with the original network. This integration leverages the insights gained during the training of the pruned network to facilitate the learning process of the fused network while leaving room for the network to discover more robust solutions. Extensive experimentation on various datasets demonstrates that PruneFuse significantly reduces computational costs for data selection, achieves better performance than baselines, and accelerates the overall training process.

Theory · Online Learning and Bandits

Sanghoon Yu, Min-hwan Oh

We study linear contextual bandits under rare parameter updates: the learner may incorporate reward feedback into its parameter estimate only at a small number of update times, while still observing contexts online and selecting actions sequentially. This viewpoint clarifies a practical distinction that is often blurred in the literature: many "strictly batched" methods additionally restrict within-interval context adaptivity, meaning that the action rule inside an interval cannot depend on the sequence of realized contexts/actions in that interval (beyond the current round's context). For linear contextual bandits, we propose two practical algorithms with only $O(\log\log T)$ parameter updates. Our first algorithm BLCE-G attains minimax-optimal regret (up to polylogarithmic factors in $T$) simultaneously in both the small-$K$ and large-$K$ regimes under a static schedule. Our second algorithm BLCE removes the near G-optimal design step---a dominant computational bottleneck in prior strictly batched static-grid methods---yet preserves minimax-optimal regret and achieves the lowest known runtime complexity among optimal algorithms. We further extend these rare-update and computational principles to generalized linear contextual bandits. Overall, our results yield statistically optimal algorithms under $O(\log\log T)$ parameter updates that are also computationally efficient in practice.

Theory · Online Learning and Bandits

Gabriel Sargent, Wei Sun, Zhengwu Zhang, Yufeng Liu

In adaptive experiments, statistical inference is essential for reliable decision-making and scientific discovery. Often in these settings, collecting labeled data is expensive, but decision-makers have access to large unlabeled datasets and strong pretrained AI models that can generate outcome predictions. Effectively leveraging these predictions in online experiments poses fundamental challenges for statistical inference: AI models may be misspecified, and data collected under adaptive policies are inherently non-i.i.d., invalidating classical inference techniques. To address these challenges, we propose a Prediction-Powered Adaptive Inference (PPAI) estimator that integrates unlabeled data, predicted labels, and adaptively collected labeled data through a single estimating equation. We establish asymptotic normality of the PPAI estimator under mild conditions on the data-collection policy, enabling valid confidence intervals and hypothesis tests for a broad class of Z-functionals. The method incorporates a data-driven tuning mechanism that adaptively weights AI predictions according to their informativeness, guaranteeing that the resulting asymptotic variance is no worse than that of the labeled-only baseline, and is strictly smaller when predictions are informative. Numerical experiments further support the theory, illustrating efficiency gains with informative AI predictions and robust performance when predictions are inaccurate.

Theory · Online Learning and Bandits

Yan-Feng Xie, Yu-Jie Zhang, Peng Zhao, Zhi-Hua Zhou

We study dynamic regret minimization in non-stationary online learning, with a primary focus on follow-the-regularized-leader (FTRL) methods. FTRL is important for curved losses and for understanding adaptive algorithms, yet existing dynamic regret analyses are less explored for FTRL. To address this, we build on the discounted-to-dynamic reduction and present a modular way to obtain dynamic regret bounds. The reduction simplifies prior proofs for online linear regression, recovers optimal rates, and provides new guarantees for online logistic regression, covering two representative curved losses. Beyond online convex optimization, we apply the reduction to analyze the Adam optimizers, obtaining optimal convergence rates in stochastic, non-convex, and non-smooth settings. The reduction also enables a more detailed treatment of Adam with two discount parameters $(\beta_1,\beta_2)$, leading to new results for both clipped and clip-free variants.

Theory · Online Learning and Bandits

Heesang Ann, Hyun-jun Choi, Taehyun Hwang, Younghoon Shin, Haeju Cheong, Min-hwan Oh

We study generalized linear bandits with memory, a non-stationary setting in which rewards depend on past actions through a finite memory matrix. Building on prior work for linear models Clerici et al.,(2024), we show that the previously known $\tilde{\mathcal{O}}(T^{3/4})$ regret stems from a loose analysis based on cyclic proxy policies, and we refine the analysis to recover a $\tilde{\mathcal{O}}(\sqrt{T})$ regret rate in the linear case. We then extend this improvement to generalized linear models and propose a block-wise algorithm based on shrinkage-based confidence bounds. Our algorithm achieves a regret bound of $\tilde{\mathcal{O}}(\sqrt{mT}+ d\sqrt{T}+\sqrt{\kappa} d^{2} m^{1/4} T^{1/4} + \kappa d^{2})$, where $d$ denotes the feature dimension, $m$ the memory length, and $\kappa$ a curvature parameter of the link function, thereby attaining a $\sqrt{T}$ rate despite nonlinear rewards and memory effects. To the best of our knowledge, this analysis provides a unified treatment of memory-induced non-stationarity and nonlinear link functions, while ensuring that the leading regret term is independent of the curvature of the link function. We conduct numerical experiments that are consistent with our theoretical findings.