Locally Adaptive Multi-Objective Learning

AI summary

Overview

• Research area: Online learning and multi-objective learning, with applications to algorithmic fairness (multiaccuracy), electricity load forecasting, and quantile/coverage estimation under distribution shift.
• Technical level: Advanced. The theoretical sections rely on minimax prediction, Blackwell approachability-style game formulations, adaptive regret, and regret bounds; the motivating intuition and the algorithmic recipe are nevertheless accessible.
• Scope: The paper proposes a meta-algorithm for online multi-objective learning that is locally adaptive over time intervals, proves a local error bound for it, and empirically compares it against prior adaptive multi-objective proposals on energy forecasting and recidivism prediction.

What This Paper Is About

When a predictor must simultaneously satisfy many objectives (such as being unbiased with respect to many subgroups, or being well calibrated), existing online algorithms typically minimize the worst-case objective over the entire time horizon, so they do not react when the data distribution shifts partway through. The paper's goal is to produce a predictor whose multi-objective error stays small not just averaged over all T rounds, but over every contiguous local subinterval, while still remaining as accurate as a given baseline forecaster.

Key Contributions

1. An alternative route to local adaptivity. Rather than augmenting the objective set with indicators for all contiguous subintervals (the approach of Lee et al. (2022)), the authors keep the objective set fixed and replace the Hedge weight-update inside the multi-objective learning scheme with an adaptive online learning method. A general meta-algorithm is given that takes any such method as input.
2. A concrete instantiation with theory. The paper instantiates the meta-algorithm with the Fixed Share method (Herbster and Warmuth, 1998) and proves a local bound: over any interval I of a user-chosen target width τ, the worst-case objective is bounded by O(sqrt(log(|L|·τ)/τ)). Fixed Share is chosen specifically because it guarantees adaptivity over intervals of a fixed target width, and because of its strong empirical performance.
3. Closing the empirical gap. The authors state that empirical evaluation of these adaptive multi-objective proposals is scarce, and they provide experiments on electricity demand forecasting and recidivism prediction, releasing a public codebase.
4. A concrete objective design for multiaccuracy. The paper shows why a prediction-error objective must be included alongside the multiaccuracy objectives: without it, the minimax program collapses to predicting only the extreme values of the label interval.

Main Findings

• Local adaptivity beats global multi-objective learning under shift. On the GEFCom2014-L electric load forecasting dataset, the proposed locally adaptive algorithm's multiaccuracy error, plotted as a weekly (168-hourly) moving average, stays close to zero across all time intervals, while a non-adaptive multiaccuracy variant shows much larger errors at many time points.
• Worst-case objective bound, localized. Theorem 2 bounds the max over objectives of the average loss on any interval I by a term depending on the Fixed Share hyperparameters γ and η; choosing γ = 1/(2|I|) and the stated optimal η gives O(sqrt(log(|L|·|I|)/|I|)) per-round on that interval, a smaller, interval-independent quantity than the method's global bound.
• A single, non-interval-specific parameter setting is used in practice. Because one cannot tune γ and η for each interval separately, the user picks a target width τ; a smaller τ gives stronger local guarantees at the cost of a looser bound. Since the optimal η depends on unknown expected squared losses, the paper follows Gibbs and Candès (2024) and uses an online-updated η that tracks the moving average of squared loss over the most recent τ steps.
• Comparison to the prior adaptive proposal. Lee et al. (2022) expand the objective set to L_adapt. and obtain a local bound of O(sqrt(T(log|L| + log T))); the paper holds the objective set fixed instead.
• Multiaccuracy is relative to a baseline. The algorithm is designed to keep prediction error (measured against a pre-existing baseline predictor sequence via a proper loss such as squared error/Brier score) low while achieving small multiaccuracy error, rather than improving multiaccuracy at the cost of forecasting usefulness.
• Multicalibration alone is slow here. Although multicalibration is a stronger condition (the paper notes ℓ_MA ≤ m·ℓ_MC + 1/(2m)), the authors report that in practice existing online multicalibration algorithms achieve multiaccuracy only at relatively slow rates, and that adaptive extensions of multicalibration improve local multiaccuracy error but cannot close that gap.
• Empirical scope. Across all benchmarks in the paper, the proposed method is reported to consistently outperform the prior proposals of Lee et al. (2022); the available content does not report the specific numeric error values for the individual experiments.

