Ron Meir

AAAI Conference 2026 Conference Paper

Unsupervised Feature Selection Through Group Discovery

• Shira Lifshitz
• Ofir Lindenbaum
• Gal Mishne
• Ron Meir
• Hadas Benisty

Unsupervised feature selection (FS) is essential for high-dimensional learning tasks where labels are not available. It helps reduce noise, improve generalization, and enhance interpretability. However, most existing unsupervised FS methods evaluate features in isolation, even though informative signals often emerge from groups of related features. For example, adjacent pixels, functionally connected brain regions, or correlated financial indicators tend to act together, making independent evaluation suboptimal. Although some methods attempt to capture group structure, they typically rely on predefined partitions or label supervision, limiting their applicability. We propose GroupFS, an end-to-end, fully differentiable framework that jointly discovers latent feature groups and selects the most informative groups among them, without relying on fixed a priori groups or label supervision. GroupFS enforces Laplacian smoothness on both feature and sample graphs and applies a group sparsity regularizer to learn a compact, structured representation. Across nine benchmarks spanning images, tabular data, and biological datasets, GroupFS consistently outperforms state-of-the-art unsupervised FS in clustering and selects groups of features that align with meaningful patterns.

ICLR Conference 2025 Conference Paper

CtD: Composition through Decomposition in Emergent Communication

• Boaz Carmeli
• Ron Meir
• Yonatan Belinkov

Compositionality is a cognitive mechanism that allows humans to systematically combine known concepts in novel ways. This study demonstrates how artificial neural agents acquire and utilize compositional generalization to describe previously unseen images. Our method, termed \`\`Composition through Decomposition'', involves two sequential training steps. In the \'Decompose\' step, the agents learn to decompose an image into basic concepts using a codebook acquired during interaction in a multi-target coordination game. Subsequently, in the \`Compose\' step, the agents employ this codebook to describe novel images by composing basic concepts into complex phrases. Remarkably, we observe cases where generalization in the `Compose' step is achieved zero-shot, without the need for additional training.

AAAI Conference 2025 Conference Paper

Unsupervised Translation of Emergent Communication

• Ido Levy
• Orr Paradise
• Boaz Carmeli
• Ron Meir
• Shafi Goldwasser
• Yonatan Belinkov

Emergent Communication (EC) provides a unique window into the language systems that emerge autonomously when agents are trained to jointly achieve shared goals. However, it is difficult to interpret EC and evaluate its relationship with natural languages (NL). This study employs unsupervised neural machine translation (UNMT) techniques to decipher ECs formed during referential games with varying task complexities, influenced by the semantic diversity of the environment. Our findings demonstrate UNMT's potential to translate EC, illustrating that task complexity characterized by semantic diversity enhances EC translatability, while higher task complexity with constrained semantic variability exhibits pragmatic EC, which, although challenging to interpret, remains suitable for translation. This research marks the first attempt, to our knowledge, to translate EC without the aid of parallel data.

AAAI Conference 2023 Conference Paper

Emergent Quantized Communication

• Boaz Carmeli
• Ron Meir
• Yonatan Belinkov

The field of emergent communication aims to understand the characteristics of communication as it emerges from artificial agents solving tasks that require information exchange. Communication with discrete messages is considered a desired characteristic, for scientific and applied reasons. However, training a multi-agent system with discrete communication is not straightforward, requiring either reinforcement learning algorithms or relaxing the discreteness requirement via a continuous approximation such as the Gumbel-softmax. Both these solutions result in poor performance compared to fully continuous communication. In this work, we propose an alternative approach to achieve discrete communication -- quantization of communicated message. Using message quantization allows us to train the model end-to-end, achieving superior performance in multiple setups. Moreover, quantization is a natural framework that runs the gamut from continuous to discrete communication. Thus, it sets the ground for a broader view of multi-agent communication in the deep learning era.

NeurIPS Conference 2023 Conference Paper

Meta-Learning Adversarial Bandit Algorithms

• Misha Khodak
• Ilya Osadchiy
• Keegan Harris
• Maria-Florina F. Balcan
• Kfir Y. Levy
• Ron Meir
• Steven Z. Wu

We study online meta-learning with bandit feedback, with the goal of improving performance across multiple tasks if they are similar according to some natural similarity measure. As the first to target the adversarial online-within-online partial-information setting, we design meta-algorithms that combine outer learners to simultaneously tune the initialization and other hyperparameters of an inner learner for two important cases: multi-armed bandits (MAB) and bandit linear optimization (BLO). For MAB, the meta-learners initialize and set hyperparameters of the Tsallis-entropy generalization of Exp3, with the task-averaged regret improving if the entropy of the optima-in-hindsight is small. For BLO, we learn to initialize and tune online mirror descent (OMD) with self-concordant barrier regularizers, showing that task-averaged regret varies directly with an action space-dependent measure they induce. Our guarantees rely on proving that unregularized follow-the-leader combined with two levels of low-dimensional hyperparameter tuning is enough to learn a sequence of affine functions of non-Lipschitz and sometimes non-convex Bregman divergences bounding the regret of OMD.

NeurIPS Conference 2023 Conference Paper

Perceptual Kalman Filters: Online State Estimation under a Perfect Perceptual-Quality Constraint

• Dror Freirich
• Tomer Michaeli
• Ron Meir

Many practical settings call for the reconstruction of temporal signals from corrupted or missing data. Classic examples include decoding, tracking, signal enhancement and denoising. Since the reconstructed signals are ultimately viewed by humans, it is desirable to achieve reconstructions that are pleasing to human perception. Mathematically, perfect perceptual-quality is achieved when the distribution of restored signals is the same as that of natural signals, a requirement which has been heavily researched in static estimation settings (i. e. when a whole signal is processed at once). Here, we study the problem of optimal causal filtering under a perfect perceptual-quality constraint, which is a task of fundamentally different nature. Specifically, we analyze a Gaussian Markov signal observed through a linear noisy transformation. In the absence of perceptual constraints, the Kalman filter is known to be optimal in the MSE sense for this setting. Here, we show that adding the perfect perceptual quality constraint (i. e. the requirement of temporal consistency), introduces a fundamental dilemma whereby the filter may have to ``knowingly'' ignore new information revealed by the observations in order to conform to its past decisions. This often comes at the cost of a significant increase in the MSE (beyond that encountered in static settings). Our analysis goes beyond the classic innovation process of the Kalman filter, and introduces the novel concept of an unutilized information process. Using this tool, we present a recursive formula for perceptual filters, and demonstrate the qualitative effects of perfect perceptual-quality estimation on a video reconstruction problem.

