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, 2022 at 6:03
  • $\begingroup$ @HansOlo the difference is, FindMinimum looks for local minimum while NMinimize finds the global one. $\endgroup$
    – kh40tika
    Sep 19, 2022 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$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .