Overview

Online learning studies how to make predictions and decisions as data arrive, rather than training once on a fixed dataset. Common approaches include Online Mirror Descent and Follow-the-Regularized-Leader for optimization, exponential-weights methods for choosing among experts, and bandit algorithms when feedback is limited. Researchers analyze regret and mistake bounds in adversarial, stochastic, and changing environments, and apply these methods to areas such as forecasting, auctions, and resource allocation. A central challenge is adapting quickly to change while remaining stable and efficient when feedback is delayed, noisy, or costly.

Latest papers

145 papers17 papers in the last four weeks, down 37% on the four weeks before. 0.1% of all new papers.

Nov 13, 2026

Online Switching Control as Learning with Experts

This paper addresses the problem of online switching control for discrete-time nonlinear systems where a controller is sequentially selected from a finite set of candidates. The goal is to generate an adaptive sequence of controllers to minimize the cumulative cost under unknown disturbances and cost functions. Specifically, we consider a full-information feedback setting where realized disturbance effects and cost functions are available after each selection. Using counterfactual costs computed from historical data, we reduce the online switching control problem to the experts problem with switching costs. Then, we propose an adaptive switching algorithm based on the Hedge algorithm with a switching suppression mechanism. Notably, the proposed algorithm achieves an expected regret of O(Tlog⁡N)O(\sqrt{T\log N}), where TT is the time horizon and NN is the number of candidate controllers, while ensuring uniform boundedness of the state. This matches the optimal regret order for the standard experts problem.
Nov 12, 2026

Capacity-Constrained Delayed Feedback for Online Conformal Risk Control

Online conformal risk control (OCRC) enables reliable uncertainty quantification in machine learning by converting model outputs into prediction sets with long-term risk guarantees. These guarantees, however, hinge on the assumption that the loss of each round is revealed immediately and losslessly. In practice, feedback may be delayed, and limited resources may prevent tracking all pending predictions, causing some feedback to be lost. To address this challenge, we develop capacity-aware OCRC (CA-OCRC), a framework that jointly determines how to allocate limited tracking feedback capacity and how to construct prediction sets. CA-OCRC is based on a randomized tracking policy that samples a proxy delay to decide whether, and for how long, feedback for the current round is tracked. CA-OCRC updates the prediction sets via inverse probability weighting, compensating for the possibility of feedback lost due to delays and limited tracking capacity. We analyze risk bounds for both arbitrary and stochastic delays, revealing a trade-off between receiving more feedback and avoiding capacity saturation. Building on these bounds, we optimize the proxy delay distribution, showing scaling laws for the tracking capacity that ensure the same long-term risk as OCRC with unlimited feedback. Experiments on medical imaging, natural language processing, computer vision, and wireless communications show the effectiveness of CA-OCRC as compared to existing OCRC mechanisms.
Nov 8, 2026

How Efficient Is Your Agent? Online Predictive Bounds under Budget Constraints

We evaluate AI agents in an online setting where tasks arrive sequentially and, before running each task, we construct an upper predictive bound on its time-to-success---the number of interactions until the task is completed successfully. Under a limited budget, some runs are stopped early, so their time-to-success is unobserved (right-censored), and the correctness of the bound may be unknown. We introduce PRedictive Bounds for Online Budget Efficiency (PROBE), a method for constructing calibrated upper predictive bounds while adaptively allocating a limited budget across agent tasks to reduce the anticipated coverage deficit. Our method calibrates the bounds online using inverse-probability-weighted feedback together with a correction designed to minimize coverage deficit while remaining unbiased. We prove that PROBE provides a coverage guarantee for any finite time horizon while satisfying the budget constraint. Experiments on software engineering, retrieval-augmented generation, and instruction following show that PROBE attains a coverage rate closer to the target level with tighter predictive bounds than a calibrated baseline.
Nov 6, 2026

Where Should Learning Live? Regret Analysis for Text, Parameter, and Joint Adaptation

Language-model systems can select prompts and parameter adapters repeatedly during deployment, using feedback to guide later choices. Earlier choices may change the context or environment inherited by later configurations. We study selection among preconstructed candidates and compare cumulative loss with the best fixed prompt--parameter pair used from the beginning. This excess loss separates into three terms: selection regret within the available family, the gap from restricting that family, and the benefit or harm of the actual deployment history. Selection is evaluated using the history each candidate would have produced if used throughout, which separates candidate quality from the effects of switching. When loss functions are fixed independently of selector randomness, past choices affect loss for only a bounded number of rounds, and every candidate's own-history loss is revealed, limiting switches yields sublinear expected regret within the selected family. We also quantify the costs and additional assumptions of independent probing and deployment-only feedback. Controlled experiments show that fewer switches can either lower or raise deployed loss, depending on whether inherited histories are harmful or helpful. With Qwen3.5-9B on Spider, text-only selection has lower within-family regret than joint selection, yet produces more failures because its candidate family excludes stronger configurations.
Nov 5, 2026

