Search

We study a new class of MDPs that employs multinomial logit (MNL) function approximation to ensure valid probability distributions over the state space. Despite its benefits, introducing non-linear function approximation raises significant challenges in both computational and statistical efficiency. The best-known method of Hwang and Oh [2023] has achieved an $\widetilde{\mathcal{O}}(\kappa^{-1}dH^2\sqrt{K})$ regret, where $\kappa$ is a problem-dependent quantity, $d$ is the feature space dimension, $H$ is the episode length, and $K$ is the number of episodes. While this result attains the same rate in $K$ as the linear cases, the method requires storing all historical data and suffers from an $\mathcal{O}(K)$ computation cost per episode. Moreover, the quantity $\kappa$ can be exponentially small, leading to a significant gap for the regret compared to the linear cases. In this work, we first address the computational concerns by proposing an online algorithm that achieves the same regret with only $\mathcal{O}(1)$ computation cost. Then, we design two algorithms that leverage local information to enhance statistical efficiency. They not only maintain an $\mathcal{O}(1)$ computation cost per episode but achieve improved regrets of $\widetilde{\mathcal{O}}(\kappa^{-1/2}dH^2\sqrt{K})$ and $\widetilde{\mathcal{O}}(dH^2\sqrt{K} + \kappa^{-1}d^2H^2)$ respectively. Finally, we establish a lower bound, justifying the optimality of our results in $d$ and $K$. To the best of our knowledge, this is the first work that achieves almost the same computational and statistical efficiency as linear function approximation while employing non-linear function approximation for reinforcement learning.

Complementary-label learning is a weakly supervised learning problem in which each training example is associated with one or multiple complementary labels indicating the classes to which it does not belong. Existing consistent approaches have relied on the uniform distribution assumption to model the generation of complementary labels, or on an ordinary-label training set to estimate the transition matrix in non-uniform cases. However, either condition may not be satisfied in real-world scenarios. In this paper, we propose a novel consistent approach that does not rely on these conditions. Inspired by the positive-unlabeled (PU) learning literature, we propose an unbiased risk estimator based on the Selected-Completely-at-Random assumption for complementary-label learning. We then introduce a risk-correction approach to address overfitting problems. Furthermore, we find that complementary-label learning can be expressed as a set of negative-unlabeled binary classification problems when using the one-versus-rest strategy. Extensive experimental results on both synthetic and real-world benchmark datasets validate the superiority of our proposed approach over state-of-the-art methods., Comment: ICML 2024

The bound state of a $\tau^+\tau^-$ pair by the electromagnetic force is the heaviest and smallest QED atom. Since the discovery of the two lightest QED atoms more than 60 years ago, no evidence for the third one has been found. We demonstrate that the $J_\tau$ ($\tau^+\tau^-$ atom with $J^{PC}=1^{--}$) resonance signal can be observed with a significance larger than $5\sigma$ including both statistical and systematic uncertainties, via the process $e^+e^-\to X^+ Y^- \slashed{E}$ ($X,\,Y=e$, $\mu$, $\pi$, $K$, or $\rho$, and $\slashed{E}$ is the missing energy) with $1.5~{\rm ab^{-1}}$ data taken around the $\tau$ pair production threshold. The $\tau$ lepton mass can be measured in a precision of 2 keV with the same data sample. This is within one year's running time of the proposed super tau-charm factory or super charm-tau factory., Comment: 7 pages, 4 figures

