Recent experiments have shown that, often, when training a neural network with gradient descent (GD) with a step size $\eta$, the operator norm of the Hessian of the loss grows until it approximately reaches $2/\eta$, after which it fluctuates around this value. The quantity $2/\eta$ has been called the “edge of stability” based on consideration of a local quadratic approximation of the loss. We perform a similar calculation to arrive at an “edge of stability” for Sharpness-Aware Minimization (SAM), a variant of GD which has been shown to improve its generalization. Unlike the case for GD, the resulting SAM-edge depends on the norm of the gradient. Using three deep learning training tasks, we see empirically that SAM operates on the edge of stability identified by this analysis.

We consider Sharpness-Aware Minimization (SAM), a gradient-based optimization method for deep networks that has exhibited performance improvements on image and language prediction problems. We show that when SAM is applied with a convex quadratic objective, for most random initializations it converges to a cycle that oscillates between either side of the minimum in the direction with the largest curvature, and we provide bounds on the rate of convergence. In the non-quadratic case, we show that such oscillations effectively perform gradient descent, with a smaller step-size, on the spectral norm of the Hessian. In such cases, SAM's update may be regarded as a third derivative---the derivative of the Hessian in the leading eigenvector direction---that encourages drift toward wider minima.

We bound the excess risk of interpolating deep linear networks trained using gradient flow. In a setting previously used to establish risk bounds for the minimum $\ell_2$-norm interpolant, we show that randomly initialized deep linear networks can closely approximate or even match known bounds for the minimum $\ell_2$-norm interpolant. Our analysis also reveals that interpolating deep linear models have exactly the same conditional variance as the minimum $\ell_2$-norm solution. Since the noise affects the excess risk only through the conditional variance, this implies that depth does not improve the algorithm's ability to "hide the noise". Our simulations verify that aspects of our bounds reflect typical behavior for simple data distributions. We also find that similar phenomena are seen in simulations with ReLU networks, although the situation there is more nuanced.

We prove a lower bound on the excess risk of sparse interpolating procedures for linear regression with Gaussian data in the overparameterized regime. We apply this result to obtain a lower bound for basis pursuit (the minimum $\ell_1$-norm interpolant) that implies that its excess risk can converge at an exponentially slower rate than OLS (the minimum $\ell_2$-norm interpolant), even when the ground truth is sparse. Our analysis exposes the benefit of an effect analogous to the “wisdom of the crowd”, except here the harm arising from fitting the noise is ameliorated by spreading it among many directions---the variance reduction arises from a foolish crowd.

The recent success of neural network models has shone light on a rather surprising statistical phenomenon: statistical models that perfectly fit noisy data can generalize well to unseen test data. Understanding this phenomenon of benign overfitting has attracted intense theoretical and empirical study. In this paper, we consider interpolating two-layer linear neural networks trained with gradient flow on the squared loss and derive bounds on the excess risk when the covariates satisfy sub-Gaussianity and anti-concentration properties, and the noise is independent and sub-Gaussian. By leveraging recent results that characterize the implicit bias of this estimator, our bounds emphasize the role of both the quality of the initialization as well as the properties of the data covariance matrix in achieving low excess risk.

van Rooyen, Menon, and Williamson (2015) introduced a notion of convex loss functions being robust to random classification noise and established that the "unhinged" loss function is robust in this sense. In this letter, we study the accuracy of binary classifiers obtained by minimizing the unhinged loss and observe that even for simple linearly separable data distributions, minimizing the unhinged loss may only yield a binary classifier with accuracy no better than random guessing.

We establish conditions under which gradient descent applied to fixed-width deep networks drives the logistic loss to zero, and prove bounds on the rate of convergence. Our analysis applies for smoothed approximations to the ReLU, such as Swish and the Huberized ReLU, proposed in previous applied work. We provide two sufficient conditions for convergence. The first is simply a bound on the loss at initialization. The second is a data separation condition used in prior analyses.

We consider bounds on the generalization performance of the least-norm linear regressor, in the over-parameterized regime where it can interpolate the data. We describe a sense in which any generalization bound of a type that is commonly proved in statistical learning theory must sometimes be very loose when applied to analyze the least-norm interpolant. In particular, for a variety of natural joint distributions on training examples, any valid generalization bound that depends only on the output of the learning algorithm, the number of training examples, and the confidence parameter, and that satisfies a mild condition (substantially weaker than monotonicity in sample size), must sometimes be very loose - it can be bounded below by a constant when the true excess risk goes to zero.

We prove bounds on the population risk of the maximum margin algorithm for two-class linear classification. For linearly separable training data, the maximum margin algorithm has been shown in previous work to be equivalent to a limit of training with logistic loss using gradient descent, as the training error is driven to zero. We analyze this algorithm applied to random data including misclassification noise. Our assumptions on the clean data include the case in which the class-conditional distributions are standard normal distributions. The misclassification noise may be chosen by an adversary, subject to a limit on the fraction of corrupted labels. Our bounds show that, with sufficient over-parameterization, the maximum margin algorithm trained on noisy data can achieve nearly optimal population risk.

