Maxwell Fishelson
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Maxwell Fishelson has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
Constantinos Daskalakis
MIT, Cambridge, MA 02139 USA and Archimedes AI, Marousi, Greece
2 shared publications- Constantinos Daskalakis
Massachusetts Institute of Technology, Cambridge, USA
2 shared publications - Noah Golowich
Massachusetts Institute of Technology, Cambridge, USA
2 shared publications - Yuval Dagan
Tel Aviv University, Tel Aviv, Israel
2 shared publications - Charilaos Pipis
Massachusetts Institute of Technology, Cambridge, USA
1 shared publication - Gabriele Farina
Massachusetts Institute of Technology
1 shared publication
Latest Publications
- 3 November 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- p. STOC25-95
Breaking the \({T^{2/3}}\) Barrier for Sequential CalibrationA set of probabilistic forecasts is calibrated if each prediction of the forecaster closely approximates the empirical distribution of outcomes on the subset of time steps where that prediction was made. We study the fundamental problem of online calibrated forecasting of binary sequences under the standard [Formula: see text] calibration error metric, which was initially studied by [D. P. Foster and R. V. Vohra, Biometrika, 85 (1998), pp. 379–390]. They derived an algorithm with [Formula: see text] calibration error after [Formula: see text] time steps, and showed a lower bound of [Formula: see text]. These bounds remained stagnant for two decades, until [ 30 ] improved the lower bound to [Formula: see text] by introducing a combinatorial game called sign preservation and showing that lower bounds for this game imply lower bounds for calibration. In this paper, we give the first improvement to the [Formula: see text] upper bound on calibration error of [ D. P. Foster and R. V. Vohra, Biometrika, 85 (1998), pp. 379–390 ]. We do this by introducing a variant of [M. Qiao and G. Valiant, STOC 2021, ACM, New York, 2021, pp. 456–466]’s game that we call sign preservation with reuse (SPR). We prove that the relationship between SPR and calibrated forecasting is bidirectional: not only do lower bounds for SPR translate into lower bounds for calibration, but algorithms for SPR also translate into new algorithms for calibrated forecasting. We then give an improved upper bound for the SPR game, which implies, via our equivalence, a forecasting algorithm with calibration error [Formula: see text] for some [Formula: see text], improving [ D. P. Foster and R. V. Vohra, Biometrika, 85 (1998), pp. 379–390 ]’s upper bound for the first time. Using similar ideas, we then prove a slightly stronger lower bound than that of [ M. Qiao and G. Valiant, STOC 2021, ACM, New York, 2021, pp. 456–466 ], namely [Formula: see text]. Our lower bound is obtained by an oblivious adversary, marking the first [Formula: see text] calibration lower bound for oblivious adversaries.
- 3 November 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- p. STOC25-95
Breaking the \({T^{2/3}}\) Barrier for Sequential CalibrationA set of probabilistic forecasts is calibrated if each prediction of the forecaster closely approximates the empirical distribution of outcomes on the subset of time steps where that prediction was made. We study the fundamental problem of online calibrated forecasting of binary sequences under the standard [Formula: see text] calibration error metric, which was initially studied by [D. P. Foster and R. V. Vohra, Biometrika, 85 (1998), pp. 379–390]. They derived an algorithm with [Formula: see text] calibration error after [Formula: see text] time steps, and showed a lower bound of [Formula: see text]. These bounds remained stagnant for two decades, until [ 30 ] improved the lower bound to [Formula: see text] by introducing a combinatorial game called sign preservation and showing that lower bounds for this game imply lower bounds for calibration. In this paper, we give the first improvement to the [Formula: see text] upper bound on calibration error of [ D. P. Foster and R. V. Vohra, Biometrika, 85 (1998), pp. 379–390 ]. We do this by introducing a variant of [M. Qiao and G. Valiant, STOC 2021, ACM, New York, 2021, pp. 456–466]’s game that we call sign preservation with reuse (SPR). We prove that the relationship between SPR and calibrated forecasting is bidirectional: not only do lower bounds for SPR translate into lower bounds for calibration, but algorithms for SPR also translate into new algorithms for calibrated forecasting. We then give an improved upper bound for the SPR game, which implies, via our equivalence, a forecasting algorithm with calibration error [Formula: see text] for some [Formula: see text], improving [ D. P. Foster and R. V. Vohra, Biometrika, 85 (1998), pp. 379–390 ]’s upper bound for the first time. Using similar ideas, we then prove a slightly stronger lower bound than that of [ M. Qiao and G. Valiant, STOC 2021, ACM, New York, 2021, pp. 456–466 ], namely [Formula: see text]. Our lower bound is obtained by an oblivious adversary, marking the first [Formula: see text] calibration lower bound for oblivious adversaries.
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 542-553
Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 542-553
Open AccessEfficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2007-2018
Breaking the T^(2/3) Barrier for Sequential Calibration
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2007-2018
Open AccessBreaking the T^(2/3) Barrier for Sequential Calibration
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1216-1222
From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces
We provide a novel reduction from swap-regret minimization to external-regret minimization, which improves upon the classical reductions of Blum-Mansour and Stoltz-Lugosi in that it does not require finiteness of the space of actions. We show that, whenever there exists a no-external-regret algorithm for some hypothesis class, there must also exist a no-swap-regret algorithm for that same class. For the problem of learning with expert advice, our result implies that it is possible to guarantee that the swap regret is bounded by є after (logN)Õ(1/є) rounds and with O(N) per iteration complexity, where N is the number of experts, while the classical reductions of Blum-Mansour and Stoltz-Lugosi require at least Ω(N/є2) rounds and at least Ω(N3) total computational cost. Our result comes with an associated lower bound, which—in contrast to that of Blum-Mansour—holds for oblivious and ℓ1-constrained adversaries and learners that can employ distributions over experts, showing that the number of rounds must be Ω(N/є2) or exponential in 1/є. Our reduction implies that, if no-regret learning is possible in some game, then this game must have approximate correlated equilibria, of arbitrarily good approximation. This strengthens the folklore implication of no-regret learning that approximate coarse correlated equilibria exist. Importantly, it provides a sufficient condition for the existence of approximate correlated equilibrium which vastly extends the requirement that the action set is finite or the requirement that the action set is compact and the utility functions are continuous, allowing for games with finite Littlestone or finite sequential fat shattering dimension, thus answering a question left open in “Fast rates for nonparametric online learning: from realizability to learning in games” and “ Online learning and solving infinite games with an ERM oracle”. Moreover, it answers several outstanding questions about equilibrium computation and/or learning in games. In particular, for constant values of є: (a) we show that є-approximate correlated equilibria in extensive-form games can be computed efficiently, advancing a long-standing open problem for extensive-form games; see e.g. “ Extensive-form correlated equilibrium: Definition and computational complexity” and “ Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games”; (b) we show that the query and communication complexities of computing є-approximate correlated equilibria in N-action normal-form games are N · poly log(N) and poly logN respectively, advancing an open problem of “Informational Bounds on Equilibria”; (c) we show that є-approximate correlated equilibria of sparsity poly logN can be computed efficiently, advancing an open problem of “Simple Approximate Equilibria in Large Games”; (d) finally, we show that in the adversarial bandit setting, sublinear swap regret can be achieved in only Õ(N) rounds, advancing an open problem of “From External to Internal Regret” and “Tight Lower Bound and Efficient Reduction for Swap Regret”.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1216-1222
Open AccessFrom External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces
We provide a novel reduction from swap-regret minimization to external-regret minimization, which improves upon the classical reductions of Blum-Mansour and Stoltz-Lugosi in that it does not require finiteness of the space of actions. We show that, whenever there exists a no-external-regret algorithm for some hypothesis class, there must also exist a no-swap-regret algorithm for that same class. For the problem of learning with expert advice, our result implies that it is possible to guarantee that the swap regret is bounded by є after (logN)Õ(1/є) rounds and with O(N) per iteration complexity, where N is the number of experts, while the classical reductions of Blum-Mansour and Stoltz-Lugosi require at least Ω(N/є2) rounds and at least Ω(N3) total computational cost. Our result comes with an associated lower bound, which—in contrast to that of Blum-Mansour—holds for oblivious and ℓ1-constrained adversaries and learners that can employ distributions over experts, showing that the number of rounds must be Ω(N/є2) or exponential in 1/є. Our reduction implies that, if no-regret learning is possible in some game, then this game must have approximate correlated equilibria, of arbitrarily good approximation. This strengthens the folklore implication of no-regret learning that approximate coarse correlated equilibria exist. Importantly, it provides a sufficient condition for the existence of approximate correlated equilibrium which vastly extends the requirement that the action set is finite or the requirement that the action set is compact and the utility functions are continuous, allowing for games with finite Littlestone or finite sequential fat shattering dimension, thus answering a question left open in “Fast rates for nonparametric online learning: from realizability to learning in games” and “ Online learning and solving infinite games with an ERM oracle”. Moreover, it answers several outstanding questions about equilibrium computation and/or learning in games. In particular, for constant values of є: (a) we show that є-approximate correlated equilibria in extensive-form games can be computed efficiently, advancing a long-standing open problem for extensive-form games; see e.g. “ Extensive-form correlated equilibrium: Definition and computational complexity” and “ Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games”; (b) we show that the query and communication complexities of computing є-approximate correlated equilibria in N-action normal-form games are N · poly log(N) and poly logN respectively, advancing an open problem of “Informational Bounds on Equilibria”; (c) we show that є-approximate correlated equilibria of sparsity poly logN can be computed efficiently, advancing an open problem of “Simple Approximate Equilibria in Large Games”; (d) finally, we show that in the adversarial bandit setting, sublinear swap regret can be achieved in only Õ(N) rounds, advancing an open problem of “From External to Internal Regret” and “Tight Lower Bound and Efficient Reduction for Swap Regret”.