Neural Information Processing Systems http://nips.cc/

We establish new connections between LwEQ-TD and LfS-TD by studying LwEQ-TD for different learner models based on the richness of their query functions. We show that LwEQ-TD isthesameaswc-TD[18],RTD[22,24],andNCTD[27]forahypothesis class when restricting query functions to specific families.

Agnostic learning of Boolean halfspaces is a fundamental problem in computational learning theory, but it is known to be computationally hard even for weak learning. Recent work [CKKMK24] proposed smoothed analysis as a way to bypass such hardness, but existing frameworks rely on additive Gaussian perturbations, making them unsuitable for discrete domains. We introduce a new smoothed agnostic learning framework for Boolean inputs, where perturbations are modeled via random bit flips. This defines a natural discrete analogue of smoothed optimality generalizing the Gaussian case. Under strictly subexponential assumptions on the input distribution, we give an efficient algorithm for learning halfspaces in this model, with runtime and sample complexity approximately n raised to a poly(1/(sigma * epsilon)) factor. Previously, such algorithms were known only with strong structural assumptions for the discrete hypercube, for example, independent coordinates or symmetric distributions. Our result provides the first computationally efficient guarantee for smoothed agnostic learning of halfspaces over the Boolean hypercube, bridging the gap between worst-case intractability and practical learnability in discrete settings.

The problem has been extensively studied but most works focus on the submodular influence diffusion models.

We define the capacity of a learning machine to be the logarithm of the number (or volume) of the functions it can implement.

The problem of cooperative data censoring in battery-powered multihop sensor networks is analyzed in this paper. We are interested in scenarios where nodes generate messages (which are related to the sensor measurements) that can be graded with some importance value. Less important messages can be censored in order to save energy for later communications. The problem is modeled using a joint Markov Decision Process of the whole network dynamics, and a theoretically optimal censoring policy, which maximizes a long-term reward, is found. Though the optimal censoring rules are computationally prohibitive, our analysis suggests that, under some conditions, they can be approximated by a finite collection of constant-threshold rules. A centralized algorithm for the computation of these thresholds is proposed. The experimental simulations show that cooperative censoring policies are energy-efficient, and outperform other non-cooperative schemes.