Sachverhalt: A. A._, geboren 1974, ist selbstständig erwerbstätig und in dieser Eigenschaft bezüglich der Sozialversicherungen der GastroSocial Ausgleichskasse (nachfolgend: GastroSocial) angeschlossen. Die GastroSocial verwaltet die Familienausgleichskassen ihrer kantonalen Sektionen. Das erste Gesuch von A._ vom Januar 2010 um Ausbildungszulagen für seine Tochter, geboren 1994, welche einen Lehrgang beim islamischen Zentrum B._ besuchte, wurde von der GastroSocial am 23. September 2010 abgewiesen, da der Lehrgang nicht den gesetzlichen Anforderungen an eine Ausbildung entspreche. Diese Verfügung erwuchs in Rechtskraft. Am 21. Mai 2013 ersuchte A._ erneut um Ausbildungszulagen für seine Tochter, welche nach wie vor diesen Lehrgang beim islamischen Zentrum B._ besuche. Unter Hinweis auf die rechtskräftige Verfügung vom 23. September 2010 wies die GastroSocial das Gesuch am 22. Mai 2013 ab. Am 31. Mai 2013 liess A._, nunmehr anwaltlich vertreten, wiederum die Ausrichtung von Ausbildungszulagen für seine Tochter beantragen. Mit Verfügung vom 21. Mai 2014, bestätigt mit Einspracheentscheid vom 29. August 2014, lehnte die GastroSocial erneut die Ausrichtung von Ausbildungszulagen, nunmehr für den Zeitraum ab August 2011, ab. B. Das Sozialversicherungsgericht des Kantons Basel-Stadt hiess die dagegen erhobene Beschwerde mit Entscheid vom 23. März 2015 teilweise gut und wies die GastroSocial an, A._ ab 1. August 2011 Ausbildungszulagen für seine Tochter auszurichten. C. Die GastroSocial führt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, es seien der vorinstanzliche Entscheid aufzuheben und der Einspracheentscheid vom 29. August 2014 zu bestätigen. Zudem sei der Beschwerde aufschiebende Wirkung zu erteilen. A._ lässt auf Abweisung der Beschwerde schliessen, soweit darauf eingetreten werden könne. Das Bundesamt für Sozialversicherungen (nachfolgend: BSV) beantragt die Gutheissung der Beschwerde. D. Mit Eingabe vom 4. September 2015 lässt A._ an seinen Ausführungen festhalten.