Philip M. Long

JMLR Journal 2024 Journal Article

Sharpness-Aware Minimization and the Edge of Stability

• Philip M. Long
• Peter L. Bartlett

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. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2024. ( edit, beta )

JMLR Journal 2023 Journal Article

Deep linear networks can benignly overfit when shallow ones do

• Niladri S. Chatterji
• Philip M. Long

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. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2023. ( edit, beta )

JMLR Journal 2023 Journal Article

The Dynamics of Sharpness-Aware Minimization: Bouncing Across Ravines and Drifting Towards Wide Minima

• Peter L. Bartlett
• Philip M. Long
• Olivier Bousquet

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. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

JMLR Journal 2022 Journal Article

Foolish Crowds Support Benign Overfitting

• Niladri S. Chatterji
• Philip M. Long

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. [abs] [ pdf ][ bib ] &copy JMLR 2022. ( edit, beta )

JMLR Journal 2022 Journal Article

The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks

• Niladri S. Chatterji
• Philip M. Long
• Peter L. Bartlett

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. [abs] [ pdf ][ bib ] &copy JMLR 2022. ( edit, beta )

JMLR Journal 2021 Journal Article

Failures of Model-dependent Generalization Bounds for Least-norm Interpolation

• Peter L. Bartlett
• Philip M. Long

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. [abs] [ pdf ][ bib ] &copy JMLR 2021. ( edit, beta )

JMLR Journal 2021 Journal Article

Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime

• Niladri S. Chatterji
• Philip M. Long

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. [abs] [ pdf ][ bib ] &copy JMLR 2021. ( edit, beta )

JMLR Journal 2021 Journal Article

When Does Gradient Descent with Logistic Loss Find Interpolating Two-Layer Networks?

• Niladri S. Chatterji
• Philip M. Long
• Peter L. Bartlett

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. [abs] [ pdf ][ bib ] &copy JMLR 2021. ( edit, beta )

ICLR Conference 2020 Conference Paper

Generalization bounds for deep convolutional neural networks

• Philip M. Long
• Hanie Sedghi

We prove bounds on the generalization error of convolutional networks. The bounds are in terms of the training loss, the number of parameters, the Lipschitz constant of the loss and the distance from the weights to the initial weights. They are independent of the number of pixels in the input, and the height and width of hidden feature maps. We present experiments using CIFAR-10 with varying hyperparameters of a deep convolutional network, comparing our bounds with practical generalization gaps.

JMLR Journal 2020 Journal Article

Learning Sums of Independent Random Variables with Sparse Collective Support

• Anindya De
• Philip M. Long
• Rocco A. Servedio

We study the learnability of sums of independent integer random variables given a bound on the size of the union of their supports. For $\mathcal{A} \subset \mathbb{Z}_{+}$, a {sum of independent random variables with collective support $\mathcal{A}$} (called an $\mathcal{A}$-sum in this paper) is a distribution $\mathbf{S} = \mathbf{X}_1 + \cdots + \mathbf{X}_N$ where the $\mathbf{X}_i$'s are mutually independent (but not necessarily identically distributed) integer random variables with $\cup_i \mathrm{supp}(\mathbf{X}_i) \subseteq \mathcal{A}.$ We give two main algorithmic results for learning such distributions. First, for the case $| \mathcal{A} | = 3$, we give an algorithm for learning an unknown $\mathcal{A}$-sum to accuracy $\epsilon$ using $\mathrm{poly}(1/\epsilon)$ samples and running in time $\mathrm{poly}(1/\epsilon)$, independent of $N$ and of the elements of $\mathcal{A}$. Second, for an arbitrary constant $k \geq 4$, if $\mathcal{A} = \{ a_1,...,a_k\}$ with $0 \leq a_1 0$. [abs] [ pdf ][ bib ] &copy JMLR 2020. ( edit, beta )

TCS Journal 2020 Journal Article

New bounds on the price of bandit feedback for mistake-bounded online multiclass learning

