Since the accepted answer does not work in recent versions of jQueryUI (> 1.10.4), I will post my hack, maybe someone will find it useful.
I am using jQueryUI 1.12.0
When adding a category I added a new class, I called it "categoryItem":
ul.append( "<li class='ui-autocomplete-category categoryItem'>" + "Category" + "</li>" );
Some of the jQueryUI functions also need to be redefined to force jquery to ignore elements with the categoryItem class (two lines changed).
$.widget("ui.menu", $.extend({}, $.ui.menu.prototype, { refresh: function() { var menus, items, newSubmenus, newItems, newWrappers, that = this, icon = this.options.icons.submenu, submenus = this.element.find( this.options.menus ); this._toggleClass( "ui-menu-icons", null, !!this.element.find( ".ui-icon" ).length ); // Initialize nested menus newSubmenus = submenus.filter( ":not(.ui-menu)" ) .hide() .attr( { role: this.options.role, "aria-hidden": "true", "aria-expanded": "false" } ) .each( function() { var menu = $( this ), item = menu.prev(), submenuCaret = $( "<span>" ).data( "ui-menu-submenu-caret", true ); that._addClass( submenuCaret, "ui-menu-icon", "ui-icon " + icon ); item .attr( "aria-haspopup", "true" ) .prepend( submenuCaret ); menu.attr( "aria-labelledby", item.attr( "id" ) ); } ); this._addClass( newSubmenus, "ui-menu", "ui-widget ui-widget-content ui-front" ); menus = submenus.add( this.element ); items = menus.find( this.options.items ); // Initialize menu-items containing spaces and/or dashes only as dividers items.not( ".ui-menu-item" ).each( function() { var item = $( this ); if ( that._isDivider( item ) ) { that._addClass( item, "ui-menu-divider", "ui-widget-content" ); } } ); // Don't refresh list items that are already adapted newItems = items.not( ".ui-menu-item, .ui-menu-divider" ).not(".categoryItem"); newWrappers = newItems.children() .not( ".ui-menu" ) .uniqueId() .attr( { tabIndex: -1, role: this._itemRole() } ); this._addClass( newItems, "ui-menu-item" ) ._addClass( newWrappers, "ui-menu-item-wrapper" ); // Add aria-disabled attribute to any disabled menu item items.filter( ".ui-state-disabled" ).attr( "aria-disabled", "true" ); // If the active item has been removed, blur the menu if ( this.active && !$.contains( this.element[ 0 ], this.active[ 0 ] ) ) { this.blur(); } }, _move: function( direction, filter, event ) { var next; if ( this.active ) { if ( direction === "first" || direction === "last" ) { next = this.active [ direction === "first" ? "prevAll" : "nextAll" ]( ".ui-menu-item" ) .eq( -1 ); } else { next = this.active [ direction + "All" ]( ".ui-menu-item" ) .eq( 0 ); } } if ( !next || !next.length || !this.active ) { next = this.activeMenu.find( this.options.items ).not(".categoryItem")[ filter ](); } this.focus( event, next ); } }));