Online Learning with Ordered Experts (via Two-point Feedback)

We study adversarial online learning with expert recommendations in a totally ordered action space, where the experts' recommendations may change and be reordered arbitrarily. Our focus is two-point feedback: on each round the learner plays two current recommendations, observes both, and pays their average. We study two problems. In the separated monotone problem, the loss is the sum of a hidden nondecreasing component and a hidden nonincreasing component, and a query reveals the two components separately. In the BV problem, the losses are bounded and have bounded variation (BV) along the order, and a query reveals only the loss. In the separated monotone problem, two paid observations achieve O(log⁡(∣\cF∣T)Tlog⁡∣\cF∣)O\bigl(\log(|\cF|T)\sqrt{T\log|\cF|}\bigr) regret against the best of ∣\cF∣|\cF| experts, within a logarithmic factor of the classical full-information bound. For the BV problem, we obtain \wtO(T+∣\cF∣)\wtO(\sqrt T+|\cF|) regret. We give an application in dynamic pricing with expert advice, showing that two-option menus matches the full information rate up to log⁡\log factors. The main technical ingredient is a marginal-preserving endpoint flow estimator. Two observations reveal a loss increment along the order; random paths supply telescoping identities that turn this local information into unbiased loss estimates for all current recommendations. A reversible pair sampler preserves the learner's intended marginal at both played actions. The estimator's second-moment and stability bounds support online updates for both feedback models.
Nov 4, 2026

Self-Directed Apple Tasting

We study the classical apple-tasting setting, a partial feedback model in which the learner observes the true label only when it predicts 11. A combinatorial characterization for the rates of this problem in the online adversarial setting has been studied by Raman et al. (2024). We study the self-directed setting, in which the learner can adaptively choose the order of the points it predicts on. In the realizable setting, we establish a tetrachotomy on the expected minimax number of mistakes made by any learner. Depending on the VC dimension, the ∅\emptyset-centered star number, and the self-directed dimension, we show that the rates could possibly be Θ(1)Θ(1), O(log⁡n)∩ω(1)O(\log n) \cap ω(1), Θ~(n)\tilde Θ(\sqrt{n}), or Θ(n)Θ(n). In the agnostic setting, the minimax regret is Θ~(n)\tilde Θ(\sqrt{n}) or Θ(n)Θ(n), depending on the VC dimension.
Nov 4, 2026

Pathwise-Budgeted LLM Routing: Online Allocation with K-Bit Tail-Cost Learning

Firms using large language models under fixed budgets must decide which model to call and whether to retry a failed task. Because a call's charge is revealed only after completion, one long response can exhaust the remaining budget and leave later tasks unserved. Our objective is to maximize the number of tasks solved before service stops. We develop a contextual bandit policy, ADP-HT, which learns each model's task-specific success probability and constructs conservative cost estimates from coarsened response-length labels on a quantile grid with 2K2^K intervals. The policy weighs predicted success against these costs, adjusting the cost penalty to realized spending and the budget available per remaining task. Under calibration, local regularity, and grid-coverage conditions, we bound the excess allowance in the policy's conservative cost estimates. At a fixed sample size, increasing KK reduces the discretization term but increases the estimation allowance. At the tightest tested budgets, ADP-HT solves more than twice as many MATH500 and GPQA tasks as the best implemented baseline. It achieves the highest mean cumulative score at ten of fourteen RouterBench budgets. On LiveCodeBench, it outperforms a deployed commercial router in both default and cost-saving modes at the three lowest test budgets.
Nov 2, 2026

End-to-End Stability of Online Active Learning in Large-Scale Neural Systems

