The warning message is useful, because the Raspberry Pi throttles down when it does not get enough power which will affect the speed and responsiveness.
I had a similar problem using a battery instead of a power supply. The battery I bought only outputs 2A over the USB port, so I was ready to exchange it for a stronger one. I did some more experimentation and it turned out to be the USB cable connecting the battery to the Raspberry Pi. Maybe try to exchange the USB cable to another one you have or get a new high quality USB cable. Anker cables are usually good.