The Geometry of Mixability

• URL: http://arxiv.org/abs/2302.11905v1
• Date: Thu, 23 Feb 2023 10:25:38 GMT
• Title: The Geometry of Mixability
• Abstract summary: We provide a simple geometric characterization of mixability for the binary and multi-class cases. Our approach provides a way to treat some concepts concerning loss functions in a ''coordinate-free'' manner.
• Score: 8.873449722727026
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mixable loss functions are of fundamental importance in the context of prediction with expert advice in the online setting since they characterize fast learning rates. By re-interpreting properness from the point of view of differential geometry, we provide a simple geometric characterization of mixability for the binary and multi-class cases: a proper loss function $\ell$ is $\eta$-mixable if and only if the superpredition set $\textrm{spr}(\eta \ell)$ of the scaled loss function $\eta \ell$ slides freely inside the superprediction set $\textrm{spr}(\ell_{\log})$ of the log loss $\ell_{\log}$, under fairly general assumptions on the differentiability of $\ell$. Our approach provides a way to treat some concepts concerning loss functions (like properness) in a ''coordinate-free'' manner and reconciles previous results obtained for mixable loss functions for the binary and the multi-class cases.

Related papers

• Loss Functions and Operators Generated by f-Divergences [21.58093510003414]
  We propose to construct new convex loss functions based on $f$-divergences. By analogy with the logistic loss, the loss function generated by an $f$-divergence is associated with an operator, that we dub $f$-softargmax. One of the goals of this paper is to determine the effectiveness of loss functions beyond the classical cross-entropy in a language model setting.
  arXiv  Detail & Related papers  (2025-01-30T18:06:18Z)
• Omnipredictors for Regression and the Approximate Rank of Convex Functions [7.549720420141907]
  An textitomnipredictor for a class $mathcal L$ of loss functions and a class $mathcal C$ of hypotheses is a predictor whose predictions incur less expected loss than the best hypothesis in $mathcal C$ for every loss in $mathcal L$.
  arXiv  Detail & Related papers  (2024-01-26T04:29:53Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions [39.864174754882754]
  Existing online learning algorithms for adversarial Markov Decision Processes achieve $O(sqrtT)$ regret after $T$ rounds of interactions. This is because it has been shown that adversarial transition functions make no-regret learning impossible. We propose an algorithm that enjoys $widetildeO(sqrtT + CtextsfP)$ regret where $CtextsfP$ measures how adversarial the transition functions are.
  arXiv  Detail & Related papers  (2023-05-27T06:10:17Z)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  We study oblivious sketching for $k$-sparse linear regression under various loss functions such as an $ell_p$ norm, or from a broad class of hinge-like loss functions. We show that for sparse $ell$vareps regression, there is an oblivious distribution over sketches with $Theta(klog(d/k)/varepsilon2)$ rows, which is tight up to a constant factor. We also show that sketching $O(mu2 klog(mu n d/varepsilon)/var
  arXiv  Detail & Related papers  (2023-04-05T07:24:19Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  We study the problem of estimating the value of a known smooth function $f$ at an unknown point $boldsymbolmu in mathbbRn$, where each component $mu_i$ can be sampled via a noisy oracle. We design an instance-adaptive algorithm that learns to sample according to the importance of each coordinate, and with probability at least $1-delta$ returns an $epsilon$ accurate estimate of $f(boldsymbolmu)$.
  arXiv  Detail & Related papers  (2022-03-18T18:50:52Z)
• Revisiting L1 Loss in Super-Resolution: A Probabilistic View and Beyond [28.90772192259691]
  Super-resolution as an ill-posed problem has many high-resolution candidates for a low-resolution input. We present a new objective function that aims at minimizing the expectation of the reconstruction error over all plausible solutions.
  arXiv  Detail & Related papers  (2022-01-25T04:04:44Z)
• Omnipredictors [19.735769148626588]
  Loss minimization is a dominant paradigm in machine learning. We introduce the notion of an ($mathcalL,mathcalC$)-omnipredictor, which could be used to optimize any loss in a family. We show that such "loss-oblivious'' learning is feasible through a connection to multicalibration.
  arXiv  Detail & Related papers  (2021-09-11T23:28:49Z)
• Coresets for Classification -- Simplified and Strengthened [19.54307474041768]
  We give relative error coresets for training linear classifiers with a broad class of loss functions. Our construction achieves $tilde O(d cdot mu_y(X)2/epsilon2)$ points, where $mu_y(X)$ is a natural complexity measure of the data matrix $X in mathbbRn times d$ and label vector $y in -1,1n$.
  arXiv  Detail & Related papers  (2021-06-08T11:24:18Z)
• Provable Robustness of Adversarial Training for Learning Halfspaces with Noise [95.84614821570283]
  We analyze the properties of adversarial learning adversarially robust halfspaces in the presence of label noise. To the best of our knowledge, this is the first work to show that adversarial training prov yields classifiers in noise.
  arXiv  Detail & Related papers  (2021-04-19T16:35:38Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• Sample Complexity of Adversarially Robust Linear Classification on Separated Data [41.30425613353595]
  We consider the sample complexity of learning with adversarial robustness. We show that for very well-separated data, convergence rates of $O(frac1n)$ are achievable.
  arXiv  Detail & Related papers  (2020-12-19T22:04:59Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  We study learning in contextual bandits with the help of loss predictors. We show that the optimal regret is $mathcalO(minsqrtT, sqrtmathcalETfrac13)$ when $mathcalE$ is known.
  arXiv  Detail & Related papers  (2020-03-04T07:36:38Z)
• On the Modularity of Hypernetworks [103.1147622394852]
  We show that for a structured target function, the overall number of trainable parameters in a hypernetwork is smaller by orders of magnitude than the number of trainable parameters of a standard neural network and an embedding method.
  arXiv  Detail & Related papers  (2020-02-23T22:51:52Z)
• Supervised Learning: No Loss No Cry [51.07683542418145]
  Supervised learning requires the specification of a loss function to minimise. This paper revisits the sc SLIsotron algorithm of Kakade et al. (2011) through a novel lens. We show how it provides a principled procedure for learning the loss.
  arXiv  Detail & Related papers  (2020-02-10T05:30:52Z)

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.