Online Active Learning (OAL) aims to extend deep learning from static inference after offline training to continuous adaptation during real-time interaction with a changing physical environment. This transition is essential for safety-critical applications, but it raises a central theoretical question: whether the online parameter update process remains stable when scaled to multilayer neural architectures. This paper develops a stability-focused OAL framework. The framework uses prediction error as a feedback signal to update a structured deep model, thereby linking online learning with Lyapunov-based energy minimization. We show that prediction error convergence alone is insufficient for global parameter convergence because multilayer networks may admit high-dimensional manifolds of equivalent output solutions. The analysis therefore separates output error regulation, internal zero dynamics, interlayer coupling, and parameter convergence. Persistency of excitation and active damping are then used to remove the residual null-space modes that remain after output error convergence. A cascaded Lyapunov analysis establishes asymptotic stability of the overall OAL learning process, while monotonic activation functions and diffeomorphic layer mappings provide the uniqueness condition for the target parameter trajectory. The resulting proof provides a theoretical basis for applying online adaptive learning to large-scale neural systems in nonstationary and safety-critical settings.
Oct 31, 2026

Streaming Virtual Metrology via Lightweight Adaptation under Temporal Distribution Shifts

Virtual metrology (VM) aims to estimate costly or delayed metrology variables from heterogeneous sensor signals and in-line measurements, and it acts as a critical component of semiconductor manufacturing. While recent data-driven models have improved VM accuracy, most are trained in batch settings and assume stationary data distributions. In practice, however, production environments evolve continuously due to equipment degradation, process adjustments, and maintenance events, making conventional batch-trained VM models difficult to maintain under temporal distribution shifts. In this work, we propose GRAPE (Global Regression with Adaptive Prediction Enhancement), a practical online learning framework for VM in evolving wafer-processing environments. GRAPE integrates a stable global predictor based on interpretable representations with two lightweight streaming adapters that correct feature-level and environment-level shifts through online updates. Experiments on two real-world semiconductor manufacturing datasets, including chronologically held-out blind-test streams, show that GRAPE improves robustness and generalization under real temporal drift compared with both conventional batch-learning methods and existing online learning baselines.
Oct 30, 2026

Learning to bid and bundle: a posterior-sampling agent for online retail

An online retailer launching a perishable product bids for sponsored-search clicks, discounts a bundle with an always-stocked staple and displays its remaining stock, which raises willingness to pay. It knows neither how clicks respond to its bid nor how strong and dispersed its market is, and learns both over repeated seasons from data its own decisions censor: a zero bid reveals nothing about paid clicks, and choices follow only clicks. We design a posterior-sampling agent for it. Each period it draws a market from an exact posterior and posts the bid and discount of that market's exactly solved season plan, so every action is one a fully informed seller could take. In a simulated online florist it has the lowest regret averaged over markets. In weak markets it gives up 12% to 23% of one season's revenue over 500 seasons, four to seven times less than drawing once per season. A planner acting on point estimates can stop bidding and never learn that bidding pays. The agent escapes after about three seasons on average, against fifty with one draw per season. Where displayed scarcity keeps willingness to pay above the posted price, the discount needs no learning. Customers waiting for the discount to return to its recent level look like lost sales, so frequent waiting makes the agent underrate its market. One discount per season removes waiting at a cost of 5.9% of clairvoyant revenue in a weak market and none in a strong one.
Oct 27, 2026

Online gas classification at the edge

Field applications in chemical sensing, from portable safety monitors to mobile robots, require models that are lightweight, fast to respond, and can be recalibrated from limited labelled data. Current gas classification pipelines assume controlled sampling cycles and offline feature extraction, and rely on computationally expensive models. With a few thousand neurons and sub-milliwatt power consumption, insects reliably classify odours in open environments. Inspired by the insect olfactory system, we present a neural network architecture that classifies raw sensor array readings using a sparse, high-dimensional binary representation. We evaluate it on random sequences of single gases and binary mixtures, introducing new samples dynamically and classifying gas identity from the transient sensor response. In this setting, the architecture out-performs a linear \gls{svm} on gas mixtures and matches an optimised non-linear \gls{svm}, while maintaining online class-level frequency estimates that distinguish familiar from novel stimuli. It relies exclusively on binary weights and Hebbian-based local learning, remaining computationally lightweight and well suited to ultra-low-power neuromorphic processors. We demonstrated the network on-chip with a hazardous gas detection experiment running on the mixed-signal neuromorphic chip TEXEL. The on-chip classifier yielded an accuracy of 74.6% while running at 482 \unit\nano\joule\unit{\nano\joule} per inference and 27 \unit{\micro\watt} of static-power.
Oct 25, 2026

Constrained Gradient Equilibrium: Approachability under Locally Constrained Adversaries