Stochastically Extended Adversarial (SEA) model is introduced by Sachs et al. [2022] as an interpolation between stochastic and adversarial online convex optimization. Under the smoothness condition, they demonstrate that the expected regret of optimistic follow-the-regularized-leader (FTRL) depends on the cumulative stochastic variance $\sigma_{1:T}^2$ and the cumulative adversarial variation $\Sigma_{1:T}^2$ for convex functions. They also provide a slightly weaker bound based on the maximal stochastic variance $\sigma_{\max}^2$ and the maximal adversarial variation $\Sigma_{\max}^2$ for strongly convex functions. Inspired by their work, we investigate the theoretical guarantees of optimistic online mirror descent (OMD) for the SEA model. For convex and smooth functions, we obtain the same $\mathcal{O}(\sqrt{\sigma_{1:T}^2}+\sqrt{\Sigma_{1:T}^2})$ regret bound, without the convexity requirement of individual functions. For strongly convex and smooth functions, we establish an $\mathcal{O}((\sigma_{\max}^2 + \Sigma_{\max}^2) \log (\sigma_{1:T}^2+\Sigma_{1:T}^2))$ bound, better than their $\mathcal{O}((\sigma_{\max}^2 + \Sigma_{\max}^2) \log T)$ result. For exp-concave and smooth functions, we achieve a new $\mathcal{O}(d\log(\sigma_{1:T}^2+\Sigma_{1:T}^2))$ bound. Owing to the OMD framework, we broaden our work to study dynamic regret minimization and scenarios where the online functions are non-smooth. We establish the first dynamic regret guarantee for the SEA model with convex and smooth functions, which is more favorable than static regret bounds in non-stationary scenarios. Furthermore, to deal with non-smooth and convex functions in the SEA model, we propose novel algorithms building on optimistic OMD with an implicit update, which provably attain static regret and dynamic regret guarantees without smoothness conditions., Comment: v3 substantially improves the presentation and has a few improvements, including the regret bound for strongly convex functions; v2 is an extended version that enriches the content with improved regret bounds for strongly convex functions, discussions on the optimism design for dynamic regret minimization, and extensions to non-smooth scenarios; v1 is the ICML 2023 conference version

Dealing with distribution shifts is one of the central challenges for modern machine learning. One fundamental situation is the covariate shift, where the input distributions of data change from training to testing stages while the input-conditional output distribution remains unchanged. In this paper, we initiate the study of a more challenging scenario -- continuous covariate shift -- in which the test data appear sequentially, and their distributions can shift continuously. Our goal is to adaptively train the predictor such that its prediction risk accumulated over time can be minimized. Starting with the importance-weighted learning, we show the method works effectively if the time-varying density ratios of test and train inputs can be accurately estimated. However, existing density ratio estimation methods would fail due to data scarcity at each time step. To this end, we propose an online method that can appropriately reuse historical information. Our density ratio estimation method is proven to perform well by enjoying a dynamic regret bound, which finally leads to an excess risk guarantee for the predictor. Empirical results also validate the effectiveness., Comment: NeurIPS 2023

The standard supervised learning paradigm works effectively when training data shares the same distribution as the upcoming testing samples. However, this stationary assumption is often violated in real-world applications, especially when testing data appear in an online fashion. In this paper, we formulate and investigate the problem of \emph{online label shift} (OLaS): the learner trains an initial model from the labeled offline data and then deploys it to an unlabeled online environment where the underlying label distribution changes over time but the label-conditional density does not. The non-stationarity nature and the lack of supervision make the problem challenging to be tackled. To address the difficulty, we construct a new unbiased risk estimator that utilizes the unlabeled data, which exhibits many benign properties albeit with potential non-convexity. Building upon that, we propose novel online ensemble algorithms to deal with the non-stationarity of the environments. Our approach enjoys optimal \emph{dynamic regret}, indicating that the performance is competitive with a clairvoyant who knows the online environments in hindsight and then chooses the best decision for each round. The obtained dynamic regret bound scales with the intensity and pattern of label distribution shift, hence exhibiting the adaptivity in the OLaS problem. Extensive experiments are conducted to validate the effectiveness and support our theoretical findings., Comment: NeurIPS 2022; the first two authors contributed equally

We investigate online convex optimization in non-stationary environments and choose dynamic regret as the performance measure, defined as the difference between cumulative loss incurred by the online algorithm and that of any feasible comparator sequence. Let $T$ be the time horizon and $P_T$ be the path length that essentially reflects the non-stationarity of environments, the state-of-the-art dynamic regret is $\mathcal{O}(\sqrt{T(1+P_T)})$. Although this bound is proved to be minimax optimal for convex functions, in this paper, we demonstrate that it is possible to further enhance the guarantee for some easy problem instances, particularly when online functions are smooth. Specifically, we introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities: the variation in gradients of loss functions, the cumulative loss of the comparator sequence, and the minimum of these two terms. These quantities are at most $\mathcal{O}(T)$ while could be much smaller in benign environments. Therefore, our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and meanwhile safeguard the same rate in the worst case. Notably, our proposed algorithms can achieve favorable dynamic regret with only one gradient per iteration, sharing the same gradient query complexity as the static regret minimization methods. To accomplish this, we introduce the collaborative online ensemble framework. The proposed framework employs a two-layer online ensemble to handle non-stationarity, and uses optimistic online learning and further introduces crucial correction terms to enable effective collaboration within the meta-base two layers, thereby attaining adaptivity. We believe the framework can be useful for broader problems., Comment: V3 changes: improve the presentation (highlighting the techniques); V2 changes: Updated to improve the presentation (emphasizing the importance of gradient-variation bounds and the contribution of Sword++ algorithm)