• Philip M. Long

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 opt std ( F ) and opt bandit ( F ) be the optimal bounds for learning F according to these two models. We show that an opt bandit ( F ) ≤ ( 1 + o ( 1 ) ) ( | Y | ln ⁡ | Y | ) opt std ( F ) bound is the best possible up to the leading constant, closing a Θ ( log ⁡ | Y | ) factor gap.

ICLR Conference 2020 Conference Paper

On the Global Convergence of Training Deep Linear ResNets

• Difan Zou
• Philip M. Long
• Quanquan Gu

We study the convergence of gradient descent (GD) and stochastic gradient descent (SGD) for training $L$-hidden-layer linear residual networks (ResNets). We prove that for training deep residual networks with certain linear transformations at input and output layers, which are fixed throughout training, both GD and SGD with zero initialization on all hidden weights can converge to the global minimum of the training loss. Moreover, when specializing to appropriate Gaussian random linear transformations, GD and SGD provably optimize wide enough deep linear ResNets. Compared with the global convergence result of GD for training standard deep linear networks \citep{du2019width}, our condition on the neural network width is sharper by a factor of $O(\kappa L)$, where $\kappa$ denotes the condition number of the covariance matrix of the training data. We further propose a modified identity input and output transformations, and show that a $(d+k)$-wide neural network is sufficient to guarantee the global convergence of GD/SGD, where $d,k$ are the input and output dimensions respectively.

ICML Conference 2018 Conference Paper

Gradient descent with identity initialization efficiently learns positive definite linear transformations

• Peter L. Bartlett
• David P. Helmbold
• Philip M. Long

We analyze algorithms for approximating a function $f(x) = \Phi x$ mapping $\Re^d$ to $\Re^d$ using deep linear neural networks, i. e. that learn a function $h$ parameterized by matrices $\Theta_1, .. ., \Theta_L$ and defined by $h(x) = \Theta_L \Theta_{L-1}. .. \Theta_1 x$. 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 $\Phi$, in the case where the initial hypothesis $\Theta_1 =. .. = \Theta_L = I$ has excess loss bounded by a small enough constant. On the other hand, we show that gradient descent fails to converge for $\Phi$ 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 $\Phi$ is symmetric positive definite, we show that an algorithm that initializes $\Theta_i = I$ learns an $\epsilon$-approximation of $f$ using a number of updates polynomial in $L$, the condition number of $\Phi$, and $\log(d/\epsilon)$. In contrast, we show that if the least squares matrix $\Phi$ 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 $\Phi$ satisfies $u^{\top} \Phi u > 0$ for all $u$, but may not be symmetric. This algorithm uses two regularizers: one that maintains the invariant $u^{\top} \Theta_L \Theta_{L-1}. .. \Theta_1 u > 0$ for all $u$, and another that "balances" $\Theta_1, .. ., \Theta_L$ so that they have the same singular values.

FOCS Conference 2018 Conference Paper

Learning Sums of Independent Random Variables with Sparse Collective Support

• Anindya De
• Philip M. Long
• Rocco A. Servedio

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 = X 1 +. .. + X N where the X i '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 = {a 1, .. ., a k } with 0 1 k, we give an algorithm that uses poly(1/ε)*log log a k samples (independent of N) and runs in time poly(1/ε, log a k ). We prove an essentially matching lower bound: if |A| = 4, then any algorithm must use Ω(log log a 4 ) 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.

JMLR Journal 2018 Journal Article

Surprising properties of dropout in deep networks

• David P. Helmbold
• Philip M. Long

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. [abs] [ pdf ][ bib ] &copy JMLR 2018. ( edit, beta )

JMLR Journal 2015 Journal Article

On the Inductive Bias of Dropout

• David P. Helmbold
• Philip M. Long