Gradient equilibrium (GEQ) is a recent framework in online learning that requires the time-averaged gradients along the learner's trajectory to vanish. We study GEQ when the learner is constrained and ask when such an equilibrium remains achievable in an adversarial environment. We first show that constrained GEQ (CGEQ) can be impossible even under simple and slowly varying constraints, motivating imposing local temporal structure on the adversary. We then develop an approachability framework for CGEQ under locally constrained adversaries, and obtain necessary and sufficient characterizations in the spirit of classical Blackwell approachability. Beyond these theoretical characterizations, we provide an algorithmic principle that converts window-wise no-regret learners into CGEQ algorithms under a local feasibility condition with margin. Experiments on synthetic and real data demonstrate that the resulting algorithms perform strongly in both achieving GEQ and respecting the constraints.
Oct 23, 2026

Batched NN 4D-Var: a performant hybrid model framework for the Integrated Forecasting System

Hybrid forecasting systems combining machine learning and numerical weather prediction offer a promising route toward improved forecast skill while preserving physical consistency. In this study, we investigate online learning of state-dependent model-error corrections within the Integrated Forecasting System using 4D-Var. Building on previous work, we represent model error using a neural network embedded within the forecast model and trained from observations through the data assimilation cycle. First, we introduce a targeted variant of neural-network 4D-Var in which only the neural-network parameters are estimated, while the atmospheric state is provided by a precomputed analysis. We then propose a batched extension that processes assimilation windows in random order and averages parameter increments over multiple windows, drawing inspiration from mini-batch stochastic optimization. Experiments are conducted with the Integrated Forecasting System of the European Centre for Medium-Range Weather Forecasts at an intermediate resolution. Sequential online learning substantially improves forecasts within the training period, with error reductions exceeding 10%in some cases. However, these improvements fail to generalize to unseen data. In contrast, the proposed batched formulation produces hybrid models that consistently improve forecast skill in out-of-sample experiments. Larger batch sizes accelerate convergence and improve robustness by reducing the noise of parameter updates. Diagnostics further show that the online-trained corrections preserve realistic forecast variability and do not improve skill through artificial smoothing. These results demonstrate that the formulation of the online learning problem is critical for generalisation and establish batched online training as a promising framework for hybrid machine-learning/data-assimilation systems.
Oct 19, 2026

A Simple and Unified Method for Gradient-Variation Regret

Gradient-variation online learning has attracted increasing attention for its connections to game theory and optimization. It has been studied in both non-stationary online learning, which aims to minimize dynamic regret against time-varying comparator sequences, and universal online learning, which seeks to adapt to unknown loss curvature. Prior work obtained gradient-variation bounds using different techniques tailored to each setting. We propose a simple and unified method based on surrogate losses with a quadratic penalty on decision movement, yielding gradient-variation bounds in both settings. For non-stationary online learning, the method induces an optimistic-to-gradient-variation reduction, enabling a broad class of algorithms to match the rate established by Zhao et al. (2024). For universal online learning, it yields a simple algorithm that matches the optimal universal regret bounds of Yan et al. (2024) while relaxing the extended smoothness assumption. Finally, we apply our method to online games and improve on existing guarantees.
Oct 16, 2026

No-Regret Language Generation

We introduce no-regret generation, which requires a generator to make a sublinear number of mistakes uniformly over all demonstration sequences and compatible target languages. We also formulate an agnostic variant that allows arbitrary demonstrations that may not be compatible with any languages. For both settings, we introduce tree-based mistake-forcing dimensions that exactly characterize finite-horizon minimax complexity and establish necessary and sufficient conditions for no-regret generation. Our characterizations reveal a rich spectrum of generation rates: up to constant rescaling, every admissible nondecreasing profile is attainable in both the realizable and agnostic settings. Finally, we connect generation complexity to online prediction: for language classes of finite Littlestone dimension dd, we obtain realizable mistake bounds of O(dlog⁡(1+T/d))O(d\log(1+T/d)) and agnostic regret bounds of O(dTlog⁡(1+T/d))O(\sqrt{dT\log(1+T/d)}). The realizable bound is optimal up to universal constants.
Oct 15, 2026

Learning Changes the World and Then What Was Learned has Changed: Training and Deploying Neural Networks in the Control Loop