NeurIPS Conference 2022 Conference Paper

Integral Probability Metrics PAC-Bayes Bounds

• Ron Amit
• Baruch Epstein
• Shay Moran
• Ron Meir

We present a PAC-Bayes-style generalization bound which enables the replacement of the KL-divergence with a variety of Integral Probability Metrics (IPM). We provide instances of this bound with the IPM being the total variation metric and the Wasserstein distance. A notable feature of the obtained bounds is that they naturally interpolate between classical uniform convergence bounds in the worst case (when the prior and posterior are far away from each other), and improved bounds in favorable cases (when the posterior and prior are close). This illustrates the possibility of reinforcing classical generalization bounds with algorithm- and data-dependent components, thus making them more suitable to analyze algorithms that use a large hypothesis space.

NeurIPS Conference 2021 Conference Paper

A Theory of the Distortion-Perception Tradeoff in Wasserstein Space

• Dror Freirich
• Tomer Michaeli
• Ron Meir

The lower the distortion of an estimator, the more the distribution of its outputs generally deviates from the distribution of the signals it attempts to estimate. This phenomenon, known as the perception-distortion tradeoff, has captured significant attention in image restoration, where it implies that fidelity to ground truth images comes on the expense of perceptual quality (deviation from statistics of natural images). However, despite the increasing popularity of performing comparisons on the perception-distortion plane, there remains an important open question: what is the minimal distortion that can be achieved under a given perception constraint? In this paper, we derive a closed form expression for this distortion-perception (DP) function for the mean squared-error (MSE) distortion and Wasserstein-2 perception index. We prove that the DP function is always quadratic, regardless of the underlying distribution. This stems from the fact that estimators on the DP curve form a geodesic in Wasserstein space. In the Gaussian setting, we further provide a closed form expression for such estimators. For general distributions, we show how these estimators can be constructed from the estimators at the two extremes of the tradeoff: The global MSE minimizer, and a minimizer of the MSE under a perfect perceptual quality constraint. The latter can be obtained as a stochastic transformation of the former.

ICML Conference 2021 Conference Paper

Ensemble Bootstrapping for Q-Learning

• Oren Peer
• Chen Tessler
• Nadav Merlis
• Ron Meir

Q-learning (QL), a common reinforcement learning algorithm, suffers from over-estimation bias due to the maximization term in the optimal Bellman operator. This bias may lead to sub-optimal behavior. Double-Q-learning tackles this issue by utilizing two estimators, yet results in an under-estimation bias. Similar to over-estimation in Q-learning, in certain scenarios, the under-estimation bias may degrade performance. In this work, we introduce a new bias-reduced algorithm called Ensemble Bootstrapped Q-Learning (EBQL), a natural extension of Double-Q-learning to ensembles. We analyze our method both theoretically and empirically. Theoretically, we prove that EBQL-like updates yield lower MSE when estimating the maximal mean of a set of independent random variables. Empirically, we show that there exist domains where both over and under-estimation result in sub-optimal performance. Finally, We demonstrate the superior performance of a deep RL variant of EBQL over other deep QL algorithms for a suite of ATARI games.

ICML Conference 2020 Conference Paper

Discount Factor as a Regularizer in Reinforcement Learning

• Ron Amit
• Ron Meir
• Kamil Ciosek

Specifying a Reinforcement Learning (RL) task involves choosing a suitable planning horizon, which is typically modeled by a discount factor. It is known that applying RL algorithms with a lower discount factor can act as a regularizer, improving performance in the limited data regime. Yet the exact nature of this regularizer has not been investigated. In this work, we fill in this gap. For several Temporal-Difference (TD) learning methods, we show an explicit equivalence between using a reduced discount factor and adding an explicit regularization term to the algorithm’s loss. Motivated by the equivalence, we empirically study this technique compared to standard L2 regularization by extensive experiments in discrete and continuous domains, using tabular and functional representations. Our experiments suggest the regularization effectiveness is strongly related to properties of the available data, such as size, distribution, and mixing rate.

ICML Conference 2020 Conference Paper

Option Discovery in the Absence of Rewards with Manifold Analysis

• Amitay Bar
• Ronen Talmon
• Ron Meir

Options have been shown to be an effective tool in reinforcement learning, facilitating improved exploration and learning. In this paper, we present an approach based on spectral graph theory and derive an algorithm that systematically discovers options without access to a specific reward or task assignment. As opposed to the common practice used in previous methods, our algorithm makes full use of the spectrum of the graph Laplacian. Incorporating modes associated with higher graph frequencies unravels domain subtleties, which are shown to be useful for option discovery. Using geometric and manifold-based analysis, we present a theoretical justification for the algorithm. In addition, we showcase its performance in several domains, demonstrating clear improvements compared to competing methods.

ICML Conference 2019 Conference Paper

Distributional Multivariate Policy Evaluation and Exploration with the Bellman GAN

• Dror Freirich
• Tzahi Shimkin
• Ron Meir
• Aviv Tamar