We investigate online convex optimization in non-stationary environments and choose the dynamic regret as the performance measure, defined as the difference between cumulative loss incurred by the online algorithm and that of any feasible comparator sequence. Let $T$ be the time horizon and $P_T$ be the path-length that essentially reflects the non-stationarity of environments, the state-of-the-art dynamic regret is $\mathcal{O}(\sqrt{T(1+P_T)})$. Although this bound is proved to be minimax optimal for convex functions, in this paper, we demonstrate that it is possible to further enhance the dynamic regret by exploiting the smoothness condition. Specifically, we propose novel online algorithms that are capable of leveraging smoothness and replace the dependence on $T$ in the dynamic regret by problem-dependent quantities: the variation in gradients of loss functions, the cumulative loss of the comparator sequence, and the minimum of the previous two terms. These quantities are at most $\mathcal{O}(T)$ while could be much smaller in benign environments. Therefore, our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and meanwhile guarantee the same rate in the worst case.

We study the Single-Parton-Scattering (SPS) production of double quarkonia (J/psi+J/psi, J/psi+Upsilon, and Upsilon+Upsilon) in pp and pp(bar) collisions at the LHC and the Tevatron as measured by the CMS, ATLAS, LHCb, and D0 experiments in the Colour-Evaporation Model (CEM), based on the quark-hadron-duality, including Next-to-Leading Order (NLO) QCD corrections up to alpha_s^5. To do so, we also perform the first true NLO --up to alpha_s^4-- study of the p_T-differential cross section for single-quarkonium production. This allows us to fix the non-perturbative CEM parameters at NLO accuracy in the region where quarkonium-pair data are measured. Our results show that the CEM at NLO in general significantly undershoots these experimental data and, in view of the other existing SPS studies, confirm the need for Double Parton Scattering (DPS) to account for the data. Our NLO study of single-quarkonium production at mid and large p_T also confirms the difficulty of the approach to account for the measured p_T spectra; this is reminiscent of the impossibility to fit single-quarkonium data with the sole 3S18 NRQCD contribution from gluon fragmentation. We stress that the discrepancy occurs in a kinematical region where the new features of the improved CEM are not relevant., Comment: LaTeX, 9 pages; 17 figures, 2 tables

In conventional supervised learning, a training dataset is given with ground-truth labels from a known label set, and the learned model will classify unseen instances to known labels. This paper studies a new problem setting in which there are unknown classes in the training data misperceived as other labels, and thus their existence appears unknown from the given supervision. We attribute the unknown unknowns to the fact that the training dataset is badly advised by the incompletely perceived label space due to the insufficient feature information. To this end, we propose the exploratory machine learning, which examines and investigates training data by actively augmenting the feature space to discover potentially hidden classes. Our method consists of three ingredients including rejection model, feature exploration, and model cascade. We provide theoretical analysis to justify its superiority, and validate the effectiveness on both synthetic and real datasets., Comment: published at Artificial Intelligence, preliminary conference version published at AAAI'21

This paper studies the problem of learning with augmented classes (LAC), where augmented classes unobserved in the training data might emerge in the testing phase. Previous studies generally attempt to discover augmented classes by exploiting geometric properties, achieving inspiring empirical performance yet lacking theoretical understandings particularly on the generalization ability. In this paper we show that, by using unlabeled training data to approximate the potential distribution of augmented classes, an unbiased risk estimator of the testing distribution can be established for the LAC problem under mild assumptions, which paves a way to develop a sound approach with theoretical guarantees. Moreover, the proposed approach can adapt to complex changing environments where augmented classes may appear and the prior of known classes may change simultaneously. Extensive experiments confirm the effectiveness of our proposed approach.