Neural networks offer critical adaptability for controlling complex systems where nominal modeling proves intractable. However, when offline-trained neural networks are deployed within closed-loop control systems, their actions fundamentally alter the state distribution upon which they were trained. This paper introduces a unified taxonomy to categorize these sequential failure modes: the initial Closed-Loop Identification Error, the deployment-induced Action Error, and the continuous Tracking Error. Through discrete-time sensitivity analysis, this work formalizes how offline-learned parameters locally guarantee a trajectory divergence upon deployment, degrading performance due to local loss geometry. To mitigate this distribution shift, we propose actionable design policies centered on time-scale separated online adaptation. These mechanisms are validated through ablation studies on a nonlinear Duffing oscillator, demonstrating that bounded continuous learning successfully mitigates trajectory divergence whereas static deployments fail, offering concrete guidelines for practitioners deploying machine learning components in safety-critical feedback systems.
Oct 15, 2026

Online Quantile Omniprediction for Proper Losses

The task of constructing a predictor that is simultaneously accurate under multiple evaluation metrics has been popularized recently under the name omniprediction. Prior work in this area has largely focused on binary prediction tasks, and existing results for multiclass and continuous outcomes typically suffer from slow error rates. In this paper, we consider forecasts expressed as a set of quantiles over a discrete but otherwise arbitrary set of probability levels. We develop sample-efficient algorithms for constructing forecasts that are accurate simultaneously across all proper losses that satisfy mild regularity conditions, where proper losses are those minimized by predicting the true quantiles. Our algorithms are online and can operate in a dynamic environment, while simultaneously taking multiple losses into account, and their forecasts offer the potential to provide diverse end-users with rich information for evaluating risk and informing a range of practical decision-making tasks. As an example, we demonstrate how our procedure can be used to ensemble quantile forecasts of COVID-19 hospitalizations made by experts during the pandemic.
Oct 12, 2026

Longitudinal Learner Participation Profiling in Online Learning: Heterogeneous Consensus Clustering under Unequal Observation Windows

Learning management system traces are clustered to identify participation profiles, but unequal observation windows may cause profiles to reflect duration rather than participation alone. Using 16,448 complete learner--course sequences from 4,599 learners across 152 courses at a South African public university, we evaluated eight participation measures. All remained related to observation-window length even when expressed as rates or shares. Course-grouped adjustment reduced these relationships. Five retained measures were evaluated using K-means, Gaussian mixtures, Ward agglomerative clustering and K-medoids, with standardised measures and principal-component summaries. Evidence supported a broad two-profile grouping and a more detailed adjusted four-profile consensus: Gradually declining, Early-concentrated, Cyclical variable and Sustained active. Profile membership accounted for 2.87% of the variation in duration in the primary consensus, versus 38.18% using original measures. Mean assignment support was 0.739; 8.35% of assignments fell below 0.50, with greatest uncertainty in Sustained active. Two week-by-week sequence analyses agreed strongly with each other but only modestly with the four-profile consensus, indicating that the profiles combined multiple aspects of participation rather than distinct sequence patterns. Profiling should therefore assess duration effects, compare clustering methods and participation summaries, and report assignment consistency.
Oct 12, 2026

A Time-Synchronous Prequential Evaluation Framework for Next-Week Student Disengagement Prediction from Moodle LMS Logs

Retrospective evaluation of early-warning models may not reflect information available when predictions are issued and outcomes become observable. We developed a time-synchronous prequential framework for online prediction of next-week student disengagement, operationalised as inactivity onset, from Moodle logs. Ordered by calendar time, models were updated only with available outcomes and remained unchanged for all predictions at each prediction cutoff; development, calibration and evaluation were chronologically separate. We compared stochastic gradient descent logistic regression (SGD-LR), online sequential extreme learning machine (OSELM) and echo state network (ESN) across predictive performance, fixed, frozen and rolling threshold policies, calendar-time variation and four behavioural feature sets. Held-out evaluation comprised 49,329 predictions with 37.68% inactivity-onset prevalence. Discrimination was similar (average precision 0.665-0.679; ROC-AUC 0.755-0.774). OSELM had the highest recall, SGD-LR the highest precision and specificity, and ESN the highest Matthews correlation coefficient and balanced accuracy. Lower thresholds increased recall and alert volume, whereas rolling adaptation did not improve MCC over frozen thresholds. Weekly performance and calibrated-probability distributions varied without sustained deterioration. During model selection, cumulative-and-temporal features achieved the highest individual-set AP, with modest gains from combining all feature groups. These findings indicate that streaming early-warning evaluation should consider calibration, threshold-dependent performance, alert burden and calendar-time variation alongside aggregate discrimination.
Oct 10, 2026