The recently proposed distributional approach to reinforcement learning (DiRL) is centered on learning the distribution of the reward-to-go, often referred to as the value distribution. In this work, we show that the distributional Bellman equation, which drives DiRL methods, is equivalent to a generative adversarial network (GAN) model. In this formulation, DiRL can be seen as learning a deep generative model of the value distribution, driven by the discrepancy between the distribution of the current value, and the distribution of the sum of current reward and next value. We use this insight to propose a GAN-based approach to DiRL, which leverages the strengths of GANs in learning distributions of high dimensional data. In particular, we show that our GAN approach can be used for DiRL with multivariate rewards, an important setting which cannot be tackled with prior methods. The multivariate setting also allows us to unify learning the distribution of values and state transitions, and we exploit this idea to devise a novel exploration method that is driven by the discrepancy in estimating both values and states.

ICML Conference 2018 Conference Paper

Meta-Learning by Adjusting Priors Based on Extended PAC-Bayes Theory

• Ron Amit
• Ron Meir

In meta-learning an agent extracts knowledge from observed tasks, aiming to facilitate learning of novel future tasks. Under the assumption that future tasks are ‘related’ to previous tasks, accumulated knowledge should be learned in such a way that they capture the common structure across learned tasks, while allowing the learner sufficient flexibility to adapt to novel aspects of a new task. We present a framework for meta-learning that is based on generalization error bounds, allowing us to extend various PAC-Bayes bounds to meta-learning. Learning takes place through the construction of a distribution over hypotheses based on the observed tasks, and its utilization for learning a new task. Thus, prior knowledge is incorporated through setting an experience-dependent prior for novel tasks. We develop a gradient-based algorithm, and implement it for deep neural networks, based on minimizing an objective function derived from the bounds, and demonstrate its effectiveness numerically. In addition to establishing the improved performance available through meta-learning, we demonstrate the intuitive way by which prior information is manifested at different levels of the network.

NeurIPS Conference 2015 Conference Paper

A Tractable Approximation to Optimal Point Process Filtering: Application to Neural Encoding

• Yuval Harel
• Ron Meir
• Manfred Opper

The process of dynamic state estimation (filtering) based on point process observations is in general intractable. Numerical sampling techniques are often practically useful, but lead to limited conceptual insight about optimal encoding/decoding strategies, which are of significant relevance to Computational Neuroscience. We develop an analytically tractable Bayesian approximation to optimal filtering based on point process observations, which allows us to introduce distributional assumptions about sensory cell properties, that greatly facilitates the analysis of optimal encoding in situations deviating from common assumptions of uniform coding. The analytic framework leads to insights which are difficult to obtain from numerical algorithms, and is consistent with experiments about the distribution of tuning curve centers. Interestingly, we find that the information gained from the absence of spikes may be crucial to performance.

NeurIPS Conference 2014 Conference Paper

Expectation Backpropagation: Parameter-Free Training of Multilayer Neural Networks with Continuous or Discrete Weights

• Daniel Soudry
• Itay Hubara
• Ron Meir

Multilayer Neural Networks (MNNs) are commonly trained using gradient descent-based methods, such as BackPropagation (BP). Inference in probabilistic graphical models is often done using variational Bayes methods, such as Expectation Propagation (EP). We show how an EP based approach can also be used to train deterministic MNNs. Specifically, we approximate the posterior of the weights given the data using a “mean-field” factorized distribution, in an online setting. Using online EP and the central limit theorem we find an analytical approximation to the Bayes update of this posterior, as well as the resulting Bayes estimates of the weights and outputs. Despite a different origin, the resulting algorithm, Expectation BackPropagation (EBP), is very similar to BP in form and efficiency. However, it has several additional advantages: (1) Training is parameter-free, given initial conditions (prior) and the MNN architecture. This is useful for large-scale problems, where parameter tuning is a major challenge. (2) The weights can be restricted to have discrete values. This is especially useful for implementing trained MNNs in precision limited hardware chips, thus improving their speed and energy efficiency by several orders of magnitude. We test the EBP algorithm numerically in eight binary text classification tasks. In all tasks, EBP outperforms: (1) standard BP with the optimal constant learning rate (2) previously reported state of the art. Interestingly, EBP-trained MNNs with binary weights usually perform better than MNNs with continuous (real) weights - if we average the MNN output using the inferred posterior.

NeurIPS Conference 2014 Conference Paper

Optimal Neural Codes for Control and Estimation

• Alex Susemihl
• Ron Meir
• Manfred Opper

Agents acting in the natural world aim at selecting appropriate actions based on noisy and partial sensory observations. Many behaviors leading to decision making and action selection in a closed loop setting are naturally phrased within a control theoretic framework. Within the framework of optimal Control Theory, one is usually given a cost function which is minimized by selecting a control law based on the observations. While in standard control settings the sensors are assumed fixed, biological systems often gain from the extra flexibility of optimizing the sensors themselves. However, this sensory adaptation is geared towards control rather than perception, as is often assumed. In this work we show that sensory adaptation for control differs from sensory adaptation for perception, even for simple control setups. This implies, consistently with recent experimental results, that when studying sensory adaptation, it is essential to account for the task being performed.

JMLR Journal 2012 Journal Article

Integrating a Partial Model into Model Free Reinforcement Learning

• Aviv Tamar
• Dotan Di Castro
• Ron Meir

In reinforcement learning an agent uses online feedback from the environment in order to adaptively select an effective policy. Model free approaches address this task by directly mapping environmental states to actions, while model based methods attempt to construct a model of the environment, followed by a selection of optimal actions based on that model. Given the complementary advantages of both approaches, we suggest a novel procedure which augments a model free algorithm with a partial model. The resulting hybrid algorithm switches between a model based and a model free mode, depending on the current state and the agent's knowledge. Our method relies on a novel definition for a partially known model, and an estimator that incorporates such knowledge in order to reduce uncertainty in stochastic approximation iterations. We prove that such an approach leads to improved policy evaluation whenever environmental knowledge is available, without compromising performance when such knowledge is absent. Numerical simulations demonstrate the effectiveness of the approach on policy gradient and Q-learning algorithms, and its usefulness in solving a call admission control problem. [abs] [ pdf ][ bib ] &copy JMLR 2012. ( edit, beta )

NeurIPS Conference 2011 Conference Paper

