Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
In Hindsight: Doklady Akademii Nauk SSSR, 181(4), 1968 Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

16. Efficient Transductive Online Learning via Randomized Rounding

verfasst von : Nicolò Cesa-Bianchi, Ohad Shamir

Erschienen in: Empirical Inference

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Most traditional online learning algorithms are based on variants of mirror descent or follow-the-leader. In this chapter, we present an online algorithm based on a completely different approach, tailored for transductive settingsTransductive setting—( Transductive online learning—(, which combines “random playout” and randomized rounding of loss subgradients. As an application of our approach, we present the first computationally efficient online algorithm for collaborative filtering with trace-norm constrained matrices. As a second application, we solve an open question linking batch learning and transductive online learning.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel The Median Hypothesis
Nächstes Kapitel Pivotal Estimation in High-Dimensional Regression via Linear Programming
Fußnoten
1
Specifically, we divide the rounds into r consecutive epochs, such that epoch i consists of 2 i rounds, and use Theorem 16.3 with confidence \(\delta \prime =\delta /{2}^{i+1}\), and a union bound, to get a regret bound of \(\mathcal{O}(\mathcal{R}_{{2}^{i}}(\mathcal{F}) + \sqrt{\left (i +\log (1/\delta ) \right ) {2}^{i}})\) over any epoch i. In the typical case where \(\mathcal{R}_{T}(\mathcal{F}) = \mathcal{O}(\sqrt{T})\), summing over i = 1, …, r where \(r =\log _{2}(T + 1) - 1\) yields a total regret bound of order \(\mathcal{O}(\sqrt{\log (T/\delta )T})\). Up to log factors, this is the same bound as if T were known in advance.
 
2
Formally, at each step t: (1) the adversary chooses and reveals the next element π t of the permutation; (2) the forecaster chooses \(p_{t} \in \mathcal{P}\) and simultaneously the adversary chooses \(y_{t} \in \mathcal{Y}\).
 
3
This fact appears in an implicit form in [9]; see also [8, Exercise 8.4].
 
Literatur
1.
Abernethy, J., Warmuth, M.: Repeated games against budgeted adversaries. In: NIPS, Vancouver (2010)
2.
Abernethy, J., Bartlett, P., Rakhlin, A., Tewari, A.: Optimal strategies and minimax lower bounds for online convex games. In: COLT, Montreal (2009)
3.
4.
Bartlett, P., Mendelson, S.: Rademacher and Gaussian complexities: risk bounds and structural results. In: COLT, Amsterdam (2001)
5.
Ben-David, S., Kushilevitz, E., Mansour, Y.: Online learning versus offline learning. Mach. Learn. 29(1), 45–63 (1997)CrossRefMATH
6.
Ben-David, S., Pál, D., Shalev-Shwartz, S.: Agnostic online learning. In: COLT, Montreal (2009)
7.
Blum, A.: Separating distribution-free and mistake-bound learning models over the Boolean domain. SIAM J. Comput. 23(5), 990–1000 (1994)MathSciNetCrossRef
8.
Cesa-Bianchi, N., Lugosi, G.: Prediction, Learning, and Games. Cambridge University Press, New York (2006)CrossRefMATH
9.
Cesa-Bianchi, N., Freund, Y., Haussler, D., Helmbold, D., Schapire, R., Warmuth, M.: How to use expert advice. J. ACM 44(3), 427–485 (1997)MathSciNetCrossRefMATH
10.
Cesa-Bianchi, N., Conconi, A., Gentile, C.: On the generalization ability of on-line learning algorithms. IEEE Trans. Inf. Theory 50(9), 2050–2057 (2004)MathSciNetCrossRef
11.
Chung, T.: Approximate methods for sequential decision making using expert advice. In: COLT, New Brunswick (1994)
12.
Dudley, R.M.: A Course on Empirical Processes, École de Probabilités de St. Flour, 1982. Lecture Notes in Mathematics, vol. 1097. Springer, Berlin (1984)
13.
Foygel, R., Salakhutdinov, R., Shamir, O., Srebro, N.: Learning with the weighted trace-norm under arbitrary sampling distributions. In: NIPS, Granada (2011)
14.
Hazan, E.: The convex optimization approach to regret minimization. In: Nowozin, S., Sra, S., Wright, S. (eds.) Optimization for Machine Learning. MIT, Cambridge (2012)
15.
Hazan, E., Kale, S., Shalev-Shwartz, S.: Near-optimal algorithms for online matrix prediction. In: COLT, Edinburgh (2012)
16.
Kakade, S., Kalai, A.: From batch to transductive online learning. In: NIPS, Vancouver (2005)
17.
Koren, Y.: Collaborative filtering with temporal dynamics. In: KDD, Paris (2009)
18.
Lee, J., Recht, B., Salakhutdinov, R., Srebro, N., Tropp, J.: Practical large-scale optimization for max-norm regularization. In: NIPS, Vancouver (2010)
19.
Rakhlin, A., Sridharan, K., Tewari, A.: Online learning: random averages, combinatorial parameters, and learnability. In: NIPS, Vancouver (2010)
20.
Rakhlin, A., Shamir, O., Sridharan, K.: Relax and localize: from value to algorithms. CoRR abs/1204.0870 (2012)
21.
Salakhutdinov, R., Mnih, A.: Probabilistic matrix factorization. In: NIPS, Vancouver (2007)
22.
Salakhutdinov, R., Srebro, N.: Collaborative filtering in a non-uniform world: learning with the weighted trace norm. In: NIPS, Vancouver (2010)
23.
Shalev-Shwartz, S.: Online learning and online convex optimization. Found. Trends Mach. Learn. 4(2), 107–194 (2012)CrossRef
24.
Shamir, O., Shalev-Shwartz, S.: Collaborative filtering with the trace norm: learning, bounding, and transducing. In: COLT, Budapest (2011)
25.
Srebro, N., Shraibman, A.: Rank, trace-norm and max-norm. In: COLT, Bertinoro (2005)
26.
Srebro, N., Rennie, J., Jaakkola, T.: Maximum-margin matrix factorization. In: NIPS, Vancouver (2004)
27.
Vapnik, V.: Statistical Learning Theory. Wiley, New York (1998)MATH
Metadaten
Titel
Efficient Transductive Online Learning via Randomized Rounding
verfasst von
Nicolò Cesa-Bianchi
Ohad Shamir
Copyright-Jahr
2013
Verlag
Springer Berlin Heidelberg
Buch
Empirical Inference

Print ISBN: 978-3-642-41135-9

Electronic ISBN: 978-3-642-41136-6

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-3-642-41136-6_16

Premium Partner

    Bildnachweise