Comments (3)
Hey there. I gave implementing the zoom line search algorithm a try, as I find it to be a generally well-working method. At least for some of the problems I have tackled in the past.
The main obstacle (apart from getting used to the JAX control flow for nested if-expressions) is how to retrieve the descent information needed to evaluate the decrease and curvature conditions as well as interpolate the step sizes. In the current implementation of the search and descent interfaces there seems to be no general way to retrieve the descent direction after the descent step is made. Also, the descent methods currently have no common naming scheme regarding the descent direction, if it's even calculated explicitly (I get that this may not alway be necessary), which further complicates things. My understanding is that one would have to divide the current step by the step size to (re-)evaluate the descent direction, which may generally be a bad idea for a value that is supposed to decrease with further convergence. Or am I missing something obvious?
If not, my proposal would be to modify the interface of the descent methods in a way that allows to retrieve the current descent direction in a unified way. Also, I think the abstract line search step method should have an additional argument for the descent direction or even the descent state, as this is most likely required by complex line search methods in one way or another.
On a side note, I'm also working on implementing the L-BFGS algorithm (kind of finished, at least from a methodological point of view), which also relies on common interfaces for descents.
Looking forward to further discuss this topic!
from optimistix.
Hello! Thanks for the interest in implementing some new line searches.
Just to be clear, for a minimisation problem of a function NewtonDescent
and SteepestDescent
. We don't have a common name/interface for the descent direction
step
method on any descent (see the abstract base class here.) The way this gets passed to the line search is via the y_eval
argument in the line search step
method. y_eval
is the proposed next step for a given step-size y_eval
from y
, see the BacktrackingArmijo
line search for an example.
As for technical details of implementing the Wolfe conditions, there should be no issues here. The classic Wolfe conditions for current iterate
and the curvature condition
for some constants
and the curvature condition
without changing the meaning of either of the conditions. When
Does this clear things up?
from optimistix.
Thank you for taking the time to write down the general line search problem and current implementation in such detail. This actually helps a lot to clarify the problem I'm currently facing.
First, you are totally right about the Wolfe conditions. I understood that the descent information is computed by substracting y
from the current evaluate y_eval
, which gives
Evaluating the sufficient decrease condition with
The problem still persisting is the computation of new trial step sizes
They propose computing new trial step sizes
with
This requires explicit computation of the derivative
of
which requires computation of the descent direction
Please let me know if you have any suggestions. Maybe I'm once again misleaded by the usual notation.
Edit: fixed some typos in equations
from optimistix.
Related Issues (20)
- Pytree inputs for `rtol` and `atol` or custom termination condition? HOT 7
- Can't use Optimistix solvers with `eqx.Module`s and filtered transformations HOT 2
- BestSoFarMinimiser behavior HOT 1
- correct name of the exception class that Equinox uses for runtime errors HOT 1
- Error in "optimistix/docs/examples /optimise_diffeq.ipynb" HOT 1
- Issue with vmap `optx.least_squares`. HOT 2
- grad of vmap of function which wraps an optax solver occasionally fails HOT 2
- `BestSoFar...` wanted behavior ? HOT 1
- Classical newton methods HOT 6
- Non-finite values in the root function are not handled well HOT 2
- Will constrained optimization be supported? HOT 4
- Behavior of BFGS HOT 2
- pytree output structure mismatch error in backprop during vmap HOT 9
- Incompatibility of least_squares and custom_vjp HOT 2
- Extracting intermediate function values/ losses from the solve HOT 4
- Zero implicit gradients when using `ImplicitAdjoint` with CG solver HOT 4
- Would an exhaustive grid search have a place in `optimistix`? HOT 2
- Using `optimistix` with an `equinox` model HOT 2
- Incompatibility with jax 0.4.27 HOT 1
- Possibly of interest HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from optimistix.