Aggregating Algorithm and Axiomatic Loss Aggregation
Authors: Armando J Cabrera Pacheco
Rabanus Derr
Robert Williamson
Venue: Accepted by TMLR ()

Abstract: Supervised learning has gone beyond the empirical risk minimization framework. Central to most of these developments is the introduction of more general aggregation functions for losses incurred by the learner. In this paper, we turn towards online learning under expert advice. Via easily justified assumptions we characterize a set of reasonable loss aggregation functions as quasi-sums. Based upon this insight, we suggest how to tailor Vovk's Aggregating Algorithm to these more general aggregation functions. The "change of variables" we propose, let us highlight that "weighting profiles" determine the contribution of each expert to the next prediction according to their loss and the multiplicative structure of the weight updates in the Aggregating Algorithm translates into the additive structure of the loss aggregation in the regret bound. In addition, we suggest that the mixability of the loss function, which is functionally necessary for the Aggregating Algorithm, is intrinsically relative to the log loss, because the standard aggregation of losses in online learning is the sum. Finally, we conceptually and empirically argue that our generalized loss aggregation functions express the attitude of the learner towards losses.

Published in Transactions on Machine Learning Research (09/2025)
Aggregating Algorithm and Axiomatic Loss Aggregation
Armando J. Cabrera Pacheco'
a.abbrema@unn--uueeinn....dd
University of Tübingen and Tübingen Al Center Tübingen, 72070 Germany
Rabanus Derr"
University of Tübingen and Tübingen AI Center Tübingen, 72070 Germany
Robert C. Williamson
bob. lob.ullllammoonnuuddddtubbengede
University of Tübingen and Tübingen AI Center Tübingen, 72070 Germany
Reviewed on OpenReview: https: // openreview. net/ forum? id- 4bUttttuDD
Abstract
Supervised learning has gone beyond the empirical risk minimization framework. Central to most of these developments is the introduction of more general aggregation functions for losses incurred by the learner. In this paper, we turn towards online learning under expert advice. Via easily justified assumptions we characterize a set reasonable loss aggregation functions as quasi-sums. Based upon this insight, we suggest how to tailor Vovk's Aggregating Algorithm these more general aggregation functions. The "change of variables" we propose, let us highlight that "weighting profiles" determine the contribution of each expert to the next prediction according to their loss and the multiplicative structure of the weight updates in the Aggregating Algorithm translates into the additive structure of the loss aggregation in the regret bound. In addition, we suggest that the mixability of the loss function, which is functionally necessary for the Aggregating Algorithm, is intrinsically relative to the log loss, because the standard aggregation of losses in online learning is the sum. Finally, we conceptually and empirically argue that our generalized loss aggregation functions express the attitude of the learner towards losses.
1 Introduction
Whether it is framed as collaborative learning, distribution shift or data corruption, machine learning scholar- ship encountered the necessity to rethink the gold standard of learning theory: expected risk minimization Central to this paradigm the minimization of the average loss over a set of instances incurred by the learner. In the named, more recent learning scenarios the average replaced by other aggregation func- tionals which take into account. the different data sources (Haghtalab al. 2022, Eq. (1)), the distribution shift (Rahimian and Mehrotra 2019 Eq. (RO)) structured noise (lacovissi al. 2023 See (Fröhlich) and Williamson| 2024) for a nice stratification of reasonable aggregations and an axiomatic approach to loss axiomatic approach to generalized loss aggregations remained
aggregation in offline learning. However, within the borders of offline learning. An analogous development in online, adversarial learning does, to the best of our knowledge, not exist. In this work, we focus on learning under expert advice, where learner, informed by expert predictions, crafts a prediction which idcally performs as good as the best expert in the
"Equal contribution.
This list far from being exhaustive, egg, fair machine learning Williamson and Menon 2019

---

Published in Transactions on Machine Learning Research (09/2025)
group of experts. The performance is measured by the regret which is the sum of losses between learners and experts. The sum as aggregation of the instance-wise losses is deliberate choice which makes every incurred loss equally important.
There have been efforts made to go beyond expert learners on sum-aggregation. For instance, discounted aggregation of losses (Cesa-Bianchi and Lugosi 2006 p. 32) down-weights the history of incurred losses of learners and experts (Chernov and Zhdannov] 2010). Or, (strongly) adaptive regret (Hazan and Seshadhri,
2007 Daniely et al.] 2015) computes the maximal regret a fixed-length subintervals of instances (Zhang et al. 2020). All of these regret types share that they change the aggregation function of the losses such that certain instance-wise losses are emphasized! X Hence, not every prediction made is equally "important" to good performance, as its relative contribution to the regret differs. The generalization of the aggregation functions is motivated by decaying interest in past performance (discounted regret) or interest in good per- formance in changing environments ((strongly) adaptive regret) (cf.. distribution shift in supervised learning theory).
In contrast, our considered aggregations are mainly motivated by judging the importance of large or small losses. For instance, this might be relevant in scenarios like weather- peather-predictin in which catastrophic mis- predictions are extremely undesired, as weather warning systems might to be triggered, but slight mis- predictions are not considered to be harmful.
The aggregation function for the losses is part of the optimization objective. Hence, the design of the objective requires an informed choice. Motivated by the context which demand for general aggregations beyond the sum named before, we offer an axiomatic access to the choice of loss aggregations. The axioms construc starting point for informed and consequenco-aware objective design.
First, we put forward an axiomatic approach to reasonable loss aggregations in online learning, providing a generalized definition of regret. More concretely, under easily justified assumptions the aggregation forms a quasi-sum generated by an appropriate function u: [0, oc) - [0, 0o), given by
Contributions:
(Z1 2,) =
= -1
Σ u(cx)) u
Based upon this insight, we suggest how to tailor the Aggregating Algorithm to these more general aggre- gation functions. The Aggregating Algorithm, first suggested by Vovk (1990), solves the learning under expert advice problem. It enjoys nice theoretical guarantees, e.g., time-independent bound regret and the recovery of Bayes' updating under appropriate choice of loss function, while keeping simplicity. The "change of variables" we propose in this work, leads us to several structural insights on the Aggregating Algorithm: (a) We identify a "weighting profile" which determines the contribution of each expert to the next prediction. (b) We arguc that the multiplicative structure of the weight updates in the Aggregating Algorithum translates into the additive structure of the loss aggregation in the regret bound. (c) We show that the mixability of the loss function, which is functionally necessary for the Aggregating Algorithm, is intrinsically relative to the log loss, because the standard aggregation of losses in online learning is the sum. Finally, argue that generalized aggregations express the attitude of the learner towards losses incurred by providing predictions. In particular, we can tune the generator u of the quasi-sum to express the aversily towards extreme losses (convex u) or the risk-seeking behavior of a learner (concave u). We provide exper- imental evidence corroborating this statement, which closes the loop by motivating the use of generalized aggregations in the first place.
2 Vovk's Aggregating Algorithm
For an intuitive and illustrated introduction to Vovk's Aggregating Algorithm see Appendix A Here, we describe it in a rigorous way following (Vokk 1990). We also use this part to set up notation and remark its main properties. prediction game (2, O, X, n) consists of the following objects:
Note that dynamic regret Zinkevich 2003 does not fit into this picture, as dynamic regret changes the comparison baseline, but not the aggregation functional.
2

---

