1
$\begingroup$

I have a function which is nicely behaved, but expensive to compute. What's the fastest way to get 2-3 digits of accuracy?

Using NMinimize is much slower calling Plot and eyeballing the minimum, both are too slow since I need to solve this minimization problem a couple thousand times. Even after downgrading all of [AccuracyGoal, PrecisionGoal, MaxIterations] it takes a while, so I may be missing some magic options.

(* Find number of steps needed for SGD to achieve lossFactor \
reduction in loss *)
stepsSGDopt[h_, lossFactor_, relativeAlpha_] := 
  Module[{d, ii, X2, \[Alpha], mat, ones, evals, evecs, 
    partialProduct, fastMatrixPower, objfunc, loss0, lossTarget, k, 
    alphaCrit},
   
   d = Length[h];
   ii = IdentityMatrix[d];
   X2 = DiagonalMatrix[h];
   ones = ConstantArray[1., {d}];
   alphaCrit = 2/(2 Max[h] + Total[h]);
   \[Alpha] = relativeAlpha*alphaCrit;
   
   (* Matrix governing evolution of diagonal cov for Gaussian SGD *)
   mat = 
    ii - 2 \[Alpha] X2 + 
     2 \[Alpha]^2 X2 . X2 + \[Alpha]^2 Outer[Times, h, h];
   
   (* 100x faster version of MatrixPower[mat,k,ones].h *);
   {evals, evecs} = Eigensystem[mat];
   partialProduct = Inverse[evecs\[Transpose]] . ones;
   fastMatrixPower = Compile[{{k, _Real}},
     (evecs\[Transpose] . (evals^k*partialProduct)) . h
     ];
   objfunc[k_?NumericQ] := fastMatrixPower[k];
   
   loss0 = Total[h];
   lossTarget = loss0/lossFactor;
   Assert[lossTarget < Total[h]];
   k /. FindRoot[objfunc[k] == lossTarget, {k, 2}]
   ];

d = 50;
h = RandomReal[{0, 1}, {d}];
lossFactor = 20;
Plot[stepsSGDopt[h, lossFactor, alpha], {alpha, 0.01, 1}]
objfunc[relativeAlpha_?NumericQ] := 
  stepsSGDopt[h, lossFactor, relativeAlpha];
NMinimize[{objfunc[alpha], 0.1 < alpha < 1}, alpha]
$\endgroup$
2
  • $\begingroup$ How about FindMinimum[..., {x, x0, x1}], which if I remember correctly is only numeric? $\endgroup$
    – Hans Olo
    Sep 19 at 6:03
  • $\begingroup$ @HansOlo the difference is, FindMinimum looks for local minimum while NMinimize finds the global one. $\endgroup$
    – kh40tika
    Sep 19 at 6:05

2 Answers 2

2
$\begingroup$

NMinmize looks for a global minimum. Since we know objfunc is convex (which MMA cannot easily infer), FindMinimum would be more efficient, which looks for local minimum.

NMinimize[{objfunc[alpha], 0.1 < alpha < 1}, alpha, PrecisionGoal -> 2] //Timing

{13.4694, {162.201, {alpha -> 0.507269}}}

FindMinimum[{objfunc[alpha], 0.1 < alpha < 1}, {alpha, 0.5}, PrecisionGoal -> 2] // Timing

{0.430142, {162.201, {alpha -> 0.507269}}}
```
$\endgroup$
3
$\begingroup$

BayesianMinimization can be also usefull here.

Objective with counter:

count = 0 ;
objfunc[relativeAlpha_?NumericQ] := (count++; stepsSGDopt[h, lossFactor, relativeAlpha]) ;

FindMinimum:

count = 0 ;
FindMinimum[{objfunc[alpha], 0.1 < alpha < 1}, {alpha, 0.5}, AccuracyGoal -> 2] 
count
(* {168.911243232702`,{alpha\[Rule]0.5156544651037186`}} *)
(* 48 *)

BayesianMinimization:

count = 0 ;
bo = BayesianMinimization[objfunc, Interval[{0.1, 1.0}], Method -> "MaxExpectedImprovement"] ;
bo["MinimumConfiguration"]
count
(* 0.5148846730372676` *)
(* 15 *)

You can control BayesianMinimization manually by setting two iterations at first and then using one iteration and previous history.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.