@article{18584, abstract = {In this paper, we describe the "Medium Bands, Mega Science" JWST Cycle 2 survey (JWST-GO-4111) and demonstrate the power of these data to reveal both the spatially integrated and spatially resolved properties of galaxies from the local Universe to the era of cosmic dawn. Executed in 2023 November, MegaScience obtained ∼30 arcmin2 of deep multiband NIRCam imaging centered on the z ∼ 0.3 A2744 cluster, including 11 medium-band filters and the two shortest-wavelength broadband filters, F070W and F090W. Together, MegaScience and the UNCOVER Cycle 1 treasury program provide a complete set of deep (∼28–30 magAB) images in all NIRCam medium- and broadband filters. This unique data set allows us to precisely constrain photometric redshifts, map stellar populations and dust attenuation for large samples of distant galaxies, and examine the connection between galaxy structures and formation histories. MegaScience also includes ∼17 arcmin2 of NIRISS parallel imaging in two broadband and four medium-band filters from 0.9 to 4.8 μm, expanding the footprint where robust spectral energy distribution (SED) fitting is possible. We provide example SEDs and multiband cutouts at a variety of redshifts, and use a catalog of JWST spectroscopic redshifts to show that MegaScience improves both the scatter and catastrophic outlier rate of photometric redshifts by factors of 2–3. Additionally, we demonstrate the spatially resolved science enabled by MegaScience by presenting maps of the [O iii] line emission and continuum emission in three spectroscopically confirmed z > 6 galaxies. We show that line emission in reionization-era galaxies can be clumpy, extended, and spatially offset from continuum emission, implying that galaxy assembly histories are complex even at these early epochs. We publicly release fully reduced mosaics and photometric catalogs for both the NIRCam primary and NIRISS parallel fields (jwst-uncover.github.io/megascience).}, author = {Suess, Katherine A. and Weaver, John R. and Price, Sedona H. and Pan, Richard and Wang, Bingjie and Bezanson, Rachel and Brammer, Gabriel and Cutler, Sam E. and Labbé, Ivo and Leja, Joel and Williams, Christina C. and Whitaker, Katherine E. and Atek, Hakim and Dayal, Pratika and De Graaff, Anna and Feldmann, Robert and Franx, Marijn and Fudamoto, Yoshinobu and Fujimoto, Seiji and Furtak, Lukas J. and Goulding, Andy D. and Greene, Jenny E. and Khullar, Gourav and Kokorev, Vasily and Kriek, Mariska and Lorenz, Brian and Marchesini, Danilo and Maseda, Michael V. and Matthee, Jorryt J and Miller, Tim B. and Mitsuhashi, Ikki and Mowla, Lamiya A. and Muzzin, Adam and Naidu, Rohan P. and Nanayakkara, Themiya and Nelson, Erica J. and Oesch, Pascal A. and Setton, David J. and Shipley, Heath and Smit, Renske and Spilker, Justin S. and Van Dokkum, Pieter and Zitrin, Adi}, issn = {1538-4357}, journal = {Astrophysical Journal}, number = {1}, publisher = {IOP Publishing}, title = {{Medium bands, mega science: A JWST/NIRCam medium-band imaging survey of A2744}}, doi = {10.3847/1538-4357/ad75fe}, volume = {976}, year = {2024}, } @inproceedings{18996, abstract = {We consider the linear causal representation learning setting where we observe a linear mixing of d unknown latent factors, which follow a linear structural causal model. Recent work has shown that it is possible to recover the latent factors as well as the underlying structural causal model over them, up to permutation and scaling, provided that we have at least d environments, each of which corresponds to perfect interventions on a single latent node (factor). After this powerful result, a key open problem faced by the community has been to relax these conditions: allow for coarser than perfect single-node interventions, and allow for fewer than d of them, since the number of latent factors d could be very large. In this work, we consider precisely such a setting, where we allow a smaller than d number of environments, and also allow for very coarse interventions that can very coarsely \textit{change the entire causal graph over the latent factors}. On the flip side, we relax what we wish to extract to simply the \textit{list of nodes that have shifted between one or more environments}. We provide a surprising identifiability result that it is indeed possible, under some very mild standard assumptions, to identify the set of shifted nodes. Our identifiability proof moreover is a constructive one: we explicitly provide necessary and sufficient conditions for a node to be a shifted node, and show that we can check these conditions given observed data. Our algorithm lends itself very naturally to the sample setting where instead of just interventional distributions, we are provided datasets of samples from each of these distributions. We corroborate our results on both synthetic experiments as well as an interesting psychometric dataset. The code can be found at https://github.com/TianyuCodings/iLCS.}, author = {Chen, Tianyu and Bello, Kevin and Locatello, Francesco and Aragam, Bryon and Ravikumar, Pradeep Kumar}, booktitle = {38th Conference on Neural Information Processing Systems}, issn = {1049-5258}, location = {Vancouver, Canada}, publisher = {Neural Information Processing Systems Foundation}, title = {{Identifying general mechanism shifts in linear causal representations}}, doi = {10.52202/079017-1343}, volume = {37}, year = {2024}, } @article{14451, abstract = {We investigate the potential of Multi-Objective, Deep Reinforcement Learning for stock and cryptocurrency single-asset trading: in particular, we consider a Multi-Objective algorithm which generalizes the reward functions and discount factor (i.e., these components are not specified a priori, but incorporated in the learning process). Firstly, using several important assets (BTCUSD, ETHUSDT, XRPUSDT, AAPL, SPY, NIFTY50), we verify the reward generalization property of the proposed Multi-Objective algorithm, and provide preliminary statistical evidence showing increased predictive stability over the corresponding Single-Objective strategy. Secondly, we show that the Multi-Objective algorithm has a clear edge over the corresponding Single-Objective strategy when the reward mechanism is sparse (i.e., when non-null feedback is infrequent over time). Finally, we discuss the generalization properties with respect to the discount factor. The entirety of our code is provided in open-source format.}, author = {Cornalba, Federico and Disselkamp, Constantin and Scassola, Davide and Helf, Christopher}, issn = {1433-3058}, journal = {Neural Computing and Applications}, number = {2}, pages = {617--637}, publisher = {Springer Nature}, title = {{Multi-objective reward generalization: Improving performance of Deep Reinforcement Learning for applications in single-asset trading}}, doi = {10.1007/s00521-023-09033-7}, volume = {36}, year = {2024}, } @article{17887, abstract = {We show convergence of the Navier-Stokes/Allen-Cahn system to a classical sharp interface model for the two-phase flow of two viscous incompressible fluids with same viscosities in a smooth bounded domain in two and three space dimensions as long as a smooth solution of the limit system exists. Moreover, we obtain error estimates with the aid of a relative entropy method. Our results hold provided that the mobility mε>0 in the Allen-Cahn equation tends to zero in a subcritical way, i.e., mε=m0εβ for some β∈(0,2) and m0>0 . The proof proceeds by showing via a relative entropy argument that the solution to the Navier-Stokes/Allen-Cahn system remains close to the solution of a perturbed version of the two-phase flow problem, augmented by an extra mean curvature flow term mεHΓt in the interface motion. In a second step, it is easy to see that the solution to the perturbed problem is close to the original two-phase flow.}, author = {Abels, Helmut and Fischer, Julian L and Moser, Maximilian}, issn = {1432-0673}, journal = {Archive for Rational Mechanics and Analysis}, number = {5}, publisher = {Springer Nature}, title = {{Approximation of classical two-phase flows of viscous incompressible fluids by a Navier–Stokes/Allen–Cahn system}}, doi = {10.1007/s00205-024-02020-9}, volume = {248}, year = {2024}, } @article{12485, abstract = {In this paper we introduce the critical variational setting for parabolic stochastic evolution equations of quasi- or semi-linear type. Our results improve many of the abstract results in the classical variational setting. In particular, we are able to replace the usual weak or local monotonicity condition by a more flexible local Lipschitz condition. Moreover, the usual growth conditions on the multiplicative noise are weakened considerably. Our new setting provides general conditions under which local and global existence and uniqueness hold. Moreover, we prove continuous dependence on the initial data. We show that many classical SPDEs, which could not be covered by the classical variational setting, do fit in the critical variational setting. In particular, this is the case for the Cahn-Hilliard equations, tamed Navier-Stokes equations, and Allen-Cahn equation.}, author = {Agresti, Antonio and Veraar, Mark}, issn = {1432-2064}, journal = {Probability Theory and Related Fields}, pages = {957--1015}, publisher = {Springer Nature}, title = {{The critical variational setting for stochastic evolution equations}}, doi = {10.1007/s00440-023-01249-x}, volume = {188}, year = {2024}, } @article{12178, abstract = {In this paper we consider the stochastic primitive equation for geophysical flows subject to transport noise and turbulent pressure. Admitting very rough noise terms, the global existence and uniqueness of solutions to this stochastic partial differential equation are proven using stochastic maximal L² regularity, the theory of critical spaces for stochastic evolution equations, and global a priori bounds. Compared to other results in this direction, we do not need any smallness assumption on the transport noise which acts directly on the velocity field and we also allow rougher noise terms. The adaptation to Stratonovich type noise and, more generally, to variable viscosity and/or conductivity are discussed as well.}, author = {Agresti, Antonio and Hieber, Matthias and Hussein, Amru and Saal, Martin}, issn = {2194-041X}, journal = {Stochastics and Partial Differential Equations: Analysis and Computations}, keywords = {Applied Mathematics, Modeling and Simulation, Statistics and Probability}, pages = {53--133}, publisher = {Springer Nature}, title = {{The stochastic primitive equations with transport noise and turbulent pressure}}, doi = {10.1007/s40072-022-00277-3}, volume = {12}, year = {2024}, } @article{17372, abstract = {In this paper, we investigate the global well-posedness of reaction-diffusion systems with transport noise on the d-dimensional torus. We show new global well-posedness results for a large class of scalar equations (e.g. the Allen-Cahn equation), and dissipative systems (e.g. equations in coagulation dynamics). Moreover, we prove global well-posedness for two weakly dissipative systems: Lotka-Volterra equations for d∈{1,2,3,4} and the Brusselator for d∈{1,2,3}. Many of the results are also new without transport noise. The proofs are based on maximal regularity techniques, positivity results, and sharp blow-up criteria developed in our recent works, combined with energy estimates based on Itô's formula and stochastic Gronwall inequalities. Key novelties include the introduction of new Lζ -coercivity/dissipativity conditions and the development of an Lp(Lq) -framework for systems of reaction-diffusion equations, which are needed when treating dimensions d∈{2,3} in the case of cubic or higher order nonlinearities.}, author = {Agresti, Antonio and Veraar, Mark}, issn = {1095-7154}, journal = {SIAM Journal on Mathematical Analysis}, number = {4}, pages = {4870--4927}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Reaction-diffusion equations with transport noise and critical superlinear diffusion: Global well-posedness of weakly dissipative systems}}, doi = {10.1137/23M1562482}, volume = {56}, year = {2024}, } @article{14884, abstract = {We perform a stochastic homogenization analysis for composite materials exhibiting a random microstructure. Under the assumptions of stationarity and ergodicity, we characterize the Gamma-limit of a micromagnetic energy functional defined on magnetizations taking value in the unit sphere and including both symmetric and antisymmetric exchange contributions. This Gamma-limit corresponds to a micromagnetic energy functional with homogeneous coefficients. We provide explicit formulas for the effective magnetic properties of the composite material in terms of homogenization correctors. Additionally, the variational analysis of the two exchange energy terms is performed in the more general setting of functionals defined on manifold-valued maps with Sobolev regularity, in the case in which the target manifold is a bounded, orientable smooth surface with tubular neighborhood of uniform thickness. Eventually, we present an explicit characterization of minimizers of the effective exchange in the case of magnetic multilayers, providing quantitative evidence of Dzyaloshinskii’s predictions on the emergence of helical structures in composite ferromagnetic materials with stochastic microstructure.}, author = {Davoli, Elisa and D’Elia, Lorenza and Ingmanns, Jonas}, issn = {1432-1467}, journal = {Journal of Nonlinear Science}, number = {2}, publisher = {Springer Nature}, title = {{Stochastic homogenization of micromagnetic energies and emergence of magnetic skyrmions}}, doi = {10.1007/s00332-023-10005-3}, volume = {34}, year = {2024}, } @inproceedings{19005, abstract = {Causal representation learning promises to extend causal models to hidden causal variables from raw entangled measurements. However, most progress has focused on proving identifiability results in different settings, and we are not aware of any successful real-world application. At the same time, the field of dynamical systems benefited from deep learning and scaled to countless applications but does not allow parameter identification. In this paper, we draw a clear connection between the two and their key assumptions, allowing us to apply identifiable methods developed in causal representation learning to dynamical systems. At the same time, we can leverage scalable differentiable solvers developed for differential equations to build models that are both identifiable and practical. Overall, we learn explicitly controllable models that isolate the trajectory-specific parameters for further downstream tasks such as out-of-distribution classification or treatment effect estimation. We experiment with a wind simulator with partially known factors of variation. We also apply the resulting model to real-world climate data and successfully answer downstream causal questions in line with existing literature on climate change. Code is available at https://github.com/CausalLearningAI/crl-dynamical-systems.}, author = {Yao, Dingling and Muller, Caroline J and Locatello, Francesco}, booktitle = {38th Conference on Neural Information Processing Systems}, issn = {1049-5258}, location = {Vancouver, Canada}, publisher = {Neural Information Processing Systems Foundation}, title = {{Marrying causal representation learning with dynamical systems for science}}, doi = {10.52202/079017-2290}, volume = {37}, year = {2024}, } @article{13129, abstract = {We study the representative volume element (RVE) method, which is a method to approximately infer the effective behavior ahom of a stationary random medium. The latter is described by a coefficient field a(x) generated from a given ensemble ⟨⋅⟩ and the corresponding linear elliptic operator −∇⋅a∇. In line with the theory of homogenization, the method proceeds by computing d=3 correctors (d denoting the space dimension). To be numerically tractable, this computation has to be done on a finite domain: the so-called representative volume element, i.e., a large box with, say, periodic boundary conditions. The main message of this article is: Periodize the ensemble instead of its realizations. By this, we mean that it is better to sample from a suitably periodized ensemble than to periodically extend the restriction of a realization a(x) from the whole-space ensemble ⟨⋅⟩. We make this point by investigating the bias (or systematic error), i.e., the difference between ahom and the expected value of the RVE method, in terms of its scaling w.r.t. the lateral size L of the box. In case of periodizing a(x), we heuristically argue that this error is generically O(L−1). In case of a suitable periodization of ⟨⋅⟩ , we rigorously show that it is O(L−d). In fact, we give a characterization of the leading-order error term for both strategies and argue that even in the isotropic case it is generically non-degenerate. We carry out the rigorous analysis in the convenient setting of ensembles ⟨⋅⟩ of Gaussian type, which allow for a straightforward periodization, passing via the (integrable) covariance function. This setting has also the advantage of making the Price theorem and the Malliavin calculus available for optimal stochastic estimates of correctors. We actually need control of second-order correctors to capture the leading-order error term. This is due to inversion symmetry when applying the two-scale expansion to the Green function. As a bonus, we present a stream-lined strategy to estimate the error in a higher-order two-scale expansion of the Green function.}, author = {Clozeau, Nicolas and Josien, Marc and Otto, Felix and Xu, Qiang}, issn = {1615-3383}, journal = {Foundations of Computational Mathematics}, pages = {1305--1387}, publisher = {Springer Nature}, title = {{Bias in the representative volume element method: Periodize the ensemble instead of its realizations}}, doi = {10.1007/s10208-023-09613-y}, volume = {24}, year = {2024}, } @article{12486, abstract = {This paper is concerned with the problem of regularization by noise of systems of reaction–diffusion equations with mass control. It is known that strong solutions to such systems of PDEs may blow-up in finite time. Moreover, for many systems of practical interest, establishing whether the blow-up occurs or not is an open question. Here we prove that a suitable multiplicative noise of transport type has a regularizing effect. More precisely, for both a sufficiently noise intensity and a high spectrum, the blow-up of strong solutions is delayed up to an arbitrary large time. Global existence is shown for the case of exponentially decreasing mass. The proofs combine and extend recent developments in regularization by noise and in the Lp(Lq)-approach to stochastic PDEs, highlighting new connections between the two areas.}, author = {Agresti, Antonio}, issn = {2194-041X}, journal = {Stochastics and Partial Differential Equations: Analysis and Computations}, pages = {1907--1981}, publisher = {Springer Nature}, title = {{Delayed blow-up and enhanced diffusion by transport noise for systems of reaction-diffusion equations}}, doi = {10.1007/s40072-023-00319-4}, volume = {12}, year = {2024}, } @article{14797, abstract = {We study a random matching problem on closed compact 2 -dimensional Riemannian manifolds (with respect to the squared Riemannian distance), with samples of random points whose common law is absolutely continuous with respect to the volume measure with strictly positive and bounded density. We show that given two sequences of numbers n and m=m(n) of points, asymptotically equivalent as n goes to infinity, the optimal transport plan between the two empirical measures μn and νm is quantitatively well-approximated by (Id,exp(∇hn))#μn where hn solves a linear elliptic PDE obtained by a regularized first-order linearization of the Monge-Ampère equation. This is obtained in the case of samples of correlated random points for which a stretched exponential decay of the α -mixing coefficient holds and for a class of discrete-time Markov chains having a unique absolutely continuous invariant measure with respect to the volume measure.}, author = {Clozeau, Nicolas and Mattesini, Francesco}, issn = {1432-2064}, journal = {Probability Theory and Related Fields}, pages = {485--541}, publisher = {Springer Nature}, title = {{Annealed quantitative estimates for the quadratic 2D-discrete random matching problem}}, doi = {10.1007/s00440-023-01254-0}, volume = {190}, year = {2024}, } @article{15334, abstract = {We consider the sharp interface limit of a Navier-Stokes/Allen Cahn equation in a bounded smooth domain in two space dimensions, in the case of vanishing mobility mε=ε√, where the small parameter ε>0 related to the thickness of the diffuse interface is sent to zero. For well-prepared initial data and sufficiently small times, we rigorously prove convergence to the classical two-phase Navier-Stokes system with surface tension. The idea of the proof is to use asymptotic expansions to construct an approximate solution and to estimate the difference of the exact and approximate solutions with a spectral estimate for the (at the approximate solution) linearized Allen-Cahn operator. In the calculations we use a fractional order ansatz and new ansatz terms in higher orders leading to a suitable ε-scaled and coupled model problem. Moreover, we apply the novel idea of introducing ε-dependent coordinates.}, author = {Abels, Helmut and Fei, Mingwen and Moser, Maximilian}, issn = {1432-0835}, journal = {Calculus of Variations and Partial Differential Equations}, number = {4}, publisher = {Springer Nature}, title = {{Sharp interface limit for a Navier–Stokes/Allen–Cahn system in the case of a vanishing mobility}}, doi = {10.1007/s00526-024-02715-7}, volume = {63}, year = {2024}, } @inproceedings{19007, abstract = {Learning modular object-centric representations is crucial for systematic generalization. Existing methods show promising object-binding capabilities empirically, but theoretical identifiability guarantees remain relatively underdeveloped. Understanding when object-centric representations can theoretically be identified is crucial for scaling slot-based methods to high-dimensional images with correctness guarantees. To that end, we propose a probabilistic slot-attention algorithm that imposes an aggregate mixture prior over object-centric slot representations, thereby providing slot identifiability guarantees without supervision, up to an equivalence relation. We provide empirical verification of our theoretical identifiability result using both simple 2-dimensional data and high-resolution imaging datasets. }, author = {Kori, Avinash and Locatello, Francesco and Santhirasekaram, Ainkaran and Toni, Francesca and Glocker, Ben and De Sousa Ribeiro, Fabio}, booktitle = {38th Conference on Neural Information Processing Systems}, location = {Vancouver, Canada}, publisher = {Neural Information Processing Systems Foundation}, title = {{Identifiable object-centric representation learning via probabilistic slot attention}}, doi = {10.52202/079017-2960}, volume = {37}, year = {2024}, } @article{15098, abstract = {The paper is devoted to the analysis of the global well-posedness and the interior regularity of the 2D Navier–Stokes equations with inhomogeneous stochastic boundary conditions. The noise, white in time and coloured in space, can be interpreted as the physical law describing the driving mechanism on the atmosphere–ocean interface, i.e. as a balance of the shear stress of the ocean and the horizontal wind force.}, author = {Agresti, Antonio and Luongo, Eliseo}, issn = {1432-1807}, journal = {Mathematische Annalen}, pages = {2727--2766}, publisher = {Springer Nature}, title = {{Global well-posedness and interior regularity of 2D Navier-Stokes equations with stochastic boundary conditions}}, doi = {10.1007/s00208-024-02812-0}, volume = {390}, year = {2024}, } @article{17462, abstract = {We are interested in numerical algorithms for computing the electrical field generated by a charge distribution localized on scale l in an infinite heterogeneous correlated random medium, in a situation where the medium is only known in a box of diameter L >>l around the support of the charge. We show that the algorithm in [J. Lu, F. Otto, and L. Wang, Optimal Artificial Boundary Conditions Based on Second-Order Correctors for Three Dimensional Random Ellilptic Media, preprint, arXiv:2109.01616, 2021], suggesting optimal Dirichlet boundary conditions motivated by the multipole expansion [P. Bella, A. Giunti, and F. Otto, Comm. Partial Differential Equations, 45 (2020), pp. 561–640], still performs well in correlated media. With overwhelming probability, we obtain a convergence rate in terms of l, L, and the size of the correlations for which optimality is supported with numerical simulations. These estimates are provided for ensembles which satisfy a multiscale logarithmic Sobolev inequality, where our main tool is an extension of the semigroup estimates in [N. Clozeau, Stoch. Partial Differ. Equ. Anal. Comput., 11 (2023), pp. 1254–1378]. As part of our strategy, we construct sublinear second-order correctors in this correlated setting, which is of independent interest.}, author = {Clozeau, Nicolas and Wang, Lihan}, issn = {1540-3467}, journal = {Multiscale Modeling and Simulation}, number = {3}, pages = {973--1029}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Artificial boundary conditions for random elliptic systems with correlated coefficient field}}, doi = {10.1137/23M1603819}, volume = {22}, year = {2024}, } @article{15119, abstract = {In this paper we consider an SPDE where the leading term is a second order operator with periodic boundary conditions, coefficients which are measurable in (t,ω) , and Hölder continuous in space. Assuming stochastic parabolicity conditions, we prove Lp((0,T)×Ω,tκdt;Hσ,q(Td)) -estimates. The main novelty is that we do not require p=q . Moreover, we allow arbitrary σ∈R and weights in time. Such mixed regularity estimates play a crucial role in applications to nonlinear SPDEs which is clear from our previous work. To prove our main results we develop a general perturbation theory for SPDEs. Moreover, we prove a new result on pointwise multiplication in spaces with fractional smoothness.}, author = {Agresti, Antonio and Veraar, Mark}, issn = {0246-0203}, journal = {Annales de l'Institut Henri Poincaré, Probabilités et Statistiques}, number = {1}, pages = {413--430}, publisher = {Institute of Mathematical Statistics}, title = {{Stochastic maximal Lp(Lq)-regularity for second order systems with periodic boundary conditions}}, doi = {10.1214/22-AIHP1333}, volume = {60}, year = {2024}, } @article{17481, abstract = {Phase-field models such as the Allen–Cahn equation may give rise to the formation and evolution of geometric shapes, a phenomenon that may be analyzed rigorously in suitable scaling regimes. In its sharp-interface limit, the vectorial Allen–Cahn equation with a potential with N≥3 distinct minima has been conjectured to describe the evolution of branched interfaces by multiphase mean curvature flow. In the present work, we give a rigorous proof for this statement in two and three ambient dimensions and for a suitable class of potentials: as long as a strong solution to multiphase mean curvature flow exists, solutions to the vectorial Allen–Cahn equation with well-prepared initial data converge towards multiphase mean curvature flow in the limit of vanishing interface width parameter ε↘0. We even establish the rate of convergence O(ε 1/2 ). Our approach is based on the gradient-flow structure of the Allen–Cahn equation and its limiting motion: building on the recent concept of “gradient-flow calibrations” for multiphase mean curvature flow, we introduce a notion of relative entropy for the vectorial Allen–Cahn equation with multi-well potential. This enables us to overcome the limitations of other approaches, e.g. avoiding the need for a stability analysis of the Allen–Cahn operator or additional convergence hypotheses for the energy at positive times.}, author = {Fischer, Julian L and Marveggio, Alice}, issn = {1873-1430}, journal = {Annales de l'Institut Henri Poincaré C}, number = {5}, pages = {1117--1178}, publisher = {EMS Press}, title = {{Quantitative convergence of the vectorial Allen–Cahn equation towards multiphase mean curvature flow}}, doi = {10.4171/AIHPC/109}, volume = {41}, year = {2024}, } @inproceedings{17098, abstract = {Turn-based discounted-sum games are two-player zero-sum games played on finite directed graphs. The vertices of the graph are partitioned between player 1 and player 2. Plays are infinite walks on the graph where the next vertex is decided by a player that owns the current vertex. Each edge is assigned an integer weight and the payoff of a play is the discounted-sum of the weights of the play. The goal of player 1 is to maximize the discounted-sum payoff against the adversarial player 2. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class and the existence of a polynomial-time algorithm is a major open question. Since breaking the general exponential barrier has been a challenging problem, faster parameterized algorithms have been considered. If the discount factor is expressed in unary, then discounted-sum games can be solved in polynomial time. However, if the discount factor is arbitrary (or expressed in binary), but the weights are in unary, none of the existing approaches yield a sub-exponential bound. Our main result is a new analysis technique for a classical algorithm (namely, the strategy iteration algorithm) that present a new runtime bound which is [EQUATION] for game graphs with n vertices and absolute weights of at most W. In particular, our result yields a deterministic sub-exponential bound for games with weights that are constant or represented in unary.}, author = {Asadi, Ali and Chatterjee, Krishnendu and Svoboda, Jakub and Saona Urmeneta, Raimundo J}, booktitle = {39th Annual ACM/IEEE Symposium on Logic in Computer Science}, isbn = {9798400706608}, issn = {1043-6871}, location = {Tallinn, Estonia}, publisher = {Association for Computing Machinery}, title = {{Deterministic sub-exponential algorithm for discounted-sum games with unary weights}}, doi = {10.1145/3661814.3662080}, year = {2024}, } @inproceedings{19510, abstract = {We propose a new variant of the Adam optimizer [Kingma and Ba, 2014] called MICROADAM that specifically minimizes memory overheads, while maintaining theoretical convergence guarantees. We achieve this by compressing the gradient information before it is fed into the optimizer state, thereby reducing its memory footprint significantly. We control the resulting compression error via a novel instance of the classical error feedback mechanism from distributed optimization [Seide et al., 2014, Alistarh et al., 2018, Karimireddy et al., 2019] in which the error correction information is itself compressed to allow for practical memory gains. We prove that the resulting approach maintains theoretical convergence guarantees competitive to those of AMSGrad, while providing good practical performance. Specifically, we show that MICROADAM can be implemented efficiently on GPUs: on both million-scale (BERT) and billion-scale (LLaMA) models, MICROADAM provides practical convergence competitive to that of the uncompressed Adam baseline, with lower memory usage and similar running time. Our code is available at https://github.com/IST-DASLab/MicroAdam.}, author = {Modoranu, Ionut-Vlad and Safaryan, Mher and Malinovsky, Grigory and Kurtic, Eldar and Robert, Thomas and Richtárik, Peter and Alistarh, Dan-Adrian}, booktitle = {38th Conference on Neural Information Processing Systems}, issn = {1049-5258}, publisher = {Neural Information Processing Systems Foundation}, title = {{MICROADAM: Accurate adaptive optimization with low space overhead and provable convergence}}, doi = {10.52202/079017-0001}, volume = {37}, year = {2024}, }