More Like this

1. When are Non-Parametric Methods Robust?

   Bhattacharjee, R; Chaudhuri, K (January 2020, Journal of machine learning research)

   A growing body of research has shown that many classifiers are susceptible to adversarial exam- ples – small strategic modifications to test inputs that lead to misclassification. In this work, we study general non-parametric methods, with a view towards understanding when they are ro- bust to these modifications. We establish general conditions under which non-parametric methods are r-consistent – in the sense that they converge to optimally robust and accurate classifiers in the large sample limit. Concretely, our results show that when data is well-separated, nearest neighbors and kernel clas- sifiers are r-consistent, while histograms are not. For general data distributions, we prove that pre- processing by Adversarial Pruning (Yang et al., 2019) – that makes data well-separated – followed by nearest neighbors or kernel classifiers also leads to r-consistency. 

   more » « less
2. Consistent Non-Parametric Methods for Maximizing Robustness

   Bhattacharjee, Robi; Chaudhuri, Kamalika (January 2021, Advances in neural information processing systems)

   Learning classifiers that are robust to adversarial examples has received a great deal of recent attention. A major drawback of the standard robust learning framework is there is an artificial robustness radius r that applies to all inputs. This ignores the fact that data may be highly heterogeneous, in which case it is plausible that robustness regions should be larger in some regions of data, and smaller in others. In this paper, we address this limitation by proposing a new limit classifier, called the neighborhood optimal classifier, that extends the Bayes optimal classifier outside its support by using the label of the closest in-support point. We then argue that this classifier maximizes the size of its robustness regions subject to the constraint of having accuracy equal to the Bayes optimal. We then present sufficient conditions under which general non-parametric methods that can be represented as weight functions converge towards this limit, and show that both nearest neighbors and kernel classifiers satisfy them under certain condition 

   more » « less
3. Order enhanced finite volume methods through non-polynomial approximation

   https://doi.org/10.1016/j.jcp.2023.111960  

   Christlieb, Andrew J.; Sands, William A.; Yang, Hyoseon (April 2023, Journal of Computational Physics)
4. Analysis of Variable-Step/Non-autonomous Artificial Compression Methods

   https://doi.org/10.1007/s00021-019-0429-2  

   Chen, Robin Ming; Layton, William; McLaughlin, Michael (June 2019, Journal of Mathematical Fluid Mechanics)
5. Non-asymptotic superlinear convergence of standard quasi-Newton methods

   https://doi.org/10.1007/s10107-022-01887-4  

   Jin, Qiujiang; Mokhtari, Aryan (September 2022, Mathematical Programming)

   Abstract In this paper, we study and prove the non-asymptotic superlinear convergence rate of the Broyden class of quasi-Newton algorithms which includes the Davidon–Fletcher–Powell (DFP) method and the Broyden–Fletcher–Goldfarb–Shanno (BFGS) method. The asymptotic superlinear convergence rate of these quasi-Newton methods has been extensively studied in the literature, but their explicit finite–time local convergence rate is not fully investigated. In this paper, we provide a finite–time (non-asymptotic) convergence analysis for Broyden quasi-Newton algorithms under the assumptions that the objective function is strongly convex, its gradient is Lipschitz continuous, and its Hessian is Lipschitz continuous at the optimal solution. We show that in a local neighborhood of the optimal solution, the iterates generated by both DFP and BFGS converge to the optimal solution at a superlinear rate of$$(1/k)^{k/2}$$ ${(1/k)}^{k/2}$, wherekis the number of iterations. We also prove a similar local superlinear convergence result holds for the case that the objective function is self-concordant. Numerical experiments on several datasets confirm our explicit convergence rate bounds. Our theoretical guarantee is one of the first results that provide a non-asymptotic superlinear convergence rate for quasi-Newton methods. 

   more » « less