We study the training of finite-width two-layer smoothed ReLU networks for binary classification using the logistic loss. We show that gradient descent drives the training loss to zero if the initial loss is small enough. When the data satisfies certain cluster and separation conditions and the network is wide enough, we show that one step of gradient descent reduces the loss sufficiently that the first result applies.

The minimum majority problem is as follows: given a matrix $A \in \{-1, 1\}^{m \times n}$, minimize $\sum_{i=1}^n x_i$ subject to $A {x} \geq {1}$ and ${x} \in ({\mathbb Z}^+)^n$. An approximation algorithm that finds a solution with value $O({opt}^2 \log m)$ in ${poly}(m,n,{opt})$ time is known, which can be obtained by rounding a linear programming relaxation. We establish integrality gaps that limit the prospects for improving upon this guarantee through improved rounding and/or the application of Lovász--Schrijver (LS) or Sherali--Adams (SA) tightening of the relaxation. These gaps show that applying LS and SA relaxations cannot improve upon the $O({opt}^2 \log m)$ guarantee by more than a constant factor in polynomial time.

For proper distribution-free learning of linear classifiers in $d$ dimensions from $m$ examples, we prove a lower bound on the optimal expected error of $\frac{d - o(1)}{m}$, improving on the best previous lower bound of $\frac{d/\sqrt{e} - o(1)}{m}$, and nearly matching a $\frac{d+1}{m+1}$ upper bound achieved by the linear support vector machine.

We study density estimation for classes of shift-invariant distributions over R^d. A multidimensional distribution is "shift-invariant" if, roughly speaking, it is close in total variation distance to a small shift of it in any direction. Shift-invariance relaxes smoothness assumptions commonly used in non-parametric density estimation to allow jump discontinuities. The different classes of distributions that we consider correspond to different rates of tail decay. For each such class we give an efficient algorithm that learns any distribution in the class from independent samples with respect to total variation distance. As a special case of our general result, we show that d-dimensional shift-invariant distributions which satisfy an exponential tail bound can be learned to total variation distance error epsilon using O~_d(1/ epsilon^{d+2}) examples and O~_d(1/ epsilon^{2d+2}) time. This implies that, for constant d, multivariate log-concave distributions can be learned in O~_d(1/epsilon^{2d+2}) time using O~_d(1/epsilon^{d+2}) samples, answering a question of [Diakonikolas et al., 2016]. All of our results extend to a model of noise-tolerant density estimation using Huber's contamination model, in which the target distribution to be learned is a (1-epsilon,epsilon) mixture of some unknown distribution in the class with some other arbitrary and unknown distribution, and the learning algorithm must output a hypothesis distribution with total variation distance error O(epsilon) from the target distribution. We show that our general results are close to best possible by proving a simple Omega (1/epsilon^d) information-theoretic lower bound on sample complexity even for learning bounded distributions that are shift-invariant.

We analyze algorithms for approximating a function [Formula: see text] mapping [Formula: see text] to [Formula: see text] using deep linear neural networks, that is, that learn a function [Formula: see text] parameterized by matrices [Formula: see text] and defined by [Formula: see text]. We focus on algorithms that learn through gradient descent on the population quadratic loss in the case that the distribution over the inputs is isotropic. We provide polynomial bounds on the number of iterations for gradient descent to approximate the least-squares matrix [Formula: see text], in the case where the initial hypothesis [Formula: see text] has excess loss bounded by a small enough constant. We also show that gradient descent fails to converge for [Formula: see text] whose distance from the identity is a larger constant, and we show that some forms of regularization toward the identity in each layer do not help. If [Formula: see text] is symmetric positive definite, we show that an algorithm that initializes [Formula: see text] learns an [Formula: see text]-approximation of [Formula: see text] using a number of updates polynomial in [Formula: see text], the condition number of [Formula: see text], and [Formula: see text]. In contrast, we show that if the least-squares matrix [Formula: see text] is symmetric and has a negative eigenvalue, then all members of a class of algorithms that perform gradient descent with identity initialization, and optionally regularize toward the identity in each layer, fail to converge. We analyze an algorithm for the case that [Formula: see text] satisfies [Formula: see text] for all [Formula: see text] but may not be symmetric. This algorithm uses two regularizers: one that maintains the invariant [Formula: see text] for all [Formula: see text] and the other that “balances” [Formula: see text] so that they have the same singular values.

