In this paper, we study the problem of online sparse linear regression (OSLR) where the algorithms are restricted to accessing only $k$ out of $d$ attributes per instance for prediction, which was proved to be NP-hard. Previous work gave polynomial-time algorithms assuming the data matrix satisfies the linear independence of features, the compatibility condition, or the restricted isometry property. We introduce a new polynomial-time algorithm, which significantly improves previous regret bounds (Ito et al., 2017) under the compatibility condition that is weaker than the other two assumptions. The improvements benefit from a tighter convergence rate of the $\ell_1$-norm error of our estimators. Our algorithm leverages the well-studied Dantzig Selector, but importantly with several novel techniques, including an algorithm-dependent sampling scheme for estimating the covariance matrix, an adaptive parameter tuning scheme, and a batching online Newton step with careful initializations. We also give novel and non-trivial analyses, including an induction method for analyzing the $\ell_1$-norm error, careful analyses on the covariance of non-independent random variables, and a decomposition on the regret. We further extend our algorithm to OSLR with additional observations where the algorithms can observe additional $k_0$ attributes after each prediction, and improve previous regret bounds (Kale et al., 2017; Ito et al., 2017).

Vision-language foundation models (VLMs), such as CLIP, exhibit remarkable performance across a wide range of tasks. However, deploying these models can be unreliable when significant distribution gaps exist between training and test data, while fine-tuning for diverse scenarios is often costly. Cache-based test-time adapters offer an efficient alternative by storing representative test samples to guide subsequent classifications. Yet, these methods typically employ naive cache management with limited capacity, leading to severe catastrophic forgetting when samples are inevitably dropped during updates. In this paper, we propose DOTA (DistributiOnal Test-time Adaptation), a simple yet effective method addressing this limitation. Crucially, instead of merely memorizing individual test samples, DOTA continuously estimates the underlying distribution of the test data stream. Test-time posterior probabilities are then computed using these dynamically estimated distributions via Bayes' theorem for adaptation. This distribution-centric approach enables the model to continually learn and adapt to the deployment environment. Extensive experiments validate that DOTA significantly mitigates forgetting and achieves state-of-the-art performance compared to existing methods.

In this paper, we study the mistake bound of online kernel learning on a budget. We propose a new budgeted online kernel learning model, called Ahpatron, which significantly improves the mistake bound of previous work and resolves an open problem related to upper bounds of hypothesis space constraints. We first present an aggressive variant of Perceptron, named AVP, a model without budget, which uses an active updating rule. Then we design a new budget maintenance mechanism, which removes a half of examples, and projects the removed examples onto a hypothesis space spanned by the remaining examples. Ahpatron adopts the above mechanism to approximate AVP. Theoretical analyses prove that Ahpatron has tighter mistake bounds, and experimental results show that Ahpatron outperforms the state-of-the-art algorithms on the same or a smaller budget.

We consider online model selection with decentralized data over $M$ clients, and study the necessity of collaboration among clients. Previous work proposed various federated algorithms without demonstrating their necessity, while we answer the question from a novel perspective of computational constraints. We prove lower bounds on the regret, and propose a federated algorithm and analyze the upper bound. Our results show (i) collaboration is unnecessary in the absence of computational constraints on clients; (ii) collaboration is necessary if the computational cost on each client is limited to $o(K)$, where $K$ is the number of candidate hypothesis spaces. We clarify the unnecessary nature of collaboration in previous federated algorithms for distributed online multi-kernel learning, and improve the regret bounds at a smaller computational and communication cost. Our algorithm relies on three new techniques including an improved Bernstein's inequality for martingale, a federated online mirror descent framework, and decoupling model selection and prediction, which might be of independent interest.

In this paper, we improve the kernel alignment regret bound for online kernel learning in the regime of the Hinge loss function. Previous algorithm achieves a regret of O((A_TT ln T)^{1/4}) at a computational complexity (space and per-round time) of O((A_TT ln T)^{1/2}), where A_T is called kernel alignment. We propose an algorithm whose regret bound and computational complexity are better than previous results. Our results depend on the decay rate of eigenvalues of the kernel matrix. If the eigenvalues of the kernel matrix decay exponentially, then our algorithm enjoys a regret of O((A_T)^{1/2}) at a computational complexity of O((ln T)^2). Otherwise, our algorithm enjoys a regret of O((A_TT)^{1/4}) at a computational complexity of O((A_TT)^{1/2}). We extend our algorithm to batch learning and obtain a O(T^{-1}(E[A_T])^{1/2}) excess risk bound which improves the previous O(T^{-1/2}) bound.

