{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T04:21:32Z","timestamp":1783398092549,"version":"3.54.6"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>By employing time-varying proximal functions, adaptive subgradient methods (ADAGRAD) have improved the regret bound and been widely used in online learning and optimization. However, ADAGRAD with full matrix proximal functions (ADA-FULL) cannot deal with large-scale problems due to the impractical time and space complexities, though it has better performance when gradients are correlated. In this paper, we propose ADA-FD, an efficient variant of ADA-FULL based on a deterministic matrix sketching technique called frequent directions. Following ADA-FULL, we incorporate our ADA-FD into both primal-dual subgradient method and composite mirror descent method to develop two efficient methods. By maintaining and manipulating low-rank matrices, at each iteration, the space complexity is reduced from $O(d^2)$ to $O(\\tau d)$ and the time complexity is reduced from $O(d^3)$ to $O(\\tau^2d)$, where $d$ is the dimensionality of the data and $\\tau \\ll d$ is the sketching size. Theoretical analysis reveals that the regret of our methods is close to that of ADA-FULL as long as the outer product matrix of gradients is approximately low-rank. Experimental results show that our ADA-FD is comparable to ADA-FULL and outperforms other state-of-the-art algorithms in online convex optimization as well as in training convolutional neural networks (CNN).<\/jats:p>","DOI":"10.24963\/ijcai.2018\/381","type":"proceedings-article","created":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T01:49:10Z","timestamp":1530755350000},"page":"2748-2754","source":"Crossref","is-referenced-by-count":4,"title":["Efficient Adaptive Online Learning via Frequent Directions"],"prefix":"10.24963","author":[{"given":"Yuanyu","family":"Wan","sequence":"first","affiliation":[{"name":"National Key Laboratory for Novel Software Technology, Nanjing University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nan","family":"Wei","sequence":"additional","affiliation":[{"name":"National Key Laboratory for Novel Software Technology, Nanjing University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lijun","family":"Zhang","sequence":"additional","affiliation":[{"name":"National Key Laboratory for Novel Software Technology, Nanjing University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}","theme":"Artificial Intelligence","location":"Stockholm, Sweden","acronym":"IJCAI-2018","number":"27","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2018,7,13]]},"end":{"date-parts":[[2018,7,19]]}},"container-title":["Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T01:52:12Z","timestamp":1530755532000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2018\/381"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2018\/381","relation":{},"subject":[],"published":{"date-parts":[[2018,7]]}}}