We analyze the joint probability distribution on the lengths of the vectors of hidden variables in different layers of a fully connected deep network, when the weights and biases are chosen randomly according to gaussian distributions. We show that if the activation function [Formula: see text] satisfies a minimal set of assumptions, satisfied by all activation functions that we know that are used in practice, then, as the width of the network gets large, the “length process” converges in probability to a length map that is determined as a simple function of the variances of the random weights and biases and the activation function [Formula: see text]. We also show that this convergence may fail for [Formula: see text] that violate our assumptions. We show how to use this analysis to choose the variance of weight initialization, depending on the activation function, so that hidden variables maintain a consistent scale throughout the network.

We study the learnability of sums of independent integer random variables given a bound on the size of the union of their supports. For a A ⊂Z+ubset A of non-negative integers, a sum of independent random variables with collective support A (called an "A-sum" in this paper) is a distribution S = X1+ ... + XNwhere the Xi's are mutually independent (but not necessarily identically distributed) integer random variables all of whose supports are contained in A. We give two main algorithmic results for learning such distributions: 1) For the case |A|=3, we give an algorithm for learning A-sums to accuracy ε that uses poly(1/ε) samples and runs in time poly(1/ε), independent of N and of the elements of A. 2) For an arbitrary constant k>=4, if A = {a1,...,ak} with 01k, we give an algorithm that uses poly(1/ε)*log log aksamples (independent of N) and runs in time poly(1/ε, log ak). We prove an essentially matching lower bound: if |A| = 4, then any algorithm must use Ω(log log a4) samples even for learning to constant accuracy. We also give similar-in-spirit (but quantitatively very different) algorithmic results, and essentially matching lower bounds, for the case in which A is not known to the learner. Our learning algorithms employ new limit theorems which may be of independent interest. Our algorithms and lower bounds together settle the question of how the sample complexity of learning sums of independent integer random variables scales with the elements in the union of their supports, both in the known-support and unknown-support settings. Finally, all our algorithms easily extend to the "semi-agnostic" learning model, in which training data is generated from a distribution that is only c*ε-close to some A-sum for a constant c>0.

This paper is about two generalizations of the mistake bound model to online multiclass classification. In the standard model, the learner receives the correct classification at the end of each round, and in the bandit model, the learner only finds out whether its prediction was correct or not. For a set $F$ of multiclass classifiers, let $\mathrm{opt}_{\mathrm{std}}(F)$ and $\mathrm{opt}_{\mathrm{bandit}}(F)$ be the optimal bounds for learning $F$ according to these two models. We show that an $$ \mathrm{opt}_{\mathrm{bandit}}(F) \leq (1 + o(1)) (|Y| \ln |Y|) \mathrm{opt}_{\mathrm{std}}(F) $$ bound is the best possible up to the leading constant, closing a $\Theta(\log |Y|)$ factor gap.

We analyze dropout in deep networks with rectified linear units and the quadratic loss. Our results expose surprising differences between the behavior of dropout and more traditional regularizers like weight decay. For example, on some simple data sets dropout training produces negative weights even though the output is the sum of the inputs. This provides a counterpoint to the suggestion that dropout discourages co-adaptation of weights. We also show that the dropout penalty can grow exponentially in the depth of the network while the weight-decay penalty remains essentially linear, and that dropout is insensitive to various re-scalings of the input features, outputs, and network weights. This last insensitivity implies that there are no isolated local minima of the dropout training criterion. Our work uncovers new properties of dropout, extends our understanding of why dropout succeeds, and lays the foundation for further progress.

We introduce a new approach for designing computationally efficient learning algorithms that are tolerant to noise, and we demonstrate its effectiveness by designing algorithms with improved noise tolerance guarantees for learning linear separators. We consider both the malicious noise model of Valiant [1985] and Kearns and Li [1988] and the adversarial label noise model of Kearns, Schapire, and Sellie [1994]. For malicious noise, where the adversary can corrupt both the label and the features, we provide a polynomial-time algorithm for learning linear separators in ℜ d under isotropic log-concave distributions that can tolerate a nearly information-theoretically optimal noise rate of η = Ω(ϵ), improving on the Ω (ϵ 3 /log 2 ( d/ϵ )) noise-tolerance of Klivans et al. [2009a]. In the case that the distribution is uniform over the unit ball, this improves on the Ω (ϵ/ d 1/4 ) noise-tolerance of Kalai et al. [2005] and the Ω (ϵ 2 /log(d/ϵ)) of Klivans et al. [2009a]. For the adversarial label noise model, where the distribution over the feature vectors is unchanged and the overall probability of a noisy label is constrained to be at most η, we also give a polynomial-time algorithm for learning linear separators in ℜ d under isotropic log-concave distributions that can handle a noise rate of η = Ω(ϵ). In the case of uniform distribution, this improves over the results of Kalai et al. [2005], which either required runtime super-exponential in 1/ϵ (ours is polynomial in 1/ϵ) or tolerated less noise. 1 Our algorithms are also efficient in the active learning setting, where learning algorithms only receive the classifications of examples when they ask for them. We show that, in this model, our algorithms achieve a label complexity whose dependence on the error parameter ϵ is polylogarithmic (and thus exponentially better than that of any passive algorithm). This provides the first polynomial-time active learning algorithm for learning linear separators in the presence of malicious noise or adversarial label noise. Our algorithms and analysis combine several ingredients including aggressive localization, minimization of a progressively rescaled hinge loss, and a novel localized and soft outlier removal procedure. We use localization techniques (previously used for obtaining better sample complexity results) to obtain better noise-tolerant polynomial-time algorithms.

