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. 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
3. 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 (August 2023, 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
4. Continuum limit of 2D fractional nonlinear Schrödinger equation

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

   Choi, Brian; Aceves, Alejandro (March 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\left(R^2\right)$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)$$ $\alpha \in (1,2)$approaches the boundaries. 

   more » « less
5. A cutFEM divergence–free discretization for the stokes problem

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

   Liu, Haoran; Neilan, Michael; Olshanskii, Maxim (January 2023, ESAIM: Mathematical Modelling and Numerical Analysis)

   We construct and analyze a CutFEM discretization for the Stokes problem based on the Scott–Vogelius pair. The discrete piecewise polynomial spaces are defined on macro-element triangulations which are not fitted to the smooth physical domain. Boundary conditions are imposed via penalization through the help of a Nitsche-type discretization, whereas stability with respect to small and anisotropic cuts of the bulk elements is ensured by adding local ghost penalty stabilization terms. We show stability of the scheme as well as a divergence–free property of the discrete velocity outside an O ( h ) neighborhood of the boundary. To mitigate the error caused by the violation of the divergence–free condition, we introduce local grad–div stabilization. The error analysis shows that the grad–div parameter can scale like O ( h −1 ), allowing a rather heavy penalty for the violation of mass conservation, while still ensuring optimal order error estimates. 

   more » « less