My rule of thumb:
under 12c: don't feed
12-15c - once every 3 days
15-19c - once every 2 days
above 20c - feed as much as you like
[that is water temp - not air temp]
That means that for a number of winter months the Koi don't get any external food and live with what they find in the pond.
That rule is not good in spring and fall. Just because the water temp goes above 55F during the day, it can drop into the low 40F at night. You need to make sure that the temp stay above 50F day and night before feeding.
Good point edotero.... My fish were begging at the surface the other day after a few days of warmer temps. Feeding in cold weather can have drastic results. Low metabolism in low water temps. causes many problems.