Minimizing the Maximal Loss: How and Why?

Abstract

A commonly used learning rule is to approximately minimize the \emph{average} loss over the training set. Other learning algorithms, such as AdaBoost and hard-SVM, aim at minimizing the \emph{maximal} loss over the training set. The average loss is more popular, particularly in deep learning, due to three main reasons. First, it can be conveniently minimized using online algorithms, that process few examples at each iteration. Second, it is often argued that there is no sense to minimize the loss on the training set too much, as it will not be reflected in the generalization loss. Last, the maximal loss is not robust to outliers. In this paper we describe and analyze an algorithm that can convert any online algorithm to a minimizer of the maximal loss. We prove that in some situations better accuracy on the training set is crucial to obtain good performance on unseen examples. Last, we propose robust versions of the approach that can handle outliers.

ICML 2016

References in corpus (1)

• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling

Cited by in corpus (22)

• Biased Importance Sampling for Deep Neural Network Training
• Robust Optimization for Non-Convex Objectives
• Large-Scale Methods for Distributionally Robust Optimization
• Task-Robust Model-Agnostic Meta-Learning
• Learning Anytime Predictions in Neural Networks via Adaptive Loss Balancing
• Adaptive Sampling for Stochastic Risk-Averse Learning
• Learning by Minimizing the Sum of Ranked Range
• Closing the gap towards end-to-end autonomous vehicle system
• Robust Attacks against Multiple Classifiers
• AdaSample: Adaptive Sampling of Hard Positives for Descriptor Learning
• Spectral risk-based learning using unbounded losses
• Adaptive Task Sampling for Meta-Learning
• A Randomized Block-Coordinate Primal-Dual Method for Large-scale Stochastic Saddle Point Problems
• A Simple and Effective Framework for Pairwise Deep Metric Learning
• Doubly-stochastic mining for heterogeneous retrieval
• IPBoost -- Non-Convex Boosting via Integer Programming
• Minimizing Close-k Aggregate Loss Improves Classification
• Efficient Online-Bandit Strategies for Minimax Learning Problems
• Coordinate Methods for Matrix Games
• Mixed Strategies for Robust Optimization of Unknown Objectives
• Sum of Ranked Range Loss for Supervised Learning
• Stochastic Bias-Reduced Gradient Methods