Dropout is a simple but effective technique for learning in neural networks and other settings. A sound theoretical understanding of dropout is needed to determine when dropout should be applied and how to use it most effectively. In this paper we continue the exploration of dropout as a regularizer pioneered by Wager et al. We focus on linear classification where a convex proxy to the misclassification loss (i.e. the logistic loss used in logistic regression) is minimized. We show: when the dropout-regularized criterion has a unique minimizer, when the dropout- regularization penalty goes to infinity with the weights, and when it remains bounded, that the dropout regularization can be non- monotonic as individual weights increase from 0, and that the dropout regularization penalty may not be convex. This last point is particularly surprising because the combination of dropout regularization with any convex loss proxy is always a convex function. In order to contrast dropout regularization with $L_2$ regularization, we formalize the notion of when different random sources of data are more compatible with different regularizers. We then exhibit distributions that are provably more compatible with dropout regularization than $L_2$ regularization, and vice versa. These sources provide additional insight into how the inductive biases of dropout and $L_2$ regularization differ. We provide some similar results for $L_1$ regularization. [abs] [ pdf ][ bib ] &copy JMLR 2015. ( edit, beta )

STOC Conference 2014 Conference Paper

The power of localization for efficiently learning linear separators with noise

• Pranjal Awasthi
• Maria-Florina Balcan
• Philip M. Long

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 R d under the uniform distribution with nearly information-theoretically optimal noise tolerance of η = Ω( ε ), improving on the Ω(&epsilon/d 1/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 R d 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.

JMLR Journal 2013 Journal Article

Algorithms and Hardness Results for Parallel Large Margin Learning

• Philip M. Long
• Rocco A. Servedio

We consider the problem of learning an unknown large-margin halfspace in the context of parallel computation, giving both positive and negative results. As our main positive result, we give a parallel algorithm for learning a large-margin halfspace, based on an algorithm of Nesterov's that performs gradient descent with a momentum term. We show that this algorithm can learn an unknown $\gamma$-margin halfspace over $n$ dimensions using $n \cdot \text{poly}(1/\gamma)$ processors and running in time $\tilde{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 an inverse quadratic running time dependence on the margin parameter $\gamma$. Our negative result deals with boosting, which is a standard approach to learning large-margin halfspaces. We prove 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. More precisely, we show that, if the algorithm is allowed to call the weak learner multiple times in parallel within a single boosting stage, this ability does not reduce the overall number of successive stages of boosting needed for learning by even a single stage. Our proof is information-theoretic and does not rely on unproven assumptions. [abs] [ pdf ][ bib ] &copy JMLR 2013. ( edit, beta )

ICML Conference 2013 Conference Paper

Consistency versus Realizable H-Consistency for Multiclass Classification

• Philip M. Long
• Rocco A. Servedio

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.

JMLR Journal 2012 Journal Article

On the Necessity of Irrelevant Variables

• David P. Helmbold
• Philip M. Long

This work explores the effects of relevant and irrelevant boolean variables on the accuracy of classifiers. The analysis uses the assumption that the variables are conditionally independent given the class, and focuses on a natural family of learning algorithms for such sources when the relevant variables have a small advantage over random guessing. The main result is that algorithms relying predominately on irrelevant variables have error probabilities that quickly go to 0 in situations where algorithms that limit the use of irrelevant variables have errors bounded below by a positive constant. We also show that accurate learning is possible even when there are so few examples that one cannot determine with high confidence whether or not any individual variable is relevant. [abs] [ pdf ][ bib ] &copy JMLR 2012. ( edit, beta )

ICML Conference 2011 Conference Paper

On the Necessity of Irrelevant Variables

• David P. Helmbold
• Philip M. Long

ICML Conference 2010 Conference Paper

Finding Planted Partitions in Nearly Linear Time using Arrested Spectral Clustering

• Nader H. Bshouty
• Philip M. Long

ICML Conference 2010 Conference Paper

Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate

• Philip M. Long
• Rocco A. Servedio

JMLR Journal 2009 Journal Article

Learning Halfspaces with Malicious Noise

• Adam R. Klivans
• Philip M. Long
• Rocco A. Servedio

We give new algorithms for learning halfspaces in the challenging malicious noise model, where an adversary may corrupt both the labels and the underlying distribution of examples. Our algorithms can tolerate malicious noise rates exponentially larger than previous work in terms of the dependence on the dimension n, and succeed for the fairly broad class of all isotropic log-concave distributions. We give poly( n, 1/ε)-time algorithms for solving the following problems to accuracy ε: Learning origin-centered halfspaces in R n with respect to the uniform distribution on the unit ball with malicious noise rate η = Ω(ε 2 / log( n /ε)). (The best previous result was Ω(ε / ( n log( n /ε)) 1/4 ).) Learning origin-centered halfspaces with respect to any isotropic log-concave distribution on R n with malicious noise rate η = Ω(ε 3 / log 2 ( n /ε)). This is the first efficient algorithm for learning under isotropic log-concave distributions in the presence of malicious noise. We also give a poly( n,1/ε)-time algorithm for learning origin-centered halfspaces under any isotropic log-concave distribution on R n in the presence of adversarial label noise at rate η = Ω(ε 3 / log(1/ε)). In the adversarial label noise setting (or agnostic model), labels can be noisy, but not example points themselves. Previous results could handle η = Ω(ε) but had running time exponential in an unspecified function of 1/ε. Our analysis crucially exploits both concentration and anti-concentration properties of isotropic log-concave distributions. Our algorithms combine an iterative outlier removal procedure using Principal Component Analysis together with "smooth" boosting. [abs] [ pdf ][ bib ] &copy JMLR 2009. ( edit, beta )

TCS Journal 2008 Journal Article

Preface

• Philip M. Long
• Frank Stephan

ICML Conference 2008 Conference Paper

Random classification noise defeats all convex potential boosters

• Philip M. Long
• Rocco A. Servedio

JMLR Journal 2007 Journal Article

Online Learning of Multiple Tasks with a Shared Loss

• Ofer Dekel
• Philip M. Long
• Yoram Singer

We study the problem of learning multiple tasks in parallel within the online learning framework. On each online round, the algorithm receives an instance for each of the parallel tasks and responds by predicting the label of each instance. We consider the case where the predictions made on each round all contribute toward a common goal. The relationship between the various tasks is defined by a global loss function, which evaluates the overall quality of the multiple predictions made on each round. Specifically, each individual prediction is associated with its own loss value, and then these multiple loss values are combined into a single number using the global loss function. We focus on the case where the global loss function belongs to the family of absolute norms, and present several online learning algorithms for the induced problem. We prove worst-case relative loss bounds for all of our algorithms, and demonstrate the effectiveness of our approach on a large-scale multiclass-multilabel text categorization problem. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

ICML Conference 2005 Conference Paper

Unsupervised evidence integration

• Philip M. Long
• Vinay Varadan
• Sarah Gilman
• Mark Treshock
• Rocco A. Servedio

I&C Journal 2004 Journal Article

Efficient algorithms for learning functions with bounded variation

• Philip M. Long

We show that the class F BV of [0, 1]-valued functions with total variation at most 1 can be agnostically learned with respect to the absolute loss in polynomial time from O 1 ϵ2 log 1 δ examples, matching a known lower bound to within a constant factor. We establish a bound of O(1/m) on the expected error of a polynomial-time algorithm for learning F BV in the prediction model, also matching a known lower bound to within a constant factor. Applying a known algorithm transformation to our prediction algorithm, we obtain a polynomial-time PAC learning algorithm for F BV with a sample complexity bound of O 1 ϵ log 1 δ; this also matches a known lower bound to within a constant factor.

AAAI Conference 2002 Conference Paper

Minimum Majority Classification and Boosting

• Philip M. Long

Motivated by a theoretical analysis of the generalization of boosting, we examine learning algorithms that work by trying to fit data using a simple majority vote over a small number of a collection of hypotheses. We provide experimental evidence that an algorithm based on this principle outputs hypotheses that often generalize nearly as well as those output by boosting, and sometimes better. We also provide experimental evidence for an additional reason that boosting algorithms generalize well, that they take advantage of cases in which there are many simple hypotheses with independent errors.

I&C Journal 2000 Journal Article

Apple tasting

• David P. Helmbold
• Nicholas Littlestone
• Philip M. Long

In the standard on-line model the learning algorithm tries to minimizethe total number of mistakes made in a series of trials. On each trial the learner sees an instance, makes a prediction of its classification, then finds out the correct classification. We define a natural variant of this model (“apple tasting”) where u • the classes are interpreted as the good and bad instances, • the prediction is interpreted as accepting or rejecting the instance, and • the learner gets feedback only when the instance is accepted. We use two transformations to relate the apple tasting model to an enhanced standard model where false acceptances are counted separately from false rejections. We apply our 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. We also present and analyze a simpler transformation useful when the instances are drawn at random rather than selected by an adversary.

TCS Journal 2000 Journal Article

Improved bounds about on-line learning of smooth-functions of a single variable

• Philip M. Long

We consider the complexity of learning classes of smooth functions formed by bounding different norms of a function's derivative. The learning model is the generalization of the mistake-bound model to continuous-valued functions. Suppose F q is the set of all absolutely continuous functions f from [0, 1] to R such that ||f′|| q ⩽1, and opt(F q, m) is the best possible bound on the worst-case sum of absolute prediction errors over sequences of m trials. We show that for all q⩾2, opt(Fq, m)= Θ( logm ), and that opt(F2, m)⩽( log 2m )/2+O(1), matching a known lower bound of ( log 2m )/2−O(1) to within an additive constant.

SODA Conference 2000 Conference Paper

Improved bounds on the sample complexity of learning

• Yi Li
• Philip M. Long
• Aravind Srinivasan

I&C Journal 2000 Journal Article

On-line learning with linear loss constraints

• David P. Helmbold
• Nicholas Littlestone
• Philip M. Long

We consider a generalization of the mistake-bound model (for learning {0, 1}-valued functions) in which the learner must satisfy a general constraint on the number M + of incorrect 1 predictions and the number M − of incorrect 0 predictions. We describe a general-purpose 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 M −.

ICML Conference 1999 Conference Paper

Associative Reinforcement Learning using Linear Probabilistic Concepts

• Naoki Abe
• Philip M. Long

STOC Conference 1997 Conference Paper

Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets

• Peter Auer
• Philip M. Long
• Aravind Srinivasan

I&C Journal 1997 Journal Article

On the Complexity of Learning from Drifting Distributions

• Rakesh D. Barve
• Philip M. Long

We consider two models of on-line learning of binary-valued functions from drifting distributions due to Bartlett. We show that if each example is drawn from a joint distribution which changes in total variation distance by at mostO(ε 3/(d log(1/ε))) between trials, then an algorithm can achieve a probability of a mistake at mostεworse than the best function in a class of VC-dimensiond. We prove a corresponding necessary condition ofO(ε 3/d). Finally, in the case that a fixed function is to be learned from noise-free examples, we show that if the distributions on the domain generating the examples change by at mostO(ε 2/(d log(1/ε))), then any consistent algorithm learns to within accuracyε.

ICML Conference 1995 Conference Paper

Learning to Make Rent-to-Buy Decisions with Systems Applications

• P. Krishnan
• Philip M. Long
• Jeffrey Scott Vitter

TCS Journal 1995 Journal Article

On-line learning of smooth functions of a single variable

• Don Kimber
• Philip M. Long

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. We prove upper bounds for these classes of smooth functions for other loss functions, and prove upper and lower bounds in terms of the number of trials.

STOC Conference 1994 Conference Paper

Simulating access to hidden information while learning

• Peter Auer
• Philip M. Long

FOCS Conference 1992 Conference Paper

Apple Tasting and Nearly One-Sided Learning

• David P. Helmbold
• Nick Littlestone
• Philip M. Long

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. >

STOC Conference 1991 Conference Paper

On-Line Learning of Linear Functions

• Nick Littlestone
• Philip M. Long
• Manfred K. Warmuth