Analytical Results for the Error in Filtering of Gaussian Processes

• Alex Susemihl
• Ron Meir
• Manfred Opper

Bayesian filtering of stochastic stimuli has received a great deal of attention re- cently. It has been applied to describe the way in which biological systems dy- namically represent and make decisions about the environment. There have been no exact results for the error in the biologically plausible setting of inference on point process, however. We present an exact analysis of the evolution of the mean- squared error in a state estimation task using Gaussian-tuned point processes as sensors. This allows us to study the dynamics of the error of an optimal Bayesian decoder, providing insights into the limits obtainable in this task. This is done for Markovian and a class of non-Markovian Gaussian processes. We find that there is an optimal tuning width for which the error is minimized. This leads to a char- acterization of the optimal encoding for the setting as a function of the statistics of the stimulus, providing a mathematically sound primer for an ecological theory of sensory processing.

ICML Conference 2011 Conference Paper

Integrating Partial Model Knowledge in Model Free RL Algorithms

• Aviv Tamar
• Dotan Di Castro
• Ron Meir

JMLR Journal 2010 Journal Article

A Convergent Online Single Time Scale Actor Critic Algorithm

• Dotan Di Castro
• Ron Meir

Actor-Critic based approaches were among the first to address reinforcement learning in a general setting. Recently, these algorithms have gained renewed interest due to their generality, good convergence properties, and possible biological relevance. In this paper, we introduce an online temporal difference based actor-critic algorithm which is proved to converge to a neighborhood of a local maximum of the average reward. Linear function approximation is used by the critic in order estimate the value function, and the temporal difference signal, which is passed from the critic to the actor. The main distinguishing feature of the present convergence proof is that both the actor and the critic operate on a similar time scale, while in most current convergence proofs they are required to have very different time scales in order to converge. Moreover, the same temporal difference signal is used to update the parameters of both the actor and the critic. A limitation of the proposed approach, compared to results available for two time scale convergence, is that convergence is guaranteed only to a neighborhood of an optimal value, rather to an optimal value itself. The single time scale and identical temporal difference signal used by the actor and the critic, may provide a step towards constructing more biologically realistic models of reinforcement learning in the brain. [abs] [ pdf ][ bib ] &copy JMLR 2010. ( edit, beta )

NeurIPS Conference 2008 Conference Paper

Temporal Difference Based Actor Critic Learning - Convergence and Neural Implementation

• Dotan Castro
• Dmitry Volkinshtein
• Ron Meir

Actor-critic algorithms for reinforcement learning are achieving renewed popularity due to their good convergence properties in situations where other approaches often fail (e. g. , when function approximation is involved). Interestingly, there is growing evidence that actor-critic approaches based on phasic dopamine signals play a key role in biological learning through the cortical and basal ganglia. We derive a temporal difference based actor critic learning algorithm, for which convergence can be proved without assuming separate time scales for the actor and the critic. The approach is demonstrated by applying it to networks of spiking neurons. The established relation between phasic dopamine and the temporal difference signal lends support to the biological relevance of such algorithms.

NeurIPS Conference 2007 Conference Paper

A neural network implementing optimal state estimation based on dynamic spike train decoding

• Omer Bobrowski
• Ron Meir
• Shy Shoham
• Yonina Eldar

It is becoming increasingly evident that organisms acting in uncertain dynamical environments often employ exact or approximate Bayesian statistical calculations in order to continuously estimate the environmental state, integrate information from multiple sensory modalities, form predictions and choose actions. What is less clear is how these putative computations are implemented by cortical neural networks. An additional level of complexity is introduced because these networks observe the world through spike trains received from primary sensory afferents, rather than directly. A recent line of research has described mechanisms by which such computations can be implemented using a network of neurons whose activ- ity directly represents a probability distribution across the possible “world states”. Much of this work, however, uses various approximations, which severely re- strict the domain of applicability of these implementations. Here we make use of rigorous mathematical results from the theory of continuous time point process filtering, and show how optimal real-time state estimation and prediction may be implemented in a general setting using linear neural networks. We demonstrate the applicability of the approach with several examples, and relate the required network properties to the statistical nature of the environment, thereby quantify- ing the compatibility of a given network with its environment.

ICML Conference 2005 Conference Paper

Reinforcement learning with Gaussian processes

• Yaakov Engel
• Shie Mannor
• Ron Meir

NeurIPS Conference 2004 Conference Paper

A Feature Selection Algorithm Based on the Global Minimization of a Generalization Error Bound

• Dori Peleg
• Ron Meir

A novel linear feature selection algorithm is presented based on the global minimization of a data-dependent generalization error bound. Feature selection and scaling algorithms often lead to non-convex opti- mization problems, which in many previous approaches were addressed through gradient descent procedures that can only guarantee convergence to a local minimum. We propose an alternative approach, whereby the global solution of the non-convex optimization problem is derived via an equivalent optimization problem. Moreover, the convex optimization task is reduced to a conic quadratic programming problem for which effi- cient solvers are available. Highly competitive numerical results on both artificial and real-world data sets are reported.

ICML Conference 2003 Conference Paper

Bayes Meets Bellman: The Gaussian Process Approach to Temporal Difference Learning

• Yaakov Engel
• Shie Mannor
• Ron Meir

NeurIPS Conference 2003 Conference Paper

Error Bounds for Transductive Learning via Compression and Clustering

• Philip Derbeko
• Ran El-Yaniv
• Ron Meir

