skip to main content

Title: Rates of convergence for regression with the graph poly-Laplacian

In the (special) smoothing spline problem one considers a variational problem with a quadratic data fidelity penalty and Laplacian regularization. Higher order regularity can be obtained via replacing the Laplacian regulariser with a poly-Laplacian regulariser. The methodology is readily adapted to graphs and here we consider graph poly-Laplacian regularization in a fully supervised, non-parametric, noise corrupted, regression problem. In particular, given a dataset$$\{x_i\}_{i=1}^n$${xi}i=1nand a set of noisy labels$$\{y_i\}_{i=1}^n\subset \mathbb {R}$${yi}i=1nRwe let$$u_n{:}\{x_i\}_{i=1}^n\rightarrow \mathbb {R}$$un:{xi}i=1nRbe the minimizer of an energy which consists of a data fidelity term and an appropriately scaled graph poly-Laplacian term. When$$y_i = g(x_i)+\xi _i$$yi=g(xi)+ξi, for iid noise$$\xi _i$$ξi, and using the geometric random graph, we identify (with high probability) the rate of convergence of$$u_n$$untogin the large data limit$$n\rightarrow \infty $$n. Furthermore, our rate is close to the known rate of convergence in the usual smoothing spline model.

more » « less
Award ID(s):
Author(s) / Creator(s):
; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Sampling Theory, Signal Processing, and Data Analysis
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Let$$X\rightarrow {{\mathbb {P}}}^1$$XP1be an elliptically fiberedK3 surface, admitting a sequence$$\omega _{i}$$ωiof Ricci-flat metrics collapsing the fibers. LetVbe a holomorphicSU(n) bundle overX, stable with respect to$$\omega _i$$ωi. Given the corresponding sequence$$\Xi _i$$Ξiof Hermitian–Yang–Mills connections onV, we prove that, ifEis a generic fiber, the restricted sequence$$\Xi _i|_{E}$$Ξi|Econverges to a flat connection$$A_0$$A0. Furthermore, if the restriction$$V|_E$$V|Eis of the form$$\oplus _{j=1}^n{\mathcal {O}}_E(q_j-0)$$j=1nOE(qj-0)forndistinct points$$q_j\in E$$qjE, then these points uniquely determine$$A_0$$A0.

    more » « less
  2. Abstract

    Approximate integer programming is the following: For a given convex body$$K \subseteq {\mathbb {R}}^n$$KRn, either determine whether$$K \cap {\mathbb {Z}}^n$$KZnis empty, or find an integer point in the convex body$$2\cdot (K - c) +c$$2·(K-c)+cwhich isK, scaled by 2 from its center of gravityc. Approximate integer programming can be solved in time$$2^{O(n)}$$2O(n)while the fastest known methods for exact integer programming run in time$$2^{O(n)} \cdot n^n$$2O(n)·nn. So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point$$x^* \in (K \cap {\mathbb {Z}}^n)$$x(KZn)can be found in time$$2^{O(n)}$$2O(n), provided that theremaindersof each component$$x_i^* \mod \ell $$ximodfor some arbitrarily fixed$$\ell \ge 5(n+1)$$5(n+1)of$$x^*$$xare given. The algorithm is based on acutting-plane technique, iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a$$2^{O(n)}n^n$$2O(n)nnalgorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a newasymmetric approximate Carathéodory theoremthat might be of interest on its own. Our second method concerns integer programming problems in equation-standard form$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$Ax=b,0xu,xZn. Such a problem can be reduced to the solution of$$\prod _i O(\log u_i +1)$$iO(logui+1)approximate integer programming problems. This implies, for example thatknapsackorsubset-sumproblems withpolynomial variable range$$0 \le x_i \le p(n)$$0xip(n)can be solved in time$$(\log n)^{O(n)}$$(logn)O(n). For these problems, the best running time so far was$$n^n \cdot 2^{O(n)}$$nn·2O(n).

    more » « less
  3. Abstract

    We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$w:NR+,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$f1,f2,,froverNand requirements$$k_1,k_2,\ldots ,k_r$$k1,k2,,krthe goal is to find a minimum weight subset$$S \subseteq N$$SNsuch that$$f_i(S) \ge k_i$$fi(S)kifor$$1 \le i \le r$$1ir. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$r=1Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$O(log(kr))approximation where$$k = \sum _i k_i$$k=ikiand this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$(1-1/e-ε)while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$O(1ϵlogr)in the cost. Second, we consider the special case when each$$f_i$$fiis a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems.

    more » « less
  4. For each odd integern≥<#comment/>3n \geq 3, we construct a rank-3 graphΛ<#comment/>n\Lambda _nwith involutionγ<#comment/>n\gamma _nwhose realC∗<#comment/>C^*-algebraCR∗<#comment/>(Λ<#comment/>n,γ<#comment/>n)C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda _n, \gamma _n)is stably isomorphic to the exotic Cuntz algebraEn\mathcal E_n. This construction is optimal, as we prove that a rank-2 graph with involution(Λ<#comment/>,γ<#comment/>)(\Lambda ,\gamma )can never satisfyCR∗<#comment/>(Λ<#comment/>,γ<#comment/>)∼<#comment/>MEEnC^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )\sim _{ME} \mathcal E_n, and Boersema reached the same conclusion for rank-1 graphs (directed graphs) in [Münster J. Math.10(2017), pp. 485–521, Corollary 4.3]. Our construction relies on a rank-1 graph with involution(Λ<#comment/>,γ<#comment/>)(\Lambda , \gamma )whose realC∗<#comment/>C^*-algebraCR∗<#comment/>(Λ<#comment/>,γ<#comment/>)C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )is stably isomorphic to the suspensionSRS \mathbb {R}. In the Appendix, we show that theii-fold suspensionSiRS^i \mathbb {R}is stably isomorphic to a graph algebra iff−<#comment/>2≤<#comment/>i≤<#comment/>1-2 \leq i \leq 1.

    more » « less
  5. Abstract

    Let$$(h_I)$$(hI)denote the standard Haar system on [0, 1], indexed by$$I\in \mathcal {D}$$ID, the set of dyadic intervals and$$h_I\otimes h_J$$hIhJdenote the tensor product$$(s,t)\mapsto h_I(s) h_J(t)$$(s,t)hI(s)hJ(t),$$I,J\in \mathcal {D}$$I,JD. We consider a class of two-parameter function spaces which are completions of the linear span$$\mathcal {V}(\delta ^2)$$V(δ2)of$$h_I\otimes h_J$$hIhJ,$$I,J\in \mathcal {D}$$I,JD. This class contains all the spaces of the formX(Y), whereXandYare either the Lebesgue spaces$$L^p[0,1]$$Lp[0,1]or the Hardy spaces$$H^p[0,1]$$Hp[0,1],$$1\le p < \infty $$1p<. We say that$$D:X(Y)\rightarrow X(Y)$$D:X(Y)X(Y)is a Haar multiplier if$$D(h_I\otimes h_J) = d_{I,J} h_I\otimes h_J$$D(hIhJ)=dI,JhIhJ, where$$d_{I,J}\in \mathbb {R}$$dI,JR, and ask which more elementary operators factor throughD. A decisive role is played by theCapon projection$$\mathcal {C}:\mathcal {V}(\delta ^2)\rightarrow \mathcal {V}(\delta ^2)$$C:V(δ2)V(δ2)given by$$\mathcal {C} h_I\otimes h_J = h_I\otimes h_J$$ChIhJ=hIhJif$$|I|\le |J|$$|I||J|, and$$\mathcal {C} h_I\otimes h_J = 0$$ChIhJ=0if$$|I| > |J|$$|I|>|J|, as our main result highlights: Given any bounded Haar multiplier$$D:X(Y)\rightarrow X(Y)$$D:X(Y)X(Y), there exist$$\lambda ,\mu \in \mathbb {R}$$λ,μRsuch that$$\begin{aligned} \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C})\text { approximately 1-projectionally factors through }D, \end{aligned}$$λC+μ(Id-C)approximately 1-projectionally factors throughD,i.e., for all$$\eta > 0$$η>0, there exist bounded operatorsABso thatABis the identity operator$${{\,\textrm{Id}\,}}$$Id,$$\Vert A\Vert \cdot \Vert B\Vert = 1$$A·B=1and$$\Vert \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C}) - ADB\Vert < \eta $$λC+μ(Id-C)-ADB<η. Additionally, if$$\mathcal {C}$$Cis unbounded onX(Y), then$$\lambda = \mu $$λ=μand then$${{\,\textrm{Id}\,}}$$Ideither factors throughDor$${{\,\textrm{Id}\,}}-D$$Id-D.

    more » « less