To Defer or Not to Defer? Online Learning with LLMs and Congested Experts

Modern AI systems increasingly combine large language models (LLMs) with human experts, using the LLM to handle routine queries while deferring uncertain cases for expert review. When expert capacity is limited, however, deferral decisions must account not only for the reliability of the LLM but also for congestion in the expert queue. We formulate this as an online sequential decision-making problem in which, for each query, the system observes the confidence signal of the LLM's answer and must decide whether to output the answer or defer the query to a capacity-constrained expert. The reliability of the confidence signal is initially unknown and must be learned from expert feedback, which is both selectively observed (only deferred queries are labeled) and delayed by queuing. We propose KL-PBD, a learning algorithm that uses Kullback--Leibler lower confidence bounds on the unknown reliability parameters to guide deferral decisions. For KK confidence levels and horizon TT, KL-PBD achieves O(Klog⁡T)O(K\log T) gap-dependent regret when the accuracy at every confidence level is bounded away from the deferral boundary, and O~(KT)\widetilde{O}(\sqrt{KT}) worst-case regret. We establish matching lower bounds, showing that these rates are optimal up to logarithmic factors. Finally, we validate our approach on synthetic instances and real-world question-answering datasets, namely GSM8K, NuminaMath, and MedMCQA, using Qwen LLMs.
Oct 10, 2026

Conformal Sequential Decision Making With Cost and Sublinear Policy Regret Guarantees

Automated decision makers, such as AI agents that control robots or network devices, must often satisfy hard cost constraints while maintaining competitive performance. In such settings, a cost measure, such as a safety violation rate, energy consumption, or a distortion level, must stay within a given budget in every episode of operation. Furthermore, a cumulative reward metric, accounting for per-step performance, must stay close to the reward of a meaningful reference policy. We formulate this setup as an episodic sequential decision problem in which the state sequence is arbitrary, and the reward and cost may depend on past actions within the same episode. We propose the online conformal episodic agent (OCEA), a policy that selects one candidate action per episode using a regret-controlled algorithm, and switches to a zero-cost action when the remaining budget cannot absorb the maximum cost of one more round. We prove that OCEA satisfies per-episode cost constraints for every state sequence and for every realization of its internal randomness, while achieving a sublinear expected policy regret with respect to the best action sequence in hindsight from a comparator class satisfying the same per-episode cost constraints. We apply OCEA to risk-averse control and online compression with distortion guarantees.
Oct 9, 2026

Prediction Is Not a Sufficient Memory State

A memory that reproduces every current prediction may still have forgotten how to learn from the next observation. We characterize this distinction for exact cumulative learning and attention. For smooth convex residual losses with unrestricted real features and labels, a continuous recurrent state of fixed dimension exists exactly when the loss is polynomial. With ordinary, unweighted observations, degree DD requires precisely r=(d+DD)−1r=\binom{d+D}{D}-1 coordinates; even among histories with one fixed current predictor, exactly r−dr-d coordinates can remain necessary for continuation. Nonpolynomial losses have unbounded requirements on such equal-prediction histories. Bounded scalar logistic examples retain this obstruction after fixing any finite derivative jet. For ridge regression, the hidden evidence is the design matrix: the exact state costs dp+d(d+1)/2dp+d(d+1)/2, versus dpdp for the predictor. On a well-conditioned zero-prediction family, optimal BB-bit compression has average one-update error of order d−12−2B/sdd^{-1}2^{-2B/s_d}, sd=d(d+1)/2s_d=d(d+1)/2, even with arbitrary randomized codes. Kernel attention gives a second exact closure classification. The results identify what future updates reveal, rather than proposing a new regression algorithm or asserting trained-model gains.
Oct 9, 2026

Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment

We study simultaneous competitive and regret guarantees for TCP acknowledgment. Each acknowledgment serves all pending packets, and the objective is to minimize the total acknowledgment and waiting costs. It is well known that no deterministic online algorithm achieves a competitive ratio better than 22. Given kk randomized online experts and 0<ε<10<\varepsilon<1, we construct a randomized online algorithm whose realized total cost is always at most (2+ε)(2+\varepsilon) times the offline optimal cost OPT\mathrm{OPT} and whose expected regret against the expert with the smallest realized cost is O(OPTlog⁡(k+1)+log⁡(1/ε))O(\sqrt{\mathrm{OPT}\log(k+1)}+\log(1/\varepsilon)). The algorithm requires no advance knowledge of the number of packets or OPT\mathrm{OPT}. Our algorithm controls switching costs between experts and uses the gap between the permitted competitive bound and its current cost to determine when to learn. We also prove lower bounds showing that, for k≥2k\ge 2, this regret bound is asymptotically optimal in OPT\mathrm{OPT}, kk, and ε\varepsilon, and that ε>0\varepsilon>0 is necessary for sublinear regret.
Oct 9, 2026