Prompt double-$J/\psi$ production at high-energy hadron colliders can be considered as a golden channel to probe double parton scatterings (DPS) --in particular to study gluon-gluon correlations inside the proton-- and, at the same time, to measure the distribution of linearly-polarised gluons inside the proton. Such studies however require a good control of both single and DPS in the respective regions where they are carried out. In this context, we have critically examined two mechanisms of single parton scatterings (SPS) that may be kinematically enhanced where DPS are thought to be dominant, even though they are either at higher orders in the strong-coupling or velocity expansion. First, we have considered a gauge-invariant and infrared-safe subset of the loop-induced contribution via Colour-Singlet (CS) transitions. We have found it to become the leading CS SPS contributions at large rapidity separation, yet too small to account for the data without invoking the presence of DPS yields. Second, we have surveyed the possible Colour-Octet (CO) contributions using both old and up-to-date non-perturbative long distance matrix elements (LDMEs). We have found that the pure CO yields crucially depend on the LDMEs. Among all the LDMEs we used, only two result into a visible modification of the NRQCD (CS+CO) yield, but only in two kinematical distributions measured by ATLAS, those of the rapidity separation and of the pair invariant mass. These modifications however do not impact the control region used for their DPS study., Comment: 32 pages, 21 figures, 3 tables

Quarkonium production in proton-proton collision is interesting in profiling the partons inside the nucleon. Recently, the impact of double parton scatterings (DPSs) was suggested by experimental data of associated quarkonium production (J/psi+Z, J/psi+W, and J/psi+J/psi) at the LHC and Tevatron, in addition to single parton scatterings (SPSs). In this proceedings contribution, we review the extraction of the effective parameter of the DPS through the evaluation of the SPS contributions under quark-hadron duality., Comment: 4 pages, 3 figures, proceedings of the 8th International Conference on Quarks and Nuclear Physics (QNP2018), November 13-17, 2018

We propose that the process of triple prompt $J/\psi$ hadroproduction is a very clean hard probe of multiple-parton scatterings at high-energy hadron colliders, especially the least known triple-parton scattering. A first complete study is carried out by considering single-, double-, and triple-parton scatterings coherently. Our calculation shows that it is a golden channel to probe double- and triple-parton scatterings, as the single-parton scattering is strongly suppressed. The predictions of the (differential) cross sections in proton-proton collisions at the LHC and the future higher-energy hadron colliders are given. Our study shows that its measurement is already feasible with the existing data collected during the period of the LHC run 2. A method is proposed to extract the triple-parton scattering contribution, and therefore it paves a way to study the possible triple-parton correlations in a proton., Comment: 6 pages, 3 figures, 1 table; v2: match to the journal version

Quarkonium production in proton-proton (pp) collision provides interesting means to study the parton content and their correlations in the proton. Recent LHC and Tevatron data of J/psi + Z, J/psi + W and J/psi +J/psi production suggest the relevance of double parton scatterings (DPSs) as opposed to single parton scatterings (SPSs). In this proceedings contribution, we review the corresponding SPS contributions and discuss their upper limits set up by quark-hadron duality. These allow us to perform an improved extraction of the DPS yields and of their implications., Comment: 4 pages, 5 figures, Proceedings of the XXXIX International Conference on High Energy Physics (ICHEP2018), 4-11 July 2018, Seoul, Korea

The production process of quarkonia in proton-proton (pp) collision is a very good probe of the parton structure of the proton. Recent experimental data of the production of J/psi+vector boson or quarkonium pairs at the LHC and Tevatron suggest the relevance of double parton scatterings (DPS). We discuss here the single parton scattering (SPS) contribution to the J/psi +Z, J/psi +W, and J/psi +J/psi productions in hadron collisions. By revisiting the computations of the SPS contributions to the J/psi+Z and J/psi +W productions, we demonstrate that the ATLAS data in fact show evidence for DPS., Comment: 6 pages, 7 figures, Proceedings of the XXVI International Workshop on Deep Inelastic Scattering and Related Subjects (DIS2018), 16- 20 April 2018, Kobe, Japan