This paper is concerned with transductive learning. Although transduc- tion appears to be an easier task than induction, there have not been many provably useful algorithms and bounds for transduction. We present ex- plicit error bounds for transduction and derive a general technique for devising bounds within this setting. The technique is applied to derive error bounds for compression schemes such as (transductive) SVMs and for transduction algorithms based on clustering. 1 Introduction and Related Work In contrast to inductive learning, in the transductive setting the learner is given both the training and test sets prior to learning. The goal of the learner is to infer (or “transduce”) the labels of the test points. The transduction setting was introduced by Vapnik [1, 2] who proposed basic bounds and an algorithm for this setting. Clearly, inferring the labels of points in the test set can be done using an inductive scheme. However, as pointed out in [2], it makes little sense to solve an easier problem by ‘reducing’ it to a much more difficult one. In particular, the prior knowledge carried by the (unlabeled) test points can be incorporated into an algorithm, potentially leading to superior performance. Indeed, a number of papers have demonstrated empirically that transduction can offer substantial advantage over induction whenever the training set is small or moderate (see e. g. [3, 4, 5, 6]). However, unlike the current state of affairs in induction, the question of what are provably effective learning principles for transduction is quite far from being resolved. In this paper we provide new error bounds and a general technique for transductive learn- ing. Our technique is based on bounds that can be viewed as an extension of McAllester’s PAC-Bayesian framework [7, 8] to transductive learning. The main advantage of using this framework in transduction is that here priors can be selected after observing the unlabeled data (but before observing the labeled sample). This flexibility allows for the choice of “compact priors” (with small support) and therefore, for tight bounds. Another simple ob- servation is that the PAC-Bayesian framework can be operated with polynomially (in m, the training sample size) many different priors simultaneously. Altogether, this added flexibil- ity, of using data-dependent multiple priors allows for easy derivation of tight error bounds for “compression schemes” such as (transductive) SVMs and for clustering algorithms. We briefly review some previous results. The idea of transduction, and a specific algorithm for SVM transductive learning, was introduced and studied by Vapnik (e. g. [2]), where an error bound is also proposed. However, this bound is implicit and rather unwieldy and, to the best of our knowledge, has not been applied in practical situations. A PAC-Bayes bound [7] for transduction with Perceptron Decision Trees is given in [9]. The bound is data-dependent depending on the number of decision nodes, the margins at each node and the sample size. However, the authors state that the transduction bound is not much tighter than the induction bound. Empirical tests show that this transduction algorithm performs slightly better than induction in terms of the test error, however, the advantage is usually statistically insignificant. Refining the algorithm of [2] a transductive algorithm based on a SVMs is proposed in [3]. The paper also provides empirical tests indicating that transduc- tion is advantageous in the text categorization domain. An error bound for transduction, based on the effective VC Dimension, is given in [10]. More recently Lanckriet et al. [11] derived a transductive bound for kernel methods based on spectral properties of the kernel matrix. Blum and Langford [12] recently also established an implicit bound for transduc- tion, in the spirit of the results in [2]. 2 The Transduction Setup We consider the following setting proposed by Vapnik ([2] Chp. 8), which for simplicity is described in the context of binary classification (the general case will be discussed in the full paper). Let H be a set of binary hypotheses consisting of functions from input space X to {±1} and let Xm+u = {x1, .. ., xm+u} be a set of points from X each of which is chosen i. i. d. according to some unknown distribution µ(x). We call Xm+u the full sample. Let Xm = {x1, .. ., xm} and Ym = {y1, .. ., ym}, where Xm is drawn uniformly from Xm+u and yi ∈ {±1}. The set Sm = {(x1, y1), .. ., (xm, ym)} is referred to as a training sample. In this paper we assume that yi = φ(xi) for some unknown function φ. The remaining subset Xu = Xm+u \ Xm is referred to as the unlabeled sample. Based on Sm and Xu our goal is to choose h ∈ H which predicts the labels of points in Xu as accurately as possible. For each h ∈ H and a set Z = x1, .. ., x|Z| of samples define

JMLR Journal 2003 Journal Article

Generalization Error Bounds for Bayesian Mixture Algorithms

• Ron Meir
• Tong Zhang

Bayesian approaches to learning and estimation have played a significant role in the Statistics literature over many years. While they are often provably optimal in a frequentist setting, and lead to excellent performance in practical applications, there have not been many precise characterizations of their performance for finite sample sizes under general conditions. In this paper we consider the class of Bayesian mixture algorithms, where an estimator is formed by constructing a data-dependent mixture over some hypothesis space. Similarly to what is observed in practice, our results demonstrate that mixture approaches are particularly robust, and allow for the construction of highly complex estimators, while avoiding undesirable overfitting effects. Our results, while being data-dependent in nature, are insensitive to the underlying model assumptions, and apply whether or not these hold. At a technical level, the approach applies to unbounded functions, constrained only by certain moment conditions. Finally, the bounds derived can be directly applied to non-Bayesian mixture approaches such as Boosting and Bagging. [abs] [ pdf ][ ps.gz ][ ps ]

JMLR Journal 2003 Journal Article

Greedy Algorithms for Classification -- Consistency, Convergence Rates, and Adaptivity

• Shie Mannor
• Ron Meir
• Tong Zhang

Many regression and classification algorithms proposed over the years can be described as greedy procedures for the stagewise minimization of an appropriate cost function. Some examples include additive models, matching pursuit, and boosting. In this work we focus on the classification problem, for which many recent algorithms have been proposed and applied successfully. For a specific regularized form of greedy stagewise optimization, we prove consistency of the approach under rather general conditions. Focusing on specific classes of problems we provide conditions under which our greedy procedure achieves the (nearly) minimax rate of convergence, implying that the procedure cannot be improved in a worst case setting. We also construct a fully adaptive procedure, which, without knowing the smoothness parameter of the decision boundary, converges at the same rate as if the smoothness parameter were known. [abs] [ pdf ][ ps.gz ][ ps ]

NeurIPS Conference 2002 Conference Paper

Data-Dependent Bounds for Bayesian Mixture Methods

• Ron Meir
• Tong Zhang

