When training deep neural networks for classification tasks, an intriguing empirical phenomenon has been widely observed in the last-layer classifiers and features, where (i) the class means and the last-layer classifiers all collapse to the vertices of a Simplex Equiangular Tight Frame (ETF) up to scaling, and (ii) cross-example within-class variability of last-layer activations collapses to zero. This phenomenon is called Neural Collapse (NC), which seems to take place regardless of the choice of loss functions. In this work, we justify NC under the mean squared error (MSE) loss, where recent empirical evidence shows that it performs comparably or even better than the de-facto cross-entropy loss. Under a simplified unconstrained feature model, we provide the first global landscape analysis for vanilla nonconvex MSE loss and show that the (only!) global minimizers are neural collapse solutions, while all other critical points are strict saddles whose Hessian exhibit negative curvature directions. Furthermore, we justify the usage of rescaled MSE loss by probing the optimization landscape around the NC solutions, showing that the landscape can be improved by tuning the rescaling hyperparameters. Finally, our theoretical findings are experimentally verified on practical network architectures.

We propose a method for identifying an ectopic activation in the heart non-invasively. Ectopic activity in the heart can trigger deadly arrhythmias. The localization of the ectopic foci or earliest activation sites (EASs) is therefore a critical information for cardiologists in deciding the optimal treatment. In this work, we formulate the identification problem as a global optimization problem, by minimizing the mismatch between the ECG predicted by a cardiac model, when paced at a given EAS, and the observed ECG during the ectopic activity. Our cardiac model amounts at solving an anisotropic eikonal equation for cardiac activation and the forward bidomain model in the torso with the lead field approach for computing the ECG. We build a Gaussian process surrogate model of the loss function on the heart surface to perform Bayesian optimization. In this procedure, we iteratively evaluate the loss function following the lower confidence bound criterion, which combines exploring the surface with exploitation of the minimum region. We also extend this framework to incorporate multiple levels of fidelity of the model. We show that our procedure converges to the minimum only after $11.7\pm10.4$ iterations (20 independent runs) for the single-fidelity case and $3.5\pm1.7$ iterations for the multi-fidelity case. We envision that this tool could be applied in real time in a clinical setting to identify potentially dangerous EASs.

This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge. This year's problem is to coordinate the motion of multiple robots in order to reach their targets without collisions and minimizing the makespan. It is a classical multi agent path finding problem with the specificity that the instances are highly dense in an unbounded grid. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them. The main ingredients include several different strategies to compute initial solutions coupled with a heuristic called Conflict Optimizer to reduce the makespan of existing solutions.

"Have you ever ordered 43 Chicken McNuggets at McDonald's?" When I first heard this story it completely blew my mind, but it is actually true that the Chicken McNuggets have a mathematical story, and it is pretty interesting. Originally, you only have boxes of 6,9 and 20 Chicken McNuggets. While he was eating with his son, the mathematician Henri Picciotto started to think about the actual numbers that he could order with a combination of these three values. This number is known as McNuggets Number. We will start by giving an in depth detail of the discrete domain that we are considering and we will end up solving an optimization problem about it.

This paper demonstrates how to recover causal graphs from the score of the data distribution in non-linear additive (Gaussian) noise models. Using score matching algorithms as a building block, we show how to design a new generation of scalable causal discovery methods. To showcase our approach, we also propose a new efficient method for approximating the score's Jacobian, enabling to recover the causal graph. Empirically, we find that the new algorithm, called SCORE, is competitive with state-of-the-art causal discovery methods while being significantly faster.

A critical change is happening in today's Internet of Things (IoT). The computational power of edge devices is steadily increasing. AI chips are rapidly infiltrating the market, smart phones nowadays have compute power comparable to everyday use laptops (Samsung 2019), Tesla just boasted that its autopilot system has computing power of more than 3000 MacBook pros (CleanTechnica 2021) and small local computers such as Raspberry Pis have become common place in many applications especially manufacturing (Al-Ali et al. 2018). This opens a new paradigm for data analytics in IoT; one that exploits local computing power to process more of the user's data where it is created. This future of IoT has been recently termed as the "The Internet of Federated Things (IoFT)" (Kontar et al. 2021) where the term federated, refers to some autonomy for IoT devices and is inspired by the explosive recent interest in federated data science.

