More Like this

1. Differentially Private Online Submodular Maximization

   Perez-Salazar, Sebastian; Cummings, Rachel (January 2021, Proceedings of Machine Learning Research)

   null (Ed.)

   In this work we consider the problem of online submodular maximization under a cardinality constraint with differential privacy (DP). A stream of T submodular functions over a common finite ground set U arrives online, and at each time-step the decision maker must choose at most k elements of U before observing the function. The decision maker obtains a profit equal to the function evaluated on the chosen set and aims to learn a sequence of sets that achieves low expected regret. In the full-information setting, we develop an (𝜀,𝛿)-DP algorithm with expected (1-1/e)-regret bound of 𝑂(𝑘2log|𝑈|𝑇log𝑘/𝛿√𝜀). This algorithm contains k ordered experts that learn the best marginal increments for each item over the whole time horizon while maintaining privacy of the functions. In the bandit setting, we provide an (𝜀,𝛿+𝑂(𝑒−𝑇1/3))-DP algorithm with expected (1-1/e)-regret bound of 𝑂(log𝑘/𝛿√𝜀(𝑘(|𝑈|log|𝑈|)1/3)2𝑇2/3). One challenge for privacy in this setting is that the payoff and feedback of expert i depends on the actions taken by her i-1 predecessors. This particular type of information leakage is not covered by post-processing, and new analysis is required. Our techniques for maintaining privacy with feedforward may be of independent interest. 

   more » « less
2. Continuum limit of 2D fractional nonlinear Schrödinger equation

   https://doi.org/10.1007/s00028-023-00881-3  

   Choi, Brian; Aceves, Alejandro (June 2023, Journal of Evolution Equations)

   Abstract We prove that the solutions to the discrete nonlinear Schrödinger equation with non-local algebraically decaying coupling converge strongly in $$L^2({\mathbb {R}}^2)$$ L 2 ( R 2 ) to those of the continuum fractional nonlinear Schrödinger equation, as the discretization parameter tends to zero. The proof relies on sharp dispersive estimates that yield the Strichartz estimates that are uniform in the discretization parameter. An explicit computation of the leading term of the oscillatory integral asymptotics is used to show that the best constants of a family of dispersive estimates blow up as the non-locality parameter $$\alpha \in (1,2)$$ α ∈ ( 1 , 2 ) approaches the boundaries. 

   more » « less
3. The Mirror Langevin Algorithm Converges with Vanishing Bias

   Ruilin Li; Molei Tao; Santosh Vempala; Andre Wibisono (March 2022, Algorithmic Learning Theory)

   The technique of modifying the geometry of a problem from Euclidean to Hessian metric has proved to be quite effective in optimization, and has been the subject of study for sampling. The Mirror Langevin Diffusion (MLD) is a sampling analogue of mirror flow in continuous time, and it has nice convergence properties under log-Sobolev or Poincare inequalities relative to the Hessian metric. In discrete time, a simple discretization of MLD is the Mirror Langevin Algorithm (MLA), which was shown to have a biased convergence guarantee with a non-vanishing bias term (does not go to zero as step size goes to zero). This raised the question of whether we need a better analysis or a better discretization to achieve a vanishing bias. Here we study the Mirror Langevin Algorithm and show it indeed has a vanishing bias. We apply mean-square analysis to show the mixing time bound for MLA under the modified self-concordance condition. 

   more » « less
4. Parameter-robust preconditioners for Biot’s model

   https://doi.org/10.1007/s40324-023-00336-2  

   Rodrigo, Carmen; Gaspar, Francisco J; Adler, James; Hu, Xiaozhe; Ohm, Peter; Zikatanov, Ludmil (March 2024, SeMA Journal)

   Abstract This work presents an overview of the most relevant results obtained by the authors regarding the numerical solution of the Biot’s consolidation problem by preconditioning techniques. The emphasis here is on the design of parameter-robust preconditioners for the efficient solution of the algebraic system of equations resulting after proper discretization of such poroelastic problems. The classical two- and three-field formulations of the problem are considered, and block preconditioners are presented for some of the discretization schemes that have been proposed by the authors for these formulations. These discretizations have been proved to be well-posed with respect to the physical and discretization parameters, what provides a framework to develop preconditioners that are robust with respect to such parameters as well. In particular, we construct both norm-equivalent (block diagonal) and field-of-value-equivalent (block triangular) preconditioners, which are proved to be parameter-robust. The theoretical results on this parameter-robustness are demonstrated by considering typical benchmark problems in the literature for Biot’s model. 

   more » « less
5. A discontinuous Galerkin method for one-dimensional nonlocal wave problems

   https://doi.org/10.1051/m2an/2026040  

   Du, Qiang; Ren, Kui; Zhang, Lu; Zhou, Yin (May 2026, ESAIM: Mathematical Modelling and Numerical Analysis)

   This paper presents a fully discrete numerical scheme for one-dimensional nonlocal wave equations and provides a rigorous theoretical analysis. To facilitate the spatial discretization, we introduce an auxiliary variable analogous to the gradient field in local discontinuous Galerkin (DG) methods for classical partial differential equations (PDEs) and reformulate the equation into a system of equations. The proposed scheme then uses a DG method for spatial discretization and the Crank-Nicolson method for time integration. We prove optimal L2 error convergence for both the solution and the auxiliary variable under a special class of radial kernels at the semi-discrete level. In addition, for general kernels, we demonstrate the asymptotic compatibility of the scheme, ensuring that it recovers the classical DG approximation of the local wave equation in the zero-horizon limit. Furthermore, we prove that the fully discrete scheme preserves the energy of the nonlocal wave equation. A series of numerical experiments are presented to validate the theoretical findings. 

   more » « less