Beyond Second-Order Information: Paid Logistic Regression with Noisy Features

We consider online binary prediction with paid stochastic features, where the learner can spend resources to obtain better observations of the underlying features. This setting is motivated by applications such as medical testing, where additional cost can provide more precise measurements of patient's features for predicting a binary outcome. At each round, a latent feature is drawn i.i.d., the response is generated through a logistic model, and the learner chooses how much to pay before observing a noisy version of the feature. The goal of learner is to jointly control prediction loss and acquisition cost. In contrast to the former result on the online linear regression with paid features, covariance information alone is no longer sufficient: two noise distributions with the same covariance may induce different optimal logistic losses, and lower variance can even lead to higher loss. Under a structural ordering in which larger payments yield better observations by removing independent noise, we obtain O~(T)\widetilde O(\sqrt{T}) regret when the noise structure is known and O~(T2/3)\widetilde O(T^{2/3}) regret when it is unknown, with matching lower bounds up to logarithmic factors.
Oct 8, 2026

AdaptLSTM: Efficient Adaptive Online Learning for Cloud Workload Forecasting under Distribution Drift

Accurate workload forecasting is critical for elastic resource provisioning in web-scale cloud services, where distribution shifts driven by viral content, product launches, and user behavior degrade offline-trained models rapidly. Naive online learning recovers accuracy but incurs prohibitive per-step compute cost. We propose AdaptLSTM, an adaptive online framework that detects drift via validation-calibrated thresholds and applies selective, targeted updates. On the Alibaba Machine Trace, AdaptLSTM recovers 54% of Naive Online's improvement at 20% cost (2.7×2.7\times efficiency, p=0.002p=0.002 over 10 seeds). On the more volatile Container Trace, it achieves 96% at 20% cost (4.8×4.8\times efficiency, +75%+75\% MAE reduction over Static). Unlike classical drift detectors (ADWIN, DDM, Page-Hinkley) which fail to trigger on regression-scale error streams, AdaptLSTM fires 42 times over 301 steps and outperforms matched-budget baselines. Wall-clock profiling shows 1.33×1.33\times throughput gain and 45% update-time reduction. The framework is model-agnostic: identical Pareto patterns hold for LSTM, GRU, and Transformer backbones.
Oct 8, 2026

Optimally Pacing Budget Spending and Learning

We establish near-optimal regret bounds for budget-constrained online learning against arbitrary classes of budget-pacing experts in the adversarial setting. In particular, given any class of FF experts and a candidate budget pacing schedule, we provide a full-information algorithm which obtains regret O(Dlog⁡F+Tlog⁡F)O(D \sqrt{\log F}+ \sqrt{T\log F}) against all experts whose cumulative spending stays within distance DD of this schedule, matching lower bounds established by Braverman et al. (2025). We additionally show that our technique extends to various problems in online resource allocation, where the learner gets to see the rewards and costs of the current options available to them, and establish O(Dlog⁡F)O(D\sqrt{\log F}) regret bounds when fractional allocation is allowed. This is the first algorithm we are aware of which can achieve o(T)o(\sqrt{T}) guarantees for such tasks.
Oct 7, 2026

Evolve on the Host, Predict on the Edge: Deploying Online Neuroevolutionary Architecture Search for Cross-sectional Stock Return Prediction

Accurate forecasting models are usually large, expensive to update online, and fixed in architecture once trained. We apply ONE-NAS, an online neuroevolutionary architecture search that evolves a population of small recurrent networks as each window of data arrives, to daily cross-sectional stock return prediction, and pilot it on a host and endpoint pipeline: the host runs the search and ships each generation's champion genomes over TCP/IP to a Raspberry Pi 4B, which predicts online. On the Pi a single champion predicts a 50-stock window in 24.6ms and the ensemble of 40 island champions in 556ms, far inside the daily decision cycle. On four panels of US mid-cap equities over 2022--2024, reading the population as a rank-mean ensemble of island champions returns +27.5%+27.5\% net of realised transaction costs, against +11.3+11.3 to +14.8%+14.8\% for online LSTM, online GRU and monthly-retrained LSTM baselines and +4.5%+4.5\% for the single best genome used in prior ONE-NAS work.
Oct 5, 2026