We argue that results produced by a heuristic optimisation algorithm cannot be considered reproducible unless the algorithm fully specifies what should be done with solutions generated outside the domain, even in the case of simple box constraints. Currently, in the field of heuristic optimisation, such specification is rarely mentioned or investigated due to the assumed triviality or insignificance of this question. Here, we demonstrate that, at least in algorithms based on Differential Evolution, this choice induces notably different behaviours - in terms of performance, disruptiveness and population diversity. This is shown theoretically (where possible) for standard Differential Evolution in the absence of selection pressure and experimentally for the standard and state-of-the-art Differential Evolution variants on special test function $f_0$ and BBOB benchmarking suite, respectively. Moreover, we demonstrate that the importance of this choice quickly grows with problem's dimensionality. Different Evolution is not at all special in this regard - there is no reason to presume that other heuristic optimisers are not equally affected by the aforementioned algorithmic choice. Thus, we urge the field of heuristic optimisation to formalise and adopt the idea of a new algorithmic component in heuristic optimisers, which we call here a strategy of dealing with infeasible solutions. This component needs to be consistently (a) specified in algorithmic descriptions to guarantee reproducibility of results, (b) studied to better understand its impact on algorithm's performance in a wider sense and (c) included in the (automatic) algorithmic design. All of these should be done even for problems with box constraints.

Within machine learning, NNLS problems arise whenever having negative labels is not meaningful, for example, when labels represent quantities like prices, age, pixel intensities, chemical concentrations, or frequency counts. NNLS is also widely used as a subroutine in nonnegative matrix factorization to extract sparse features in applications like image processing, computational biology, clustering, collaborative filtering, and community detection [Gil14]. From a statistical perspective, NNLS problems can be shown to possess a regularization property that enforces sparsity similar to LASSO [Tib96], while being comparatively simpler, without the need to tune a regularization parameter or perform cross-validation [SH14, BEZ08, FK14]. From an algorithmic standpoint, the nonnegativity constraint in NNLS problems is typically viewed as an obstacle: most NNLS algorithms need to perform additional work to handle it, and the problem is considered harder than unconstrained least squares. However, in many applications that use NNLS, the data is also nonnegative. This is true, for example, in problems arising in image processing, computational genomics, functional MRI, and in applications traditionally addressed using nonnegative matrix factorization. We argue in this paper that when the data for NNLS is nonnegative, it is in fact possible to obtain stronger guarantees than for traditional least squares problems.

We analyse the convergence of the proximal gradient algorithm for convex composite problems in the presence of gradient and proximal computational inaccuracies. We derive new tighter deterministic and probabilistic bounds that we use to verify a simulated (MPC) and a synthetic (LASSO) optimization problems solved on a reduced-precision machine in combination with an inaccurate proximal operator. We also show how the probabilistic bounds are more robust for algorithm verification and more accurate for application performance guarantees. Under some statistical assumptions, we also prove that some cumulative error terms follow a martingale property. And conforming to observations, e.g., in \cite{schmidt2011convergence}, we also show how the acceleration of the algorithm amplifies the gradient and proximal computational errors.

This thesis rigorously studies fundamental reinforcement learning (RL) methods in modern practical considerations, including robust RL, distributional RL, and offline RL with neural function approximation. The thesis first prepares the readers with an overall overview of RL and key technical background in statistics and optimization. In each of the settings, the thesis motivates the problems to be studied, reviews the current literature, provides computationally efficient algorithms with provable efficiency guarantees, and concludes with future research directions. The thesis makes fundamental contributions to the three settings above, both algorithmically, theoretically, and empirically, while staying relevant to practical considerations.