generateData[y_,m_,σ_,domain_:{0,1}]:=Map[x|->{x,y[x]+RandomVariate[NormalDistribution[0,σ]]},Range[0,1,1/(m-1)]]

Show[ListPlot[generateData[Sin,20,0.1]],Plot[Sin[x],{x,0,1}]]

cost[basis_,data_]:=Evaluate[Map[dat|->(((Total[MapIndexed[{f,i}|->Slot[First[i]]f[dat[[1]]],basis]]-dat[[2]]))^2),data]]&

dCost[basis_,data_]:=Evaluate[2MapIndexed[{g,j}|->Map[dat|->(Total[MapIndexed[{f,i}|->Slot[First[i]]f[dat[[1]]],basis]]-dat[[2]])g[dat[[1]]],data],basis]]&

ClearAll[gradientDescent]

gradientDescent[basis_,data_,N_,batchSize_:1][a0__]:=Module[{as={a0},dC=Compile[Evaluate[{a[#],_Real}&/@Range[Length[basis]]],Evaluate[dCost[basis,data]@@Array[a,Length[basis]]]],c=Compile[Evaluate[{a[#],_Real}&/@Range[Length[basis]]],Evaluate[cost[basis,data]@@Array[a,Length[basis]]]],α=1./1000,gC,ds},
Do[
ds=RandomSample[Range[Length[data]],Ceiling[batchSize Length[data]]];
gC=Total[Transpose[dC@@as][[ds]]];
While[(Total[(c@@as)[[ds]]])-(Total[(c@@(as-α gC))[[ds]]])<=(1/2)α ((Norm[gC])^2),
α/=2];
as-=α gC;
α*=1.5;
,N];
as
]

gradientDescent2[basis_,data_,N_,γ_:0][a0__]:=Module[{as={a0},dC=Compile[Evaluate[{a[#],_Real}&/@Range[Length[basis]]],Evaluate[Total[Transpose[dCost[basis,data]@@Array[a,Length[basis]]]]]],c=Compile[Evaluate[{a[#],_Real}&/@Range[Length[basis]]],Evaluate[Total[cost[basis,data]@@Array[a,Length[basis]]]]],α=1./1000,gC,ds},
Do[
gC=dC@@as;
as-=α gC+γ RandomVariate[NormalDistribution[],Length[as]];
,N];
as
]

polynomialBasis[m_]:=Prepend[(x|->(x^(#)))&/@Range[1,m-1],1&]

edgeBasis[m_]:=Prepend[Map[(x|->Abs[x-#/(m-1)])&,Range[0,m-2]],1&]

edgeBasis[m_]:=Map[(x|->UnitStep[(x-#/(m-1))(m-1)])&,Range[0,m-1]]

trialFunction[basis_][as__]:=Total[MapIndexed[{f,i}|->{as}[[First[i]]]f[#],basis]]&

testdat=generateData[Sin[2π#]&,100,0.2];

testini=RandomVariate[NormalDistribution[],10];

Norm[Total[Transpose[dCost[edgeBasis[10],testdat]@@(testresult=gradientDescent[edgeBasis[10],testdat,60000]@@testini)]]]

Show[ListPlot[testdat],Plot[{Sin[2π x],(trialFunction[edgeBasis[10]]@@testresult)[x]},{x,0,1}]]

testini2=RandomVariate[NormalDistribution[],100];

Norm[Total[Transpose[dCost[edgeBasis[100],testdat]@@(testresult2=gradientDescent[edgeBasis[100],testdat,1000000]@@testini2)]]]

Show[ListPlot[testdat],Plot[{Sin[2π x],(trialFunction[edgeBasis[100]]@@testresult2)[x]},{x,0,1}]]

testini3=0RandomVariate[NormalDistribution[],100];

Norm[Total[Transpose[dCost[edgeBasis[1000],testdat]@@(testresult3=gradientDescent[edgeBasis[1000],testdat,10000]@@testini3)]]]

Show[ListPlot[testdat],Plot[{Sin[2π x],(trialFunction[edgeBasis[1000]]@@testresult3)[x]},{x,0,1}]]

testini4=0RandomVariate[NormalDistribution[],100];

Norm[Total[Transpose[dCost[edgeBasis[100],testdat]@@(testresult4=gradientDescent2[edgeBasis[100],testdat,300000,0.01]@@testini4)]]]

Show[ListPlot[testdat],Plot[{Sin[2π x],(trialFunction[edgeBasis[100]]@@testresult4)[x]},{x,0,1}]]

2dCost[(x|->(x^(#)))&/@Range[0,5],testdat]//Simplify

testas=RandomReal[{0,1},6];

cost[(x|->(x^(#)))&/@Range[0,5],testdat]@@testas

(Derivative[0,1,0,0,0,0,0][cost[(x|->(x^(#)))&/@Range[0,5],testdat]]@@testas)-(dCost[(x|->(x^(#)))&/@Range[0,5],testdat]@@testas)[[2]]//Simplify

d