Methodology in Plain English

The setup is a two-player game played over T rounds. At each round the learner sees features x_t and must output a prediction; an adversary holds a set of weights, one per objective. The learner picks the prediction that minimizes the adversary's weighted mixture of objectives against the worst possible label, and only then is the true label revealed. The adversary's weights then move toward whichever objective is doing badly.

In the prior work, the adversary updates weights with Hedge, which produces good guarantees averaged over the whole run but not over short stretches. The authors' change is surgical: keep the learner's step identical and swap the weight update for Fixed Share, which mixes the Hedge update with a small uniform exploration term so that no weight collapses to zero. This exploration is what allows the scheme to recover quickly after the environment changes. They prove two lemmas — one bounding how much the weighted mixture can undershoot the worst individual objective on an interval, and one showing the mixture loss is non-positive on any interval because of the learner's minimax choice — and combine them into the main interval bound. They then instantiate the framework twice: once for multiaccurate mean estimation (multiaccuracy objectives plus a prediction-error objective) and once for multiaccurate quantile estimation (coverage objectives at level α plus a pinball-loss objective relative to baseline quantile predictions). Experiments apply the mean-estimation version to electricity load data and to recidivism prediction over time.

Why This Matters

• Research impact: The paper gives a general recipe — swap the no-regret routine inside a multi-objective scheme for an adaptive one — that applies beyond multiaccuracy to multi-group learning and omniprediction, and it supplies the missing empirical evaluation for locally adaptive multi-objective learning.
• Electricity demand forecasting: Deciding whether hourly load exceeds a threshold, multiaccurate with respect to temperature bands, so that predictions remain trustworthy across times of day and seasons.
• Algorithmic fairness in risk prediction: Removing bias from baseline recidivism predictors across subgroups as the population being scored shifts over time.
• Quantile and coverage forecasting: Producing prediction intervals whose coverage rate matches a target level α locally, not merely on average over the whole deployment.
• Industry relevance: Deployed prediction systems face feedback loops, policy changes, and exogenous shocks; methods that only guarantee good performance averaged over all history can silently degrade, so interval-level guarantees are directly relevant to monitoring and retraining decisions in real-time decision-making.

Future Directions

• Substituting other adaptive online learners for Fixed Share: the authors explicitly note that strongly adaptive procedures (Daniely et al., 2015; Jun et al., 2017), which give bounds depending on the interval width |I| for all intervals, are an untried alternative instantiation.
• The choice of the target interval width τ is left to the user and trades off the strength of the guarantee against how loose the bound is; how best to select τ, or to adapt it, is not resolved.
• When no baseline predictor p̃_t(x_t) is available in advance, the authors recommend pairing the procedure with a standard online learner such as online gradient or mirror descent (Algorithm 5 in the appendix), but the behavior of that combination is not the paper's focus.
• The available content does not report the concrete empirical error values behind the qualitative claims, nor the details of the recidivism experiments, leaving room for fuller empirical characterization.

Target Audience

Researchers and graduate students working on online learning, multi-objective learning, multicalibration and multiaccuracy, and distribution-shift robustness, as well as applied machine learning practitioners who deploy predictors in non-stationary environments (energy forecasting, fairness auditing of risk-scoring systems, quantile forecasting) and need interval-level rather than whole-run guarantees. Readers should be comfortable with minimax formulations, regret bounds, and the standard notation of online learning; those mainly interested in the high-level algorithmic idea can read the introduction and results figures alone.

Authors’ abstract

We consider the general problem of learning a predictor that satisfies multiple objectives of interest simultaneously, a broad framework that captures a range of specific learning goals including calibration, regret, and multiaccuracy. We work in an online setting where the data distribution can change arbitrarily over time. Existing approaches to this problem aim to minimize the set of objectives over the entire time horizon in a worst-case sense, and in practice they do not necessarily adapt to distribution shifts. Earlier work has aimed to alleviate this problem by incorporating additional objectives that target local guarantees over contiguous subintervals. Empirical evaluation of these proposals is, however, scarce. In this article, we consider an alternative procedure that achieves local adaptivity by replacing one part of the multi-objective learning method with an adaptive online algorithm. Empirical evaluations on datasets from energy forecasting and algorithmic fairness show that our proposed method improves upon existing approaches and achieves unbiased predictions over subgroups, while remaining robust under distribution shift.