Published in Transactions on Machine Learning Research (09/2025)
Sample space Q. This is regarded as the set of outcomes from nature. In general, we do not impose any structure on it.
Decision space r. This is thought as the allowed predictions. is a topological space endowed with the o-algebra generated by the open sets.
Parameter space O We index the experts (or decision stralegies) by 0 E O. We define (0,F, (4) as a measure space with y being a base measure on the o-algebra F on O. For the sake simplicity we do not write out the base mcasure μ in the rest of the paper, c.g., we write the inteegaa for measurable E F, (E) Sg
Loss function A: 12 r + [0, oo|. This gives us a way to measure the quality of the predictions.
Learning rate 17 0. A positive real number, typically as large as possible.
Example 2.1. A widely used loss function in the prediction game is the log-loss Amn Q + (0, In particular, when elements r are of the form y: 12 + + [0. 1], we define it \m)(w,)) In(r(w)).
The prediction game works as follows. At each time (T) = (1, CN,,
1. The experts make their predictions. That is, we have measurable map & Q - r. Ei(O) is interpreted by the prediction made by the expert 0.
2. The learner (who observes the predictions made by the experts) makes prediction Yt E P.
Nature chooses the outcome w/ E Ω.
The goal of the learner is to ensure that its cumalative loss is as good as the best expert's cumulative loss. In other words, we want to bound the regret,
T A(we, 7c)
T
(0) = (learner) (T) =
Σ A(wi, (O)),, vo e.
Vovk's Aggregating Algorithm (Vokk 1990 2001 (see Algorithm D gives a bound which is independent of the number of played rounds T,
Lr(learner) (r((0) < In E 7
(1)
when the number of experts is finite (n = |0| < xo) and when the game is mirable, i.e., we assume the existence of substitution function 2 for given X and such that A(w, E(v) S ((w), for all w E Ω and all pseutd-predictions v of the form (2) below 3 As one can easily see, mixability is required for the third step of the Algorithm Since the first two steps are independent of how the substitution concretely looks like, they are sometimes summarized as the Aggregating Pseudo-Algorithm (APA). The separation as well A fundamental property of the AA that, under some conditions, the updating scheme (Step (1) in AA (Algorithm 1 is reduced to Bayesian updating (see Appendix A.1
simplifies the analysis of the algorithm.
3 Generalizing the loss aggregation in learning under expert advice
The primary goal of the AA, as well other algorithms solving the learning under expert advice problem, is to bound the summed loss of the learner by the summed loss of each of the experts plus error term. We now turn towards approach to loss aggregation from first principles. Instead of presuming the slandard summation we provide a. list of axioms for loss aggregation functionals which we readily justify (see for example (Grabisch et al.] 2009)). Clearly, the choice of axioms is, and should not be, universal. We consider our suggested list as a starting point for discussions which can be used for designers of machine
For several games, the log-loss (Fxample 2.1 can be shown mixable for 7)
3

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm 1: Aggrogating Algorithm (AA)
Data: Mixable prediction game (2, D, O, X, n) and prior distribution Po-
Result: Predictions (70)200
for every do
(1) Update experts' weights = - -10)==00100(0)---111001
(2) Provide peuudo-predition,
<w(w) = In- 1 (1( Pi with P0-1(0)= Je P (0) d0
Pt-
(2)
(3) Substitute the ceuudo-prediction by an allowed prodiction = E(vr such that
X(w, M(bb)) I (bww), for all w E Ω2
end
learning systems to justify the desired objective in a certain context. In particular, the axioms structure the existing options for aggregations. Given an axiomatic characterization of aggregations certain properties of aggregations can be discussed, accepted as being important or neglected as being irrelevant.
Our specific choice of axioms emphasize the special role of quasi-sums as they allow for the switch from additive to multiplicative structure necessary for the AA. The set of axioms potentially not minimal, in the sense that axiom can be derived from the others. Furthermore, this list of axioms is definitely not exhaustive. However, it is sufficient to disentangle parts and propertics of the AA stated in the contributions in Section [
Definition 3.1 (Aggregation Functions). A function A: UnEN10, oo)" - 00) is called an aggregation
function. We wrile (..,,....., for the aggregation of n instances. Let Iı,..., Tn, [0, 20). We define the following properties of A.
(A1) Continuity. We say A is continuous is for every xi, E [m],
lim A A Fi....,....................... 2n) ,. ....,,, vn).
(A2) Monotonicity. We say that A is strictly increasing if for v, < x/ i [n], we have A ...) < (x 24.........
(A3) Associativity. We say that A is associative if sor all x E 10, and [m] we have
(1 = x, A, (1 Fi In) (2 ..... 2z), An An-i( ...................... x.)))
(A4) Loss compatibility. We say that A loss compatible if (O,))., =0
seem, dependent context, relevant to impose on aggregation A of losses since they can be interpreted as follows. If A is continuous, an infinitesimally small change in loss will result in an infinitesimal change in the aggregate of the losses. If it is strictly increasing, more loss on any instance give more aggregated loss. If it. is associative, it is irrelevant how the losses are grouped together for aggregation. Associativity is arguably the most contested axiom, which is not fulfilled by discounted aggregation or adaptive aggregation (cf. Section D. Furthermore, associativity does most of the heavy-lifting in the characterization result below. However, note that even though this type of associativity immediately implies that the aggregation function is completely determined by the binary aggregation (Grabisch et al. 2009 p. 33), it does not directly imply commutativity Loss compatibility means that 0 losses aggregate to 0. It turns out we can fully characterize aggregation functions satisfying the properties above.
Properties A1 A4
'oor instance, consider the aggregation which gives back the last value, terms the intrinsic ordering the input, of elements.
4

---

Published in Transactions on Machine Learning Research (09/2025)
Lemma 3.2 (axiomatic Characterization of Loss- Aggregations). Let A Unexl0, - 10, 00) be an ag- gregation funclion. Suppose that A salisfies [A1)
Then, there exists continnous, strielly increasing function u: (0) - [0, oo), with u(0) = O, such that
[A4)
Σ u(ai)) m
Inn ) u
(3)
We call such aggregations quasi-sums generated by u, and we denote them by Q". (Proof F.1 Example 3.3 (p-Norms). Let u(x) = x for O. Then (TI In. = (E xx") 1/D
If furthermore A is positively homogeneous, i.e., scaling the losses scales the aggregation of losses AA. XI,) A (fI.....,,, for all À > 0, then u(x) = for some E (0, oo) in 3 (Proof
Lemma 3.4 (Quasi-Sum to Quasi-Product). Let Q" be quasi-sum. Then, there erists continuous, striclly decreasing function f: (o) - (0, with f(0) = 1, such that
= 9 (f( x f(xn)), where g: [0, > 10, 00) is the inverse of f (Proof F.
(4)
Example 3.5. Let u(x)= I., then f(x) em and the corresponding aggregation of the form 44 is the usual sum:
A An( 2.) = 9(f(es))...(x..) = [e,,
Remark 3.6. In the remainder of this work we will sometimes write a quosi-sum Q" as an aggregation function A of the form (4) when convenient. This will be explicitly stated clear from contert.
Equipped with this characterization of reasonable aggregation functions of losses, natural to ask how can solve the extended learning under expert advice problem: In which way do have to modify existing online learning algorithms in order to provide regret guarantecs such that the aggregated loss of the learner is bound above in terms of the aggregated loss of any expert and some constant error term?
3.1 Relation to existing literature
The axiomatization of aggregation functionals has long history (Grabisch et al., 2009 The set of idempo- tent aggregation functionals is of particular relevance to our work. Idempotent aggregations map an n-tuple of constant c's to Averages and generalizations thereof are often idempotent. Hence, offline learning setups usually fall back to idempotent loss aggregations. Online learning most often focuses on sums, a non-idempotent aggregation functional, to offer more fine-grained statements on the regret guarantees.
The set of quasi-arithmetic means forms the set of idempotent analogues to the set of quasi-sums character- ized above (see Grabisch et al.) 2009 Section 6.5.1) for details). Kolmogorov and Castelnuovo (1930) and independently provided an axiomatic characterization of this set which strongly resembles our Lemma 3.2 In (Li et al. 2023 the authors use a subset of those quasi-arithmetic mcans generated by family of exponential functions, the entropic risk measures, to extend the standard empirical risk minimization framework.
Nagumo 1930)
Note that coherent risk measures (Delbaen 2002), another set of generalized expectations proven useful generalize empirical risk minimization (Fröhlich and Williamson, 2024). are idempotent, and allow for an axiomatic description. However, an axiomatic description of the non-idempotent analogues of coherent risk measures is still an open question. The existence of such a description would be helpful for the use of such aggregations in online learning.
The axiomatic characterizations of aggregations for loss functions should not be conflated with axiomatic characterizations of decision behavior. Certainly, there are relations between the axiomatic characterization
For the sake readability we neglect the multiplication sign further expressions.
5

---

Published in Transactions on Machine Learning Research (09/2025)
of expected utility behavior based on the seminal work by Von Neumann and Morgenstern (9553) and the axiomatic characterization of quasi-arithmetic means by Kolmogorov and Castelmuvo (1930) and Nagumo [1930) mentioned before (Muliere and Parmigiani 1993). However, the goals of the axiomatic statement and hence the axioms are quite different. Again differently, an axiomatic approach to aggregations experts, not the losses, put forward in (Neyman and Roughgarden 2023 The authors use quasi-means to pool forccaster a low-regret fashion.
Finally, in Section 1 we already hinted towards other generalizations of aggregations in online learning. The mentioned discounted loss aggregation fulfill all axioms listed in Definition 3.1 including positive homogene- ity, except for associativity. The aggregation implicitly defined in (strong) adaptive, however, are only loss compatible, positive homogeneous and continuous.
4 A change of variables for the AA
It turns out that the answer to the question how to learn under expert advice such that the learner can provide regret guarantees under generalized loss aggregations is relatively straightforward. Via a "change of variables"-trick we obtain regret bounds for generalized aggregations relying on the standard Aggregating Algorithm. Despite its simplicity, we take this observation as a starting point to re-investigate the structure and requirements of the Aggregating Algorithm.
Corollary 4.1 (Change of variables for the AA). g= (2,T,,))) be mizable prediction game with [0] = n. Purthermore, we assume = u o for some loss function X and continuous, striclly increasing function u: oo) - [0, oo), with u(0) 0. The AA applied on G achieves the following regret bound:
(In(n) )):
Q (leanner) = (A(ar, E(wr))).. ((rr))))))))) Q (2)(0),
(5)
1
for any 0 E e.
Proof. Under the assumptions on G the AA achieves the following regret. bound (Vovk 1990
T
T u (A(we, (x())))
+ In (n)
" (A(ur. I(be))
which is equivalent to
T Σ a (M(ar, E(b))) < w- (u(s
E (((Ner.s(00)))) + u (u-- (In (12) (In(1) (1-((1,)))
and, because u is strictly increasing,
--1 u (N(w,, X((e)) s--1 u u- Σ Ee(Mi (A(un, (M(rn)((0))) a- In (n)
(w-1
which is (5)
Remark 4.2. It is worth to point out that often is interested in composing loss functions from the "inside", i.e., reparametrizations [Willamssnn et al.) 2016). Here the trunsformation is extrinsic, we push the loss curve via obtaining "distorted" version of the original loss function X.
The lemma shows that it is a matter of perspective to consider the loss u with standard sum aggregation or the loss l with Q"-aggregation. Obtained in this way, the regret bound seems artificial and the arithmetic juggling unmotivated. Therefore, we shift our focus to understanding what is happening in the background, that is, why can a loss distortion be translated into a change of aggregation. In order do so we dctour through the development of an Aggregated Algorithm adapted to Quasi- which is a reparametrization of the standard iggregating Algorithm. We learn that:

---

Published in Transactions on Machine Learning Research (09/2025)
(a) The Aggregating Algorithm involves weighting function, by default fixed to be the negative expo- nential e e- which explains the down- the or up-weighting of experts based on their incurred loss. (Section 4.1
(b) The multiplicative structure of the weight updates directly translates into the additive structure of the loss aggregation. (Section 4.2)
(c) The fundamentality of the log loss in the definition of mixability required for the Aggregating Algorithm is an artifact of the standard use of summation for loss aggregation. (Section 4.3
Let := (2, 7,,,, 7) be a prediction game. In the following, we step-by-step go through the Aggrogating Al Algorithm under the premise that the loss function À is decomposable, i..,, X = o X, with À being a loss function and u: [0, oo) - [0, oo) being a continuous, strictly increasing function with u(0) = 0.
4.1 The Weight Updates
Step (1) in Algorithm 1 is the updating of the experts' weights. For the moment, we set the learning rate
17 == 1. Under the assumption of decomposability of X, i.., x = A, the update can be written as,
P.(0) = e P.- (0)
(A(w,,
for ((x =--((a) In particular, the function f allows for the interpretation as being the profile to judge the experts. It determines how much the expert 0 contributes to the next pseudo-prediction (Step 2) depending on the incurred loss in the current time step. For this reason, we call f weighting profile. Weighting profiles fulfill three simple requirements directly derived from the properties of u (cf. Lemma
F.2
Definition 4.3 (Weighting Profile). We say that a continuous J: [0, oo) - (0, 1] is weighting profile if (a) f(0) = (b) f is strictly decreasing, and (c) lim f(x) = 0.
2400
However, the properties of f can be justified independently of the properties of u. The normalization ʃ(0)= = means that weights should be positive and bounded from above by 1. The expert incurring 0 loss should get assigned full weight, while f being strictly decreasing implics that the higher the loss the less weight should be put on the expert. The limiting behavior of f says that an expert which incurs extremely large losses should be punished by getting down-weighted to O. Note that most of our following statements are framed for choice of weighting profile f instead for the tantamount choice of Hence, the change of aggregation Q" amounts to the change of weighting profile.
To illustrate Table 1 provides a short list of potential aggrogation functions, their corresponding function a (see Section 5.1 and weighting profile. Note that we use the term focal aggregation in the table to emphasize that the composition of the corresponding u with the log-loss recovers the often used focal loss (with 7 = 2) (Lin et al. 2017].
For fixed loss function we can analyze and compare weighting profiles for different aggregation functions. For instance (see Table D,, observe that for n--m aggregations switching the value of p from less than 1 to strictly bigger than drastically changes the shape of the weighting profile. Let us shortly compare the Lz-norm and sum. For the sake of simplicity, we focus on the arbitrary learning rate n = 0.5. The weighting profile corresponding to the Lg- punishes higher losses stronger than smaller losses compared to the sum. This, however, comes with the cost that for small losses the L2 weighting profile does not finely distinguish between good and even better experts. Both of them get nearly updated with the same weight, in contrast to the sum.
Crucially, comparisons of weighting profiles require to fix a loss a priori. The domain and distribution of the loss values themselves strongly interact with the choice of aggregation. For instance, the Brier score only provides values between 0 and 1. Thus, the weighting profile beyond 1 on the r-axis is irrelevant for the comparison. Hence, conclusive interpretations are only possible for fixed losses and different aggregations. Note that mixability might not be maintained for arbitrary combinations of losses and weighting profiles (Section B). For this reason, we go beyond this qualitative interpretation of the effect. of aggregations and
7

---

Published in Transactions on Machine Learning Research (09/2025)
Table 1: Aggregations, their corresponding function and weighting profiles for different learning rates (lightscagroen: 0.001, limegreen: f 0.5, mediumscagroen:
1, scagreen:
2, darkgreen: ") = 10,
darkslategray: ff 100).
Aggregation
u(z) =
Weighting Profile
Ta.s-norm (Vri V12 +..)²
V
0.5
3
1.0
Sum I1 + x2 +
0.0
3
L--norm V2f+ + 2 +...
x22
0.0
Lio-norm (z10 + x/ +...).b
0.5
3
1.0
Focal aggregation
(1 - exp(-x)))²
0.0
2 3
illustrate via an experiment how the aggregation changes the performance of the Aggrogating Algorithm in Section 5.2
The properties a weighting profile f imply the existence of a contimuous inverse, which we denote by g: (0, 1] [0, oo), such that (a) g(1) o, (b) g strictly decreasing, and (c) lim g(z) = oc. Finally, 2-40
note that when choosing A(x) = g(x) in the experts' weight updates one recovers Bayes' updating much as described in detail in [ook 2001 Section 2.2) for A(x) log
4.2 The Preddtt-reii
Different to the exponential weight algorithm (cf. (Cesa-Biandee Bianchi and Lugosi 2006 p. 14)), which shares the weight updates, the Aggregating Algorithm additional involves pseudo-prediction step, which then used to derive the actual prediction. For 1, Ā À and f(x) e--((x) as above, the pseudo-prediction (2)
writes as,
(w(w)) In.-1 ((AAA.1100)))
PA-1(0)
(0) = Je P()1(0)
For notational convenience, we introduce the following slight variant,
(((w) = - (b)(w() = ( ((0))))))))PPP10)()))
(6)
8

---

Published in Transactions on Machine Learning Research (09/2025)
where g is the inverse of f as described above. For the sake of readability, we sometimes do not explicitly highlight the dependence of va on f in every instance. However, use the rp notation in those cases where the dependency on f is not clear or particularly important.
The
allows for several interpretations:
Normalizing Factor At cach step t we define the I-dependent family of mcasures on θ, given by
pe(O:w) - (.(w)
where P--1 is the normalization of Pt-1. Here, we do not specify of Ω - [0, 20). Imposing pe(O;w) w) be probability distribution on yields to the pseudo-pradiction given in Heence we can interpret of as the normalizing factor of pr(0;w).
Loss Mapping Suppose that we E 1 is revealed by nature. Then
of (we) = [[ f((Ws) ((0)))
A(wr, (0)) >> 1 for all 0 E O, by properties of the weighting profile f. the value of th (wx) will be very large. On the other hand, if &(we,&r(0)) 0, for all 0 E O, then its value will be close to 0. this sense, we can interpret vi{ (wx) as the loss incurred by pseudo-prediction wi when wi is observed (cf. (Vovk] 2001 Section 2.1)).
Concluding, we summarize the reparametrization of the first two steps of the Aggregating Algorithm in
Algorithm 2 Leaning on Vovk (2001)'s I's naming convention we call it the Aggregating Pscudo-Algorihhe for
Quasi-Sums (APA-QS). Given the loss interpretation of the pseudo-prediction, we can prove the following
Lemma 4.4
Note that consider the aggregation function A Unevl0,, - [0, oo) given by
An In) = ((s(
(7)
for a fixed weighting profile ʃ (and hence its inverse g). Recall that using can be expressed as a quasi-sum Q" via the relation f(x) -w(x) =(x)
Algorithm 2: Aggrogating Escudo-Algorithe for Quasi-Sums (APA-QS)
Data: Prediction game (2, O, and prior distribution Po-
Result: Predictions (7t).
for every do
(1) Update experts' weights P.(0) = [[(]==(((<s< (:-0)))
Po-1(0) Provide pseudo-prediction with (0) = To 1(0) do
(e(w) = 9 1 ((AWw&&(0)))P==1....
(8)
end
Lemma 4.4 (Bound for APA-Loss). Let f: [0, oo) - lR be a weighting profile and g ils inverse. Then
AT(APA())) AT (vf (Wi), wis (wz), vf(wr)) 9 [[ Po((
Moreover, when |0| = and Po is the uniform probability distribution with weights /n,
Ar (APA((Po) < A2 (AT(0*), ()
(9)
for any expert 0* E e. F.3
9

---

Published in Transactions on Machine Learning Research (09/2025)
The statement follows from yet another "change of variables" for Lemma 1 in (Vovk 2001 However, for didactic reasons we include a full proof from scratch in the appendix (Lemma F.3 In particular, the proof reveals that the multiplicative structure of the weight updates directly translates into the multiplicative structure of Ar. This gives rise to the additive structure by the exponential relation in 44
Note that incorporating a learning rate rj > 0 in the APA (as (ook 2001 amounts set f(x) e-
Corollary 4.5. Let f: [0, oo) - be a weighting profile. Let n E (0, oo) be a learning rate and define 9,(2) = (f When O and Po is the uniform probability distribution with weights 1/n,
(APA(())) 7) = AT(AA(())) & A2 (Ar(f)).0) In (n)
(10)
for any expert 0* E @..
F.4
Finally, notice that by setting f(z) = e- in Corollary 4.5
we recover the bound found by Vovk (1990].
4.3 The Substitution Step
As a last step the Aggregating Algorithm derives an actual prediction from the pseudo-prediction This is achieved by using substitution function Σ. The substitution function maps a an allowed prediction such that the loss of the allowed prediction is smaller than the value of the pscudo- prediction evaluated in every possible outcome. More formally, a substitution function E makes the following inequality hold, X(w, (v))) s (b((w) for all w Ω and all pseudo prediccrrediiiooss the. The existence of such a substitution function is guaranteed by the mixability the game g = (2,r, θ, X, n) (see Section 2). Concretely, Vovk (2001) suggests the substitution function Σ(t) E arg min supwer ((w.)///((e) Since
to
À decomposes, we apply the change of variables as well to the definition of mixability. To this end, we introduce f) as the set of all pseudo-predictions of the form,
(w) 9 [/ ((ACu
[/ F(M(s, ((MG)))))
(11)
for some distribution Q on T. Definition 4.6 -J--xxxiiailllt)). Let (9,1,,0,,,1) 7) be a prediction game. weighting profile and consider pseudo- predicopredicioons vbd E P(X,,)) In) given by 11 We call (9, (f,1)- mixable there erists a substitution function E such that
Let f: [0, - [0,1] be
M(,, A(, E(w S 15 (w).
(12)
for all E Ω. If the game is (f, -fimaale for some 7); we say the game is f-mixable.
Lemma 4.7 (J-Mixability is Mixability of Composite Loss). A loss is -1)mmabllee if and only if x = yon for u(z)= = - In f(x) is m-mixable. (Proof F.5
As noted by Erven et al. (2011) and Cabrera Pacheco and Williamson (023), the definition of mixability a comparison of the loss function À and the learning rate r with the log-loss. Our (f, miimixbbllity emphasizes the relativity to some function f. Note that if f(z) x = (- log (=ogzz)-! =1 the definition directly reduces to the original definition.
Given the prediction game (2,T, is (f,n) (respectively the prediction game r, (, 7, is mixable), the substitution steps completes the Aggregating Algorithm. We finally obtain Corollary in a slightly different, but equivalent, formulation.
Corollary 4.8. Let f: oz) - E be a weighting profile. Let n (0, be a learning rate. When O, X,)) is (f,n)-mirable, |0]= and Po is the uniform probability distribution with weights 1/n,
(learnerr) = AT(M(w (.. M(441)) < A2 (Ar(0"), In (1-
(13)
for any expert 6* E
When proper, mixable loss functions considered in class probability estimation, antipolar losses constitute another universal substitution function.
Kamalaruban et
2015 argue that.
10

---

Published in Transactions on Machine Learning Research (09/2025)
Remark 4.9. The substitution function is computational bottleneck which, in particular in high- dimensional prediction lasks, might lead to suboplimal time performance. We haven't found literature to address this shortcoming.
Remark 4.10. Vook (2015) argues that the log-loss is in a particular way fundamental. As Cabrera Pacheco and Williasson (2025) have shown, bolh Vook's fundamentality and mizability (in the sufficienlly differen- täable case) are equivalent. to a curvature comparison betweee a given loss and the log-loss. Definition 4-6 and the analysis of the AA with more general aggregation functions, emphasize that the choice of aggregation is tightly intertwined with the definition of mixability. Particularly, standard sum aggregation corresponds to slandard mirabilily. Hence, the Jundamenlality of the log-loss is a particularily of the slandard sum aggre- gation and does not imply that the log-loss is fundamental for other aggregations. However, Corollary 4-1 suggest connection back to type Jundamentality of log-loss via u, which con potentially be described geometrically. We will not go deeper into this observation here.
The corollary requires the prediction game to be (J: n)-mixable. However, it turns out that we can generalize the bound on the aggregated loss of the learner to non-mixable losses.
4.3.1 The Mixability Constant for Non-Mixable Losses
To slacken the requirement of mixability (Vovk 2001 introduced the mirabilily constant. In our symbols,
cf) = inf IR V E P(A. f). By e, Yw, f(M(, 2 f(v (w))),
(14)
and set [o] = 20. Note that cf) 2 1 (Lemma C.2
Our definition of the mixability constant is equivalent to Vovk (2001 's definition. This is easy to see, since f() 2 f(b (w)) + X(w,)) 2 ceh(w)
(cf. Proof F.5). When the infimum in 14 is attained, a substitution function Σ (which also depends on n
and X) exists and satisfies
2 (((())
(15)
for all w E Ω.
Remark 4.11. Note that if we fir f and consider fn(x) = f())", where v) > O is the learning rate, then we can consider the constant c(fx) in [11 to depend only on 7). When we do this we simply denote it by e(r)-
With the mixability constant at hand one can provide a generalized bound on the aggregated loss of the
learner to non-mixable, losses (Theorem C.3) ; which is analogous to (Vokk 1990. Eq. (15)). Even the optimality result for the AA (Vovk 1995). , i.c., the constants in this Theorem C.3 cannot be undercut by
any other prediction algorithm, translates to our reparametriiaaion and even slightly generalizes the former statement (Section Ch.
5 How aggregation changes prediction
In the previous sections we have argued that the Aggregating Algorithm is generally applicable for losses interacting nicely with "reasonable" aggregation functions. However, it is still unclear how the aggregation influences the actual predictions made by the Aggregating Algorithm.
We qualitatively approach this question in two ways. First, we propose to interpret the generator functions of aggregations as utility functions. Then, we illustrate in an experiment that aggregations can actually express the forecaster's attitude towards losses.
5.1 Aggregation and utility of losses
Aggregation functions for losses are, under mild conditions, quasi-sums Q" (cf. Lemma 3.2 On one hand, as we have shown, the u-quasi-sum of losses \ the regret bound is tantamount summing up distorted losses o (Corollary 4.1p. On the other hand, u can be interpreted as the negative utility function for the losses X of the predictors. It. expresses the dis-satisfaction of the learner to incur certain losses. Therefore,
11

---

Published in Transactions on Machine Learning Research (09/2025)
whether we talk about a certain choice of negative utility of losses or whether talk about u-quasi-sums aggregation functional does not make a difference. For illustrated, comparative example see Appendix D
More generally, it is true that risk-avoider prefer convex u, i.e. high losses are up-valued, low losses are down-valued. In contrast, risk-taker consider concave u, which means that low losses are up-valued and high losses are down-valued (cf. (Winkler and Murphy, 1970). concavity and convexity are switched therein for reasons of sign flip). Hence, we can conclude: the type of aggregation captures the attitude of the forecaster towards losses.
5.2 Weather prediction via Aggregating Algorithm
The preceding discussions suggest that aggregation, weighting profile and utility are essentially different facets of the same object. We earlier asked, how does the type of aggregation change the behavior of the Aggregating Algorithm? The proposed interpretations as weighting profile and utility lead us to the following three hypothesis, which we substantiale by a real-world data prediction experiment.
Ha(a) Convex additive generators express the aversion towards extreme losses.
H-(b) Concave additive generators express the risk-loving behavior in terms of accepting extreme losses, but seeking for the "perfect" predictor.
H-(c) Focal aggregation expresses aversion towards extreme losses.
We provide the log-loss (sometimes called cross-entropy loss) profile of several applications of the AA-QS for different aggregations on sequential weather classification task. We use the Aggregating Algorithm to aggregate probabilistic predictions of 9 simple classification algorithms. The AA-QS was implemented using the log-loss. The task is detailed in Appendix []] Table 2 summarizes our findings for the data collection from the Zugspitze (Germany). See Appendix E. for further experiments. The loss histograms particularly reveal the difference between convex and concave utility function. Concave utility functions (i.c., Lo.s and Sum) lead to a high number of predictions with extremely small loss values, with the downside that some predictions incur a high loss. Convex utility functions (i.c., L2 and Sum) damp the tails of high losses, i.e., only few predictions with high losses are made. On the other hand, there are many predictions made incurring small but suboptimal loss. In this realm, L10 is the most extreme example in which many sub- optimal predictions are made, but the tails are banned. The focal aggregation leads to behavior largely similar to the one induced by Lz-aggrogation. All three hypothesis about the change of prediction given a certain aggregalion can be substantiated in this explorative study. An exhaustive experimental study would be required to provide more conclusive statements. Nevertheless, there is a conceptual problem in comparing different aggregation schemes on a given problem and asking which one is "better". We are not proposing different algorithms for a given objective. We actually change the objective.
6 Conclusion
In this paper, we put forward a general, axiomatic approach to loss aggregation online learning. Analogous to the development in offline learning, but differently motivated, we show that set of reasonable aggregations in online learning is characterized by the set of quasi-sums. It turns out that the AA can be adapted to deal with those general aggregations. Not only we transfer the nice theoretical properties of the AA to its modified variant, we also provide experimental evidence that the choice of general aggregation determines the extremne-loss seeking or extreme-loss averse behavior of the AA. Hence, we span up a new dimension of choice, for which we think that the modified. AA is just a starting point. We believe that similar modifications can be provided for other online learning algorithms such as weighted majority algorithm [Littlestone and Warmuth 1994), follow the regularized leader (Abernethy et al. 2009), or follow the perturbed leader (Kalai and Vempala 2005
12

---

Published in Transactions on Machine Learning Research (09/202)
Table 2: Aggregations, and their corresponding utility function u. The loss histogram shows the number of predictions (y-axis) incurring the loss (x-axis) in a certain bin. The blue line depicts the average loss.
Aggregation
u(x)=
Loss Histogram (Weather Zugspitze)
400
300
Lor--norm
200
100
0.0
0.5
1.5
2.0
25
3.0
3,5
400
800
Sum
T
300
Le-norm
x
200
100
0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
400
800
Li-nnorm
x 10
200
500
Focal aggregation
-
200
100
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
13

---

Published in Transactions on Machine Learning Research (09/2025)
6.1 Broader impact and position statement
The generality of the learning under expert advice setting allows for the deployment of the adapted Ag- gregating Algorithm in a variety of settings, which do not exclude any malicious nor benevolent use. Note that the type of aggregation creates another choice parameter which, depending on the deployment context, might call for a participatory, democratic approach to the determination the used quasi-sum. This con- textualization requires further studies. We are convinced that our socialization has shaped our method and approach to research. We might have been ignorant to aspects of our work which against other socio-cultural backgrounds might miss need reframing.
7
Acknowledgements
The authors appreciale and thank the International Max Planck Research School for Intelligent System (IMPRS-TS) for supporting the second author. Part of this project was conducted when the second author was visiting Aaron Roth at the University of Pennsylvania. The stay was supported by a fellowship of the German Academic Exchange Service (DAAD). This work was funded part by the Deutsche Forschungsgemennschatt (DFG, German Research Foundation) under Germany's Excellence Strategy EXC number 2064/1 Project number 390727645; was also supported by the German Federal Ministry of Education and Research (BMBF): Tübingen Al Center.
References
Jacob D. Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Conference Learning Theory, number 110, 2009.
Jean Aczél. Sur les opérations définies pour nombres réels. Bulletin de la Sociélé Mathématique de France, 76:59-60 64, 1948.
Jean Aczél. solution of some problems of K. Borsuk and L. Jánossy. Acta physica, 4:351-362, 1955.
Joseph Aczél. short course on functional equations: based upon recent applications to the social and behavioral sciences, volume Springer Science Business Media, 2012.
Armando J. Cabrera Pachoco and Robert C. Williamson. The geometry of mixability. Transactions on Muchine Learning Research, 2023.
Nicolo Cesa- Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Alexey Chernov and Fedor Zhdanov. Prediction with expert advice under discounted loss. In International Conference on Algorithmic Learning Theory, pages 255 269. Springer, 2010.
Robert Craigen and Zsolt Páles. The associativity equation revisited. aequationes mathematicae, 37:306 312, 1989.
Amit Daniely, Alon Gonen, and Shai Shalev-Shward Strongly adaptive online learning. In International Conference Machine Learning, pages 1405 1411. PMLR, 2015.
Freddy Delbaen. Coherent risk measures general probability spaces. In Advances in finance and stochas- tics, pages 1-37. Springer, 2002.
Tim Erven, Mark D. Reid, and Robert C. Williamson. Mixability is bayes risk curvature relative log loss. In Proceedings of the 24th Annual Conference Learning Theory, pages 233-252. JMLR Workshop and Conference Proceedings, 2011.
Christian Fröhlich and Robert. C. Williamson. Risk measures and upper probabilities: Coherence and stratification. Journal of Machine Learning Research, 25:1-99, 2024.
Richard J. Gardner and Markus Kiderlen. Operations between functions. Communications in Analysis and Geometry, 26(4):787-88) 855, 2018.
14

---

Published in Transactions on Machine Learning Research (09/2025)
Michel Grabisch, Jean-Luc Marichal, Radko Mesiar, and Endre Pap. Aggregation functions, volume 127. Cambridge University Press, 2009.
Nika Haghtalab, Michael Jordan, and Eric Zhao. On-demand sampling: Learning optimally from multiple distributions. Advances in Neural Information. Processing Systems, 35:406-419, 2022.
Elad Hazan and Comandur Seshadhri. Adaptive algorithms for online decision problems. In Electronic colloquium on computational complezity (ECCC), number 88 in 14, 2007.
Laura Tacovissi, Nan Lu, and Robert C. Williamson. A general framework for learning under corruption: Label noise, attribute noise, and beyond. arXiv preprint 0rXiv23377086453 2023.
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-300 2005.
Paramcswaran Kamalaruban, Robort C. Williamson, and Xinhua Zhang. Exp-concavity of proper composite losses. Conference on Learning Theory, pages 1035 1065. PMLR, 2015.
Andreí Nikolaevich Kolmogorov and Guido Castelmuovo. Sur la notion de la moyenne. G. Bardi, tip. della R. Accad. dei Lincei, 1930.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. On tilted losses in machine learning: Theory and applications. Journal of Machine Learning Research, 24(142):1 79, 2023.
Tsung-Y Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision, pages 1980-2988, 2017.
Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-26) 1994.
Pictro Mulicre and Giovanni Parmigiani. Utility and means in the 1930s. Statistical Science, pages 421-432, 1993.
Mitio Nagumo. Über eine Klasse der Mittelwerte. In Japanese journal of mathematics: transactions and abstracts, volume pages 71-79. The Mathematical Society of Japan, 1930.
Eric Neyman and Tim Roughgarden. From proper scoring rules to max-min optimal forecast aggregation. Operations Research, 2023.
Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. orXiv preprint arXiv:1908.0580 2019.
John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior. Princeton university pross, 3rd edition, 1953.
Vladimir Vovk. Aggregating strategies. In Proceedings of 3rd Anna. Workshop on Comput. Learning Theory, pages 371 383, 1990.
Vladimir Vovk. A game of prediction with expert advice. In Proceedings of the 8th annual conference on Computational learning theory, pages 51-60, 1993.
Vladimir Vovk. The fundamental nature of the log loss function. Fields of logic and computation II: Essays dedicated To Yuri Gurevich the Occasion of His 75th Birthday, pages 307-318, 2015.
Volodya Vovk. Competitive on-line statistics. International Statistical Review, (9))) 2001.
Robert C. Williamson and Aditya Menon. Fairness risk measures. In International conference machine learning, pages 6786-6797. PMLR, 2019.
Robert C. Williamson, Elodie Vernet, and Mark D. Reid. Composite multiclass losses. Journal of Machine Learning Research, 17(222):1 2016.
15

---

Published in Transactions on Machine Learning Research (09/2025)
Robert L. Winkler and Allan H. Murphy. Nonlinear utility and the probability score. Journal of Applied Meteorology and Climalolgy,, 9(1):143-144) 1970.
Lijun Zhang, Shiyin Lu, and Tianbao Yang. Minimizing dynamic regret and adaptive regret simultancously. In International Conference on Artificial Intelligence and Statistics, pages 309-3 019-119.00 PMI.R, 2020.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning, pages 928 028-936,440 2003.
A A simple introduction to Aggregating Algorithm
The Aggregating Algorithm is a relatively straightforward algorithm with strong theoretical guarantees. In order to motivate our theoretical development in this paper and to provide a low-threshold introduction to this algorithm, we first lead the reader through sensibly simplified scenario of learning under expert advice.
Consider a binary class probability estimation task on the outcome space Ω == {0,1). 13. We repeatedly see 2 experts O = {0,, 02) predicting the probability that the next outcome will be 1, i.e,, in every round E [T] = (1.... T} each expert 0 E θ provides a prediction Eo(0) E [0, 1]. After the predictions are given, the learner (who has seen the experts' predictions) has to commit to a prediction % E [0, 1] as well. Then, nature reveals an outcome We E {0. 1}. We mcasure the quality of the experts' and Iearner's prodiction by [0, 1] (s here refers to the prediction made either by the expert or the learner). Note that the set of possible predictions can be regarded as the probability simplex s + (s, 1 - s) for s E [o, 1], cf. top-left in Figure 1. Morcover, we can
the log-loss, that. is, X(s,uz) = [ 0] (- In(s)) + [av 1] (-In(11- (1]1-))), 8)), for
interpret the log-loss as an embedding of the simplex into R2, i.., (8, 1 - 8) + (-In(s), - In(1 - 8)), see
top-right in Figure 0
Now, the Aggregating Algorithm, as learner, uses the embedding of the simplex into I2 and exponentiates
it by the exponential mapping (Ag,Ai) + (e -mm e m-:)),, ), where 17 > 0 is called the learning rate. Figure | right-top to bottom illustrates this step. In particular, the predictions of the experts can be traced through both mappings, the log-loss and the exponential mapping. The Aggregating Algorithm then forms convex combination of the mapped experts' predictions d),. The weights on how much each experts' prediction contributes to this mixture are based on generalized Bayes' updating (see Section A.1 The updating puts (orange-browe)
more weight on the experts which performed well in the past. As Figure [ obtained convex combination is not necessarily on the exponentiated embedding of the simplex anymore. We later call it preuddopreiittion for this reason. Pseudo- predictions have nice theoretical properties (see Section 4.2 but they are not helpful predictions, since they are not in the prediction space. That is why the Aggregating Algorithm requires characteristical step: the substitution E of the geeudo-prediction by an actual prediction with similar theoretical properties. This substitution is intuitively a projection of the pseudo-prediction vi to the exponentiated embedded simplex (cf. Figure [ darkgreen). Crucially, a property called "mixability" (sce Definition (.6) guarantees that the pseudo-predicting the exponentiated embedded simplex. The obtained actual predictions guarantee that the accumulated loss of the Aggregating Algorithm (learner), i.c., ΣT A(n, wi) with % = E(va is always smaller than the accumulated loss of any expert, i.e., Ets X(Ex(0), for all 0 E θ, up to constant C. In other words, the Aggregating Algorithm's regret is bounded above by a constant, independent of the number of played rounds:
illustrates, the
lics bottom-left to
T
T (()) - Σ )CC,())
5C e.
[=1
A.1 Bayes' updating for weights
A fundamental property of the AA is that, under some conditions, the updating scheme (Step (1) in AA (Algorithm 1 is reduced to Bayesian updating (Vovk 2001 Section 2.2). More precisely, make the following
16

---

Published in Transactions on Machine Learning Research (09/202))
w = 0
(- In 8, -In1 8)
(s, 1 -
T1 = E(OI)
A = In
(v)
T2 = E(f2)
32
==1
len en
Figure 1: Graphical Summary of the Steps in the Aggregating Algorithm. Experts 0 and 0g provide predictions ((0i) and {(22), respectively, which are placed in the simplex (top-left) x (E(0)), 1, 1-(()()))) ((0)) and = (E(02), 1 {(02)) via s + (s.1-5) 1). s). The log-loss embeds the simplex as a curve in R² (top-right), i.e, ~ - In s is applied coordinate-wise and maps 2 and to x' and ويg- Then, the exponential mapping projects them into [0, 112 The Aggregating Algorithm forms a convex combination t of the projected predictions xf and w!f based on weights updated by a Bayesian-type formula (orange-brown), called pseudo- prediction, which is substituted back to the simplex via a substitution function Σ (darkgreen).
17

---

Published in Transactions on Machine Learning Research (09/2025)
choices: (a) Q is finite, (b) r (Q), the set of all probability mcasures on Qt (c) loss function is the log-loss Ann and (d) the learning rate 7 1.
For an expert whose prediction at time is Ex(0) E (12), we write (w)) as the probability of seeing wt forecasted by 8, who has observed all data points up to time step t 1. Let Pr(0)* denote the normalized density P())::
(-AAllurR((0)) P. (0) Pa(O)* [e Te-nAul &. P: (0)1 (((00)())PP-1())1))
(()
One can interpret (wr) as the likelihood to observe we at time given the expert 6. Analogously, (0) can be thought of as the prior on the experts after - observations. Note that crucial in this derivation is the correspondence the exponential projection em (with n = 1) used in the definition of the pseudo-prediitions and the log-loss Ain-
B The Effect of u on the Mixability of Losses
The crucial property making the substitution step of the Aggregating Algorithm run, is mixability. A priori it is unclear how the composition of loss function À with a strictly increasing, continuous function u with u()) = 0 effects the mixability. We shortly argue that all interesting cases are possible. For the sake of simplicity, we look binary outcome sets and predictions E [0, 1]. Hence, we can write the loss function as X(p) (1
(1) non-mixable to mixable The absolute loss \ehe(p) = (1 p,p) is not mixable for any learning rate > O. Applying the function u(x) = In gives Amn = (- In - - pn the log-loss which mixable, e.g., for 1j =
(2) mixable to non-mixable The Brier score (p(p) = ((1 p)) is mixable for = 2. However, the square root of the Brier score recovers the absolute loss Aabs. which not mixable for any > 0.
mixable to mixable The mixable (with = 1) log loss Ap) = (-In1 - - -np) composed with u(x) = - e²) gives the Brier score (p(p) = ((1 - p)2, which is mixable for r7 =
C AA-optimality for quasi-sums
In the majority of the paper have assumed that the prediction game in consideration -mixxabe. In this case obtain direct bound for the aggregated loss of the predictions given via the substitution function and the APA-QS. As it happens with the usual AA, there is no guarantee that the given loss will be (f, mixxxale... We deal with this situation in this section. With this at hand we also provide an optimality result for the Aggregating Alg Algorithm under quasi-sum aggregation.
First, will be useful to impose some mild conditions on the prodiction game.
Definition C.1 (Regular Local Prediction Game (Vovk] 1995)). We call the tuple (2, (, a local prediction game. A local prediction game is called regular if the following four assumptions hold
(a) is a compact topological space.
(b) For ench Ω the function y () continuous.
(c) There erists y I such that, X(w, 7) < oo for all Ω.
(d) For all 7 E T there exists w E Ω such that A(w, 7) +
In this section it will be always assumed that the (Ω, (2 is local prediction game.
18

---

Published in Transactions on Machine Learning Research (09/2025)
C.1 Aggregation algorithm for non-mixable losses
Fix (,,,, G and weighling profile S, as in Section 4.3 Note, we assumne that we obtain regular local prediction game when we drop the set of experts θ Recall that in this case, the aseudo-predictte belong to P(A.f) that is, they are of the form
(bww ((NW
for some distribution Q on r.
The proof is basically the same and we include it for the First we show that с 2 1 as in Vovk 1990 reader's convenience.
Lemma C.2. For given (Q,T, and weighting profile f, then c(f) 2 1.
Proof. Suppose that there is f such that c= 1. Let 7 E I and Qu be defined Q+-(7)) and 0 otherwise. Then, there exists such that for all Ω
s(A(w,7)) (0 [1 ((A(W))))
(()(w,)))).
Since 0 < f(x) for all x, we have
0 0 In (f(A(w), = c(- ((A(w,,)))))
By assumption (c), we know there exists E I such that (w < co. By the argument above (with y = >)) we know there is 7/2 E I such that
0 S - In (f(A(w, S (n
Continuing this way, obtain sequence } C I such that
0 < - In (6 S c(- (f(A(w, mk))))
Using the compactness of Г (assumption (a)), let y T be limit point of this sequence. By continuity (assumption (b)), - In (f(X(w, 7))) is the limit of subsequence (- m)))).
Note that we have
< (J(((s,,, m))) < c- (-I(((((44,
thus when k oo we conclude that In (f(A(w, 7)) 0, that is A(w,)) = O, which contradicts (d).
We ready to obtain analogous bound to
13
Theorem C.3. For given (2, r, 0, A) and weighting profile f. Let c c()). When |0] and Po is the uniform probability distribution with weights 1/n, we have the bound.
Al(leareer) s AA((APA-S((P)) S f(AT((0)))
(16)
for any expert 6* e e.
Moreover, if we consider a learning rate n 0, fn(x) = f(x)" and G, = c(()) we have Ar(learner) & (A(PA((P)) S (( {((((A(()))'))
(17)
where In is the inverse of Jn
19

---

Published in Transactions on Machine Learning Research (09/2025)
Proof. Let v be pseudo-prediction Then, have f(A(w,)) 2 f(((w)))
(l(aeneer)) = ()))) & g(f(v) (arr
This motivate us to define new aggregation function given by
(21, In) = "..()=".......
Using the fact that 2 1 (Lemma C.2
and the notation in Lemin 4.4 we see that
(()())))(())
Proceeding as the in the proof of Lemma
4.4 we obtain
/ (B)(()) Po(0) do s f(01(01)))
and hence,
o f (B) Po(O) d0 2 g (( Ar(AA((P))).
(18)
We left to estimate the LHS of 18
[/[ f (B) Po(0) d8
| f (AT(O))) (o(0) da
f (AT()
5
n
(AT(())))
$g
no
proving 16
To obtain 17 let f = Sn and Cy = c(fr), then we have
In 1 Jn ((B)) (0) do) 1 1/ Sn (A) Po(O) do
(A7
S 9n
n Cr
where
(f f,,,,,( = R..)
The result follows since
(A77)(()))
(B") (A77'00) (,,((00)),,,111)) (n
9n
(AT())))
=(()(Ar(8")) (n
20

---

Published in Transactions on Machine Learning Research (09/2025)
Remark C.4. Recall that the weighting profile in Theorem C.3 be written in the form f() c- for an appropriate u. In this case, for > 0, we have
o(f(Ar(0'))) f(o ()) = u- (c,u(Ar(00) + t,,
u-' ())((Ar((0) + Sa In(n) n
In porticular, when u(z) this gives
LT(PPA(Po.)) S cG,LT(0") + In(n)
as Vook 1990
C.2 optimmally
Surprisingly, is possible show that the Aggregating Algorithm a game-theoretic sense optimal (Vovk 1995). In general game between an adversarial environment, which gets to choose experts' predictions and nature's outcome and learner, the learner can only win if they achieve the bounds which are suggested by the Aggregating Algorithm, cf. Remark C.4 We formalize this statement and extend it to more general aggregation functions in the following.
Definition C.5. Let A be a continuous, strictly increasing and associative aggregation function. Let (2, A) a regular local prediction game. We call the following full-information game & between encironment and learner L global prediction game:
1. E chooses the size n of a set of experts θ
2. For every t E [T],
(i) E chooses predictions (0) E I for every O.
(ä) L chooses a prediction "i E
((0) E chooses an outcome We Ω.
(tv) (0) A2(A, ( M(ai, (()) for all 0 θ
(v) (learner) = A2(A, (learner), X(wr, 7)))
Definition C.6. We say that the learner L wins the global prediction game @ if for all t E [2] and 0 E θ there are constants e and a such that
Aclearner) I ue u(A)(0)) + an())))
(19)
otherwise, we say that nature wins. Note, that the aggregation function is a quasi-sum with generator u, i.e., A Qu-
Optimality here is grounded in the global game specified above. Intuitively, the following theorem shows that in a worst-case scenario, concerning the choice of experts and outcomes, every learner under expert advice can at best achieve the regret bound parametrized by e and of (19h. Note that we don't put any restrictions on the abilities of the learner until this point. Strikingly, the Aggregating Algorithm can achieve this regret bound, hence is optimal.
Theorem C.7 (Optimality of Constant Regret Bound for All Predictors). Let A be a continuous, strictly increasing and associative aggregation function. Consider the global prediction game following Definition C.5. There exisls learner L, which against urbilrary adversarial excironment wins, i.e, for all T E N and all 0 E θ,
Ar(L) = AT(A(11, n....... A(WT, S l u(Ar((')) + +aln(n)).
if and only if e c(n) and a > ala) for some E [0, o0) with c(n) as defined in and u is the generalor of the oggregation, i.e., A Q..
7 we Ao(#) for all e.
21

---

Published in Transactions on Machine Learning Research (09/2025)
Proof. First, note that the aggregation A fulfills u: (0) + [0, oo), continuous and strictly increasing with u(0) 0 (Temma 3.2
(A3) Hence, A Q" for some generator (A1)
Let us define the surrogate loss X = u. It is straightforward to check that (Ω, fulfills all conditions for regular local prediction game. The first condition holds by assumption. The second condition is clear, since the composition of continuous functions is continuous. Thirdly, there exists E T such that, X(w,n) oo for all Ω. It. follows X(w: 7) u()(w,))) do for all E Ω. Finally, for all y I there exists f such that X(w,n) A O, hence for all y there exists w E Q such that X(w,7) = u((ww,)) 7)) # 0, because u(0) = 0 and u strictly increasing. Concluding, (2, A) is a regular local prediction game.
Theorem 1 in [Vovk 1995) states that in the specified game the learner L is guaranteed to achieve the regret bound, for all 7 and all E θ
T
X(ur, 74)) S Σ t=1
Σ
M(r, (x(0)) + a (101),
(20)
if and only if c ē(n) and 2 dny for some 1) E [0, where
ā(1) = inf E V P(A,e P By E ET, Vw, e enb(wn))) 2 e-(l(w)"
and set (2] = 00, Note, that
ε(σ) inf E R V E e (m())), By ET, Ww, e-m(((()))))) 2 2 =)(((()))))
inf E R P(A, B7 ET, tw, f(M(,)))) 2 (
for f=e" hence ?(n) coincides with e(n) defined in 14 We give equivalent forms of 20 First, since u- (xx) is incrcasing, 20 is equívalent to
T
S su- Xur, ni))
i(wr. (1)) + a (101)
Furthermore, = uol A and f(x) = e e-(()), so 20 is equivalent to
Ar(A(wi:n)... MWT.TT) S a a- u(A((())) + +al(n)).
Remark C.8. The optimality of the Aggregating Algorithm under quasi-sum aggregation only refers to this specific definition of global prediction game, Note, if c >>> the tightness of the regret-like bound depends on the performance of the ezperts. Standard O( -regret algorithms in learning under expert advice, e.g., Exponential Weighting Algorithm, can potentially perform better, in terms of less loss, than the Aggregating Algorithmm, even though the Aggregating Algorithm is optimal in the sense specified above (Cesa-Biancee Bianchi and Lugosi 2006, p. 14).
An illustrated, comparative example for different aggregations
Let us consider a comparative example: the simple negative utility function u(x) = corresponds to the standard sum. The negative utility function u(x) = x² generates the Euclidean norm aggregation. Compared to summation, in the Euclidean norm large loss values contribute relatively more to the result than small loss values. The analogous statement true for the utility functions. As a negative utility function u(x) x². large loss values hurt, since higher negative utility (cf. orange-brown arrow in Figure relatively more than small loss values (ef. darkgreen arrow in Figure
22

---

Published in Transactions on Machine Learning Research (09/2025)
((()
u(x) x²
u(x) =
Figure 2: Comparative Example of Linear and Squared Utility. The horizontal axis denotes the loss value. The vertical axis the negative utility of the loss. We compare the negative utility function u(x) to u(x) = x². In particular, for two values highlighted by a darkgreen arrow, low value, and an orange-brown arrow, high value.
Table Weather data collections from the DWD (German Weather Agency).
Place
File
Zugspitze
[agerpaeerr..t...r...o..oo.o.o22 zip
tageswerte_KL__ ____KK___0992222 11000000110222221311111 http:/1_hhittttee
Potsdam
tageswerte X3__03977_0. otg.e//ee___LLooo.ere.o.ooo00120
Putbus
tageswerte _0.00004111000001222222002200000 2tt.222211111hssttiiipg
Weissenburg-Emetzzle Emetzheim
Place
Days with Missing Values
Final Number of Days (Train Test))
Zugspitze
15
8386 (6708/1678)
Potsdam
8759 (7007/1752)
Putbus
431
8323 (6658/1665)
Crrissenburg-Emetzhher
8744 (6995/17499
E
Sequential weather classification task
We run tabular classification task weather data collection. The data is curated and provided by the DWD (German Weather Agency). The data collections are publicly available at https:/ dwd. For the file names see Table g Note that the files are constantly updated, hence the file names potentially change. The file [ names are of the format tageswerte KL_ [location identifier] [start date]] [end date] hist .ipp
climate environment/CDC/
Each collcction provides daily measurements of weather-relatod attributes for one place. In every collection we deleted days with missing values. For statistic of the data collections see Table
Based on daily average air pressure, average temperature, average relative humidity, maximum temperature, minimum temperature and date we train 9 classifiers to distinguish between four classes of weather: cloudy, rainy /snowy, sunny and unsettled, which are defined according to Table 4 We use the first (in chronological order) 80% the data points as training set for the following classifiers provided by the scikit learn package: logistic regression (LR), gaussian naive bayes (NB), support vector machine (SVC), lincar model with stochastic gradient descent (SGD), decision tree (DT), k-nearest neighbors (KNN), random foreast (RF), bagging decision trees (BAGGING), gradient boosting decision trees (GB).
23

---

Published in Transactions on Machine Learning Research (09/2025)
Table 4: Definition of weather classes.
Precipitation I 2mm Precipitation 2mm
Sunshine Hours 4h sunny
unsettled
Sunshine Hours Σ 4h
cloudy
rainy/snowy
Then, run the classifiers on the remaining 20% of the data. We apply the Aggregating Algorithm for quasi-sums with the log-loss P We use different aggregations in the Aggregating Algorithm as specified in Table | We observed that the learning rate did not have a big impact on the loss histograms in our experiment. So slightly arbitrarily, we chose = for sum and focal aggregation, we chose 1j = for Lo.s: 7 = 0.001 for L1o and r = 0.5 for L2. We remark that the chosen learning rates (or the aggregations) don't 't necessarily guarantee that (J, miiixabilityy with respect to the aggregation holds for the log-loss function. However, Theorem C.3 still applies for all aggregations.
The code was run on MacBook Pro with Intel Core 19. However, the experiments only required fraction of the compute power. We used Python 3.10.2, scikit learn 1.4.0, pandas 1.4.1, numpy 1.22.2, matplotlib 3.5.1.
For the loss histograms we usod automatic binning on the interval 0.0 to 3.4. Higher values, which turned out to be inf, were cut off. For this reason, we introduced the ba- in the plots where necessary. See Section E. for more experiments.
Note that the classifiers have necessarily been trained using the log-loss function. This "mismatch" " in classification tasks does not diminish the performance Aggregating Algorithm. However, does allow for further optimization of the entire classification pipeline.
24

---

Published in Transactions on Machine Learning Research (09/2025)
E.1 More Experiments
The following lables provide more examples of the same experiment described in Section 5.2 Note that in some of the experiments we observed oc-losses due to numerical instabilities close to O.
Table 5: Aggregations, their corresponding utility function and loss histograms for the AA-QS on the weather data collection from Potsdam. The blue line depicts the average loss excluding co-losses.
Aggregation
Loss Histogram (Weather Potsdam)
u(z))
400
300
Lorm V
200
0
0.5
1.5
2.0
3.0
400
Sum
200
100
0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
400
300
Lz-norm x²
200
100
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
400
300
Lio-norm 10
100
0
1.0
1.5
3.0
3.5
Focal aggregation
200
(1 - (-eep(-x))²²
100
0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
25

---

Published in Transactions on Machine Learning Research (09/2025)
Table 6: Aggregations, their corresponding utility function and loss histograms for the AA-QS on the weather data collection from Putbus. The blue line depicts the average loss excluding co-losses.
Aggregation
Loss Histogram (Weather Putbus)
u(x)
400
Lor--norm V
200
100
0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
400
300
Sum
200
100
0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
400
Lz-norm
200
100
0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
400
300
Lig-norm 2,10
200
100
0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
400
300
Focal aggregation
(1 - exp(-x))²²
0
0.5
1.0
1.5
3.0
26

---

Published in Transactions on Machine Learning Research (09/2025)
Table 7: Aggregations, their corresponding utility function and loss histogram for the AA-QS on the weather data collection from Yoiisenburg--Emethhiin. Emetzheim. The blue line depicts the average loss excluding co-losses.
Aggregation
Loss Histogram (Weather Weissenburg- Eenrrburerg-eteeeemnn
u(x)=
400
Lor--norm V
200
100
0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
400
300
Sum
200
100
0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
400
Lz-norm
200
100
0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
400
300
Lig-norm 2,10
200
100
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
400
300
Focal aggregation
(1 - exp(-x))²²
0.0
2.5
3.0
F Proofs
Lemma F.1 (Proof of Lemma 3.2 Let A: O, - 10, 00) be an aggregation function. Suppose
that A is continuous, striclly increasing, associalive and loss compatible, i.e., it satisfies (A1) (A4) Then,
27

---

Published in Transactions on Machine Learning Research (09/2025)
there erists continuous, strictly increasing function u: 00) - [0, oc), with z(0) O, such that
An(z1..... ,,),..,,,))))))).))))r) ) = u-
Σ u(2z))
(21)
If furthermore A is posilively homogeneous, i.e., for every E [0, oc) and N we have An Aa(ri,,.... : (TI Ti.... then u(r) = x² for some & E (0, oo) in
Proof. Associativity
A3)
guarantees that we can write
(11 ( mnd) A2 A2(..)).
for all n 2 2 (ef. Grabisch et al. In particular,
2009 33))
As 02, A2(11,
A2),
Hence, A2: 00, 00) x [0, oo) - oo) monotone, i.e., strictly increasing, continuous and associative in the
sense Aczél 1948) (for an English translation see (Aczél 2012 for a different proof (Craigen and Páles 1989)), ) where it shown that there exists w: [0, 0o) 00, 00) strictly increasing and continuous such that
A2(21, u (u(21) + u(x2))
Since 0 =2(0,))===-- (u(() v0)), follows that u(0)
Finally, obtain by induction (and associativity)
A Fn) = A An (I1, Bn--1);
)) + u(zn)
Σ i=1
u(xx))
u
Σ u(zz)
u
For the second statement, we go back to A which is now not only strictly increasing, continuous, associative and loss compatible, but as well positive homogeneous, i.e.,
A2(cr1, ((2)),))2) = cA2 (
for E oo). Hence, Theorem in Aczél 1955 This implies
(cf. Gardner and Kiderlen 2018 p. 797)) applies.
A2(11,02) = (ot + 2g)) k
for some (0). By induction as above, we have
In)
3.4h. Let Q" be quasi-sum. Then, there cxists continuous, strictly decreasing function f: [0, xc) (0, with f(0) 1, such that
Lemma F.2 (Proof of Lemma
Qn (,, xn) = (f(
(22)
where g: [0, - o0) the inverse of f.
28

---

Published in Transactions on Machine Learning Research (09/2025)
Proof. Let f()) @-m(a), It is straightforward to check that f is strictly decreasing and that f(0) 1. Let ((x) = (- (n))) be its inverse. Then, we can write
Σ u(xx)) 2( (e- - - - -(((0)))-(((
On (n = u-
Lemma F.3 (Proof of Lemma 4.4). Let f: [0, 00) - R be a weighting profile. Then
AT(APA(P6) = Ar (th (wi), (22(w2), (T((w))) [ ((A
Moreover, when |0| = and Po is the uniform probability distritration with weights 1 1/n,
AA(AA((P)) & A2 (Ar(0),,
(23)
for any expert 8* e
Proof. We will follow the general idea of the proof of Lemma 1 updating rule (2) we have
(Vovk 2001 Recall that using the
Pr(0)
It follows that:
(A(w1, ((Ar = (01 (Men Po(o)
fA(WT, & (0)) P Ig Pr (8) d0
S 11
Pr- d0 f (M(wr, &r (0))) (0)
J8
Pr ( d0 1000f((1mz ((vT(WT)) (MWTT, (0))) - PF
Pr-1(0) dB ( (l:wT).
Integrating with respect to we obtain
[ f (AT()) Pr) f((T(WT))
(24)
We now analyze 1o (0) d0. Using similar arguments as above, we have
(f) ((
= - (0)
J0 Pr 20) d0
[6 (r)
/
11t-000000000eieeeae//////////e0 (P)
d0 (0000000000000000000000000000010
Integrating over θ gives
1 Pr-1 Pr-2 -r--(00d0---o7-1000---
29

---

Published in Transactions on Machine Learning Research (09/2025)
Continuing this process arrive to
1 [(AT())) Po(0)
Po(O) d0 f(bi (wi)) (w))))
(25)
f(o)(w1))....(((((())))
(26)
Applying to both sides of 25 we obtain
1 f (AT( do) (( = AT(AAA(P)),
as desired.
If |+] and Po is the uniform probability distribution with weights 1/n (cf. Vovk 1990)). any fixed 0* E O
have for
9 11 (AT(()) Po(O) do = (AT(O))
n
19=1
(AT()*))
- 9
n
= 9 [$ (Ar(6*) {) (g (n ")]]
= A2 (Ar((*) (,0 (n ))
Let f: (0) - R be a weighting profile. Let E (0) be learning rate. When O = n and Po is the uniform probability distribution with weights 1/n,
Corollary F.4 (Proof of Corollary 4.5
Ar -
=
s A2 (At(f") In (n)
(27)
for any expert 0* E e.
Proof- Consider [x( = fxx)" to define A (see 7 and notice that
A (Z (.) = -(f(())).._ = A(z
(28)
Thus, applying Lemma 4.4 with A we have
Ar(APA(P), n) (A(AA(()))) 9, V f, (A) Po(0) d8
Further assuming that [0] = and Po is the uniform probability distribution with weights 1/n, we have (by
the proof of Lemma 4.4
[/ f, (A77()) d0 < AA (A) 9x
In
for any 8* E e.
Using 28 again, we conclude that.
AT(APA(P)).)) A2 (AT(0"), (m))
30

---

Published in Transactions on Machine Learning Research (09/2025)
Lemma F.5 (Proof of Lemma 4.7 A loss X is -mizable if and only if x uu x for u(x) == - In f(x) is mimibbble.
Proof. If A is (Jin)-miable,, there exists substitution function E such that for all of E P(),
X(w S o (w), EWED
[(, S 9h [ (,NAA(45))))0)))) Vw EQ
- M(w, Xww s n-1 (-mm In U ((1 drl) me En
- E+))) 1 lne-
do vw ES,
where 2b == u vf with v E P(A, (²) and n' is the mapping such that v + vs + (()). Hence, 2 is a substitution function for all v PA) (z) e v*), which is the standard n-mixxbilityy.
31


Reviews:
[{"review_id": "yX2FyKD5ey", "reviewer": "Reviewer_hCiS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths** \n   \nThe generalization of the classic aggregating algorithm seems like it could be useful for studying risk-sensitive problem settings, or for designing robust experts algorithms. The generalized mixability condition could potentially be very useful, given that regular mixability is already quite useful.\n\n**Weaknesses**\n\n- I feel that the paper fails to properly situate itself in relation to existing literature. The base idea behind these quasi-sums is strongly related to many existing notions in game theory and economics that I feel these aren't properly discussed. For instance, much of section 5 seemed a bit redundant to me --- many of the interesting implications of these quasi-sums are already well understood and well studied through the lens of utility theory. This connection is hinted at briefly in section 5 but not systematically explored to a meaningful degree. Indeed, if this connection was thoroughly explored the experiments wouldn't even be necessary: it is already well-understood from utility theory how convex and concave utility functions relate to risk aversion/seeking. There's no reason to explore these questions empirically as there's already quite a broad literature on the topic, answering precisely these questions. Moreover, note that the utility theoretic perspective of preferences is inherently axiomatic as well, dating back to the seminal work of Von Neumann & Morgenstern (1947). Similarly, there are connections to the wide literature on risk-sensitive learning that are similarly axiomatic in nature, particularly wrt the prospect theoretic point of view and the study of coherent risk measures such as the Conditional Value at Risk. \n\n- While paper presents a nice set of generalized results, it would benefit from more discussion of the implications of this generalization. For instance, how might the properties of particular utility functions effect convergence rates or learning stability.\n\n- Section 3 states that each of the axioms are natural to impose, but I'm not sure I agree that the associativity axiom is all that natural for an online learner. Aggregation strategies which capture temporal locality will generally not satisfy this axiom. For instance, any weighted averaging or discounting schemes will generally not be associative. Yet handling \"local averages\" of this kind would be important to express attitudes related to temporal structure (e.g. learners which adapt to a non-stationary data sequence need to \"forget\" old data over time in order to track a time-varying solution). If such a fundamental consideration doesn't fit into the current set of axioms it makes me question whether these really are the \"right\" axioms for an online problem setting.\n\n- I'm not entirely sure I understand the value of developing an axiomatic characterization. I can glean bits and pieces from the exposition here (e.g., remark 4.10 discussing how the log-loss being seemingly fundamental for summation aggregation but not necessarily other types of aggregation). However, overall I felt that this motivation was not very well articulated throughout the paper, and I came away without a clear vision of why I should want to start from axioms rather than just starting from the performance measure that I care about (e.g., regret, weighted regret, etc), as one usually would in online learning.\n\n- I found the general layout and development of the paper a bit puzzling. It felt like many versions of the same results were being repeated with only minor variations (e.g. Corollaries 4.1, 4.5, 4.8, Lemma 4.4, all seem like they're all showing minor variations of the same result).\n\n**Questions**\n- Is the utility of these quasi-sums firmly affixed to the LEA setting, or do you expect that the techniques here could be similarly applied to reason about different ways of aggregating losses in OLO? i.e. FTRL can be viewed as doing a sort of loss aggregation, by setting $w_{t+1}=\\nabla\\psi^*(-\\sum_{s=1}^tg_s)$, which is related to regret in terms of cumulative loss. \n- Are there any interesting implications for strongly-adaptive/dynamic regret? For instance, the fixed-share algorithm is able to achieve nice regret guarantees on every sub-interval when considering mixable losses (see e.g. the second edition of Hazan's text). Perhaps something interesting could be said by considering more general aggregations.\n- Since the goal is to develop an axiomatic view, can it be shown that the set of proposed axioms is a minimal characterization of these quasi-sums?\n- What is the inherent value of developing an axiomatic approach?\n\n**Minor Typos**\n- p5/6: \"why does a loss distortion can be translated into a change of aggregation\", \"on this way\", \"For the sake of the moment\"\n- eq (2) the logarithm is seemingly in base $e^{-\\eta}$?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a generalization of Vovk's Aggregating Algorithm in the context of online learning with expert advice. The key contribution is the introduction of quasi-sum aggregation functions of the form $$Q_u(x_1,\\ldots,x_n)=u^{-1}\\left(\\sum_iu(x_i)\\right),$$ which generalizes the usual additive loss aggregation used by the classic aggregating algorithm. A generalized form of mixability is introduced to handle non-linear aggregations of the losses. The analysis captures the existing guarantees as a special case, while enabling more general expressions of a learner's risk attitude.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My main requests would be a more thorough discussion of the related prior works mentioned in the previous section, some additional discussion about the possible limitations of the axioms explored here (e.g. inability to capture temporal locality), and some additional motivation for why an axiomatic perspective is inherently valuable or desirable", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7dEgwbJDCH", "reviewer": "Reviewer_TTUp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### **Strengths**\n\n1. **Novelty and Rigor**  \n   The paper introduces an innovative axiomatic framework for generalizing loss aggregation functions in online learning, expanding beyond traditional summation methods. The theoretical contributions, including the characterization of quasi-sums and the derivation of regret bounds, are mathematically rigorous and demonstrate originality.\n\n2. **Clarity of Examples**  \n   Including examples, such as the weather prediction task, effectively bridges the gap between theoretical concepts and their practical implications. These examples help clarify the proposed approach and illustrate its potential utility in real-world scenarios.\n\n3. **Expansion of the Aggregating Algorithm (AA) Framework**  \n   The paper broadens its applicability to a wider range of learning scenarios by systematically integrating quasi-sum aggregation functions into the AA framework. This added flexibility makes adapting the AA for different loss structures possible, enhancing its practical relevance.\n\n4. **Potential for Practical Insights**  \n   The framework introduces the idea of weighting profiles and utility functions, offering a new perspective on learner attitudes (e.g., risk aversion or risk-seeking behavior). This interpretive layer adds depth and could inspire further research on tailoring online learning algorithms to specific applications.\n\n---\n\n### **Weaknesses**\n\n1. **Lack of Motivation**  \n   The introduction does not clearly explain why the problem addressed by this paper is important. For instance:\n   - The abrupt statement *\"However, an axiomatical approach to generalized loss aggregations remained within the borders of offline learning\"* lacks context on the necessity of extending such approaches to online learning.\n   - The importance of \"learning under expert advice\" is mentioned without explaining its relevance in the broader context of online learning challenges.  \n   A stronger narrative explaining the practical and theoretical importance of this work would significantly improve its impact.\n\n2. **Insufficient Discussion of Related Work**  \n   The paper does not adequately position itself within the existing literature. For example, the tilted empirical risk minimization framework (the following [1]) offers a related approach to replacing traditional summation, but the connection to this work is not discussed.\n\n3. **Limited Background and Context**  \n   The paper would benefit from a more detailed explanation of online learning, its inherent challenges, and why alternative loss aggregation functions are needed. A robust background section would help readers understand the significance of quasi-sums and their potential impact.\n\n4. **Narrow Experimental Scope**  \n   The empirical validation relies solely on a weather prediction dataset, which is insufficient to demonstrate the generalizability of the approach. Broader experiments across diverse tasks and datasets would:\n   - Highlight the practical relevance of the proposed framework.\n   - Provide stronger evidence for the claims about the impact of different aggregation functions on learner behavior.\n\n5. **Computational Challenges**  \n   The substitution step of the Aggregating Algorithm introduces a potential computational bottleneck, particularly in high-dimensional settings. While this issue is mentioned, the paper does not propose strategies to address it, which limits its practical applicability in complex tasks.\n\n---\n\n### **References**\n\n[1] Li T, Beirami A, Sanjabi M, et al. *On tilted losses in machine learning: Theory and applications*. Journal of Machine Learning Research, 2023, 24(142): 1-79.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a novel approach to generalizing loss aggregation functions through the use of quasi-sums, integrating them into the well-established Aggregating Algorithm (AA) framework. \n\nWhile the method essentially adapts AA to a new loss function, the axiomatic characterization of loss aggregation functions and the derivation of regret bounds for quasi-sums are both well-justified and mathematically rigorous. \n\nThe paper is mostly well-organized, and examples like weather prediction help illustrate the theoretical concepts.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "#### **Critical Adjustments**\n\n1. **Motivation and Background**\n   - Expand the introduction to clearly articulate the significance of the problem being addressed. Specifically:\n     - Justify why alternative loss aggregation methods are necessary in online learning compared to traditional risk minimization approaches.\n     - Explain the importance of transitioning from offline to online settings and why this generalization matters for practice.\n     - Address the abrupt transition to \"learning under expert advice\" and provide context for its relevance.\n   - Add more background on online learning to help readers understand why new loss functions, such as quasi-sums, are beneficial.\n\n2. **Discussion of Related Work**\n   - Provide a detailed comparison with existing works, particularly the **tilted empirical risk minimization** framework ([1]) and other relevant methods.\n     - Discuss similarities, differences, and complementary aspects of these approaches.\n     - Explain the advantages of the proposed framework over these methods, particularly in terms of regret bounds and applicability to online learning.\n\n3. **Clarity of Theoretical Contributions**\n   - Elaborate on the differences between the axiomatic approaches to loss aggregation in offline and online learning, as implied in Section 3.1. This distinction is crucial for understanding the novelty and significance of the proposed method.\n   - Provide more intuitive explanations or diagrams for dense sections, such as the generalization of mixability constants.\n\n4. **Experimental Validation**\n   - Expand the empirical study to include multiple datasets and tasks, especially those with diverse loss distributions and real-world challenges.\n   - Perform a more rigorous analysis of the experimental results, including statistical evaluations to substantiate claims about learner attitudes (e.g., risk-averse vs. risk-seeking behaviors).\n\n#### **Non-Critical Adjustments**\n\n1. **Computational Implications**\n   - Address the computational bottlenecks of the substitution step, especially in high-dimensional settings. While not critical, proposing strategies to mitigate these issues would enhance the practical applicability of the method.\n\n2. **Empirical Comparisons**\n   - Include empirical comparisons with other online learning methods, such as the weighted majority algorithm, to provide a clearer picture of the framework's performance.", "broader_impact_concerns": "N/A/", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xP3WKc7Jkd", "reviewer": "Reviewer_8nXn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. The idea of considering a general aggregated loss seems to be original in the context of online learning.\n2. The technical result in Corollary 4.1 appears to be interesting, although the proof is relatively simple.\n\n**Weaknesses**\n\n1. (Major) While the philosophical message of the paper is appreciated, I find the technical contribution unclear. It is not evident which result constitutes the main contribution. Is it Corollary 4.1? I recommend that the authors clearly highlight their main result in a \"Theorem\" environment, rather than relegating it to a lemma or corollary.\n\n2. (Major) The technical results in Sections 4.1–4.3 appear to be restatements of Corollary 4.1. Can the authors clarify the purpose of introducing another operator $\\mathbf{A}$ and function $f$, especially given that on page 9, it is mentioned that these can be converted to $\\mathbf{Q}$ by setting $f = e^{-u}$? Isn't this tautological?\n\n3. (Major) The experimental section (Section 5) is poorly presented. Can you specify the loss function $\\lambda$ used and provide details on how the algorithm is implemented? Additionally, what is the purpose of studying the histogram of losses when the objectives differ (i.e., when using different $u$)?\n\n4. (Minor) Can you instantiate your results for specific examples, such as particular choices of $u$, $\\lambda$, $\\Omega$, or $\\Theta$? This would help readers better understand the differences compared to classical results.\n\n5. (Minor) What are the differences between the notations $\\mathbf{Q}_n^u$, $\\mathbf{Q}_n$, and $\\mathbf{Q}^u$? Please clarify this in the paper.\n\n\n**Overall:** At this point, I am not convinced that this work represents a meaningful contribution to TMLR. However, I would be willing to reconsider my recommendation if the authors address the concerns outlined above.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of learning from expert advice by considering more general aggregation of the losses. Specifically, suppose a learner incurs losses $l_1, \\cdots, l_T$. In the classical setting, the risk is simply computed as the sum $\\sum_{t=1}^T l_t$, which serves as the objective for optimization. Instead, this paper considers an objective of the form $u^{-1}(\\sum_{t=1}^T u(l_t))$, where $u$ is a general function. The paper shows that one can still bound the aggregated loss by running Vovk's Aggregation Algorithm on the composite loss $u \\circ \\lambda$, where $\\lambda$ is the original loss that induces the $l_t$ values.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)