5
$\begingroup$

I am trying to minimize a function of the following form $$f(\vec{x}) = \sum_{i = 1}^n\operatorname{ReLU}(\vec{v}_i \cdot \vec{x} + b_i) $$

$x \in \mathbb{R}^m$ with $m$ around $100$ to $1000$ and $n$ around $10^5$ to $10^7$. I wish to get to the global minimum as soon as possible. What are some methods I should try?

Things I tried:

a) gradient descent with line search, but it seems to get stuck and not progress due to all the discontinuous derivatives.

b) When doing line search, optimum occurs at a pivot (where derivative jumps). Thus by sorting the pivots and doing cumsum to get derivatives around the pivots, I can just choose the lowest pivot point. But this has the same issue of derivative being chosen in the direction where I can't make any more progress.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Introduce nonnegative variables $y_i$ and minimize $\sum_i y_i$ subject to linear constraints $$y_i \ge v_i \cdot x + b_i$$

Improve this answer
$\endgroup$
4
  • $\begingroup$ I tried it. It has way too many variables and constraints. The scipy implementation is way too slow. $\endgroup$
    – JEK
    Commented Jul 28, 2022 at 5:14
  • 1
    $\begingroup$ @JEK Did you pass all the exact derivatives to scipy? If not, scipy approximates the derivatives by finite differences under the hood, which is known to be slow, especially for large problems like yours. That being said, since the problem is an LP, you could solve it with the Highs solver that is interfaced by scipy's linprog anyway. $\endgroup$
    – joni
    Commented Jul 28, 2022 at 6:04
  • $\begingroup$ I provided the exact derivative. But it was still very slow. I used linprog. But by creating slack variables, I now have around $10^7$ variables and $10^7$ constraints. I think the problem becomes too massive. $\endgroup$
    – JEK
    Commented Jul 28, 2022 at 12:09
  • $\begingroup$ @JEK Are you using a sparse constraint matrix? Can you share the raw input data ($v$ and $b$)? $\endgroup$
    – RobPratt
    Commented Jul 28, 2022 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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