We consider Bayesian mixture approaches, where a predictor is constructed by forming a weighted average of hypotheses from some space of functions. While such procedures are known to lead to optimal predictors in several cases, where su–ciently accurate prior information is available, it has not been clear how they perform when some of the prior assumptions are violated. In this paper we establish data-dependent bounds for such procedures, extending previous randomized approaches such as the Gibbs algorithm to a fully Bayesian setting. The flnite-sample guarantees established in this work enable the utilization of Bayesian mixture approaches in agnostic settings, where the usual assumptions of the Bayesian paradigm fail to hold. Moreover, the bounds derived can be directly applied to non-Bayesian mixture approaches such as Bagging and Boosting. 1 Introduction and Motivation The standard approach to Computational Learning Theory is usually formulated within the so-called frequentist approach to Statistics. Within this paradigm one is interested in constructing an estimator, based on a flnite sample, which possesses a small loss (generalization error). While many algorithms have been constructed and analyzed within this context, it is not clear how these approaches relate to standard optimality criteria within the frequentist framework. Two classic optimality criteria within the latter approach are the minimax and admissibility criteria, which charac- terize optimality of estimators in a rigorous and precise fashion [9]. Except in some special cases [12], it is not known whether any of the approaches used within the Learning community lead to optimality in either of the above senses of the word. On the other hand, it is known that under certain regularity conditions, Bayesian estimators lead to either minimax or admissible estimators, and thus to well-deflned optimality in the classical (frequentist) sense. In fact, it can be shown that Bayes estimators are essentially the only estimators which can achieve optimality in the above senses [9]. This optimality feature provides strong motivation for the study of Bayesian approaches in a frequentist setting. While Bayesian approaches have been widely studied, there have not been generally applicable bounds in the frequentist framework. Recently, several approaches have attempted to address this problem. In this paper we establish flnite sample data- dependent bounds for Bayesian mixture methods, which together with the above optimality properties suggest that these approaches should become more widely used. Consider the problem of supervised learning where we attempt to construct an es- timator based on a flnite sample of pairs of examples S = f(x1; y1); :: :; (xn; yn)g, each drawn independently according to an unknown distribution „(x; y). Let A be a learning algorithm which, based on the sample S, constructs a hypothesis (esti- mator) h from some set of hypotheses H. Denoting by ‘(y; h(x)) the instantaneous loss of the hypothesis h, we wish to assess the true loss L(h) = E„‘(y; h(x)) where the expectation is taken with respect to „. In particular, the objective is to provide data-dependent bounds of the following form. For any h 2 H and – 2 (0; 1), with probability at least 1 ¡ –, L(h) • ⁄(h; S) + ¢(h; S; –); (1) where ⁄(h; S) is some empirical assessment of the true loss, and ¢(h; S; –) is a com- plexity term. For example, in the classic Vapnik-Chervonenkis framework, ⁄(h; S) i=1 ‘(yi; h(xi)) and ¢(h; S; –) depends on the VC- dimension of H but is independent of both the hypothesis h and the sample S. By algorithm and data-dependent bounds we mean bounds where the complexity term depends on both the hypothesis (chosen by the algorithm A) and the sample S. is the empirical error (1=n)Pn 2 A Decision Theoretic Bayesian Framework Consider a decision theoretic setting where we deflne the sample dependent loss of an algorithm A by R(„; A; S) = E„‘(y; A(x; S)). Let (cid: 181)„ be the optimal predictor for y, namely the function minimizing E„f‘(y; (x))g over. It is clear that the best algorithm A (Bayes algorithm) is the one that always return (cid: 181)„, assuming „ is known. We are interested in the expected loss of an algorithm averaged over samples S: R(„; A) = ESR(„; A; S) =Z R(„; A; S)d„(S); where the expectation is taken with respect to the sample S drawn i. i. d. from the probability measure „. If we consider a family of measures „, which possesses some underlying prior distribution …(„), then we can construct the averaged risk function with respect to the prior as, r(…; A) = E…R(„; A) =Z d„(S)d…(„)Z R(„; A; S)d…(„jS); R„ d„(S)d…(„) is the posterior distribution on the „ family, which where d…(„jS) = d„(S)d…(„) induces a posterior distribution on the sample space as …S = E…(„jS)„. An algorithm minimizing the Bayes risk r(…; A) is referred to as a Bayes algorithm. In fact, for a given prior, and a given sample S, the optimal algorithm should return the Bayes optimal predictor with respect to the posterior measure …S. For many important practical problems, the optimal Bayes predictor is a linear functional of the underlying probability measure. For example, if the loss function is quadratic, namely ‘(y; A(x)) = (y ¡A(x))2, then the optimal Bayes predictor (cid: 181)„(x) is the conditional mean of y, namely E„[yjx]. For binary classiflcation problems, we can let the predictor be the conditional probability (cid: 181)„(x) = „(y = 1jx) (the optimal classiflcation decision rule then corresponds to a test of whether (cid: 181)„(x) > 0: 5), which is also a linear functional of „. Clearly if the Bayes predictor is a linear functional of the probability measure, then the optimal Bayes algorithm with respect to the prior … is given by

NeurIPS Conference 2000 Conference Paper

Weak Learners and Improved Rates of Convergence in Boosting

• Shie Mannor
• Ron Meir

The problem of constructing weak classifiers for boosting algo(cid: 173) rithms is studied. We present an algorithm that produces a linear classifier that is guaranteed to achieve an error better than random guessing for any distribution on the data. While this weak learner is not useful for learning in general, we show that under reasonable conditions on the distribution it yields an effective weak learner for one-dimensional problems. Preliminary simulations suggest that similar behavior can be expected in higher dimensions, a result which is corroborated by some recent theoretical bounds. Addi(cid: 173) tionally, we provide improved convergence rate bounds for the gen(cid: 173) eralization error in situations where the empirical error can be made small, which is exactly the situation that occurs if weak learners with guaranteed performance that is better than random guessing can be established.

NeurIPS Conference 1998 Conference Paper

Almost Linear VC Dimension Bounds for Piecewise Polynomial Networks

• Peter Bartlett
• Vitaly Maiorov
• Ron Meir

We compute upper and lower bounds on the VC dimension of feedforward networks of units with piecewise polynomial activa(cid: 173) tion functions. We show that if the number of layers is fixed, then the VC dimension grows as W log W, where W is the number of parameters in the network. This result stands in opposition to the case where the number of layers is unbounded, in which case the VC dimension grows as W 2 •

NeurIPS Conference 1998 Conference Paper

On the Optimality of Incremental Neural Network Algorithms

• Ron Meir
• Vitaly Maiorov

We study the approximation of functions by two-layer feedforward neu(cid: 173) ral networks, focusing on incremental algorithms which greedily add units, estimating single unit parameters at each stage. As opposed to standard algorithms for fixed architectures, the optimization at each stage is performed over a small number of parameters, mitigating many of the difficult numerical problems inherent in high-dimensional non-linear op(cid: 173) timization. We establish upper bounds on the error incurred by the al(cid: 173) gorithm, when approximating functions from the Sobolev class, thereby extending previous results which only provided rates of convergence for functions in certain convex hulls of functional spaces. By comparing our results to recently derived lower bounds, we show that the greedy algo(cid: 173) rithms are nearly optimal. Combined with estimation error results for greedy algorithms, a strong case can be made for this type of approach. 1 Introduction and background A major problem in the application of neural networks to real world problems is the ex(cid: 173) cessively long time required for training large networks of a fixed architecture. Moreover, theoretical results establish the intractability of such training in the worst case [9][4]. Ad(cid: 173) ditionally, the problem of determining the architecture and size of the network required to solve a certain task is left open. Due to these problems, several authors have considered incremental algorithms for constructing the network by the addition of hidden units, and estimation of each unit's parameters incrementally. These approaches possess two desir(cid: 173) able attributes: first, the optimization is done step-wise, so that only a small number of parameters need to be optimized at each stage; and second, the structure of the network -This work was supported in part by the a grant from the Israel Science Foundation tThe author was partially supported by the center for Absorption in Science, Ministry of Immi(cid: 173) grant Absorption, State of Israel. 296 R. Meir and V Maiorov is established concomitantly with the learning, rather than specifying it in advance. How(cid: 173) ever, until recently these algorithms have been rather heuristic in nature, as no guaranteed performance bounds had been established. Note that while there has been a recent surge of interest in these types of algorithms, they in fact date back to work done in the early seventies (see [3] for a historical survey). The first theoretical result establishing performance bounds for incremental approximations in Hilbert space, was given by Jones [8]. This work was later extended by Barron [2], and applied to neural network approximation of functions characterized by certain conditions on their Fourier coefficients. The work of Barron has been extended in two main direc(cid: 173) tions. First, Lee et at. [10] have considered approximating general functions using Hilbert space techniques, while Donahue et al. [7] have provided powerful extensions of Jones' and Barron's results to general Banach spaces. One of the most impressive results of the latter work is the demonstration that iterative algorithms can, in many cases, achieve nearly optimal rates of convergence, when approximating convex hulls. While this paper is concerned mainly with issues of approximation, we comment that it is highly relevant to the statistical problem of learning from data in neural networks. First, Lee et at. [10] give estimation error bounds for algorithms performing incremental opti(cid: 173) mization with respect to the training error. Under certain regularity conditions, they are able to achieve rates of convergence comparable to those obtained by the much more com(cid: 173) putationally demanding algorithm of empirical error minimization. Moreover, it is well known that upper bounds on the approximation error are needed in order to obtain per(cid: 173) formance bounds, both for parametric and nonparametric estimation, where the latter is achieved using the method of complexity regularization. Finally, as pointed out by Don(cid: 173) ahue et al. [7], lower bounds on the approximation error are crucial in establishing worst case speed limitations for learning. The main contribution of this paper is as follows. For functions belonging to the Sobolev class (see definition below), we establish, under appropriate conditions, near-optimal rates of convergence for the incremental approach, and obtain explicit bounds on the parameter values of the network. The latter bounds are often crucial for establishing estimation error rates. In contrast to the work in [10] and [7], we characterize approximation rates for functions belonging to standard smoothness classes, such as the Sobolev class. The former work establishes rates of convergence with respect to the convex hulls of certain subsets of functions, which do not relate in a any simple way to standard functional classes (such as Lipschitz, Sobolev, Holder, etc. ). As far as we are aware, the results reported here are the first to report on such bounds for incremental neural network procedures. A detailed version of this work, complete with the detailed proofs, is available in [13]. 2 Problem statement We make use of the nomenclature and definitions from [7]. Let H be a Banach space of functions with norm II. II. For concreteness we assume henceforth that the norm is given by the Lq norm, 1 < q < 00, denoted by II. Ilq. Let linn H consist of all sums of the form L~=l aigi, gi E H and arbitrary ai, and COn H is the set of such sums with ai E [0, 1] and L~=l ai = 1. The distances, measured in the Lq norm, from a function f are given by dist(1innH, f) = inf {l lh - fllq: hE linnH}, dist(conH, f) = inf {l lh - fllq: hE conH}. The linear span of H is given by linH = Un linn H, while the convex-hull of H is coH = Uncon H. We follow standard notation and denote closures of sets by a bar, e. g. coH is the closure of the convex hull of H. In this work we focus on the special case where H = H1} ~ {g: g(x) = eCJ(aT x + b), lei: :; 1}, IICJ(·)llq: :; I},

NeurIPS Conference 1997 Conference Paper

Structural Risk Minimization for Nonparametric Time Series Prediction

• Ron Meir

