3
$\begingroup$

Consider the following cost function $$ f(\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N,\theta) = \sum_{i=1}^{N} J(\mathbf{x}_i,\theta) $$ where $\mathbf{x}_i \in \mathbb{R}^d$, $\theta \in \mathbb{R}^K$, and $J$ is some function. Suppose I want to minimize this function with respect to $\theta$ using gradient descent. The update rule is $$ \theta_{k+1} \leftarrow \theta_k - \alpha_k \cdot \nabla_\theta f(\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N,\theta_k) $$ where $\alpha_k$ is some step size. I am trying to choose an appropriate $\alpha_k$ at each step using the secant method. More precisely, let $$ \phi (\alpha_k) = f\left(\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N,\left[\theta + \alpha_k \cdot \nabla_\theta f(\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N,\theta_k)\right]\right) $$ such that the optimal $\alpha_k$ is determined using the update rule $$ \alpha_{k+2} \leftarrow \alpha_{k+1} - \frac{\alpha_{k+1} - \alpha_{k}}{\frac{\text{d} \phi (\alpha_{k+1})}{\text{d} \alpha} - \frac{\text{d} \phi (\alpha_{k})}{\text{d} \alpha}} \cdot \frac{\text{d} \phi (\alpha_{k+1})}{\text{d} \alpha} $$ However, my problem is that the term $$ \nabla_\theta f(\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N,\theta_k) $$ is just too big $(> 10^5)$, and the reason for this is $$ \nabla_\theta f(\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N,\theta_k) = \sum_{i=1}^{N} \nabla_\theta J(\mathbf{x}_i,\theta_k) $$ When $N$ is large, $\nabla_\theta f(\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N,\theta_k)$ is large regardless of how small each of the gradient terms are. Although the secant method update rule above deals with large gradients through the fraction, I've observed cases where large gradients caused problems. To make the gradient small, I've tried modifying the cost function as follows: $$ f(\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N,\theta) = \frac{1}{N^\ell} \sum_{i=1}^{N} J(\mathbf{x}_i,\theta) $$ For different exponents $\ell = 1,2,...$. This has worked reasonably well, but I was wondering if there are other well-known (or better) monotonically increasing functions that can be applied to $f(\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N,\theta)$ to make its gradients smaller.

$\endgroup$
6
  • $\begingroup$ Why are large numbers a problem (as to big would imply)? Floating point numbers should have no problem with $10^5$. Maybe there is a more elegant solution then we exactly know what your problem is. $\endgroup$ Oct 18 at 23:04
  • $\begingroup$ @worldsmithhelper while the secant method may compensate for large numbers, other line search methods, such as backtracking, do not. Moreover, as the magnitude of the gradient increases, I've found that the optimal step size gets smaller and smaller. With backtracking, this means I need to backtrack for longer until I can get to the optimal step size. Backtracking is just an example here, and I've faced a similar problem in similar situations. $\endgroup$
    – mhdadk
    Oct 19 at 0:19
  • $\begingroup$ Are you looking specifically for additively separable functions (so that you can continue to evaluate the gradient separately for each $i$)? $\endgroup$
    – prubin
    Oct 19 at 15:21
  • 1
    $\begingroup$ If the values of $f$ are large, the partial of $\log(f(x))$ will be smaller than the partials of $f$. $\endgroup$
    – prubin
    Oct 19 at 18:52
  • 1
    $\begingroup$ One traditional way is to use the inverse hessian (or the inverse hessian diagonal). It can be approximated using (L-)BFGS. If the function is seperable and not pathological coordinate descent or something similar can be used. Functions are usually not varied by the amount of parameters they take so the problem you suggest is uncommon. In addition scaling the gradient wouldn't impact a line search(!) on top. $\endgroup$ Oct 19 at 18:53

Your Answer

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

Browse other questions tagged or ask your own question.