Online non-convex optimization with imperfect feedback
- URL: http://arxiv.org/abs/2010.08496v1
- Date: Fri, 16 Oct 2020 16:53:13 GMT
- Title: Online non-convex optimization with imperfect feedback
- Authors: Am\'elie H\'eliou and Matthieu Martin and Panayotis Mertikopoulos and
Thibaud Rahier
- Abstract summary: We consider the problem of online learning with non- losses.
In terms of feedback, we assume that the learner observes - or otherwise constructs - an inexact model for the loss function at each stage.
We propose a mixed-strategy learning policy based on dual averaging.
- Score: 33.80530308979131
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of online learning with non-convex losses. In terms
of feedback, we assume that the learner observes - or otherwise constructs - an
inexact model for the loss function encountered at each stage, and we propose a
mixed-strategy learning policy based on dual averaging. In this general
context, we derive a series of tight regret minimization guarantees, both for
the learner's static (external) regret, as well as the regret incurred against
the best dynamic policy in hindsight. Subsequently, we apply this general
template to the case where the learner only has access to the actual loss
incurred at each stage of the process. This is achieved by means of a
kernel-based estimator which generates an inexact model for each round's loss
function using only the learner's realized losses as input.
Related papers
- Probably Approximately Precision and Recall Learning [62.912015491907994]
Precision and Recall are foundational metrics in machine learning.
One-sided feedback--where only positive examples are observed during training--is inherent in many practical problems.
We introduce a PAC learning framework where each hypothesis is represented by a graph, with edges indicating positive interactions.
arXiv Detail & Related papers (2024-11-20T04:21:07Z) - LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
An adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown to the learner.
We present a robust online rounds optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown.
arXiv Detail & Related papers (2024-08-12T17:08:31Z) - Adversarial Online Learning with Temporal Feedback Graphs [13.267203883254087]
We study a variant of prediction with expert advice where the learner's action at round $t$ is only allowed to depend on losses on a specific subset of the rounds.
We present a novel learning algorithm for this setting based on a strategy of partitioning the losses across sub-cliques of this graph.
arXiv Detail & Related papers (2024-06-30T03:14:17Z) - On the Dynamics Under the Unhinged Loss and Beyond [104.49565602940699]
We introduce the unhinged loss, a concise loss function, that offers more mathematical opportunities to analyze closed-form dynamics.
The unhinged loss allows for considering more practical techniques, such as time-vary learning rates and feature normalization.
arXiv Detail & Related papers (2023-12-13T02:11:07Z) - A Unified Generalization Analysis of Re-Weighting and Logit-Adjustment
for Imbalanced Learning [129.63326990812234]
We propose a technique named data-dependent contraction to capture how modified losses handle different classes.
On top of this technique, a fine-grained generalization bound is established for imbalanced learning, which helps reveal the mystery of re-weighting and logit-adjustment.
arXiv Detail & Related papers (2023-10-07T09:15:08Z) - Resilient Constrained Learning [94.27081585149836]
This paper presents a constrained learning approach that adapts the requirements while simultaneously solving the learning task.
We call this approach resilient constrained learning after the term used to describe ecological systems that adapt to disruptions by modifying their operation.
arXiv Detail & Related papers (2023-06-04T18:14:18Z) - Zeroth-order non-convex learning via hierarchical dual averaging [26.023679256204737]
We propose a hierarchical version of dual dynamic averaging for zeroth-order online non- norm optimization.
We derive tight bounds for both the learners static dynamic regret - i.e., the best policy in hindsight the play.
arXiv Detail & Related papers (2021-09-13T09:59:06Z) - A Mathematical Analysis of Learning Loss for Active Learning in
Regression [2.792030485253753]
This paper develops a foundation for Learning Loss which enables us to propose a novel modification we call LearningLoss++.
We show that gradients are crucial in interpreting how Learning Loss works, with rigorous analysis and comparison of the gradients between Learning Loss and LearningLoss++.
We also propose a convolutional architecture that combines features at different scales to predict the loss.
We show that LearningLoss++ outperforms in identifying scenarios where the model is likely to perform poorly, which on model refinement translates into reliable performance in the open world.
arXiv Detail & Related papers (2021-04-19T13:54:20Z) - Reducing Representation Drift in Online Continual Learning [87.71558506591937]
We study the online continual learning paradigm, where agents must learn from a changing distribution with constrained memory and compute.
In this work we instead focus on the change in representations of previously observed data due to the introduction of previously unobserved class samples in the incoming data stream.
arXiv Detail & Related papers (2021-04-11T15:19:30Z) - A Loss-Function for Causal Machine-Learning [0.0]
Causal machine-learning is about predicting the net-effect (true-lift) of treatments.
There is no similarly well-defined loss function due to the lack of point-wise true values in the data.
We propose a novel method to define a loss function in this context, which is equal to mean-square-error (MSE) in a standard regression problem.
arXiv Detail & Related papers (2020-01-02T21:22:18Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.