The problem of time series prediction is studied within the uniform con(cid: 173) vergence framework of Vapnik and Chervonenkis. The dependence in(cid: 173) herent in the temporal structure is incorporated into the analysis, thereby generalizing the available theory for memoryless processes. Finite sam(cid: 173) ple bounds are calculated in terms of covering numbers of the approxi(cid: 173) mating class, and the tradeoff between approximation and estimation is discussed. A complexity regularization approach is outlined, based on Vapnik's method of Structural Risk Minimization, and shown to be ap(cid: 173) plicable in the context of mixing stochastic processes. 1 Time Series Prediction and Mixing Processes A great deal of effort has been expended in recent years on the problem of deriving robust distribution-free error bounds for learning, mainly in the context of memory less processes (e. g. [9]). On the other hand, an extensive amount of work has been devoted by statisticians and econometricians to the study of parametric (often linear) models of time series, where the dependence inherent in the sample, precludes straightforward application of many of the standard results form the theory of memoryless processes. In this work we propose an extension of the framework pioneered by Vapnik and Chervonenkis to the problem of time series prediction. Some of the more elementary proofs are sketched, while the main technical results will be proved in detail in the full version of the paper. Consider a stationary stochastic process X = {. .. ,X -1, X 0, X 1, .. . }, where Xi is a ran(cid: 173) dom variable defined over a compact domain in R and such that IXil: :; B with probability 1, for some positive constant B. The problem of one-step prediction, in the mean square sense, can then be phrased as that of finding a function f (. ) of the infinite past, such that E IXo - f(X=~) 12 is minimal, where we use the notation xf = (Xi, Xi ti, .. ., Xj ), ·This work was supported in part by the a grant from the Israel Science Foundation Structural Risk Minimization/or Nonparametric Time Series Prediction 309 j ~ i. It is well known that the optimal predictor in this case is given by the conditional mean, E[XoIX: !J While this solution, in principle, settles the issue of optimal predic(cid: 173) tion, it does not settle the issue of actually computing the optimal predictor. First of all, note that ~o compute the conditional mean, the probabilistic law generating the stochastic process X must be known. Furthermore, the requirement of knowing the full past, X=-~, is of course rather stringent. In this work we consider the more practical situation, where a finite sub-sequence Xi" = (Xl, X 2, ···, XN) is observed, and an optimal prediction is needed, conditioned on this data. Moreover, for each finite sample size N we allow the pre. dictors to be based only on a finite lag vector of size d. Ultimately, in order to achieve full generality one may let d -+ 00 when N -+ 00 in order to obtain the optimal predictor. We first consider the problem of selecting an empirical estimator from a class of functions Fd, n: Rd -+ R, where n is a complexity index of the class (for example, the number of computational nodes in a feedforward neural network with a single hidden layer), and If I: :; B for f E Fd, n. Consider then an empirical predictor fd, n, N(Xi=~), i > N, for Xi based on the finite data set Xi" and depending on the d-dimensional lag vector Xi=~, where fd, n, N E Fd, n. It is possible to split the error incurred by this predictor into three terms, each possessing a rather intuitive meaning. It is the competition between these terms which determines the optimal solution, for a fixed amount of data. First, define the loss of a functional predictor f: Rd -+ R as L(f) = E IXi - f(xi=~) 12, and let fd, n be the optimal function in Fd, n minimizing this loss. Furthermore, denote the optimal lag d predictor by fd' and its associated loss by L'd. We are then able to split the loss of the empirical predictor fd, n, N into three basic components, L(fd, n, N) = (Ld, n, N - L'd, n) + (L'd, n - L'd) + L'd, (I) where Ld, n, N = L(fd, n, N). The third term, L'd, is related to the error incurred in using a fi(cid: 173) nite memory model (of lag size d) to predict a process with potentially infinite memory. We do not at present have any useful upper bounds for this term, which is related to the rate of convergence in the martingale convergence theorem, which to the best of our knowledge is unknown for the type of mixing processes we study in this work. The second term in (1), is related to the so-called approximation error, given by Elfei (X: =-~) - fel, n (Xf=~) 12 to which it can be immediately related through the inequality IIalP - IblPI: :; pia - bll max( a, b) Ip-l. This term measures the excess error incurred by selecting a function f from a class of lim(cid: 173) ited complexity Fd, n, while the optimal lag d predictor fei may be arbitrarily complex. Of course, in order to bound this term we will have to make some regularity assumptions about the latter function. Finally, the first term in (1) r~resents the so called estimation error, and is the only term which depends on the data Xl. Similarly to the problem of regression for i. i. d. data, we expect that the approximation and estimation terms lead to conflicting demands on the choice of the the complexity, n, of the functional class Fd, n. Clearly, in order to minimize the approximation error the complexity should be made as large as pos(cid: 173) sible. However, doing this will cause the estimation error to increase, because of the larger freedom in choosing a specific function in Fd, n to fit the data. However, in the case of time series there is an additional complication resulting from the fact that the misspecification error L'd is minimized by choosing d to be as large as possible, while this has the effect of increasing both the approximation as well as the estimation errors. We thus expect that sOrhe optimal values of d and n exist for each sample size N. Up to this point we have not specified how to select the empirical estimator f d, n, N. In this work we follow the ideas of Vapnik [8], which have been studied extensively in the con(cid: 173) text of i. i. d observations, and restrict our selection to that hypothesis which minimizes the empirical error, given by LN(f) = N~d 2: :~d+l IXi - f(x: =~)12. For this function it is easy to establish (see for example [8]) that (Ld, n, N - L'd, n): :; 2 sUP! E. rd, n IL(f) - LN(f)I· The main distinction from the i. i. d case, of course, is that random variables appearing in

NeurIPS Conference 1996 Conference Paper

Time Series Prediction using Mixtures of Experts

• Assaf Zeevi
• Ron Meir
• Robert Adler

We consider the problem of prediction of stationary time series, using the architecture known as mixtures of experts (MEM). Here we suggest a mixture which blends several autoregressive models. This study focuses on some theoretical foundations of the predic(cid: 173) tion problem in this context. More precisely, it is demonstrated that this model is a universal approximator, with respect to learn(cid: 173) ing the unknown prediction function. This statement is strength(cid: 173) ened as upper bounds on the mean squared error are established. Based on these results it is possible to compare the MEM to other families of models (e. g. , neural networks and state dependent mod(cid: 173) els). It is shown that a degenerate version of the MEM is in fact equivalent to a neural network, and the number of experts in the architecture plays a similar role to the number of hidden units in the latter model.