In this paper, we study zeroth-order algorithms for nonconvex-concave minimax problems, which have attracted widely attention in machine learning, signal processing and many other fields in recent years. We propose a zeroth-order alternating randomized gradient projection (ZO-AGP) algorithm for smooth nonconvex-concave minimax problems, and its iteration complexity to obtain an $\varepsilon$-stationary point is bounded by $\mathcal{O}(\varepsilon^{-4})$, and the number of function value estimation is bounded by $\mathcal{O}(d_{x}+d_{y})$ per iteration. Moreover, we propose a zeroth-order block alternating randomized proximal gradient algorithm (ZO-BAPG) for solving block-wise nonsmooth nonconvex-concave minimax optimization problems, and the iteration complexity to obtain an $\varepsilon$-stationary point is bounded by $\mathcal{O}(\varepsilon^{-4})$ and the number of function value estimation per iteration is bounded by $\mathcal{O}(K d_{x}+d_{y})$. To the best of our knowledge, this is the first time that zeroth-order algorithms with iteration complexity gurantee are developed for solving both general smooth and block-wise nonsmooth nonconvex-concave minimax problems. Numerical results on data poisoning attack problem validate the efficiency of the proposed algorithms.
We consider goal-oriented adaptive space-time finite-element discretizations of the regularized parabolic p-Laplace problem on completely unstructured simplicial space-time meshes. The adaptivity is driven by the dual-weighted residual (DWR) method since we are interested in an accurate computation of some possibly nonlinear functionals at the solution. Such functionals represent goals in which engineers are often more interested than the solution itself. The DWR method requires the numerical solution of a linear adjoint problem that provides the sensitivities for the mesh refinement. This can be done by means of the same full space-time finite element discretization as used for the primal non-linear problems. The numerical experiments presented demonstrate that this goal-oriented, full space-time finite element solver efficiently provides accurate numerical results for different functionals.
A new procedure to construct symplectic methods for constrained mechanical systems is developed in this paper. The definition of a map coming from the notion of retraction maps allows to adapt the continuous problem to the discretization rule rather than viceversa. As a result, the constraint submanifold is exactly preserved by the discrete flow and the extension of the methods to the case of non-linear configuration spaces is straightforward.
Falls among the elderly are a major health concern, frequently resulting in serious injuries and a reduced quality of life. In this paper, we propose "BlockTheFall," a wearable device-based fall detection framework which detects falls in real time by using sensor data from wearable devices. To accurately identify patterns and detect falls, the collected sensor data is analyzed using machine learning algorithms. To ensure data integrity and security, the framework stores and verifies fall event data using blockchain technology. The proposed framework aims to provide an efficient and dependable solution for fall detection with improved emergency response, and elderly individuals' overall well-being. Further experiments and evaluations are being carried out to validate the effectiveness and feasibility of the proposed framework, which has shown promising results in distinguishing genuine falls from simulated falls. By providing timely and accurate fall detection and response, this framework has the potential to substantially boost the quality of elderly care.
The linear saturation number $sat^{lin}_k(n,\mathcal{F})$ (linear extremal number $ex^{lin}_k(n,\mathcal{F})$) of $\mathcal{F}$ is the minimum (maximum) number of hyperedges of an $n$-vertex linear $k$-uniform hypergraph containing no member of $\mathcal{F}$ as a subgraph, but the addition of any new hyperedge such that the result hypergraph is still a linear $k$-uniform hypergraph creates a copy of some hypergraph in $\mathcal{F}$. Determining $ex_3^{lin}(n$, Berge-$C_3$) is equivalent to the famous (6,3)-problem, which has been settled in 1976. Since then, determining the linear extremal numbers of Berge cycles was extensively studied. As the counterpart of this problem in saturation problems, the problem of determining the linear saturation numbers of Berge cycles is considered. In this paper, we prove that $sat^{lin}_k$($n$, Berge-$C_t)\ge \big\lfloor\frac{n-1}{k-1}\big\rfloor$ for any integers $k\ge3$, $t\ge 3$, and the equality holds if $t=3$. In addition, we provide an upper bound for $sat^{lin}_3(n,$ Berge-$C_4)$ and for any disconnected Berge-$C_4$-saturated linear 3-uniform hypergraph, we give a lower bound for the number of hyperedges of it.
We propose a general framework for solving forward and inverse problems constrained by partial differential equations, where we interpolate neural networks onto finite element spaces to represent the (partial) unknowns. The framework overcomes the challenges related to the imposition of boundary conditions, the choice of collocation points in physics-informed neural networks, and the integration of variational physics-informed neural networks. A numerical experiment set confirms the framework's capability of handling various forward and inverse problems. In particular, the trained neural network generalises well for smooth problems, beating finite element solutions by some orders of magnitude. We finally propose an effective one-loop solver with an initial data fitting step (to obtain a cheap initialisation) to solve inverse problems.
We consider the problem of solving linear least squares problems in a framework where only evaluations of the linear map are possible. We derive randomized methods that do not need any other matrix operations than forward evaluations, especially no evaluation of the adjoint map is needed. Our method is motivated by the simple observation that one can get an unbiased estimate of the application of the adjoint. We show convergence of the method and then derive a more efficient method that uses an exact linesearch. This method, called random descent, resembles known methods in other context and has the randomized coordinate descent method as special case. We provide convergence analysis of the random descent method emphasizing the dependence on the underlying distribution of the random vectors. Furthermore we investigate the applicability of the method in the context of ill-posed inverse problems and show that the method can have beneficial properties when the unknown solution is rough. We illustrate the theoretical findings in numerical examples. One particular result is that the random descent method actually outperforms established transposed-free methods (TFQMR and CGS) in examples.
Nonconvex-nonconcave minimax optimization has received intense attention over the last decade due to its broad applications in machine learning. Unfortunately, most existing algorithms cannot be guaranteed to converge globally and even suffer from limit cycles. To address this issue, we propose a novel single-loop algorithm called doubly smoothed gradient descent ascent method (DSGDA), which naturally balances the primal and dual updates. The proposed DSGDA can get rid of limit cycles in various challenging nonconvex-nonconcave examples in the literature, including Forsaken, Bilinearly-coupled minimax, Sixth-order polynomial, and PolarGame. We further show that under an one-sided Kurdyka-\L{}ojasiewicz condition with exponent $\theta\in(0,1)$ (resp. convex primal/concave dual function), DSGDA can find a game-stationary point with an iteration complexity of $\mathcal{O}(\epsilon^{-2\max\{2\theta,1\}})$ (resp. $\mathcal{O}(\epsilon^{-4})$). These match the best results for single-loop algorithms that solve nonconvex-concave or convex-nonconcave minimax problems, or problems satisfying the rather restrictive one-sided Polyak-\L{}ojasiewicz condition. Our work demonstrates, for the first time, the possibility of having a simple and unified single-loop algorithm for solving nonconvex-nonconcave, nonconvex-concave, and convex-nonconcave minimax problems.
Finite element methods and kinematically coupled schemes that decouple the fluid velocity and structure's displacement have been extensively studied for incompressible fluid-structure interaction (FSI) over the past decade. While these methods are known to be stable and easy to implement, optimal error analysis has remained challenging. Previous work has primarily relied on the classical elliptic projection technique, which is only suitable for parabolic problems and does not lead to optimal convergence of numerical solutions to the FSI problems in the standard $L^2$ norm. In this article, we propose a new kinematically coupled scheme for incompressible FSI thin-structure model and establish a new framework for the numerical analysis of FSI problems in terms of a newly introduced coupled non-stationary Ritz projection, which allows us to prove the optimal-order convergence of the proposed method in the $L^2$ norm. The methodology presented in this article is also applicable to numerous other FSI models and serves as a fundamental tool for advancing research in this field.
In this paper, a class of smoothing modulus-based iterative method was presented for solving implicit complementarity problems. The main idea was to transform the implicit complementarity problem into an equivalent implicit fixed-point equation, then introduces a smoothing function to obtain its approximation solutions. The convergence analysis of the algorithm was given, and the efficiency of the algorithms was verified by numerical experiment
Non-convex optimization is ubiquitous in modern machine learning. Researchers devise non-convex objective functions and optimize them using off-the-shelf optimizers such as stochastic gradient descent and its variants, which leverage the local geometry and update iteratively. Even though solving non-convex functions is NP-hard in the worst case, the optimization quality in practice is often not an issue -- optimizers are largely believed to find approximate global minima. Researchers hypothesize a unified explanation for this intriguing phenomenon: most of the local minima of the practically-used objectives are approximately global minima. We rigorously formalize it for concrete instances of machine learning problems.