If your paramount objective is power saving, then using a voltage regulator will worsen things because it will suck energy while cutting the extra voltage (and it won't either augment voltage when battery are low, obiously).
If you look at the specs here:
http://www.atmel.com/dyn/resources/prod_documents/doc8161.pdfyou'll find this meaningful diagram that shows how the 328 can be run from 1.8V to 5.5V:

In order to decide if your project can cope with low voltages, you'll have to consider these facts
Pros
- running at a lower voltage will draw much less and extend battery life (running at 3V instead of 5V means kind of 3x improvement) .
Cons
- analog inputs will use supply voltage as reference
- all outputs can't go over the power supply voltage
- you have to run slower, ex: 2.7V=8mhz and you have to consider battery voltage decreasing with time (alkaline voltage drop is very steep, nimh and lithium are better) anything in the range 3V-5V might be reasonable.
- clock frequency won't be precise, consequently all time related functions as well.
(the latter two points might need code compensation)
- peripherals will get at max power supply voltage.
If your project can manage the cons you'll have a larger choice of battery options.