The trade-off between regret and computational cost is a fundamental problem for online kernel regression, and previous algorithms worked on the trade-off can not keep optimal regret bounds at a sublinear computational complexity. In this paper, we propose two new algorithms, AOGD-ALD and NONS-ALD, which can keep nearly optimal regret bounds at a sublinear computational complexity, and give sufficient conditions under which our algorithms work. Both algorithms dynamically maintain a group of nearly orthogonal basis used to approximate the kernel mapping, and keep nearly optimal regret bounds by controlling the approximate error. The number of basis depends on the approximate error and the decay rate of eigenvalues of the kernel matrix. If the eigenvalues decay exponentially, then AOGD-ALD and NONS-ALD separately achieves a regret of $O(\sqrt{L(f)})$ and $O(\mathrm{d}_{\mathrm{eff}}(\mu)\ln{T})$ at a computational complexity in $O(\ln^2{T})$. If the eigenvalues decay polynomially with degree $p\geq 1$, then our algorithms keep the same regret bounds at a computational complexity in $o(T)$ in the case of $p>4$ and $p\geq 10$, respectively. $L(f)$ is the cumulative losses of $f$ and $\mathrm{d}_{\mathrm{eff}}(\mu)$ is the effective dimension of the problem. The two regret bounds are nearly optimal and are not comparable.

Neural networks with random weights (NNRWs) which randomly assign weights to new hidden nodes, provide a new and promising stochastic approach for the research of neural networks, and have been proved to enjoy the universal approximation property. However, the design of existing learning algorithms for NNRWs is only based on the square loss function, which hinders the development of NNRWs. For strictly convex and strongly convex loss functions, it is unclear how to design learning algorithms, and what the convergence rates are. In this paper, we answer the questions affirmatively. First, we propose a new supervisory mechanism for constructing NNRWs, and prove the universal approximation property. Then we design a new learning algorithm and analyze the convergence rates of the algorithm, based on which the time complexities are also analyzed. To be specific, the proposed algorithm enjoys sublinear convergence for smooth and strictly convex loss functions, and linear convergence for smooth and strongly convex loss functions. Finally, experimental results on several real-world datasets verify the convergence rates of the algorithm with different loss functions.

We study kernel selection for online kernel learning, also known as online kernel selection which can be treated as a sequential decision problem and thus must balance the regret and the time complexity. Existing online kernel selection approaches via expert advice and classical adversarial bandit model can not meet the issue. In this work, we propose a novel grouped adversarial bandit solution to the problem. We first correspond each candidate kernel to a basic arm of an adversarial bandit problem. Then, all of the kernels are divided into several groups where each group is abstracted as a super arm. At each round, we choose a super arm and a basic kernel within the selected super arm, and make prediction by an online kernel learning algorithm. Besides, we introduce a Bernoulli random variable to decide whether to choose all of the rest super arms. Theoretical analysis shows the proposed approach balances the regret and the time complexity explicitly, which could enjoy better pseudo-regret and high probability regret bound than classical adversarial bandit model and lighter time complexity than expert advice model. Experimental results on benchmark datasets verify that the proposed approach balances the efficiency and effectiveness better.

Online kernel selection is critical to online kernel learning, but most of the existing online kernel learning methods ignore the online kernel selection process, and instead they empirically preset and fix a kernel or adjust kernel parameters by gradient descent, which is sensitive to the initial setting and has no theoretical guarantee. In this work, we propose an online kernel selection wrapper via the multi-armed bandit model, which can select a kernel at each round from a set of candidate kernels with theoretical guarantee and can be applied to any online kernel learning model. Specifically, the wrapper consists of two layers. In the outer layer, the wrapper corresponds each candidate kernel to an arm of the multi-armed bandit model, and chooses an arm according to the probability distribution maintained by the model at each round. In the inner layer, the wrapper updates the probability distribution according the loss of the selected arm, which is incurred by the prediction of the online kernel learning algorithm. We propose a new online kernel selection regret to measure the performance of the proposed wrapper, and prove that the proposed wrapper enjoys a sub-linear expected online kernel selection regret with respect to the cumulative loss of the optimal kernel among the candidates kernels. Experimental results on benchmark datasets demonstrate the effectiveness of the proposed wrapper.