On the input side, you might want to feed your tank less. I feed my full grown bimac about a table spoon sized piece of scallop meat every third day. That's at 62 degrees f; when I kept him at 56 degrees, I fed about 65% of that amount. I think it extends their life, and of course results in slower nitrate production. In general I reduce feeding until I notice my octopus getting slimmer, or attacking tank mates that he would normally leave alone (like cleaner snails). Then I crank it up about 15% and only increase is as the octopus get larger (which isn't happening anymore)
Adding more live rock will help, because live rock can support anaerobic (nitrate eating) bacteria.
I don't use live rock, but I know my DSB (Deep Sand Bed (5"-6") reduces nitrates, but that function is disrupted when my bimac digs, so I don't recommend a DSB for a digging octopus.
A Remote DSB (RDSB) is very easy to set up, very cheap, and reportedly works very well to remove nitrate. It's just a 5 gallon bucket filled to within 4 or 5 inches of the top with play sand, with tank water running across the top of the sand (fast enough to keep particles from settling onto the sand). There's
a very long thread describing them on RC.
From what I've read, sulfur based nitrate filters can cause problems with water chemistry (PH I think). A very similar, but I think better, device is a vodka fed nitrate filter which, as a bonus, also reduces Phosphate. These are physically almost identical to the sulfur reactor in the DIY link above, except that all that is inside are bioballs, and the outflow rate must be cranked down to a fast drip (about 650 ml/hr). You also need to set up a little tube through which you can inject a few ml of a 25% solution of vodka every day or every week. (The best solution is to set up a peristaltic pump to inject the vodka solution for you). With such a slow water flow, the oxygen in the water inside the filter is quickly used up, creating a perfect environment for the anaerobic bacteria that eat nitrate (and carbon from the vodka) to produce nitrogen gas. A trusted brand of "nitrate filter" is made by Deltec, but you can build your own for a lot cheaper.
Here's a link to a DIY thread. This guy added a redox sensor and solinoid valve to monitor the oxygen level and automatically increase the flow as needed to keep it from going too low (causing toxic hydrogen sulfide to be produced). Redox monitors are very expensive, and the sensor needs to be cleaned almost daily. That's a pain, and you can simply test the output water yourself at first and adjust the output flow rate and vodka feeding amount until it matches and balances with your feeding rate.
Some people swear by a new thing called BioPellets, but they don't work for some people, including Steve Weast, who has kept several very successful cold water tanks, and feeds heavily like I do. Steve likes the vodka fed Deltec style nitrate filter.
The short version of my advice is to consider feeding less, and set up a RDSB as soon as possible. My in-tank DSB kept pace with my minimally fed but large bimac, and a RDSB would certainly work better. It will probably solve your nitrate problem after it has a couple of months to allow the bacteria to colonize the sand. If you feed your octopus very heavily or stock your tank with a lot of other animals, you might need to reduce nitrate even more, in which case I would recommend buying a Deltec Nitrogen Filter, or building your own (which is what I plan to do).
BTW: Use a hole saw and UniSeals to plumb PVC pipes in and out of the 5 gallon plastic bucket when making your RDSB. Also, since bacteria grow a lot slower at lower temps, If you chill your tank, don't insulate the RDSB for the first few months, until after it is really working well. Then insulate it to keep cooling costs down and prevent sweating.