We introduce a new approach for designing computationally efficient and noise tolerant algorithms for learning linear separators. We consider the malicious noise model of Valiant [41, 32] and the adversarial label noise model of Kearns, Schapire, and Sellie [34]. For malicious noise, where the adversary can corrupt an η of fraction both the label part and the feature part, we provide a polynomial-time algorithm for learning linear separators in Rd under the uniform distribution with nearly information-theoretically optimal noise tolerance of η = Ω(ε), improving on the Ω(&epsilon/d1/4) noise-tolerance of [31] and the Ω(ε2/log(d/ε) of [35]. For the adversarial label noise model, where the distribution over the feature vectors is unchanged, and the overall probability of a noisy label is constrained to be at most η, we give a polynomial-time algorithm for learning linear separators in Rd under the uniform distribution that can also handle a noise rate of η = Ω(ε). This improves over the results of [31] which either required runtime super-exponential in 1/ε (ours is polynomial in 1/ε) or tolerated less noise.

This paper presents a systematic evaluation of recent methods in the fine-grained categorization domain, which have shown significant promise. More specifically, we investigate an automatic segmentation algorithm, a region pooling algorithm which is akin to pose-normalized pooling [31] [28], and a multi-class optimization method. We considered the largest and most popular datasets for fine-grained categorization available in the field: the Caltech-UCSD 200 Birds dataset [27], the Oxford 102 Flowers dataset [19], the Stanford 120 Dogs dataset [16], and the Oxford 37 Cats and Dogs dataset [21]. We view this work from a practitioner's perspective, answering the question: what are the methods that can create the best possible fine-grained recognition system which can be applied in practice? Our experiments provide insights of the relative merit of these methods. More importantly, after combining the methods, we achieve the top results in the field, outperforming the state-of-the-art methods by 4.8% and 10.3% for birds and dogs datasets, respectively. Additionally, our method achieves a mAP of 37.92 on the of 2012 Imagenet Fine-Grained Categorization Challenge [1], which outperforms the winner of this challenge by 5.7 points.

For $S \subseteq \{0,1\}^n$, a Boolean function $f: S \to \{-1,1\}$ is a halfspace over $S$ if there exist $w \in \mathbb{R}^n$ and $\theta \in \mathbb{R}$ such that $f(x)=\mathrm{sign}(w \cdot x - \theta)$ for all $x \in S$. We give bounds on the size of integer weights $w_1,\dots,w_n \in \mathbb{Z}$ that are required to represent halfspaces over Hamming balls $S = \{x \in \{0,1\}^n : x_1 + \cdots + x_n \leq k\}.$ Such weight bounds for halfspaces over Hamming balls have immediate consequences for the performance of learning algorithms in the common scenario of learning from very high-dimensional categorical examples which are such that only a small number of features are active in each example. We give upper and lower bounds on weight both for exact representation (when $\mathrm{sign}(w \cdot x {-\theta})$ must equal $f(x)$ for every $x \in S$) and for $\varepsilon$-approximate representation (when $\mathrm{sign}(w \cdot x {- \theta})$ may disagree with $f(x)$ for up to an $\varepsilon$ fraction of points $x \in S$). Our results show that extremal bounds for exact representation are qualitatively rather similar whether the domain is all of $\{0,1\}^n$ or the Hamming ball $\{0,1\}^n_{\leq k}$, but extremal bounds for approximate representation are qualitatively very different between these two domains.

We prove that active learning provides an exponential improvement over PAC (passive) learning of homogeneous linear separators under nearly log-concave distributions. Building on this, we provide a computationally efficient PAC algorithm with optimal (up to a constant factor) sample complexity for such problems. This resolves an open question of (Long, 1995, 2003; Bshouty et al., 2009) concerning the sample complexity of efficient PAC algorithms under the uniform distribution in the unit ball. Moreover, it provides the first bound for a polynomial-time PAC algorithm that is tight for an interesting infinite class of hypothesis functions under a general class of data-distributions, providing significant progress towards a long standing open question of (Ehrenfeucht et al., 1989; Blumer et al., 1989). We also provide new bounds for active and passive learning in the case that the data might not be linearly separable, both in the agnostic case and and under the Tsybakov low-noise condition. To derive our results, we provide new structural results for (nearly) log-concave distributions, which might be of independent interest as well.

A consistent loss function for multiclass classification is one such that for any source of labeled examples, any tuple of scoring functions that minimizes the expected loss will have classification accuracy close to that of the Bayes optimal classifier. While consistency has been proposed as a desirable property for multiclass loss functions, we give experimental and theoretical results exhibiting a sequence of linearly separable data sources with the following property: a multiclass classification algorithm which optimizes a loss function due to Crammer and Singer (which is known not to be consistent) produces classifiers whose expected error goes to 0, while the expected error of an algorithm which optimizes a generalization of the loss function used by LogitBoost (a loss function which is known to be consistent) is bounded below by a positive constant. We identify a property of a loss function, realizable consistency with respect to a restricted class of scoring functions, that accounts for this difference. As our main technical results we show that the Crammer–Singer loss function is realizable consistent for the class of linear scoring functions, while the generalization of LogitBoost is not. Our result for LogitBoost is a special case of a more general theorem that applies to several other loss functions that have been proposed for multiclass classification.

For S ⊆ {0,1}n, a Boolean function f: S -> {-1,1} is a halfspace over S if there exist w ∈ Rn and θ ∈ R such that f(x)=sign(w ⋅ x - θ) for all x ∈ S. We give bounds on the size of integer weights w1,...,wn ∈ Z that are required to represent halfspaces over Hamming balls centered at 0n, i.e. halfspaces over S ={0,1}n≤ k = {x ∈ {0,1}n : x1 + ⋅⋅⋅ + xn ≤ k}. Such weight bounds for halfspaces over Hamming balls have immediate consequences for the performance of learning algorithms in the increasingly common scenario of learning from very high-dimensional categorical examples which are such that only a small number of features are active in each example.

We describe a simple algorithm that runs in time poly(n,1/gamma,1/eps) and learns an unknown n-dimensional gamma-margin halfspace to accuracy 1-eps in the presence of malicious noise, when the noise rate is allowed to be as high as Theta(eps gamma sqrt(log(1/gamma))). Previous efficient algorithms could only learn to accuracy eps in the presence of malicious noise of rate at most Theta(eps gamma). Our algorithm does not work by optimizing a convex loss function. We show that no algorithm for learning gamma-margin halfspaces that minimizes a convex proxy for misclassification error can tolerate malicious noise at a rate greater than Theta(eps gamma); this may partially explain why previous algorithms could not achieve the higher noise tolerance of our new algorithm.

We study the fundamental problem of learning an unknown large-margin halfspace in the context of parallel computation. Our main positive result is a parallel algorithm for learning a large-margin halfspace that is based on interior point methods from convex optimization and fast parallel algorithms for matrix computations. We show that this algorithm learns an unknown gamma-margin halfspace over n dimensions using poly(n,1/gamma) processors and runs in time ~O(1/gamma) + O(log n). In contrast, naive parallel algorithms that learn a gamma-margin halfspace in time that depends polylogarithmically on n have Omega(1/gamma^2) runtime dependence on gamma. Our main negative result deals with boosting, which is a standard approach to learning large-margin halfspaces. We give an information-theoretic proof that in the original PAC framework, in which a weak learning algorithm is provided as an oracle that is called by the booster, boosting cannot be parallelized: the ability to call the weak learner multiple times in parallel within a single boosting stage does not reduce the overall number of successive stages of boosting that are required.

A broad class of boosting algorithms can be interpreted as performing coordinate-wise gradient descent to minimize some potential function of the margins of a data set. This class includes AdaBoost, LogitBoost, and other widely used and well-studied boosters. In this paper we show that for a broad class of convex potential functions, any such boosting algorithm is highly susceptible to random classification noise. We do this by showing that for any such booster and any nonzero random classification noise rate η, there is a simple data set of examples which is efficiently learnable by such a booster if there is no noise, but which cannot be learned to accuracy better than 1/2 if there is random classification noise at rate η. This negative result is in contrast with known branching program based boosters which do not fall into the convex potential function framework and which can provably learn to high accuracy in the presence of random classification noise.

In recent work Long and Servedio LS05short presented a ``martingale boosting'' algorithm that works by constructing a branching program over weak classifiers and has a simple analysis based on elementary properties of random walks. LS05short showed that this martingale booster can tolerate random classification noise when it is run with a noise-tolerant weak learner; however, a drawback of the algorithm is that it is not adaptive, i.e. it cannot effectively take advantage of variation in the quality of the weak classifiers it receives. In this paper we present a variant of the original martingale boosting algorithm and prove that it is adaptive. This adaptiveness is achieved by modifying the original algorithm so that the random walks that arise in its analysis have different step size depending on the quality of the weak learner at each stage. The new algorithm inherits the desirable properties of the original LS05short algorithm, such as random classification noise tolerance, and has several other advantages besides adaptiveness: it requires polynomially fewer calls to the weak learner than the original algorithm, and it can be used with confidence-rated weak hypotheses that output real values rather than Boolean predictions.

This paper studies boosting algorithms that make a single pass over a set of base classi(cid:2)ers. We (cid:2)rst analyze a one-pass algorithm in the setting of boosting with diverse base classi(cid:2)ers. Our guarantee is the same as the best proved for any boosting algo- rithm, but our one-pass algorithm is much faster than previous approaches. We next exhibit a random source of examples for which a (cid:147)picky(cid:148) variant of Ad- aBoost that skips poor base classi(cid:2)ers can outperform the standard AdaBoost al- gorithm, which uses every base classi(cid:2)er, by an exponential factor. Experiments with Reuters and synthetic data show that one-pass boosting can sub- stantially improve on the accuracy of Naive Bayes, and that picky boosting can sometimes lead to a further improvement in accuracy.

We show that any weak ranker that can achieve an area under the ROC curve slightly better than 1/2 (which can be achieved by random guessing) can be effi- ciently boosted to achieve an area under the ROC curve arbitrarily close to 1. We further show that this boosting can be performed even in the presence of indepen- dent misclassification noise, given access to a noise-tolerant weak ranker.

We consider the well-studied problem of learning decision lists using few examples when many irrelevant features are present. We show that smooth boosting algorithms such as MadaBoost can efficiently learn decision lists of length k over n boolean variables using poly(k , log n) many examples provided that the marginal distribution over the relevant variables is "not too concentrated" in an L 2 -norm sense. Using a recent result of Hastad, we extend the analysis to obtain a similar (though quantitatively weaker) result for learning arbitrary linear threshold functions with k nonzero coefficients. Experimental results indicate that the use of a smooth boosting algorithm, which plays a crucial role in our analysis, has an impact on the actual performance of the algorithm.

Many biological propositions can be supported by a variety of different types of evidence. It is often useful to collect together large numbers of such propositions, together with the evidence supporting them, into databases to be used in other analyses. Methods that automatically make preliminary choices about which propositions to include can be helpful, if they are accurate enough. This can involve weighing evidence of varying strength.We describe a method for learning a scoring function to weigh evidence of different types. The algorithm evaluates each source of evidence by the extent to which other sources tend to support it. The details are guided by a probabilistic formulation of the problem, building on previous theoretical work. We evaluate our method by applying it to predict protein-protein interactions in yeast, and using synthetic data.

We establish a mistake bound for an ensemble method for classification based on maximizing the entropy of voting weights subject to margin constraints. The bound is the same as a general bound proved for the Weighted Majority Algorithm, and similar to bounds for other variants of Winnow. We prove a more refined bound that leads to a nearly opti- mal algorithm for learning disjunctions, again, based on the maximum entropy principle. We describe a simplification of the on-line maximum entropy method in which, after each iteration, the margin constraints are replaced with a single linear inequality. The simplified algorithm, which takes a similar form to Winnow, achieves the same mistake bounds.

Haussler, Littlestone and Warmuth (1994) described a general-purpose algorithm for learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a mistake in terms of the number of examples seen and the Vapnik-Chervonenkis (VC) dimension of the concept class being learned. We show that their bound is within a factor of 1+o(1) of the best possible such bound for any algorithm.

We show that a vccf&rJ bound on the rate of drift of the distribution generating the examples is sufficient for agnostic learning to relative accuracy E, where c > 0 is a constant; this matches a known necessary conditionto within a constant factor.We establish a A7 sufficient condition for the realizable case, also matching a known necessary condition to within a constant factor.We provide a relatively sim 0 (5 (VCdim(3) + log k 7 le proof of a bound of ) on the sample complexity of agnostic learning in a fixed environment.

Proceedings of the Annual ACM Conference on Computational Learning Theory

We present and compare methods for choosing motion vectors for block-based motion-compensated video coding. The primary focus is on videophone and videoconferencing applications, where low bit rates are necessary, where motion is usually limited, and where the amount of computation is also limited. In a typical block-based motion-compensated video coding system, motion vectors are transmitted along with a lossy encoding of the residuals. As the bit rate decreases, the proportion required to transmit the motion vectors increases. We provide experimental evidence that choosing motion vectors explicitly to minimize rate (including motion vector coding), subject to implicit constraints on distortion, yields better rate-distortion tradeoffs than minimizing some measure of prediction error. Minimizing a combination of rate and distortion yields further improvements. Although these explicit-minimization schemes are computationally intensive, they provide invaluable insight which we use to develop practical algorithms. We show that minimizing a simple heuristic function of the prediction error and the motion vector code length results in rate-distortion performance comparable to explicit-minimization schemes while being computationally feasible. Experimental results are provided for coders that operate within the H.261 standard.

We propose a model for situations where an algorithm needs to make a sequence of choices to minimize an evaluation function, but where the evaluation function must be learned on-line as it is being used.We describe algorithms for learning linear evaluation functions in this model, and prove performance bounds for them that hold in the worst case.Each bound is on the expectation, with respect to an algorithm's randomization, of the sum of differences between the costs of the choices the algorithm makes and the best choices available.The bounds are in terms of the extent to which a linear model is appropriate, the number of altematives to choose from, and the number of choices that need to be made.Ideas from the above analysis yield new absolute loss bounds for learning linear functions in the standard on-line prediction model.These bounds are on difference between the sum of absolute prediction errors made by the learning algorithm, and the best sum of absolute prediction errors that can be obtained by fixing a linear function in the given class.Known results imply that our bounds on this difference cannot be improved by more than a constant factor.

We consider re-representing the alphabet so that a representation of a character reflects its properties as a predictor of future text. This enables us to use an estimator from a restricted class to map contexts to predictions of upcoming characters. We describe an algorithm that uses this idea in conjunction with neural networks. The performance of this implementation is compared to other compression methods, such as UNIX compress, gzip, PPMC, and an alternative neural network approach.

The PAC learning of rectangles has been studied because they have been found experimentally to yield excellent hypotheses for severaf applied learning problems.Also, pseudorandom sets for rectangles have been actively studied recently because (i) they are a subpmblem common to the derandomization of depth-2 (DIW) circuits and derandotnizing Randomized Logspace, and (ii) they approximate the distribution of n independent multivalued random variables.We present improved upper bounds for a class of such problems of "approximating" highdlmensional rectangles that arise in PAC learning and pseudorandomness.Key words and phrases.Rectangles, machine learning, PAC learning,

Information and Computation

Machine Learning

We make a case that, even with severe efficiency constraints, taking the number of bits to code each motion vector into account when estimating motion for video compression results in significantly better performance at low bit rates, using simulation studies on established benchmark image sequences. In particular, we examine an algorithm that differs from a "vanilla" implementation of the H.261 standard by choosing motion vectors to minimize a cost function of prediction error and the number of bits to code a particular motion vector, where the coefficients of the cost function are adapted on-line using the Widrow-Hoff (1960) rule. We show that this algorithm performs comparably to a variety of more idealized, computationally intensive methods we examined in earlier papers and substantially better than the original "vanila" method, which ignores the number of bits to code the motion vector when choosing it.

Studies the performance of gradient descent (GD) when applied to the problem of online linear prediction in arbitrary inner product spaces. We prove worst-case bounds on the sum of the squared prediction errors under various assumptions concerning the amount of a priori information about the sequence to predict. The algorithms we use are variants and extensions of online GD. Whereas our algorithms always predict using linear functions as hypotheses, none of our results requires the data to be linearly related. In fact, the bounds proved on the total prediction loss are typically expressed as a function of the total loss of the best fixed linear predictor with bounded norm. All the upper bounds are tight to within constants. Matching lower bounds are provided in some cases. Finally, we apply our results to the problem of online prediction for classes of smooth functions.

We present a new general-purpose algorithm for learning classes of [0, I]-valued functions in a generalization of the prediction model, and prove a general upper bound on the expected absolute error of this algorithm

Motivated by the desire to find text compressors that compress better than existing dictionary methods, but run faster than PPM implementations, we describe methods for text compression using multiple dictionaries, one for each context of preceding characters, where the contexts have varying lengths. The context to be used is determined using an escape mechanism similar to that of PPM methods. We describe modifications of three popular dictionary coders along these lines and experiments evaluating their efficacy using the text files in the Calgary corpus. Our results suggest that modifying LZ77 along these lines yields an improvement in compression of about 4%, that modifying LZFG yields a compression improvement of about 8%, and that modifying LZW in this manner yields an average improvement on the order of 12%.

We prove an Omega(d/epsilon+1/epsilonlog1/delta) lower bound on the PAC (probably approximately correct) learning sample complexity of learning half-spaces against the uniform distribution on the unit ball in R(d).

We consider the problem of learning real-valued functions from random examples when the function values are corrupted with noise. With mild conditions on independent observation noise, we provide characterizations of the learnability of a real-valued function class in terms of a generalization of the Vapnik-Chervonenkis dimension, the fat shattering function, introduced by Kearns and Schapire. We show that, given some restrictions on the noise, a function class is learnable in our model if and only if its fat-shattering function is finite. With different (also quite mild) restrictions, satisfied for example by gaussian noise, we show that a function class is learnable from polynomially many examples if and only if its fat-shattering function grows polynomially. We prove analogous results in an agnostic setting, where there is no assumption of an underlying function class.

Compares methods for choosing motion vectors for motion-compensated video compression. The primary focus is on videophone and videoconferencing applications, where very low bit rates are necessary, where the motion is usually limited, and where the frames must be coded in the order they are generated. the authors provide evidence, using established benchmark videos of this type, that choosing motion vectors to minimize codelength subject to (implicit) constraints on quality yields substantially better rate-distortion tradeoffs than minimizing notions of prediction error. They illustrate this point using an algorithm within the p/spl times/64 standard. They show that using quadtrees to code the motion vectors in conjunction with explicit codelength minimization yields further improvement. They describe a dynamic-programming algorithm for choosing a quadtree to minimize the codelength.>

Abstraet. The majority of results in computational learning theory are concerned with concept learning, i.e. with the special case of function learning for classes of functions with range {0, 1}. Much less is known about the theory of learning functions with a larger fange such as Nor IR. In particular relatively few results exist about he general structure of common models for function learning, and there are only very few nontrivial function classes for which positive learning results have been exhibited in any of these models. We introduce in this paper the notion of a binaly branching adversary tree for function learning, which allows us to give a somewhat surprising equivalent characterization f the optimal learning cost for learning a class of real-valued functions (in terms of a max-min definition which does not invoive any "learning " model). Another general structural result of this paper elates the cost for learning a union of function classes to the learning costs for the individual function classes. Furthermore, we exhibit an efficient leaming algorithm for learning convex piecewise linear functions from Rd into IR. Previously, the class of linear functions from 1R d into R was the only class of functions with multi-dimensional domain that was known to be learnable within the rigorous framework of a formal model for on-line leaming. Finally we give a sufficient condition for an arbitrary class 5 ~ of functions from IR into R that allows us to learn the class of all functions that can be written as the pointwise maximum of k functions from 5 r. This allows us to exhibit a number of further nontrivial classes of functions from ~ into R for which there exist eflicient]earning algorithms.

Article Free Access Share on Worst-case quadratic loss bounds for a generalization of the Widrow-Hoff rule Authors: Nicolò Cesa Bianchi View Profile , Philip M. Long View Profile , Manfred K. Warmuth View Profile Authors Info & Claims COLT '93: Proceedings of the sixth annual conference on Computational learning theoryAugust 1993 Pages 429–438https://doi.org/10.1145/168304.168390Published:01 August 1993Publication History 8citation245DownloadsMetricsTotal Citations8Total Downloads245Last 12 Months27Last 6 weeks12 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider a generalization of the mistakebound model (for learning {O, 1}-valued functions) in which the learner must satisfy a general constraint on the number M+ of incorrect 1 predictions and the number JW_ of incorrect O predictions.We describe a generalpurpose optimal algorithm for our formulation of this problem.We describe several applications of our general results, involving situations in which the learner wishes to satisfy linear inequalities in M+ and Tf_. 1.The learner receives z~E X from the environment, 2. The learner outputs a prediction & c {O, 1}, 3. The learner discovers the value ~(zt).Note that the learner only discovers the value of ~(zt ) after making the prediction in trial t.If At # ~(zt ), we say that the learner makes a mistake on trial t,and q This author gratefully acknowledges the support of a Lice Meitner Postdoctoral FeUowship from the Fends zur

We investigate the PAC learnability of classes of {0,…,n}-valued functions. For n = 1, it is known that the finiteness of the Vapnik-Chervonenkis dimension is necessary and sufficient for learning. In this paper we present a general scheme for extending the VC-dimension to the case n > 1. Our scheme defines a wide variety of notions of dimension in which several variants of the VC-dimension, previously introduced in the context of learning, appear as special cases. Our main result is a simple condition characterizing the set of notions of dimension whose finiteness is necessary and sufficient for learning. This provides a variety of new tools for determining the learnability of a class of multi-valued functions. Our characterization is also shown to hold in the “robust” variant of PAC model.

We study the on-line learning of classes of functions of a single real variable formed through bounds on various norms of functions' derivatives. We determine the best bounds obtainable on the worst-case sum of squared errors (also “absolute” errors) for several such classes.

In the standard on-line model the learning algorithm tries to minimize the total number of mistakes made in a series of trials. On each trial the learner sees an instance, either accepts or rejects that instance, and then is told the appropriate response. The authors define a natural variant of this model ('apple tasting') where the learner gets feedback only when the instance is accepted. They use two transformations to relate the apple tasting model to an enhanced standard model where false acceptances are counted separately from false rejections. They present a strategy for trading between false acceptances and false rejections in the standard model. From one perspective this strategy is exactly optimal, including constants. They apply the results to obtain a good general purpose apple tasting algorithm as well as nearly optimal apple tasting algorithms for a variety of standard classes, such as conjunctions and disjunctions of n boolean variables. They also present and analyze a simpler transformation useful when the instances are drawn at random rather than selected by an adversary.>

We present an algorithm for the on-line learning of linear functions which is optimal to within a constant factor with respect to bounds on the sum of squared errors for a worst case sequence of trials.The bounds are logarithmic in the number of variables, Furthermore, the algorithm is shown to be optimally robust with respect to noise in the data (again to within a constant factor).We also discuss an application of our methods to the iterative solution of sparse systems of linear equations.