sHAIL-Causal: A Sequential Staircase Procedure for Invariant Causal Predictor Discovery

We introduce sHAIL-Causal, the causal specialization of the Saturated Hierarchical Atomic Incremental Learning (sHAIL) paradigm: a sequential staircase procedure that ascends a nested hierarchy of hypothesis classes H_0 < H_1 < ... < H_K once a saturation signal indicates that mastery of the current stage has plateaued. Where general sHAIL leaves the saturation criterion open, sHAIL-Causal instantiates it with a joint criterion of goodness-of-fit saturation and cross-environment invariance, replacing the complexity control of Structural Risk Minimization. We show, theoretically and by simulation, that complexity-only staircases are seduced by confounded predictors that lower empirical risk without reflecting stable causal structure, whereas an invariance-gated staircase provably halts at the true causal predictor set under a per-variable Richness condition. We show that naive greedy search fails to recover the causal set even under Richness, trace the failure to non-monotonicity of the invariance statistic along single-variable paths, and validate a fix combining bounded-exhaustive block-seeding with a calibrated acceptance threshold. We then extend the guarantee to environments arriving sequentially, yielding a confidence guarantee that stays valid at every arrival, which one-shot exhaustive search cannot offer without repeating its full combinatorial search. We close by formalizing the intervention of a wise teacher who lifts a saturated learner off a plateau of boredom.
Oct 5, 2026

AdaSpark: Adaptive DSpark with Online Learning for Tree Verification and N-gram Fill

Block drafters such as DSpark propose ranked candidates for several positions in one forward pass, and a tree verifier checks them in one pass of the target. The number of rows to verify trades the tokens a wider tree is expected to accept against the time a wider verify takes. Most schedulers that choose this number take the verify time from a table or model measured before serving, corrected online by at most one scale factor, and take acceptance from the drafter's confidence estimates or from a map fitted offline. AdaSpark learns both quantities while it serves, with no profile, calibration or sweep in advance. It learns which verify widths are worth offering and fits each one's verify time as a function of context. It fits each candidate's acceptance probability to the target's verify outcomes, with the drafter's confidence head as one input, and orders and sizes the tree by that fit instead of by the head. The same model prices n-gram continuations of the request's own text, so drafted and text-derived candidates compete for rows in one best-first order. The width is chosen by pricing time at the long-run decode rate. On single- and multi-turn conversations from six public datasets, on three dense targets and one mixture-of-experts target, AdaSpark decodes 1.5-3.1x faster than llama.cpp's DSpark with the same drafters. Our imparo engine with AdaSpark is 1.17-1.52x faster than imparo running with a three-token chain (the default llama.cpp setting); this gain comes from the scheduler alone. Without a width sweep, AdaSpark is never more than 0.3% slower than the best pinned tree width on any dense target or context band. On the mixture-of-experts target it ties the best pinned width, and the other pinned widths from 4 to 16 rows are 5-14% slower.
Oct 3, 2026

Understanding Generative AI Use in Programming MOOCs: The Role of Course Context and Learner Characteristics

The increasing availability of generative artificial intelligence (GenAI) tools, such as ChatGPT and code-completion assistants, raises questions about how learners integrate these tools into learning activities, particularly in MOOCs that attract diverse participant populations. This study examines the use of GenAI in two programming MOOCs taught in Estonian that differ in duration, workload, topic complexity, and assignment volume: About Programming (4 weeks, 26 expected hours, n = 187) and Introduction to Programming (8 weeks, 78 expected hours, n = 182). Post-course questionnaire data were analyzed using non-parametric statistical methods to examine self-reported adoption, usage frequency, and purposes of GenAI use across courses and learner backgrounds. The results show that GenAI adoption was widespread in both MOOCs, with no statistically significant differences by gender, age, education level, or prior programming experience. However, participants in the longer, more extensive MOOC reported significantly higher usage frequency and were more likely to use GenAI for debugging and idea generation. Reported usage frequency for code explanation and debugging was also higher in the longer course. Exploratory analyses found limited relationships between GenAI use and learning-related outcomes. The findings suggest that course context may play a greater role than learner characteristics in shaping how GenAI tools are used. These results provide implications for instructional design and guidance in programming education.